下载掌阅APP，畅读海量书库
立即打开
由线性表的概念可知线性表的逻辑结构，实际上是基于前面元素和后面元素之间的一种相邻关系的结构。一种逻辑结构可对应多种存储结构，每种存储结构都有自己的存储特点和操作方式。线性表的存储结构可分为顺序存储结构和链式存储结构两种。根据线性表的两种存储结构，线性表可分为顺序表和链表两大类，下面讲解第一种存储方式——顺序存储结构。
顺序表是指按顺序存储结构存储的线性表，顺序表中的结点在内存中占用一段连续的存储单元。即线性表中逻辑相邻的元素在内存中存储位置也相邻。如以学号和姓名为数据元素的顺序表存储结构如图2.2所示。
图2.2 以学号和姓名为数据元素的顺序表存储结构图
图2.2 中add为第一个元素a 1 的地址，每个数据元素（包括学号和姓名）占用内存的长度为len，因此在顺序存储结构中有如下关系：
Loc（a i ）=Loc（a 1 ）+（i-1）len （1<=i<=n）
其中Loc（a 1 ）的地址为add，也就是说，只要知道顺序表的首地址和每个数据元素所占地址的单元个数，就可以求出第i个数据元素的地址，这也是顺序表具有按数据元素序号随机存取的特点。根据顺序表的存储特点，我们通常用数组去实现顺序表。
顺序表的三个优点：
（1）方法简单，各种高级语言中都有数组，容易实现。
（2）不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度大。
（3）顺序表具有按元素序号随机访问的特点，查找速度快，时间复杂度较小。
顺序表的两个缺点：
（1）在顺序表中进行插入、删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表执行效率低。
（2）需要预先分配适当的存储空间，预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。
根据图2.1所示的学生表顺序存储结构对应的顺序表，实现对该表中数据元素的插入、删除、查找等运算。为了便于理解，后面示例中顺序表均以学号和姓名为数据元素。
根据顺序表的存储特点，要在顺序表中某位置i插入一个新数据元素，则要进行如下四步操作：
（1）先判断表是否满，再判断插入位置i是否合理。如果插入前表已满，或插入位置超出表的范围，则插入失败。
（2）从位置i到表尾位置的所有数据元素均要向后移一个存储位置，为新插入结点腾出第i个位置。（注意：后移是从表尾位置起后移到位置i结束）
（3）将新结点插入到空余位置i处。
（4）修改表长度，使之增加1。
【例2.1】编程实现在学生顺序表的张阳同学前插入数据元素（120010131，郑克龙）。
首先要定义学生信息结构体来存放学生记录，具体如下：
接下来插入对应结点的过程如下：
图2.3 插入前学生表
插入前如图2.3所示。
数据元素后移，从表尾数据元素（120010130，黄凯）起，逐条数据依次后移，直到数据元素（120010103，张阳）被移动后结束，移动后如图2.4所示。
将数据元素（120010131，郑克龙）插入空出的空间里，插入后如图2.5所示。
图2.4 数据元素移动后的学生表
图2.5 插入新结点后的学生表
在表的第i个位置前插入新数据元素stu，其中data为存放学生表各数据元素的数组，length为表的长度，curlen为表的实际长度，则插入操作流程图如2.6所示。
图2.6 插入操作流程图
根据顺序表的存储特点，要删除表中某结点i，则要进行如下操作：
（1）先判断表是否为空，再判断删除位置i是否合理。如果删除前表为空，或删除位置超出表的范围，则删除失败。
（2）从位置i+1 到表尾位置的所有数据元素均要向前移一个存储位置，则原来第i+1个结点覆盖第i个结点，以此类推，直到表尾则可实现第i个结点的删除。（注意：前移是从第i+1 个位置起前移到表尾位置结束）
（3）修改表长度，使之减1。
【例2.2】删除学生顺序表中数据元素（120010102，王丽）。
图2.7 删除王丽同学结点前的学生表
首先要定义学生信息结构体来存放学生记录，具体参见Student结构体定义，接下来删除对应结点的过程如下：
删除前的学生表如图2.7所示。
数据元素前移，从数据元素（120010131，郑克龙）起，逐条数据依次前移，前移的数据元素将覆盖上一位置的数据，直到表尾数据元素（120010130，黄凯）被移动后结束，则实现了数据元素（120010102，王丽）的删除，移动过程如图2.8所示。
图2.8 删除王丽同学结点过程的学生表
删除表的第i个位置的数据元素，其中data为存放学生表各数据元素的数组，curlen为表的实际长度，则删除操作流程图如图2.9所示。
图2.9 删除操作流程图
在上面插入代码的基础上，增加删除函数Student* Delete(int i)，实现顺序表的删除功能，具体如下：
