顺序存储的实现
了解了顺序表，那么我们接下来实现一个顺序表，并完成其查找、插入和删除等基本操作。在实现各种数据结构时，都以C语言为例。
1、创建顺序表
在创建顺序表时，需要先创建一个头结点来存放顺序表的长度、大小和地址等信息，然后再创建顺序表，同时将顺序表的地址保存在头结点中，其示意图如图1所示。
图1 顺序表示意图
实现思路如下：
（1）定义一个struct来保存顺序表信息。
（2）为头结点分配空间。
（3）为顺序表分配空间，将顺序表空间地址保存在头结点中。
（4）将头结点地址返回给调用者。
代码实现如下：
typedef struct _tag_SeqList //头结点，记录表的信息
{
int capacity; //表容量
int length; //表长度
int * node; //node[capacity]，为指针数组
}TSeqList;
//创建顺序表
SeqList* SeqList_Create(int capacity) //返回值为SeqList*类型，即顺序表的地址
{
int ret;
TSeqList *temp = NULL;
temp = (TSeqList*)malloc(sizeof(TSeqList)); //为头结点分配空间
if (temp == NULL)
{
ret = 1;
printf("func SeqList_Create() error:%d\n", ret);
return NULL;
}
memset(temp, 0, sizeof(TSeqList));
temp->capacity = capacity;
temp->length = 0;
temp->node = (int*)malloc(sizeof(void*)*capacity); //分配一个指针数组
if (temp->node == NULL)
{
ret = 2;
printf("func SeqList_Create() error:%d\n", ret);
return NULL;
}
return temp; //将分配好的顺序表的地址返回
}顺序表的实现并不难，而且实现方式也有多种，只要思路清晰，代码实现就很简单，读者也可以试着自己来实现一遍。
2、求顺序表容量
在实现顺序表时，一般将顺序表信息保存在头结点中，因此求顺序表容量时，可以直接从头结点中获取。代码实现如下所示：
//求顺序表容量
int SeqList_Capacity(SeqList* list) //参数为顺序表地址
{
TSeqList *temp = NULL;
if (list == NULL) //作健壮性判断
{
return;
}
temp = (TSeqList *)list;
return temp->capacity;
}3、求顺序表长度
和求顺序表的容量一样，求顺序表大小也是从头结点中获取信息，代码如下所示：
//获取顺序表长度
int SeqList_Length(SeqList* list)
{
TSeqList *temp = NULL;
if (list == NULL)
{
return;
}
temp = (TSeqList *)list;
return temp->length;
}4、插入元素
增删改查是数据结构的核心操作，每种数据结构都要实现这几种最基本的操作。在顺序表中，要插入元素，则需要将插入位置后的所有元素向后移动，其示意图如图2所示。
图2 插入元素
在图2中，要在顺序表的1角标位置插入元素X，则在插入时，需要将1角标和其后的元素都向后移动一个单元，其过程如图3所示。
图3 插入元素X
图2和图3演示了往顺序表中插入元素的过程。在插入过程中，需要考虑一些异常情况：
● 当顺序表已满时，表中的元素无法向后移动，需要作出特别处理（例如不插入，或者新开辟一块更大的空间来存储这些元素）。
● 当插入的位置在空闲区域时，需要作出相应处理：在空闲位置插入元素，如图4所示。
图4 在空闲区域插入元素
在图4中，容量为5的顺序表中只有两个元素，当插入新元素X时，指定的位置是角标3的位置，这样就造成元素不连续，不符合顺序表的存储规则。在这种情况下可以作适当的修正，将插入位置改为角标2。
有了插入元素的思路后，接下来用代码来实现，代码如下：
//插入元素
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
//参数为顺序表地址，要插入的元素地址，插入位置
int i;
TSeqList *temp = NULL;
//先作健壮性判断
if (list == NULL ||node == NULL) //如果顺序表为空，或者结点为空
{
return -1;
}
temp = (TSeqList *)list;
//如果顺序表已满
if (temp->length >= temp->capacity)
{
return -2;
}
//容错
if (pos > temp->length) //如果给出的pos在长度后，即中间有空余，
pos = temp->length; //就修正到最后一个元素后面
for (i = temp->length; i > pos; i--) //将插入位置的元素依次后移动
{
temp->node[i] = temp->node[i - 1];
}
temp->node[i] = (int)node; //然后在腾出的位置插入新元素结点
temp->length++; //插入成功后，长度加1
return 0;
}5、删除元素
从顺序表中删除某一个元素，则将元素删除后，需要将后面的元素依次向前移动来补齐空位，删除过程如图5所示。
图5 删除元素
删除过程相对来说没有插入过程那么复杂，不必考虑内存不足时的“溢出”问题，但因为要移动元素，效率还是较低的。其代码实现如下所示：
//删除元素
SeqList* SeqList_Delete(SeqList* list, int pos)
{
int i;
//先作健壮性判断
TSeqList * tlist = NULL;
SeqListNode * temp = NULL;
tlist = (TSeqList *)list;
if (list == NULL || pos < 0 || pos >= tlist->capacity)
{
printf("SeqList_Delete() error\n");
return NULL;
}
temp = (SeqListNode *)tlist->node[pos]; //要删除的元素
for (i = pos + 1; i < tlist->length; i++) //将删除元素位置后的所有元素向前移动
{
tlist->node[i - 1] = tlist->node[i];
}
tlist->length--; //删除元素后，长度要减
return temp;
}6、查找某个位置上的元素
在顺序表中查找某个元素是非常方便的，因为顺序表在底层是以数组来实现的，每个存储单元都有索引标注，要查找某个位置上的元素，直接按索引来查找就可以。
查找元素的代码实现如下所示：
SeqList* SeqList_Get(SeqList* list, int pos)
{
//先作健壮性判断
TSeqList * tlist = NULL;
SeqListNode * temp = NULL;
tlist = (TSeqList *)list;
if (list == NULL || pos < 0 || pos >= tlist->capacity)
{
printf("SeqList_Get() error\n");
return NULL;
}
temp = (SeqListNode *)tlist->node[pos]; //将表中pos位置的结点指针赋给temp
return temp;
}7、清空表
清空顺序表是将表中的内容全部置为0。其代码实现如下所示：
//清空顺序表
void SeqList_Clear(SeqList* list)
{
TSeqList *temp = NULL;
if (list == NULL)
{
return;
}
temp = (TSeqList *)list;
temp->length = 0;
memset(temp->node, 0, (temp->capacity * sizeof(void*))); //将顺序表全部归0
return;
}8、销毁表
销毁顺序表是将表整个销毁，无法再进行使用。其代码实现如下所示：
//销毁顺序表
void SeqList_Destory(SeqList* list)
{
TSeqList* temp = NULL;
if (list == NULL) //如果参数顺序表为空
{
return;
}
temp = (TSeqList *)list;
if (temp->node != NULL)
{
free(temp->node); //先释放头结点中的指针数组
}
free(temp); //再释放头结点
return;
}至此，已经实现了一个顺序表最基本的操作，可以完成简单的增删改查的功能。接下来可以用测试程序来测试一下这个顺序表的使用情况。
注意：本书同系列教材《C语言程序设计教程》、《C++程序设计教程》均使用Visual Studio2013来开发，同样，在本书中仍然使用Visual Studio2013作为数据结构的开发环境，关于Visual Studio2013的安装与使用，请参考《C语言程序设计教程》一书（传智播客高教产品研发部 著），本书不再重复叙述。
在上述讲解中，每一个函数都已实现，因此在本例中，只添加头文件SeqList.h与测试程序main.c两个文件，而函数实现代码的SeqList.c文件，本例中不再重复给出，具体如例1所示。
例1
SeqList.h //头文件
1 #ifndef _SEQLIST_H_
2 #define _SEQLIST_H_
3
4 typedef void SeqList;
5 typedef void SeqListNode;
6
7 SeqList* SeqList_Create(int capacity); //创建顺序表
8 void SeqList_Destory(SeqList* list); //销毁顺序表
9 void SeqList_Clear(SeqList* list); //清空线性表
10 int SeqList_Length(SeqList* list); //获取顺序表长度
11 int SeqList_Capacity(SeqList* list); //获取顺序表容量
12 int SeqList_Insert(SeqList* list, SeqListNode* node, int pos); //在pos位置插入元素
13 SeqList* SeqList_Get(SeqList* list, int pos); //获取pos位置上的元素
14 SeqList* SeqList_Delete(SeqList* list, int pos); //删除pos位置的元素
15
16 #endifmain.c //测试程序的文件
17 #include "SeqList.h"
18 #include <stdio.h>
19 #include <stdlib.h>
20
21 typedef struct _Teacher
22 {
23 char name[32];
24 int age;
25 }Teacher;
26
27 int main()
28 {
29 int ret = 0;
30 SeqList * list = NULL;
31 Teacher t1, t2, t3, t4, t5; //结点元素
32 t1.age = 31;
33 t2.age = 32;
34 t3.age = 33;
35 t4.age = 34;
36 t5.age = 35;
37 //创建结点
38 list = SeqList_Create(10); //创建顺序表
39
40 //插入结点
41 ret = SeqList_Insert(list, (SeqListNode*)&t1, 0); //位置0表示始终在头部插入
42 ret = SeqList_Insert(list, (SeqListNode*)&t2, 0);
43 ret = SeqList_Insert(list, (SeqListNode*)&t3, 0);
44 ret = SeqList_Insert(list, (SeqListNode*)&t4, 0);
45 ret = SeqList_Insert(list, (SeqListNode*)&t5, 0);
46
47 printf("顺序表容量：%d\n", SeqList_Capacity(list));
48 printf("顺序表长度：%d\n", SeqList_Length(list));
49
50 //遍历顺序表
51 printf("遍历顺序表：\n");
52 for (int i = 0; i < SeqList_Length(list); i++)
53 {
54 Teacher* temp = (Teacher*)SeqList_Get(list, i); //获取链表结点
55 if (temp == NULL)
56 {
57 printf("func SeqList_Get() error\n", ret);
58 return;
59 }
60
61 printf("age: %d\n", temp->age);
62 }
63
64 //销毁链表
65 printf("销毁顺序表时：\n");
66 while (SeqList_Length(list) > 0)
67 {
68 Teacher* temp = (Teacher *)SeqList_Delete(list, 0); //删除头部元素
69 if (temp == NULL)
70 {
71 printf("func SeqList_Get() error\n", ret);
72 return;
73 }
74
75 printf("age: %d\n", temp->age);
76 }
77 SeqList_Destory(list);
78
79 system("pause");
80 return 0;
81 }运行结果如图6所示。
图6 例1运行结果
由图6可知，例1中创建了一个容量为10的顺序表，并且存入了5个元素。在本例中，第21-25行代码定义了一个Teacher结构体，保存了Teacher的姓名和年龄；第31-36行代码创建了5个结点，并且为结点中的age赋值；第38行代码调用SeqList_Create()函数创建了一个顺序表，第41-45行代码将Teacher的5个结点插入到顺序表中，每次都从头部插入；第47-48行代码分别调用相应函数求算顺序表的容量和长度；第52-62行代码遍历顺序表中的元素并打印；第66-76行代码是逐一删除顺序表中的元素，并打印删除的元素；第77行代码将顺序表销毁。
通过本节的学习，读者应对线性表的顺序存储有了一定的掌握。其实它并不难，只要理清思路，代码便是手到擒来。
隐藏目录
