3.1 线性表顺序存储及运算

线性表是一种最简单也是最常见的数据结构，采用顺序存储方式存储的线性表称之为顺序表。顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。顺序表的主要运算有插入、删除、查找和排序等。

3.1.1 线性表的基本概念

线性表（Linear List）是n个类型相同的数据元素的有限序列，数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。例如，英文字母表（a，b，…，z）就是一个简单的线性表，如图3-1所示。

表中的每一个英文字母是一个数据元素，每个元素之间存在唯一的顺序关系，如在英文字母表字母b的前面是字母a，而字母b后面是字母c。

在较为复杂的线性表中，数据元素（Data Elements）可由若干数据项组成，如图书馆的书目检索系统的图书书目信息表中，每种图书及其各种相关信息是一个数据元素，它由图书编号、书名、作者及出版时间等数据项（Item）组成，常被称为一个记录（Record），含有大量记录的线性表称为文件（File）。数据对象（Data Object）是性质相同的数据元素集合，见表3-1。

1.线性表的定义

线性表（Linear List）是由n（n≥0）个类型相同的数据元素组成的有限序列，数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继，记作（a1，a2，…，ai-1，ai，ai＋1，…，an）。

我们把线性结构中的结点叫做元素，如图3-2所示。

这里的数据元素ai（1≤i≤n）只是一个抽象的符号，其具体含义在不同情况下可以不同，它既可以是原子类型，也可以是结构类型，但同一线性表中的数据元素必须属于同一数据对象。线性表中相邻数据元素之间存在着序偶关系，即对于非空的线性表（a1，a2，…，ai-1，ai，ai＋1，…，an），表中ai-1领先于ai，称ai-1是ai的直接前驱，而称ai是ai-1的直接后继。除了第1个元素a1外，每个元素ai有且仅有一个直接前驱的结点ai-1；除了最后一个元素an外，每个元素ai有且仅有一个直接后继的结点ai＋1。线性表中元素的个数n被定义为线性表的长度，n＝0时称为空表。2.线性表的特点线性表的特点可概括如下： 1）同一性。线性表由同类数据元素组成，每一个ai必须属于同一数据对象。2）有穷性。线性表由有限个数据元素组成，表长度就是表中数据元素的个数。3）有序性。线性表中相邻数据元素之间存在着序偶关系＜ai，ai＋1＞。由此可以看出，线性表是一种最简单的数据结构，因为数据元素之间是由一个前驱与一个后继的直观有序的关系确定的；线性表又是一种最常见的数据结构，因为矩阵、数组、字符串、堆栈、队列等都符合线性条件。

3.1.2 顺序表的基本概念和结构特征

1.顺序表的基本概念

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

采用顺序存储结构的线性表通常称为顺序表。

2.顺序表的结构特征

假设线性表中有n个元素，每个元素占k个存储单元，第一个元素的地址为loc（a1），则可以通过式（3-1）计算出第i个元素的地址loc（ai）：

loc（ai）＝loc（a1）＋（i-1）×k （3-1）其中，loc（a1）称为线性表的起始位置或基地址。

图3-3给出了线性表的顺序存储结构示意。从图中可看出，在顺序表中，每个结点ai的存储地址是该结点在表中的逻辑位置i的线性函数，只要知道线性表中第一个元素的存储地址（基地址）和表中每个元素所占存储单元的多少，就可以计算出线性表中任

意一个数据元素的存储地址，从而实现对顺序表中数据元素的随机存取。

说明：

1）类型标示符DataType可以是基本数据类型，如：int、float、char等，也可以是struct定义的复合数据类型。在算法中，除特别说明外，规定DataType的默认类型是int。

2）在C语言程序中，数组下标从0开始，但元素序号仍从1开始。例如：顺序表中第一个元素是data［0］，第i个元素是data［i-1］。如图3-4所示。

顺序表中每个元素在存储器中占用的空间大小相同，若第一个元素存放的位置是loc（a0），每个元素占用的空间大小为k，元素ai的存放位置：

loc（ai）＝loc（a0）＋k*i （3-2）

3.1.3 顺序表的算法

1.初始化顺序表

此处对顺序表进行初始化使用了InitSList函数，在函数中对传来的顺序表L进行操作，将L的last分量赋值为-1即可实现。在C函数中有值传递和引用传递两种形式，引用传递中形参名称形式：＆变量名称。引用传递时被调用函数和主调函数共享同一个变量。

代码如下：

2.求顺序表长度

顺序表的长度是顺序表中数据元素的个数，在顺序表的结构中，last分量是最后一个元素在数组中的位置，所以顺序表的长度为last＋1，代码如下：

3.插入操作

顺序表的插入运算是指在表中的第i（1≤i≤n＋1）个位置，插入一个新元素x，使长度为n的顺序表（a1，…，ai-1，ai，…，an）变成长度为n＋1的顺序表（a1，…，ai-1，x，ai，…，an）。

用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此我们必须将原表中位置n，n-1，…，i上的结点，依次后移到位置n＋1，n，…，i＋1上，空出第i个位置，然后在该位置上插入新结点x。当i＝n＋1时，是指在顺序表的末尾插入结点，所以无须移动结点，直接将x插入表的末尾即可。

说明：

1）返回值为1代表正确插入，返回值-1代表插入位置出错；返回值0代表顺序表已满，无法插入。也可以在代码中直接打印出错原因。

2）顺序表的插入过程中，插入的位置i最大为表长度＋1，最小为1。

4.删除操作

线性表的删除运算是指将表中的第i（1≤i≤n）个元素删去，使长度为n的顺序表（a1，…，ai-1，ai，ai＋1，…，an），变成长度为n-1的顺序表（a1，…，ai-1，ai＋1，…，an）。

说明：

1）返回值为1代表正确删除，返回值为-1代表删除位置出错；返回值为0代表顺序表为空，不能删除。也可以在代码中添加打印出错原因。　　

2）顺序表的删除过程中，删除的位置i最大为表长度，最小为1。

在顺序表中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。对于插入算法而言，设Pi为在第i个元素之前插入元素的概率，并假设在任何位置上插入的概率相等，即。设Eins为在长度为n的表中插入一元素所需移动元素的平均次数，则

同理，设Qi为删除第i个元素的概率，并假设在任何位置上删除的概率相等，即 2，…，n）。则删除一元素所需移动元素的平均次数Edel为：

由以上分析可知，在顺序表中插入和删除一个数据元素时，其时间主要耗费在移动数据元素上。进行一次插入或删除操作平均需要移动表中一半的元素，当n较大时效率较低。5.查找操作顺序表有两种基本的查找运算。按序号查找Locate（SeqList＆L，int i），查找线性表L中第i个数据元素，要求函数首先判断i的取值范围是否为1≤i≤n。因为线性表（a1，a2，…，ai-1，ai，ai＋1，…，an）对应的数组下标为各元素的序号-1，因此在i取值合法时，函数直接返回L.data［i-1］即可。按内容查找GetData（SeqList＆L，DataType x），查找线性表L中与给定值x相等的数据元素，其结果是：若在表L中找到与x相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。查找运算可采用顺序查找法实现，即从第一个元素开始，依次将表中元素与x相比较，若相等，则查找成功，返回该元素在表中的序号；若x与表中的所有元素都不相等，则查找失败，返回“-1”。

说明：

1）返回值为查找到的元素位置，返回值为-1代表查找失败。

2）当顺序表为空时查找失败。

3.1.4 顺序表算法编程实例

使用顺序表实现一个电话簿管理程序，电话簿中的每条记录包括姓名和电话两项。程序实现了菜单，初始化，添加、删除和显示等功能。

C语言程序源代码：