2.3　顺序表结构

顺序表（Sequential List）就是按照顺序存储方式存储的线性表，该线性表的结点按照逻辑次序依次存放在计算机的一组连续的存储单元中，如图2-1所示。

由于顺序表是依次存放的，只要知道了该顺序表的首地址及每个数据元素所占用的存储长度，那么就很容易计算出任何一个数据元素（即数据结点）的位置。

一般的，假设顺序表中所有结点的类型相同，则每个结点所占用的存储空间大小亦相同，每个结点占用c个存储单元。其中第一个单元的存储地址则为该结点的存储地址，并设顺序表中开始结点a1的存储地址（简称为基地址）为LOC（a1），那么结点ai的存储地址LOC（ai）可通过下式计算：

LOC（ai）=LOC（a1）+（i-1）*c1≤i≤n

这就是能够操作顺序表进行运算的基本规则。接下来分析如何在C语言中建立顺序表，并完成顺序表的基本运算。

2.3.1　准备数据

学习了前面的理论知识后，下面就开始顺序表结构的程序设计。首先需要准备数据，也就是准备在顺序表操作中需要用到的变量及数据结构等。示例代码如下：

在上述代码中，定义了顺序表的最大长度MAXLEN，顺序表数据元素的类DATA及顺序表的类SLType。在类SLType中，ListLen为顺序表已存结点的数量，即当前顺序表的长度，ListData是一个对象数组，用来存放各个数据结点。

其实，可以认为该顺序表是一个班级学生的记录。其中，key为学号，name为学生的名称，age为年龄。

由于Java语言中数组都是从下标0开始的。在这里，为了讲述和理解的方便，从下标1开始记录数据结点，下标0的位置不使用。

2.3.2　初始化顺序表

在使用顺序表之前，首先要创建一个空的顺序表，即初始化顺序表。这里，在程序中只需设置顺序表的结点数量ListLen为0即可。这样，后面需要添加的数据元素将从顺序表的第一个位置存储。代码示例如下：

需要注意的是，这里并没有清空一个顺序表。读者也可以采用相应的程序代码来清空，只需简单地将结点数量ListLen设置为0即可，这样如果顺序表中原来已有数据，也会被覆盖，并不影响操作，反而提高了处理的速度。

2.3.3　计算顺序表长度

计算顺序表长度即计算线性表L中结点的个数。由于在类SLType中使用ListLen来表示顺序表的结点数量，因此程序只要返回该值就可以了。代码示例如下：

2.3.4　插入结点

插入结点就是在线性表L的第i个位置插入一个新的结点，使得其后的结点编号依次加1。这时，插入一个新结点之后，线性表L的长度将变为n+1。插入结点操作的难点在于随后的每个结点数据都要进行移动，计算量比较大。代码示例如下：

在上述代码中，在程序中首先判断顺序表结点数量是否已超过最大数量，以及插入结点序号是否正确。所有条件都满足后，然而将顺序表中的数据向后移动，同时插入结点，并更新结点数量ListLen。

2.3.5　追加结点

追加结点并不是一个基本的数据结构运算，其可以看作插入结点的一种特殊形式，相当于在顺序表的末尾新增一个数据结点。由于追加结点的特殊性，其代码实现相比插入结点要简单，因为不必进行大量数据的移动，因此这里单独给出其实现的程序。代码示例如下：

在上述代码中，仅简单判断这个顺序表是否已经满了，然后便追加该结点，并更新结点数量ListLen。

2.3.6　删除结点

删除结点即删除线性表L中的第i个结点，使得其后的所有结点编号依次减1。删除一个结点之后，线性表L的长度将变为n-1。删除结点和插入结点类似，都需要进行大量数据的移动。代码示例如下：

在上述代码中，首先判断待删除的结点序号是否正确，然后开始移动数据，并更新结点数量ListLen。

2.3.7　查找结点

查找结点即在线性表L中查找值为x的结点，并返回该结点在线性表L中的位置。如果在线性表中没有找到值为x的结点，则返回一个错误标志。根据值x类型的不同，查找结点可以分为按照序号查找结点和按照关键字查找结点两种方法。

1）按照序号查找结点

对于一个顺序表，序号就是数据元素在数组中的位置，也就是数组的下标标号。按照序号查找结点是顺序表查找结点最常用的方法，这是因为顺序表的存储本身就是一个数组。代码示例如下：

2）按照关键字查找结点

另一个比较常用的方法是按照关键字查找结点。这里，关键字可以是数据元素结构中的任意一项。以key关键字为例介绍，由前面知道key可以看作学生的学号。代码示例如下：

2.3.8　显示所有结点

显示所有结点数据并不是一个数据结构基本的运算，因为其可以简单地逐个引用结点来实现。不过为了方便，还是将其单独列为一个方法。代码示例如下：

2.3.9　顺序表操作实例

学习了前面的顺序表的基本运算之后，便可以轻松地完成对顺序表的各种操作。下面给出一个完整的例子，来演示顺序表的创建、插入结点、查找结点等操作。代码示例如下：

【程序2-1】

在上述代码中，main（）主方法首先初始化顺序表，然后循环添加数据结点，当输入全部为0时则退出结点添加的进程。接下来显示所有的结点数据，并分别按照序号和关键字来进行结点的查找。该程序执行结果，如图2-2所示。