🌏个人博客主页：意疏-CSDN博客

希望文章能够给到初学的你一些启发～ 如果觉得文章对你有帮助的话，点赞 + 关注+ 收藏支持一下笔者吧～

阅读指南：

开篇说明线性表的定义线性表的顺序存储结构（顺序表）顺序存储结构的插入与删除（顺序表）插入操作删除操作线性表顺序存储结构的优缺点

开篇说明

数据结构是组织和存储数据的一种方式，它不仅定义了数据的类型，还规定了数据之间的关系以及对数据进行操作的方法。线性表是一种基本的数据结构，用于存储一组有序的数据元素。线性表中的元素具有线性关系，即每个元素有且只有一个前驱和一个后继（除了第一个元素没有前驱和最后一个元素没有后继）。线性表可以分为顺序存储结构和链式存储结构两种实现方式。

在本篇中，我们将深入探讨线性存储中顺序表的实现细节、基本操作（如插入、删除、查找），通过这些内容的学习，希望我们可以一起进步。

线性表的定义

线性表：是具有相同数据类型为n(n>=0)个数据元素的有限序列，它是典型的线性结构。除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继。

这里首先要强调的是，首先它是一个序列，也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继。元素的个数是有限的。

如用数字语言来进行定义，若将线性表记为（

a

1

a_1

a1​，…，

a

i

a_i

ai​-1，a，

a

i

a_i

ai​+1，…，

a

n

a_n

an​）

则表中

a

i

a_i

ai​-1领先于

a

i

a_i

ai​，

a

i

a_i

ai​领先于

a

i

a_i

ai​+1，我们称

a

i

a_i

ai​-1是

a

i

a_i

ai​的直接前驱，

a

i

a_i

ai​+1是

a

i

a_i

ai​的直接后继元素。当i = 1,2，n-1时，

a

i

a_i

ai​有且仅有一个直接后继，当i = 2,3，n时，

a

i

a_i

ai​有且仅有一个直接前驱。

这里是示例图：

所以线性元素的个数 n n(>=0) 定义为线性表的长度，当n=0时，称为空表。

在非空表中的每个数据元素都有一个确定的位置，如

a

1

a_1

a1​是第一个数据元素，

a

n

a_n

an​是最后一个数据元素，

a

i

a_i

ai​是第i个数据元素，称i为数据元素

a

i

a_i

ai​在线性表中的位序。

在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

线性表的抽象数据类型定义如下：

在实际问题中，关于线性表的更复杂操作，完全可以用这些基本的操作组合来实现。例如，实现两个线性表集合A和B的并集操作。即要使得集合A = A

∪

\cup

∪ B

简单来说就是把存在集合B但不存在A中的数据元素插入到A中即可。

我们只要循环集合B中的每个元素，判断当前元素是否存在A中，若不存在，则插入A即可。

我们假设

L

a

L_a

La​表示集合A，

L

b

L_b

Lb​表示集合B，则实现的代码如下：

这里，我们对于union操作，用到了前面线性表基本操作ListLength、GetElem、LocateElem、ListInsert等，其实复杂的操作，其实就是把基本操作组合起来实现的。

线性表的顺序存储结构（顺序表）

我们来看一下线性表的两种物理结构的第一种：顺序存储结构。

线性表的顺序存储结构是指：用一段地址连续的存储单元依次存储线性表的数据元素，从而使逻辑上相邻的两个元素在物理位置上也相邻。

线性表（

a

1

a_1

a1​，

a

2

a_2

a2​，…，

a

n

a_n

an​）的顺序存储示例图如下：

线性表的顺序存储结构，就是在内存中找地方，通过占位的形式，把一定内存空间给占掉了，然后把相同数据类型的数据元素依次存放在这片空地中。线性表的每个数据元素的类型都相同，所以可以用C语言的一维数组来实现顺序存储结构。即把第一个数据元素存储到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

。数组的分配，在正常情况下是静态分配，但我们也可以动态分配。

我们首先来看静态分配：静态分配：数组大小和空间已经固定，一旦空间占满，再加入新的数据，就会产生溢出，导致程序崩溃（空间固定）

<code>#define MaxSize 100//存储空间初始分配量

typedef struct {

ElemType data[MaxSize];//数组存储数据元素，最大值为MAXSIZE

int length;//线性表当前长度

} SeqList;

这里我们可以发现描述顺序存储结构需要三个属性：

1. 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。

2. 线性表的最大存储容量：数组长度MaxSize。

3. 线性表的当前长度：length。

这里我们需要注意的是：

数组的长度与线性表的长度两者的区分:

数组的长度是存放线性表的存储空间的长度，存储分配后这个量是一般是不会变的。

线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是会变化的。

在任何时刻，线性表的长度都需要小于等于数组的长度。

我们再来看动态分配：动态分配：存储数据的空间在程序执行中动态语句分配，一旦空间占满，可以另外开辟更大空间，用来替换原始空间。（空间不固定）

#define InitS 100

typedef struct {

ElemType *data;//包含的数组

int length;//当前表中有几个元素

} SeqList;

顺序存储结构的插入与删除（顺序表）

获得元素操作

对于线性表的顺序存储结构来说，如果我们要实现GetElem操作，即将线性表L中的第i个位置元素值返回。就程序而言，只要i的数值在数组下标范围内，就是把数组第i－1下标的值返回即可。

例

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

typedef int Status;

//Status是函数的类型，其值是函数结果状态代码，如OK等。

//初始条件：顺序线性表L已存在，1<=i<=ListLength (L)。

//操作结果：用e返回L中第i个数据元素的值。

Status GetElem(SqList L, int i, ElemType *e)

{

if (L.length == 0 || i < 1 || i > L.length)

return ERROR;

*e = L.data[i-1];

return OK;

}

注：

这里返回值类型是Status 是一个整型，返回OK代表1，ERROR代表0。

插入操作

我们要实现ListInsert（*L，i，e），就是将线性表L中的第i个位置插入新元素e。

插入算法的思路：

如果插入位置不合理的话，抛出异常。如果线性表长度大于或等于数组长度，则抛出异常或动态增加容量。从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置。将要插入的元素填到位置 i 处。表长加1。

代码如下：

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)

//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1

Status ListInsert(SqList *L, int i, ElemType e)

{

int k;

if (L-> length == MAXSIZE)//顺序线性表已满

return ERROR;

if (i < 1 || i > L-> length + 1) //当i不在范围内时，返回错误

return ERROR;

if (i <= L-> length)//若插入位置不在表尾

{

for (k = L-> length; k >= i-1; k--)//将后面的元素后移一位

L-> data[k+1] = L-> data[k];

}

L-> data[i-1] = e; //插入新元素

L-> length++; //表长加1

return OK;

}

删除操作

删除算法的思路：

如果删除位置不合理的话，抛出异常。取出删除元素从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置。表长减1。

代码如下：

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)

//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1

Status ListDelete(SqList *L, int i, ElemType *e)

{

int k;

if (L-> length == 0)//线性表为空时，返回错误

return ERROR;

if (i < 1 || i > L-> length) //删除位置不正确

return ERROR;

*e = L-> data[i-1]; //返回被删除元素的值

if (i <L-> length)//若插入位置不在表尾

{

for (k=i;k = L-> length; k++)//将删除位置后继元素前移

L-> data[k-1] = L-> data[k];

}

L-> length--; //表长减1

return OK;

}

线性表顺序存储结构的优缺点

优点

无须为表示表中元素之间的逻辑关系而增加额外的存储空间。可以快速地存取表中任一位置的元素。

缺点

插入和删除操作需要移动大量元素当线性表长度变化较大时，难以确定存储空间的容量造成存储空间的‘碎片’

意气风发，漫卷疏狂

学习是成长的阶梯，每一次`的积累都将成为未来的助力。我希望通过持续的学习，不断汲取新知识，来改变自己的命运，并将成长的过程记录在我的博客中。

如果我的博客能给您带来启发，如果您喜欢我的博客内容，请不吝点赞、评论和收藏，也欢迎您关注我的博客。

您的支持是我前行的动力。听说点赞会增加自己的运气，希望您每一天都能充满活力！

愿您每一天都快乐，也欢迎您常来我的博客。我叫意疏，希望我们一起成长，共同进步。

我是意疏 下次见！