【链表5】线性表（List）简介

文 /Edward

  结构体数组与线性表A

前面我们使用结构体数组设计出了类似于“表（Table）“数据结构的存储序列，它以整个定长度的结构体数组为单位，并且以每个结构体数组中的元素来存放具体的数据对象。再深入思考一下，前面我们讲过数组中每个元素的内存地址是顺序的，那是不是就是这个表就是线性表呢？其实不是，这种用结构体数组组成的类似于表格的存储单元，他不具备一个”表“数据结构的完整特征，即动态地增，减，删，查。而在C语言数据结构中，有一种专门的数据结构叫做”线性表“。

”线性表“和我们前面所讲述的结构体数组表之间唯一的区别就是，”线性表“可以动态地增，减，删，查这个表中的所有表项，也即我们所谓的表”节点“。好了，现在问题变得非常简单了，我们可以将之前讲述的结构体数组表类比于一个普通的数组，那么线性表相比于结构体数组表就类似要解决的问题就是，动态地去改变这个”数组“的长度。

  动态改变“数组“长度

我们前面讲过了，一个数组的长度是在这个数组被定义完成之后所决定的，因为这是牵扯到内存分配的问题，因此我们根本无法去修改这个这个数组的长度，怎么现在又要来改变它的长度了呢？这个问题其实也很好解决，我们再来回顾一下数据的内存排列，如图1所示。

图1 数组内存分布

图1中的数组内存分布相信大家都非常简单就可以看懂，就让我们再来回顾一下。假设这个数组的类型是char类型的，当我们定义好了这个数组之后，这个数组名在C语言中其实就是代表着这个数组存放的首地址，也即第一个数组元素的地址。而第二个元素其实是在这个数组的首地址基础上偏移一个数组类型的长度（如char类型数组偏移1，int类型偏移2或者4）。

因此，我们只要知道两个信息就可以在一个数组里面找到任何一个元素了，这两个信息就是这个数组的起始地址和偏移量。

我们再来深层次地思考一下，数组的本质其实就是将多个同一类型的变量打包到一起去，便于我们编程和检索。而如果我们知道数组的起始地址和偏移量这两个维度的信息，那么它本质上是不是数组其实都无所谓，因为其最终表达的含义也跟数组差不多。

所以实现一个动态长度的数组就变得很简单了，我们只需要定义一个结构体用来存储用这个数组的起始地址和长度。注意，这个长度是我们为这个表增加的节点数，而这个起始地址存储着我们使用malloc函数为我们指定长度的数组申请好内存之后的返回值。

因此，我们就可以使用如图2中所示的代码来初始化这个线性表的第一个节点，即初始节点。

图2 创建初始节点

好了，现在一个不定长度的数组被创建完成了，只要我们每次配分数组时，指定这个数组的长度，程序就会按照我们的要求为我们创建一个新的指定长度的数组了。此时数组分配好的内存示意如图3所示。

图3 线性表创建好初始节点

创建完成表之后，接下来要做的就是对这个表里面插入新的数据了，即相当于对数组元素进行赋值。赋值的时候，我们前面讲数组的时候也说了，对于数组某一项赋值也可以使用“基地址+偏移量”的形式。添加新的数据项的代码如图4所示。

图4 写入和读出数据项

以上就是线性表的一些基本知识，我们这里只是将其作为动态数组的形式来读写这个线性表的。事实上，这个线性表和结构体数组比起来改善好不到哪里去，因为它的数据项也只有每次在初始化的时候改变。而且如果在对线性表插入数据的时候，需要将数组内所有的数据移位，特别占用时间。因此，这种线性表在我们日常的应用中基本不会用到，我们就不对其进行深入学习了。

本文源码

#include<stdio.h>#include<stdlib.h>#define SUCCESS 0#define FAIL 1typedef int ListNode_t;typedef struct{ ListNode_t *ListNode; //存放线性表的初始地址int length; //存放线性表当前存放数据的长度} List_t;
/**@brief: 初始化线性表，即分配初始地址和申请指定长度的内存*/int InitList(List_t *List, int legnth){int RetVal = SUCCESS; List->ListNode = NULL; List->ListNode = (ListNode_t *)malloc(sizeof(ListNode_t) * legnth);if(List->ListNode == NULL) { RetVal = FAIL; } List->length = 0;return RetVal;}
/**@brief: 在线性表的某个索引赋值*@Para:List_t *List --- 表首地址 int index --- 写入的索引 ListNode_t data --- 写入的数据 int ArrayMaxLen --- 最大的数组长度，这个可以使用define定义的符号代替*/int ListAddElem(List_t *List, int index, ListNode_t data, int ArrayMaxLen){int RetVal = SUCCESS;if(index < 0 || index >= ArrayMaxLen) { RetVal = FAIL; } *(List->ListNode + index) = data; List->length ++;return RetVal;}/**@brief: 读取线性表的某个索引中的数据*@Para:List_t *List --- 表首地址 int index --- 写入的索引 ListNode_t data --- 写入的数据 int ArrayMaxLen --- 最大的数组长度，这个可以使用define定义的符号代替*/ListNode_t ListReadElem(List_t *List, int index, int ArrayMaxLen){ ListNode_t RetVal = 0;if(index < 0 || index >= ArrayMaxLen) { RetVal = FAIL; } RetVal = *(List->ListNode + index);return RetVal;}int main(void){ List_t NameList; ListNode_t Elem;int ArrayLength = 5;if(InitList(&NameList, ArrayLength) == FAIL) {printf("Create list fail"); }else {printf("Create list successfully, address is %#x\n", NameList.ListNode); } ListAddElem(&NameList, 0, 14, 5); Elem = ListReadElem(&NameList, 0, 5);printf("The element is %d\n", Elem);return 0;}