数据结构——线性表（顺序存储结构）

• 语言：C语言
• 软件：Visual Studio 2022
• 笔记书籍：数据结构——用C语言描述
• 如有错误，感谢指正。若有侵权请联系博主

一、线性表的逻辑结构

线性表是n个类型相同的数据元素的有限序列，对n>0，除第一元素无直接前驱、最后一个元素无直接后继外，其余的每个元素只有一个直接前驱和一个直接后继。

线性表的特点：

1. 同一性。线性表由同类数据元素组成，每一个aⁱ必须属于同一数据类型。
2. 有穷性。线性表由有限个数据组成，表长度就是表中数据元素的个数。 
3. 有序性。线性表中相邻数据元素之间存在着序偶关系<aⁱ，aⁱ+1>

由此可以看出，线性表既是一种最简单的数据结构（数据元素之间由前驱/后继直观、有序的关系确定），又是一种常见的数据结构（矩阵、数组、字符串、堆栈、队列等都符合线性条件）。

二、线性表的抽象数据定义

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

ADT LinearList{
    数据对象：D={aⁱ|aⁱ∈D₀,i=1,2,...,n,n≥0,D₀为某一数据对象}
    结构关系：R={<aⁱ,aⁱ+1>|aⁱ,aⁱ+1∈D,i=1,2,...,n-1}
    基本操作：
    1.InitList(L)
      操作前提：L为未初始化线性表。
      操作结果：将L初始化为空表。
    2.ListLength(L)
      操作前提：线性表L已存在。
      操作结果：如果L为空表则返回0，否则返回表中的元素的个数。
    3.GetData(L,i)
      操作前提：表L存在，且1≤i≤ListLength(L)。
      操作结果：返回线性表L中第i个合法元素的值。
    4.InsList(L,i,e)
      操作前提：表L已存在，e为合法元素值且1≤i≤ListLength(L)+1。
      操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。
    5.DelList(L,i,e)
      操作前提：表L已存在且非空，1≤i≤ListLength(L)。
      操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。
    6.Locate(L,e)
      操作前提：表L已存在，e为合法数据元素值。
      操作结果：如果L中存在数据元素e，则返回e在L中的位置，否则返回空位置。
    7.DestroyList(L)
      操作前提：线性表已存在。
      操作结果：将L销毁。
    8.ClearList(L)
      操作前提：线性表L已存在。
      操作结果：将L置为空表。
    9.EmptyList(L)
      操作前提：线性表L已存在。
      操作结果：如果L为空表则返回TRUE，否则返回FALSE。    
}ADT LinearList;

以上仅为一个抽象数据类型。因为一个抽象数据类型仅是一个模型的定义，并不设计模型的具体实现，因此这里使用参数不考虑具体类型。在实际问题中对线性表的运算可能很多，例如有时需要将多个线性表合并成一个线性表，以及在此问题基础之上进行的有条件合并等。像合并分拆/复制/排序等复合运算问题都可以利用基本运算的组合来实现。

三、线性表的顺序存储结构的具体实现（使用数组即栈内存）

1、线性表顺序存储的表示

#define MAXSIZE 100         //此处的宏定义常量表示线性表的最大长度
typedef struct
{
  ElemType elem[MAXSIZE];  //线性表占用的数组空间
  int last;                //记录线性表中最后一个元素在数组elem[]中的位置(下标值)，空表置为-1
}SeqList;

说明：

节点类型定义中ElemType数据类型是为了描述的统一而自定。在实际应用中，用户可根据实际需要具体定义顺序表中的数据类型。

注意类型与变量的区别。类型是模板，变量是真正的存储空间。

利用定义的顺序表的数据类型SeqList就可以定义变量了。变量L的定义与使用方法有一下两种：

1. 通过变量定义语句SeqList L;将L定义为SeqList类型的变量。可通过L.elem[i-1]访问顺序表中序号为i的元素aⁱ;通过L.last得到顺序表中最后一个元素的下标，而L.last+1就是顺序表的长度。
2. 通过指针变量定义语句SeqList L₁，*L；l=&L₁；将L定义为指向SeqList类型的指针变量。使用时，可通过L->elem[i-1]访问顺序表中序号为i的元素aⁱ，使用L->last+1得到顺序表的长度。

2、线性表初始化函数InitList(L)

 算法思想：先使用memset初始化函数，将开辟的数组空间初始化为指定的NULL值。再将记录线性表中最后一个元素在数组中的位置的值last置为-1。

/*初始化函数*/
int InitList(SeqList *L)
{
	memset(L->elem,NULL,sizeof(L->elem));		//初始化数据为NULL
	L->last = -1;						//空表为-1
	return 0;
}

第四行：使用了memset函数，它的作用将数组内的每个空间初始化，它有三个参数（数组名，需要填充的数据此处填充的是NULL值，数组空间的大小）。

第五行：将线性表最后一个元素的下标值置-1，为什么要为-1嘞，因为当有数据加入的时候先将last值加一，然后把last值当做数组的下标值，-1去+1刚好是0 数组起始下标就是0。

第六行：函数返回结果为0，结束函数。

3、返回线性表中元素的个数ListLength(L)

算法思想：返回表中元素个数，即返回最后一个下标值last+1的值

/*返回表中元素个数*/
int ListLength(SeqList L)
{
	return L.last+1;
}

第四行：直接返回下标值+1

4、返回线性表中第i个合法元素的值GetData(L)

算法思想：先判断这个i是否在这个线性表范围内，即：1≤i≤ListLength(L)，没有超出返回其值，超出范围，返回-1。

/*返回线性表中第i个合法元素的值*/
ElemType GetData(SeqList L,int i) {         //ElemType是一个宏定义的量，在这篇中是用它来代替int，代码编译的时候后自动进行转换的
	if ((1 <= i) && (i <= ListLength(L))) {
		return L.elem[i - 1];
	}
	else {
		printf("超出线性表的范围");
		return -1;							//若ElemType发生改变，这里需要改变
	}
}

第三行：判断传入的参数i是否合法，即他要在这个数组拥有的数据范围内，即1～ListLength（L）之间，也可以把这个函数改成1～last+1之间，'&&'为短路与，即它前边和后边都满足才执行后续大括号内的代码，当第一个条件不满足时 直接结束判断，进入大括号后边代码，不再去判断第二个条件了。

第四行：返回数组中i位置的值，因为数组开始是0开始的 我们数个数是从1开始的 所以第i个数据在数组中的位置为i-1。

第五行：即判断条件为假执行该行代码。

第六行：用于方便观察代码执行情况 可去掉。

第八行：索引不再数据范围内，返回结果-1。

5、将新的元素e插入表尾 InsListEnd(L,e)

算法思想：先判断表有没有满，满了输出表已满。没满的话，将下标值last+1，将e存入数组中

 
/*将新的元素e插入表尾*/
int InsListEnd(SeqList* L, ElemType e) {
	if (L->last >= MAXSIZE - 1) {
		printf("表已插满");
		return 0;
	}
	L->last++;
	L->elem[L->last] = e;
	return 0;
}

第三行：判断数组是否满了，即看下标值是否等于数组内的最后一个下标。当数组大小为50时，最后一个下标为49 因为下标是从0开始的，故这行代码比较下标和数组大小-1的值进行比较。

第四行：便于函数执行过程观察 可去除。

第五行：函数返回结果0 结束函数的执行。

第七行：第三行判断为假执行该行，即数组没满，将下标值+1。

第八行：将新的last值作为数组的下标值，将传入的数据存入数组中。

第九行：表示数据插入成功 返回结果0函数执行结束。

6、将一个新元素e插入表头 InsListStart(L,e)

算法思想：先判断表有没有满，满了返回表已满。若没有，将数组中的所有元素往后移一位，将e放到elem[0]的位置，下标长度last+1。

/*将一个新元素e插入表头*/
int InsListStart(SeqList* L, ElemType e) {
	if (L->last >= MAXSIZE - 1) {
		printf("表已插满");
		return 0;
	}
	for (int k = L->last; k >= 0; k--) {
		L->elem[k + 1] = L->elem[k];
	}
	L->elem[0] = e;
	L->last++;
	return 0;
}

第三、四、五行：同上第三、四、五行，判断表有没有满。

第七行：因为要插入到表头，所以需要将数组内的所有数据往后移一个位置，腾出第一个位置用于存储新的数据；这里从后边开始移，将最后一个下标值赋值给一个新的变量，用做计数器，即每变一次，值小一个，同时这个计数器的值也可以当做下标值进行变化，也保证了last不会变化。

第八行：即将当前下标的值赋给后一位下标。

第十行：数据移完了，然后将新数据存入第一个空间中。

第十一行：将表长度last+1。

7、在第i个元素值之前插入新的数据元素 InsList(L,I,e)

算法思想：先判断表有没有满，若满了，输出打印表已满，返回0结束。再判断插入位置是否合法，若不合法，输出插入不合法，返回0结束。若均满足，将从i开始数据都往后移一位，再将e存入第i处即下标为i-1处，记录下标值的last值+1。

/*在第i个元素值之前插入新的数据元素*/
int InsList(SeqList *L,int i, ElemType e) {
	
	if (L->last >= MAXSIZE - 1) {
		printf("表已满，无法插入");
		return 0;
	}
	/*判断插入位置是否合法*/
	if ((i < 1) || (i > L->last + 2)) {
		printf("插入位置i值不合法");
		return 0;
	}
	for (int k = L->last; k >= i - 1; k--) {
		L->elem[k + 1] = L->elem[k];
	}
	L->elem[i - 1] = e;
	L->last++;
	printf("插入完成");
	return 1;
}

第三～六行：同上，判断表有没有满。

第八行：判断插入位置是否合法，因为我们数个数从1开始数，故插入位置最少是1，即小于1为假，同时最后一个数为last+1，这是最后最后一个下标值按照正常数数位于的地方，但这个地方还有数据，所以插入的最后一个位置按照数数来算应该是last+1个，不能超过这个，超过这个了，中间就有空的位置了，线性表是连续的，有空位置就不连续了，无意义。

第九行：便于观察代码执行过程，可去除。

第十行：代表插入地址无意义 没必要执行函数内的后续代码了，直接结束函数，返回结果0。

第十二行：同上的第七行，将从续插入数据的位置开始往后的数据都往后移一位，包括需插入数据的位置。

第十四行：将需要存入的数据存入想存的位置。

第十五行：将线性表长度last+1。

第十六行：便于函数执行观察，可去除。

第十七行：函数执行完毕，返回结果1。

8、删除L的第i个数据元素 DelList(L,i)

算法思想：先判断需删除位置i是否合法，若不合法，输出打印输入位置i不合法，返回0结束。合法的话，将需删除的数据存入一个变量中，将从需要删除的位置起，之后的数据都往前移一位。将last小标值-1，返回删除的数据e的值。

/*删除L的第i个数据元素*/
ElemType DelList(SeqList* L, int i) {
	ElemType e;
	if ((i<1) || (i>L->last+1)) {
		printf("输入位置i不合法");
		return 0;						 //若ElemType发生改变，这里需要改变
	}
	e = L->elem[i-1];
	for (; i <= L->last; i++) {
		L->elem[i - 1] = L->elem[i];
	}
	L->last--;
	return e;
}

第三行：定义一个变量，用于存储删除数据的值，最后返回这个值。

第四～七行：用于判断插入地址是否合法，'||'为短路或，即有一个为真即为真，当第一个为真时，就不判断第二个条件了，需要删除的值应该在1～last+1范围内，即下标值是0～last范围内。

第八行：将第i个元素取出，即下标为i-1。实在理解不了的可以对比这代码行数，想第几行第几行是我们数的，即从1开始，但下标是从0开始的。也就是第一行，下标是为0，第二行下标为1（这个学计算机的是必须得去理解的）。

第九行：for循环将从删除地方开始的后续数据都往前移一位，以覆盖的形式去删除数据，最后一个数据会有俩，但只要将表长度减一即可，虽然最后一个数据还在那，但当有新的数据存入时会去覆盖它的，而且表中是用last值作为下标去访问，故最后一个元素是不可见的。

第十一行：将表长last-1，使原最后一个数据不可见。

第十二行：结束函数 返回取出的结果。

9、顺序表的按内容查找数据元素 Locate(L,e)

算法思想：从第一个数据遍历直到表中最后一个数据（非数组中最后一个数据），每次循环加一个判断语句，判断数据是否和需查找一致。存在则返回下标值last+1即所处位置（非下标位置，下标是从0开始，位于第几个是从1开始）。

/*顺序表的按内容查找数据元素
  如果L中存在数据元素e则返回e在L中的位置，否则返回空位置
*/
int Locate(SeqList L, ElemType e) {
	for (int i = 0; i < L.last; i++) {
		if (L.elem[i] == e) {
			return i+1;
		}
	}
	printf("数据不在表中\n");
	return -1;
}

第五行：for循环去遍历整个表。

第六行：在遍历的时候增加一个判断条件（不做无意义的遍历），将数组中的各个节点与需查找的数据进行匹配判断。

第七行：返回匹配的位置结果。

第十行：便于函数执行过程观察，可去除。

第十一行：无匹配结果，返回-1。

10、将线性表L置为空表 ClearList(L)

算法思想：直接调用初始化线性表函数即可

/*将线性表L置为空表*/
int ClearList(SeqList* L) {
	InitList(L);
	return 0;
}

第三行：初始化线性表函数中有一个memset函数，能够将数组内所有空间置为同一个数据，这里同置NULL，也将下标置为了-1。

11、判断表是否为空 EmptyList(L)

算法思想：判断last值是否为-1即可

/*判断表是否为空表*/
bool EmptyList(SeqList L) {
	if (L.last == -1)
		return true;
	return false;
}

第三行：判断下标是否为-1，这是顺序线性表的一个标准性。下标为-1即表为空。

第四行：判断为真执行，结束函数 返回bool类型ture。

第五行：判断为假执行，结束函数 返回bool类型 false。

12、打印输出顺序表 PrintList(L)

算法思想：若为空表则返回0即可，否则，遍历循环打印输出数组中在last范围内的值。

int PrintList(SeqList L) {
	if (L.last < 0) {
		return 0;
	}
	printf("[");
	for (int i = 0; i <= L.last-1; i++) {    //遍历到last-1是因为最后一个数据输出后不需要逗号，需要一个返回来的"]"符号
		printf("'%d',", L.elem[i]);
	}
	printf("'%d']", L.elem[L.last]);
	return 0;
}

该函数为我自定义便于观察的函数，不做说明，可不要。

13、销毁线性表 DestroyList(L)

顺序表是静态存储分配，在顺序表变量退出作用域时，自动释放该变量所占的内存单元。因此，顺序表无须销毁。(若使用malloc函数分配的堆内存，使用free函数进行销毁即可)

四、顺序表全部代码及每个模块测试

#include <iostream>
 
#define MAXSIZE 100
#define ElemType int      //若改变数据类型，GetData（），DelList（）函数的返回值需改变
 
typedef struct
{
	ElemType elem[MAXSIZE];
	int last;
}SeqList;
 
/*初始化函数*/
int InitList(SeqList *L)
{
	memset(L->elem,NULL,sizeof(L->elem));		//初始化数据为NULL
	L->last = -1;						//空表为-1
	return 0;
}
 
/*返回表中元素个数*/
int ListLength(SeqList L)
{
	return L.last+1;
}
 
/*返回线性表中第i个合法元素的值*/
ElemType GetData(SeqList L,int i) {
	if ((1 <= i) && (i <= ListLength(L))) {
		return L.elem[i - 1];
	}
	else {
		printf("超出线性表的范围");
		return -1;							//若ElemType发生改变，这里需要改变
	}
}
 
/*将新的元素e插入表尾*/
int InsListEnd(SeqList* L, ElemType e) {
	if (L->last >= MAXSIZE - 1) {
		printf("表已插满");
		return 0;
	}
	L->last++;
	L->elem[L->last] = e;
	return 0;
}
 
/*将一个新元素e插入表头*/
int InsListStart(SeqList* L, ElemType e) {
	if (L->last >= MAXSIZE - 1) {
		printf("表已插满");
		return 0;
	}
	for (int k = L->last; k >= 0; k--) {
		L->elem[k + 1] = L->elem[k];
	}
	L->elem[0] = e;
	L->last++;
	return 0;
}
 
 
/*在第i个元素值之前插入新的数据元素*/
int InsList(SeqList *L,int i, ElemType e) {
	
	if (L->last >= MAXSIZE - 1) {
		printf("表已满，无法插入");
		return 0;
	}
	/*判断插入位置是否合法*/
	if ((i < 1) || (i > L->last + 2)) {
		printf("插入位置i值不合法");
		return 0;
	}
	for (int k = L->last; k >= i - 1; k--) {
		L->elem[k + 1] = L->elem[k];
	}
	L->elem[i - 1] = e;
	L->last++;
	printf("插入完成");
	return 1;
}
 
/*删除L的第i个数据元素*/
ElemType DelList(SeqList* L, int i) {
	ElemType e;
	if ((i<1) || (i>L->last+1)) {
		printf("输入位置i不合法");
		return 0;						 //若ElemType发生改变，这里需要改变
	}
	e = L->elem[i-1];
	for (; i <= L->last; i++) {
		L->elem[i - 1] = L->elem[i];
	}
	L->last--;
	return e;
}
 
/*顺序表的按内容查找数据元素
  如果L中存在数据元素e则返回e在L中的位置，否则返回空位置
*/
int Locate(SeqList L, ElemType e) {
	for (int i = 0; i < L.last; i++) {
		if (L.elem[i] == e) {
			return i+1;
		}
	}
	printf("数据不在表中");
	return -1;
}
 
/*将线性表L置为空表*/
int ClearList(SeqList* L) {
	InitList(L);
	return 0;
}
 
/*判断表是否为空表*/
bool EmptyList(SeqList L) {
	if (L.last == -1)
		return true;
	return false;
}
 
 
/*打印输出顺序表*/
int PrintList(SeqList L) {
	if (L.last < 0) {
		return 0;
	}
	printf("[");
	for (int i = 0; i <= L.last-1; i++) {
		printf("'%d',", L.elem[i]);
	}
	printf("'%d']", L.elem[L.last]);
	return 0;
}
 
 
int main()
{
	SeqList list,*L;
	L = &list;
	printf("————————初始化线性表—————-—————\n");
	printf("初始化返回结果：%d", InitList(L));
	printf("\n——————返回线性表中元素的个数——————\n");
	printf("线性表中元素个数为：%d",ListLength(list));
	printf("\n——————返回线性表中第i元素——————\n");
	printf("返回结果：%d",GetData(list,2));
	printf("\n——————将线性表中表尾插入法插入十个元素——————\n");
	for (int i = 0; i < 10; i++)
		InsListEnd(L, i * 2);
	printf("插入结果为：");
	PrintList(list);
	printf("\n——————再次返回线性表中元素的个数——————\n");
	printf("线性表中元素个数为：%d", ListLength(list));
	printf("\n——————将新元素77插入表头——————\n");
	InsListStart(L,77);
	printf("插入结果为：");
	PrintList(list);
	printf("\n——————将新元素99插入第7的位置——————\n");
	InsList(L, 7, 99);
	printf("插入结果为：");
	PrintList(list);
	printf("\n——————将新元素100插入第50的位置——————\n");
	InsList(L, 50, 100);
	printf("\n—————-删除第3个元素——————\n");
	printf("删除的数为：%d", DelList(L, 3));
	printf("删除后表为为：");
	PrintList(list);
	printf("\n—————-判断表是否为空表——————\n");
	printf("空为1，不空为0：%d", EmptyList(list));
	printf("\n—————-查找12，50位于表的哪个位置——————\n");
	printf("12位于第%d个元素。\n",Locate(list,12));
	printf("50位于第%d个元素。",Locate(list, 50));
	printf("\n—————-将线性表置为空表——————\n");
	ClearList(L);
	printf("置后结果为：");
	PrintList(list);
	printf("\n—————-再次判断表是否为空表——————\n");
	printf("空为1，不空为0：%d", EmptyList(list));
}

测试结果为：