顺序表和链式表存储结构研究

梁少刚

（宝鸡职业技术学院，陕西 宝鸡721000）

1 线性表的概述

线性表（Linear list）是最简单且最常用的一种数据结构。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。

1.1 线性表的逻辑结构

线性表是有限元素（a1,a2,a3，…，an）有序序列的集合，a1，a2，…，an都是完全相同结构的数据类型，同时它们之间的排列严格有序，其中任何元素都对应唯一的前驱以及唯一的后继。这样一个序列可以有查询、删除、插入队列任何位置的数据操作。

1.2 线性表的物理结构

顺序线性表是用一定大小的数据来存放线性表，数组长度代表线性表的长度，元素在数组的位置代表元素在线性表的位置。但对数组中元素不能跳跃插入，因为线性表中元素是顺序且连接着的，不像数组中间可以空元素。同时删除元素时，必须大量移动剩下的元素，因为必须实现其连续性。插入元素同样需要大量移动数据。因此这样存储的运行效率并不够高。所以对于有着频繁插入和删除运算的线性表，是不适合采用顺序存储的。

链式线性表是通过动态分配，分配物理上不一定相邻的存储单元。为表示他们的连续性连接性，再在分配这个存储单元时，附加一部分存储单元———指针域来指出这个元素的后继元素的存储地址。链式存储结构又分为单链表、循环链表和双向链表等。这样的链式存储多节省了操作的时间，但需要更多的存储空间。

2 顺序线性表

2.1 顺序表及其存储结构

用一组地址连续的存储单元依次存放线性表里的数据元素。用这种方法存储的线性表简称顺序表。

线性表的起始地址称作线性表的地址，以存储位置相邻来表示有序对〈ai-1，ai〉即线性表中第i个数据元素的存储位置LOC(ai)和第i-1个数据元素的存储位置LOC(ai-1)之间满足下列关系：

LOC(ai)=LOC(ai-1)+L（一个数据元素所占的存储位置）

所有数据元素的存储位置均取决于第一个数据元素的存储位置：顺序表的类型定义如下：

2.2 顺序表的基本运算

2.2.1 插入算法

1）不用查找插入位置i，只需要判断i的合法位置，其范围是1≤i≤L.length+1，否则不合法；

2）判断线性表是否满，若L.length≥L.listsize说明线性表满了，不能进行插入数据元素操作，要增加存储空间的分量或者做出错处理；

3）将线性表的最后一个数据元素到第i-1个数据元素依次往后移动一个数据单元，空出第i-1个位置的数据单元；

4）把新的数据元素插入到刚才空出来的数据单元中；5）线性表长度增加 1。

2.2.2 删除算法

1）不用查找删除位置i，也不用另外判断线性表是否为空，只要 i取值为1≤i≤L.length就包括了线性表判空操作和删除位置i的合法性判断了，否则不合法。

2）将线性表的第i个数据元素到最后一个数据元素依次往前移动一个数据单元，就算删除了第i个数据元素。

3）线性表长度减 1。

2.2.3 查找算法

1）顺序查找算法对数据元素有序、无序没有要求，只要把给定的关键字与线性表中的数据元素逐个进行比较，若相等查找就成功，若找遍整个线性表中的数据元素都没有找到与关键字相等的数据元素，则查找失败。

2）折半查找是要求顺序存储和存储的数据元素有序，查找时把给定的关键字与表中的中间位置元素进行比较，若相等就查找成功，若关键字比中间位置大，则下次在右半部分查找，若比中间位置上的数据元素小，则下次在左半部分查找，依次重复，直到找完查找区间的所有数据元素也没有找到与关键字相等的数据元素存在，则查找失败。

3）索引查找是把顺序表中的数据元素等分成相等的几部分，使后一个子表的所有数据元素均大于前一个子表的最大数据元素，并用每一个子表的最大关键字建立索引表。进行查找时，将给定关键字先与索引表中的关键字进行比较，确定此关键字属于哪一个子表，再在这个子表上进行查找。

4）哈希查找是关键字与哈希函数存在某种对应关系，只要通过哈希函数就能直接确定数据元素在哈希表中的对应位置。如果数据元素没有冲突，不用查找就能找到关键字；如果存在冲突，就利用解决冲突的办法来查找这个关键字。

3 链式线性表

3.1 单链表及其存储结构

线性表最简单的链式存储形式称为单链表或线性链表，链表中每个结点仅含一个数据域和一个指针域，可描述为：

其中ElemType可根据需要用int，char等类型来代替；当然这里的数据域也可以是一个记录（如学生记录）。在这里我们使用带头结点的单链表。

3.2 链表的基本运算

3.2.1 插入算法

1）链式存储的线性表做插入操作，不判断线性表是否满，但是要从头指针开始，通过循环语句循环查找第i-1个结点。

2）判断i的合法性，i的合法范围是1≤i≤n，否则就是不合法。

3）申请一个结点的存储空间，并用一个指针变量指向这个结点，把需要插入的数据元素值赋给这个结点的数据域中。

4）修改插入数据元素的指针，完成插入操作。

3.2.2 删除算法

1）链式存储的线性表做删除操作前，要从头指针开始，通过循环语句循环查找需要删除的第i个结点。

2）判断第i个结点的合法性，i的合法范围是1≤i≤n，否则不合法。

3）修改删除数据元素的指针，完成删除操作。

4）释放删除结点的存储空间。

3.2.3 查找算法

1）单链表。只能从头指针开始，一个结点接着一个结点地顺序查找，不能找结点前驱，只能找结点后继结点。

2）循环链表。可以从头指针开始，也可以从尾指针开始顺序地查找结点的后继元素。

3）双向链表。从头指针开始顺序查找结点，既可以查找结点的前驱元素，也可以查找结点的后继元素。

4）对比分析

顺序表的优点：实现方法简单。一维数组在内存中占用的空间就是一组连续的存储区域，因此，用一维数组来表示顺序表的数据存储是最合适的。其次，顺序表中元素间的物理位置关系正好反映了线性表元素间的逻辑关系，因此，不需要增加额外的存储开销。另外顺序表还具有按元素序号随机访问的特点，只要知道顺序表的首地址和每个数据元素所占存储单元的个数，就可以求出第 i个数据元素的存储地址。

顺序表的缺点：由数组来实现时，数组下标所标出的必须是定量，但是实际问题中，线性表中的元素个数是不固定的，线性表中的元素用顺序表实现时，必须预先分配足够大的存储空间，存储空间估计过大，可能导致顺序表后部空间大量闲置，浪费存储空间；预留分配过小，又会造成溢出。而且在顺序表中做插入和删除操作时，由于顺序表中元素的物理位置必须相邻，因此需要平均移动大约表中一半的元素，那么当顺序表中的元素较多时，顺序表的运行效率就会很低。

单链表的优点：是一种动态的存储结构，链表中每个结点占用的存储空间不是预先分配的，而是系统运行时根据需求生成的，只要内存有足够的空间，就可以存储任意长度的线性表，一般不会产生溢出。单链表不需要用地址连续的存储单元来实现，因为它不要求逻辑上相邻的两个数据元素物理上也相邻，在单链表中做插入和删除操作时，由于元素间的物理位置关系是由指针实现的，因此只需要改变指针就可以了，不需要移动大量的数据元素，大大提高了运行效率。

单链表的缺点：需要对每个元素设置一个指针域，用来存储指示其直接后继的信息，这就增加了存储开销。而且，单链表不具有按序号随机访问的特点，访问任意一个元素时都需要从表头开始依次查找，访问效率较低。

［1］严蔚敏,吴伟民.数据结构：C 语言版[M].北京：清华大学出版社,1997.

［2］李春葆.数据结构教程[M].2 版.北京：清华大学出版社,2007.

［3］从艳,任益夫,刘向玲.线性表不同存储结构的比较与应用[J].电脑知识与技术,2007(08).