顺序线性表的抽象数据模型
ADT {
数据对象：ElemType型数据集合，此处假设为int
数据关系：每个元素有一个前驱和一个后驱，第一个元素只有后驱，最后一个元素只有前驱
基本操作：
- 初始 init_sqlist： 构造一个空的线性表
- 销毁 destroy_sqlist： 释放动态分布给线性表的内存
- 清空 clear_sqlist： 将线性表重置为空表
- 查空 is_empty： 检验线性表是否为空表
- 查长 length_sqlist： 获取线性表长度
- 提取 get_sqlist： 提取线性表的第i个元素
- 插入 insert_sqlist： 在线性表第i个位置插入新元素
- 删除 delete_sqlist： 删除线性表第i个元素并返回其值
- 查找 locate_sqlist： 获取满足一定条件的元素在线性表中的位置
- 前驱 prior_sqlist： 获取元素在线性表中的前驱
- 后驱 next_sqlist： 获取元素在线性表中的后驱
- 遍历 traverse_sqlist：用某个visit函数遍历线性表
}在具体实现中，我们将创建三个文件：
sqlist.h：头文件，宏定义，定义数据类型，声明操作函数。sqlist.c：源文件，定义操作函数。main.c：主函数，测试该数据类型的实现。
在头文件中，定义如下宏：
"sqlist.h"
#include <stdlib.h>
#include <stdbool.h>
#define LIST_INIT_SIZE 100 // 线性表初始存储空间
#define LIST_INCREMENT 10 // 当线性表容量不足时，增加的额外容量
#define OVERFLOW false // 内存溢出定义数据类型
数据类型在头文件中定义。首先要注意的是，写头文件时应该加上这样的语句：
"sqlist.h"
#ifndef SQLIST
#define SQLIST
/*... 主体内容 ...*/
#endif这些语句的作用是防止宏的重复定义和函数的重复声明。另外，类型定义typedef的重复在C中是被禁止的。
假定数据类型是ElemType，则顺序线性表可以定义为一个结构体：
"sqlist.h"
typedef int ElemType; // 线性表元素数据类型，这里定为int
typedef struct tagSqList {
ElemType *elem; // 指向存储空间基地址的指针
int length; // 当前顺序表长度
int listsize; // 当前分配的存储容量(元素个数)
} SqList;这里值得注意的是tagSqList，它在声明结构体中暂时给后面的结构体一个标签，然后再在类型定义中将SqList定义为struct tagSqList这样的类型。如果没有tagSqList，编译器将报错。
声明为SqList类型的变量L将是一个结构体，包含了存储空间基地址指针、当前顺序表长度、当前分配的存储容量这三个成员。
对于结构体L，获取元素的方法是用 . 运算符：用L.length获得顺序表长度值。
对于指向结构体L的指针pL，获取元素的方法是用->运算符：用L->length获得顺序表长度值。
定义抽象数据操作
下面的操作函数将在头文件sqlist.h中声明，在sqlist.c中定义。
下面的大多数操作都将通过指针的方式传入线性表和获得元素值。使用指针的好处是：
- 传入：让函数可以直接在原来的线性表上进行操作，节省制作副本的空间；
- 传出：函数可以输出关于运行成功与否的信息。记住，C中的函数只能输出一个值。
初始化
初始化一个线性表为空表。传入一个已声明的线性表指针，为其数组分配空间，初始化其长度和容量。若运行成功，返回一个真值。
"sqlist.c"
bool init_sqlist(SqList *L)
{
L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L->elem) exit(OVERFLOW); // 存储分配失败
L->length = 0; // 空表长度为0
L->listsize = LIST_INIT_SIZE; // 初始存储容量
return true;
}这里要特别注意malloc的用法。malloc将分配一块指定大小的连续内存空间，并返回指向其起始地址的一个通用指针void *。接着，(ElemType *)将该指针类型强制转换。最后，L->elem是指向存储空间基址的指针，通过赋值语句将这个指针指向所分配的空间。这片空间的大小等于表初始大小（以元素个数为单位）乘以每个元素的大小（sizeof(ElemType)）。
销毁
销毁线性表操作的核心是释放动态分布的内存。非动态分布的内存无需考虑。
"sqlist.c"
bool destroy_sqlist(SqList *L)
{
if (L->elem) {
free(L->elem);
L->elem = NULL;
return true;
}
}这里的重点是将存储空间基址的指针设置为空指针NULL。“野指针”会留下很大后患。
free()函数用来释放一片动态分布的存储空间，应该传入指向该存储空间的指针。
清空
清空线性表的核心是将其长度设置为0。事实上，这是足够的。超出线性表长度的（原）内容可被视为内存空间上“随机内容”，会被其它所有操作忽视。
"sqlist.c"
bool clear_sqlist(SqList *L)
{
if (L->length) {
L->length = 0;
}
}查空
若线性表为空，返回真值。
"sqlist.c"
bool is_empty(SqList *L)
{
if (L->length == 0) return true;
else return false;
}查长
获取线性表的长度。
sqlist.c
int length_sqlist(SqList *L)
{
return L->length;
}提取
获得线性表L中第i个元素的值，并用e返回。
"sqlist.c"
bool get_sqlist(SqList *L, int i, ElemType *e)
{
if (i < 1 || i > L->length) return false;
*e = L->elem[i-1];
return true;
}此处要注意的是，线性表的是从1开始数的，而数组是从0开始数的。
第二个需要注意的地方是，本操作需要传入一个ElemType *指针来获得想要的值。在实际操作中，可以这样：
ElemType e5; \\ 想要获得第五个元素
get_sqlist(&L, 5, &e5);
printf("Fifth element: %d", e5);插入
在线性表L中第i个位置插入新的元素e。原来从i到最后一位的元素往后顺延一位。
"sqlist.c"
bool insert_sqlist(SqList *L, int i, ElemType e)
{
ElemType *insert_pos, *end_pos, *p;
if (i < 1 || i > L->length+1) return false; // i值不合法
if (L->length >= L->listsize) allocate_sqlist(L); // 当前存储空间已满，增加分配
insert_pos = &(L->elem[i-1]); // 线性表要插入的位置
end_pos = &(L->elem[L->length-1]); // 线性表末尾的位置
for (p = end_pos; p >= insert_pos; p--)
*(p+1) = *p;
*insert_pos = e; // 插入e
L->length++; // 长度增加1
return true;
}注意，当前存储空间已满时，会通过一个allocate_sqlit(L)函数分配更多空间。此处L是指向线性表的指针。下面是该函数的定义。
"sqlist.c"
// 增加存储空间
bool allocate_sqlist(SqList *L)
{
ElemType *newbase;
newbase = (ElemType *)realloc(L->elem, (L->listsize + LIST_INCREMENT) * sizeof(ElemType));
if (!newbase) exit(OVERFLOW); // 存储分配失败
L->elem = newbase; // 若成功，给顺序表分配新基址（数组名可以作储存空间指针）
L->listsize += LIST_INCREMENT; // 增加存储容量
return true;
}注意，由于该函数只是辅助性的，不应该被外部获取，所以不将它放在头文件中。与此相应的，要在sqlist.c文件开头声明函数原型。
可以看到，重置动态内存的函数realloc和malloc相似，但要先传入一个指向已动态分配空间的指针。
删除
在线性表中删除第i个元素，并用e返回其真值。此操作依然需要在删除后把i后面的所有元素往前移动。
"sqlist.c"
bool delete_sqlist(SqList *L, int i, ElemType *e)
{
ElemType *del_pos, *end_pos, *p;
if (i < 1 || i > L->length) return false; // i值不合法
del_pos = &(L->elem[i-1]); // 被删除元素的位置
end_pos = &(L->elem[L->length-1]); // 表尾元素的位置
*e = *del_pos; // 将被删除元素的值赋给e
p = del_pos + 1; // 将指针指向被删除元素的后一个
for (p; p <= end_pos; p++)
*(p-1) = *p; // 被删除元素之后的元素左移
L->length--; // 表长减一
return true;
}查找
在顺序表中查找第一个与e满足compare()关系的元素的为序。
"sqlist.c"
int locate_sqlist(SqList *L, ElemType e, bool (* compare)(ElemType, ElemType))
{
int i = 1;
ElemType *p;
p = &(L->elem[0]); // p 指向第一个元素的位置
while (i <= L->length && !(*compare)(*p, e)) { // 当i在长度以内，以及不符合条件
i++; // 增加次序
p++; // 指向下一个
}
if (i <= L->length) return i;
else return -1; // 若不存在
}此处最重要的是传入一个指向compare()函数的指针。其形式参数应该如下格式：
返回类型 (* 函数名)(传入类型);其实际参数可以直接用函数名传入：
locate_sqlist(&L, e, compare);此处将会用的compare()比较函数的将定义在main.c里，这样可以保证程序的可移植，对于使用sqlist.h的不同源文件可以定制不同的比较函数。
"main.c"
bool equal(int e1, int e2)
{
if (e1 == e2) return true;
else return false;
}前驱
返回某个元素cur_e在线性表中的前驱，同样，用一个指针返回结果。
"sqlist.c"
bool prior_sqlist(SqList *L, ElemType cur_e, ElemType *pre_e)
{
int i;
if (L->elem[0] == cur_e) return false;
for (i = 1; i < L->length; i++) {
if (L->elem[i] == cur_e) {
*pre_e = L->elem[i-1];
return true;
}
}
return false;
}后驱
返回某个元素cur_e在线性表中的后驱，用一个指针返回。
"sqlist.c"
bool next_sqlist(SqList *L, ElemType cur_e, ElemType *next_e)
{
int i;
if (L->elem[L->length-1] == cur_e) return false;
for (i = 0; i < L->length-1; i++) {
if (L->elem[i] == cur_e) {
*next_e = L->elem[i+1];
return true;
}
}
return false;
}遍历
用一个visit函数遍历线性表内的元素，同样，函数通过指针传入。
"sqlist.c"
bool traverse_sqlist(SqList *L, bool (*visit)(ElemType))
{
int i;
if (L->length <= 0) return false;
for (i = 0; i < L->length; i++) {
if (!visit(L->elem[i])) return false;
}
return true;
}同样，visit将定义在main.c中。此处的例子中，visit将打印遇到的线性表元素值。
"main.c"
bool visit(int e)
{
if (!printf("%d\n", e)) return false;
else return true;
}填充
此操作不属于上面列出的抽象数据类型操作，本质上是重复使用插入操作，但定义此操作可以带来很多方便。这个操作接受一个数组，把它的元素填充到线性表中。
"sqlist.c"
bool populate_sqlist(SqList *L, int size, ElemType inputs[size])
{
for (int i = 0; i < size; i++) {
insert_sqlist(L, i+1, inputs[i]);
}
return true;
}测试
我们的测试用例写在main.c中。
#include <stdio.h>
#include "sqlist.h" //将头文件typedef定义为int
bool visit(int e);
bool equal(int e1, int e2);
int main(void)
{
SqList num_list;
// 初始化顺序线性表
init_sqlist(&num_list);
// 插入10-20
for (int i = 1; i <= 10; i++) {
insert_sqlist(&num_list, i, i*20);
}
// 查表的长度
printf("Length: %d\n", length_sqlist(&num_list));
// 提取第五个元素
int five_elem;
get_sqlist(&num_list, 5, &five_elem);
printf("5th elem: %d\n", five_elem);
// 插入99到第五位
insert_sqlist(&num_list, 5, 99);
// 删除第2个元素
int deleted_e;
delete_sqlist(&num_list, 2, &deleted_e);
printf("deleted 2nd elem: %d\n", deleted_e);
// 查找等于120的元素
int find_pos;
find_pos = locate_sqlist(&num_list, 120, equal);
printf("Found at: %d\n", find_pos);
// 100的前驱
int pre_e;
prior_sqlist(&num_list, 100, &pre_e);
printf("Predecessor: %d\n", pre_e);
//160的后驱
int next_e;
next_sqlist(&num_list, 160, &next_e);
printf("Successor: %d\n", next_e);
// 打印整个表格
printf("Print the list: \n");
traverse_sqlist(&num_list, visit);
printf("----End of Print----\n");
// 清空表
clear_sqlist(&num_list);
printf("----cleared----\n");
printf("Print the list: \n");
traverse_sqlist(&num_list, visit);
printf("----End of Print----\n");
// 导入数组
int new_list[6] = {1, 2, 3, 4, 5, 6};
populate_sqlist(&num_list, 6, new_list);
printf("Print the list: \n");
traverse_sqlist(&num_list, visit);
printf("----End of Print----\n");
// 销毁表
destroy_sqlist(&num_list);
if (!num_list.elem)
printf("Destroyed");
return 0;
}
// visit 与 compare 的定义见上文。在终端中，使用如下命令编译文件。
gcc -o sqlist main.c sqlist.c sqlist.h运行结果如下：
Length: 10
5th elem: 100
deleted 2nd elem: 40
Found at: 6
Predecessor: 99
Successor: 180
Print the list:
20
60
80
99
100
120
140
160
180
200
----End of Print----
----cleared----
Print the list:
----End of Print----
Print the list:
1
2
3
4
5
6
----End of Print----
Destroyed