数据结构（3）— 线性表之顺序存储详解介绍（含代码）

（1）博客代码在数据结构代码---GitHub仓库；

线性表介绍

线性表的基础概念

（1）甲骨文表示：线性表是零个或多个数据元素的有限序列。
（2）线性表，顾名思义，就是说这个数据存储是线性的。而线性的东西具有什么特征呢？
<1>数据是一对一的排列的，中间的数据都有且仅有一个前面数据（前面的数据叫做前驱）和一个后面的数据（后面的数据叫做后继）。而数据表的最前面的数据叫做表头，最尾端的数据叫做表尾。表头无前驱，表尾无后继。
<2>线性表是有限的。因为计算机的存储空间是有限的，所以线性表必然有限。
<3>线性表中的元素必须是相同类型。这个就像是我们在定义数组，一个数组中的元素，要么都是int型数据，要么都是char型数据，不可能数组中，第一个元素是int型数据，第二个元素变成了char型数据了。
（3）线性表的元素个数n（n>=0）表示线性表的长度，当n=0时，我们将这个表称之为空表。
（4）在非空表中，每个数据元素都有一个确定的位置，比如a1就是第一个数据元素，a2就是第二个数据元素，ai就是第i个数据元素。所以我们将i称为数据元素的位序。

一个数据元素可以拥有多个数据项

（1）我们上面看到，一个数据元素只有一个数据项。在数据结构（1）前言中我说了，一个数据元素可以有多个数据项，在研究数据结构时，我们都是着眼于数据元素。那有没有一个数据元素拥有多个数据项的线性表呢？有，我们常见的就是花名册。
（2）我们看到如下花名册里面，有姓名，性别，文化程度等等一些元素。这些元素就是数据项。而人具有这些元素，所以人这个个体就是数据元素。我们将这些人进行按照顺序排列，最后形成了花名册，这也叫做线性表。

线性表种类

（1）常见的线性表有：顺序存储（说白了就是数组），是链式存储，栈，队列。
（2）链式存储中又分为四种，单链表，静态链表，循环链表，双向链表。

线性表顺序存储介绍

顺序存储定义

定义

（1）定义：线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
（2）将上面这段话用白话文来说就是，线性表的顺序存储就是一个数组，不过与数组有些许不同，数据结构中的顺序存储定义需要增加一个length用于显示线性表的当前长度。
（3）这个时候可能会有人有疑惑了。为什么需要一个length呢？假设我们在排队买东西，由于空间的限制，只能来20个人（MAXSIZE）。而这个时候，排队的有5个人，如果有第6个人也要来排队，因为人很聪明，知道排到第五个人后面就可以了，但是在写程序的时候，你怎么知道需要将新来的数据放在哪里呢？如果不小心放在了第4个空间中，那么数据会被覆盖，出问题。放在第7位，那么第6位空着，浪费空间。
（4）线性表的顺序存储就是一个排队的过程，MAXSIZE用于定义这个队伍最大多长，而length用于指示当前位置排到哪里了。如果中间一个人突然走了，从这个人开始的后面所有人都要往前面移动，同时length要马上自减一次。如果有一个人因为紧急事件，不得不插队，从插队的位置往后移动，所有人都需要往后移动，length需要马上自增一次。
（5）因为按照编程习惯，我们的数组首元素下标为0。所以当线性表为空的时候，last为-1，而last=1时候，线性表长度=last+1=1！！！

#define success 0
#define fail  -1
#define MAXSIZE 20          /* 存储空间初始分配量 */typedef int ElemType;       /* ElemType类型根据实际情况而定，这里假设为int */typedef struct
{ElemType data[MAXSIZE]; /* 数组，存储数据元素 */int last;             /* 线性表当前位置，last+1=length */
}SqList,*SqLink;     /*SqList是定义线性表，SqLink是定义线性表的结构体指针*/

顺序存储方式和地址计算

其实如果学了C语言数组了，这部分没有什么可以说的。就是跟数组那样存储，是连续的。不清楚的自行去重新学习数组的知识。

数组长度与线性表长度区别

（1）我们上面说了，MAXSIZE是数组长度，这个规定了能够放进来多少数据，他的值是固定的。而length是线性表长度，他的长度是会随着线性表的删除，插入等操作发生改变，是动态的。任意时刻length<=MAXSIZE。
（2）至于为什么数组不改成动态分配，是因为这会带来性能上的消耗。我查了一些资料，以及问了bingAI，剥去关于没有及时释放不用的内存以外，更多的是malloc和free会造成资源消耗。

顺序存储实操

这里需要说的是，如果是操作成功了，返回0，操作失败返回-1。

#define success 0
#define fail  -1
#define MAXSIZE 20          /* 存储空间初始分配量 */typedef int ElemType;       /* ElemType类型根据实际情况而定，这里假设为int */typedef struct
{ElemType data[MAXSIZE]; /* 数组，存储数据元素 */int last;             /* 线性表当前位置，last+1=length */
}SqList,*SqLink;     /*SqList是定义线性表，SqLink是定义线性表的结构体指针*/

创建顺序存储线性表

（1）我们先申请一个结构体指针，然后分配一个空间过来，如果没有分配成功，将会打印提示。
（2）如果创建成功之后，因为刚刚申请的空间中存放的值是未知的。所以按照习惯，我们一般都会将其设置为0。
（3）注意：memset函数必须写在 L -> length = -1; 前面，因为memset这一步，会将 L -> length 变成0。因为按照数组下标的习惯，0表示首元素地址，所以当线性表为空的时候，length==-1。（可能在部分教材里面length=0表示线性表为空，所以下面关于length部分代码会有所差异，需要注意）

/*作用:   创建线性表*传入参数：无*返回参数：创建失败打印错误报告，创建成功返回创建线性表的结构体指针*/
SqLink list_create(void)
{//建立线性表SqLink L;L = (SqLink)malloc(sizeof(SqList));//确认线性表是否存在if(L == NULL){printf("list malloc failed!\n");return L;}//线性表存在，将其内容清空//注意，这两句别写反了，否则last会变成0。memset(L , 0 , sizeof(SqList));L -> last = -1;  //last表示线性表的指向位置，因为在C语言中，下标是从0开始，所以当为空表是last=-1//返回线性表return L;
}

判断线性表是否存在

判断线性表是否存在，我们可以检测他指向的地址是否有问题。

/*作用:   判断线性表是否存在*传入参数：*    @L: 线性表的结构体指针*返回参数：线性表不存在返回fail，线性表存在返回success*/
int list_if_exist(SqLink L)
{if(L==NULL){printf("list is not exist!\n");return fail;}return success;
}

删除线性表

（1）如果线性表为NULL，表示传入线性表不存在，打印提示。
（2）如果线性表存在，将释放内存，同时将指针指向NULL。

/*作用:   删除线性表*传入参数：*    @L: 线性表的结构体指针*返回参数：线性表不存在返回fail，线性表成功删除返回success*/
int list_delete(SqLink L)
{if(L==NULL){printf("list is not exist!\n");return fail;}free(L);L=NULL;return success;
}

清空线性表

解析看创建顺序存储线性表。

/*作用:   清空线性表*传入参数：*    @L: 线性表的结构体指针*返回参数：成功返回succes,失败返回fail*/
int list_clear(SqLink L)
{//确认线性表是否存在if(L == NULL){printf("list is not exist!\n");return fail;}//线性表存在，将其内容清空//注意，这两句别写反了，否则last会变成0。memset(L , 0 , sizeof(SqList));L -> last = -1;  //last表示线性表的指向位置，因为在C语言中，下标是从0开始，所以当为空表是last=-1return success;
}

判断线性表是否为空

（1）先判断线性表是否存在
（2）我们只需要判断length即可。如果对于length是什么依旧不清楚的，看下图。

/*作用:   判读线性表是否为空(因为使用者并不知道函数实现具体细节，所以需要加上这个)*传入参数：*    @L: 线性表的结构体指针*返回参数：线性表为空返回succes,否则返回fail*/
int list_if_empty(SqLink L)
{//确认线性表是否存在if(L==NULL){printf("list is not exist!\n");return fail;}if(L -> last ==-1){printf("list is empty!\n");return success;}return fail;
}

获取当前线性表长度

获取线性表长度就看length+1即可。

/*作用:   查看当前线性表长度*传入参数：*    @L: 线性表的结构体指针*返回参数：返回当前线性表的长度*/
int list_get_length(SqLink L)
{//确认线性表是否存在if(L==NULL){printf("list is not exist!\n");return fail;}return (L->last+1);
}

判断指定数值是否在线性表中

（1）先判断线性表是否存在
（2）我们只需要将线性表中的值一个一个的与value对比即可。

/*作用:   判断value是否在线性表中*传入参数：*  @L:线性表的结构体指针*  @value:需要查看线性表中是否存在的值*        @可输入值范围受到ElemType决定*返回参数：value在线性表中存在返回succes,value不在线性表中或线性表不存在返回fail*/
int list_value_if_locate(SqLink L,ElemType value)
{int i;//确认线性表是否存在if(L==NULL){printf("list is not exist!\n");return fail;}//逐个判断线性表中的值for(i = 0;i<=L->last;i++){if(L->data[i]==value){return success;}}return fail;
}

在线性表指定位置插入数据

（1）判断线性表是否存在
（2）先判断线性表是否已经满了
（3）判断插入位置是否合理
（4）将要插入的位置元素都向后移动，腾出空间，让新数据插入
（5）插入新数据，last自增

/*作用:   插入数据，在线性表L的pos处插入数据value*传入参数：*  @L: 线性表的结构体指针*  @value: 需要插入线性表的值*        @可输入值范围受到ElemType决定*  @pos：需要插入的位置*        @插入位置范围受到MAXSIZE限制*返回参数：返回当前线性表的长度*/
int list_insert(SqLink L,ElemType value,int pos)
{int i; //确认线性表是否存在if(L==NULL){printf("list is not exist!\n");return fail;}//如果线性表满了if(L->last == MAXSIZE-1){printf("list is full\n");return fail;}//判断插入的位置是否合法if(pos<0 || pos > L->last+1){printf("pos is invaild\n");}//向后移动for(i = L -> last;i >= pos;i--){L->data[i+1]=L->data[i];}//更新last和插入部分数值L->data[pos]=value;L->last++;return success;
}

删除指定位置元素

（1）检查线性表是否存在
（2）是否为空表
（4）删除位置是否合理
（5）将所有数据向前移动（此时原来pos位置的数据会被pos+1处覆盖）
（6）last自减

/*作用:   删除指定位置的元素*传入参数：*  @L: 线性表的结构体指针*  @pos： 需要删除的数据的位置*        @插入位置范围受到MAXSIZE限制*返回参数：删除失败返回fail，成功删除返回success*/
int list_delete_pos_value(SqLink L,int pos)
{int i;//确认线性表是否存在if(L==NULL){printf("list is not exist!\n");return fail;}//检测是否为空表if(L->last==-1){printf("list is empty!\n");return fail;}//检测删除位置是否合理if(pos < 0 || pos > L->last){printf("pos is invalid！\n");return fail;}//向前移动for(i=pos+1;i<=L->last;i++){L->data[i-1]=L->data[i];}//更改lastL->last--;return success;
}

获取两个线性表的并集

（1）判断三个线性表是否存在
（2）判断他们是否为空
（3）先将L1的值存入L3中
（4）然后将L2中拥有，但是L1中没有的值存入L3中

/*作用: L1和L2并集，将并集值给到L3*传入参数：*  @L1，L2: 两个不同的线性表*  @L3： L1和L2并集*返回参数：失败返回fail，成功返回success*/
int list_merge(SqLink L1,SqLink L2,SqLink L3)
{int i;//判断L1，L2，L3是否存在list_if_exist(L1);list_if_exist(L2);list_if_exist(L3);//判断L1，L2,是否为空list_if_empty(L1);list_if_empty(L2);//将L1中的所有元素存放到L3中for(i = 0; i <= L1->last;i++){list_insert(L3, L1->data[i],L3->last+1);}for(i = 0; i <= L2->last;i++){//判读L2中的每一个元素是否在L1中,如果不在，就存入到L3中if(list_value_if_locate(L1,L2->data[i])==-1){//如果L3满了，提前结束if(list_insert(L3,L2->data[i],L3->last+1)==fail){return fail;}}}return success;
}

删除线性表中重复元素

（1）判断线性表是否存在
（2）如果只有一个元素就不需要判断
（3）我们选择从第二个元素开始（建立变量i），判断i位置的元素是否与i前面元素有重复，如果重复了，那么就删除i位置的元素。此时可以跳出循环。
（4）因为删除位置i的元素之后，原来位置i+1的元素会替补到位置i处。所以我们需要先将位置i自减一次，然后在for语句中自增一次，为了保持位置i不变，所以我们需要i自减一次抵消。
（5）如果没有重复元素，那么i就自增。

/*作用:删除线性表中重复元素*传入参数：*    @L1 : 线性表的结构体指针*返回参数：删除成功返回success*/
int list_purge(SqLink L)
{int i,j;//确认线性表是否存在if(L==NULL){printf("list is not exist!\n");return fail;}//如果当前线性表只有一个元素，就没有必要判断了if(L->last==0){return success;}//让i不断向后移动for(i=1;i<=L->last;i++){//将位置i之前的元素与i处元素进行判断，相同就删除for(j=i-1;j>=0;j--){//如果发现前面有与位置i相同的元素，删除，保持i不动if(L->data[i]==L->data[j]){//位置i与前面有重复，就删除位置i的值list_delete_pos_value(L,i);//因为需要保持位置i不动，而for语句中有i++，所以这里用i--抵消i--;break;}}}return success;
}

获取指定位置元素

（1）判断线性表是否存在
（2）判断是否为空表
（3）判断获取数据的位置是否合理
（4）返回指定位置值

/*作用: 返回指定位置的值*传入参数：*  @L: 线性表的结构体指针*  @pos：指定位置*        @插入位置范围受到MAXSIZE限制*返回参数：线性表为空，返回fail。成功打印返回success*/
int list_pos_value(SqLink L,int pos)
{//判断线性表是否存在if(L==NULL){printf("list is not exist!\n");return fail;}//判断是否为空表if(L->last==-1){printf("list is empty!\n");}//判断获取数据的位置是否合法if(pos<0 || pos > L->last+1){printf("pos is invaild\n");}//返回指定位置值return (L->data[pos]);
}

显示线性表中的值

（1）线性表是否存在
（2）是否为空表
（3）逐个打印线性表中的元素

/*作用: 显示线性表中的值*传入参数：*    @L: 线性表的结构体指针*返回参数：线性表为空，返回fail。成功打印返回success*/
int list_show(SqLink L)
{int i;//判断线性表是否存在if(L==NULL){printf("list is not exist!\n");return fail;}//判断是否为空表if(L->last==-1){printf("list is empty!\n");}//将线性表中的值打印出来for(i=0;i<=L->last;i++){printf("%d ",L->data[i]);}printf("\n");return success;
}

线性表顺序结构优缺点

优点

（1）存储密度高
（2）查找线性表中元素也方便

缺点

（1）需要提供一大片较大的连续存储空间。
（2）插入，删除等运算耗时，存在元素在存储空间成片移动的现象

总结

如果我们需要插入删除操作比较多，比如游戏开发中的装备经常会更换，这个用线性存储就非常不合适，链式存储就比较好。但是如果我们需要频繁查找元素，比如查找游戏ID，查看用户性别等等用顺序存储就很方便。