/*
数据结构C语言版 线性表的动态分配顺序存储结构表示和实现 编译环境：Dev-C++ */
#include
typedef int ElemType; // 定义数据结构元素的数据类型
#define LIST_INIT_SIZE 10 // 线性表存储空间的初始分配量 #define LISTINCREMENT 5 // 线性表存储空间的分配增量
// 线性表的动态分配顺序存储结构 typedef struct {
ElemType *elem; // 存储空间基址 int length; // 当前长度
int listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位) }SqList;
// 算法2.3，P23
// 构造一个空的顺序线性表即对顺序表结构体中的所有元素 // 进行初始化。
int InitList(SqList *L) {
// 分配指定大小的存储空间给顺序表
(*L).elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if( !(*L).elem ) // 存储分配失败 exit(0);
(*L).length = 0; // 当前长度初始化为0 // 指定分配的存储容量
(*L).listsize = LIST_INIT_SIZE;
return 1; }
// 销毁顺序线性表L即将顺序表结构体中的所有成员销毁（空间释放， // 数值置0）。
int DestroyList(SqList *L) {
// 先释放空间，然后置空 free( (*L).elem );
(*L).elem = NULL;
(*L).length = 0; (*L).listsize = 0;
return 1; }
// 将L重置为空表（当前长度为0即是空表）。 int ClearList(SqList *L) {
(*L).length = 0;
return 1; } /*
若L为空表，则返回1，否则返回0。
如何判断是否为空表呢？结构体中已经包含一个可以说明的元素， 那就是length，表示当前顺序表的长度，根据当前的长度就可以 判断了，为0就是空表，不为0就不是空表了。 */
int ListEmpty(SqList L) {
if(0 == L.length) return 1; else
return 0; }
// 返回L中数据元素个数。 int ListLength(SqList L) {
// L.length刚好记录了当前顺序表的长度，直接返回 return L.length; }
// 用e返回L中第i个数据元素的值，第i个数据元素就是L.elem[i-1]。 int GetElem(SqList L,int i,ElemType *e) {
// 首先进行异常处理
if(i < 1 || i > L.length) exit(0);
/*
注意顺序表基址L.elem[0] 表示第一个数，而第i个数则是用 基址L.elem + i - 1来表示,也可以用L.elem[i-1]表示。为什么 可以那样表示呢？因为l.elem是基地址，相当于数组头一样，指 示了一个首地址，然后对地址进行加减，形成不同元素的地址。 *是取地址所指的内容，所以*(L.elem+i-1)就是第i个数据的值了。 */
*e = *(L.elem + i - 1); // *e = L.elem[i-1];
return 1; }
/* 算法2.6，P26
返回L中第1个与e满足关系compare()的数据元素的位序。 若这样的数据元素不存在，则返回值为0。 */
int LocateElem(SqList L,ElemType e,
int(* compare)( ElemType, ElemType)) {
ElemType *p;
int i = 1; // i的初值为第1个元素的位序
p = L.elem; // p的初值为第1个元素的存储位置即地址
// 循环比较，直到找到符合关系的元素
while(i <= L.length && !compare(*p++, e) ) ++i;
if(i <= L.length) return i; else
return 0; }
#if 0
/* 算法2.7 与算法2.2区别
已知顺序线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的顺序 线性表Lc,Lc的元素也按值非递减排列。
算法的时间复杂度为O(La.length + Lb.length). */
void MergeList(SqList La, SqList Lb, SqList *Lc) {
ElemType *pa, *pa_last, *pb, *pb_last, *pc;
pa = La.elem; //pa指向线性表La的头结点
pb = Lb.elem; //pb指向线性表Lb的头结点 /* 不用InitList()创建空表Lc */
(*Lc).listsize = (*Lc).length = La.length + Lb.length; // pc指向线性表Lc的头结点 pc = (*Lc).elem =
(ElemType *)malloc((*Lc).listsize*sizeof(ElemType)); if( !(*Lc).elem ) /* 存储分配失败 */ exit(0);
pa_last = La.elem + La.length - 1; //pa_last指向线性表La的尾结点 pb_last = Lb.elem + Lb.length - 1; //pb_last指向线性表Lb的尾结点 while(pa <= pa_last && pb <= pb_last) /* 表La和表Lb均非空 */ { /* 归并 */
if(*pa <= *pb) //*pa更小接到pc后 *pc++ = *pa++;
else //*pb更小接到pc后 *pc++ = *pb++; }
while(pa <= pa_last) /* 表La非空且表Lb空 */ *pc++ = *pa++; /* 插入La的剩余元素 */ while(pb <= pb_last) /* 表Lb非空且表La空 */ *pc++ = *pb++; /* 插入Lb的剩余元素 */ }
#endif
// 若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否 // 则返回0。
int PriorElem(SqList L, ElemType cur_e, ElemType *pre_e) {
int i = 2;
// 因为第一个数据元素无前继，从第二个数据元素开始 ElemType *p = L.elem + 1;
// 找到该cur_e对应的元素并赋给p while(i <= L.length && *p != cur_e) {
p++; i++; }
if(i > L.length) return 0; else {
/*
将该cur_e的前驱赋给*pre_e.