1、数据结构C语言版线性表的动态分配顺序存储结构表示和实现文库/* 数据结构C语言版 线性表的动态分配顺序存储结构表示和实现 编译环境：Dev-C+ */#include #include #include typedef int ElemType; / 定义数据结构元素的数据类型#define LIST_INIT_SIZE 10 / 线性表存储空间的初始分配量#define LISTINCREMENT 5 / 线性表存储空间的分配增量/ 线性表的动态分配顺序存储结构typedef struct ElemType *elem; / 存储空间基址 int length; / 当前长度 int lis
2、tsize; / 当前分配的存储容量(以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_IN
3、IT_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。 如何判断是否为空表呢？结构体中已经包含一个可以说明的
4、元素， 那就是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.elemi-1。int GetElem(SqList L,int i,ElemType *e) / 首先进行异常处理 if(i
5、L.length) exit(0); /* 注意顺序表基址L.elem0 表示第一个数，而第i个数则是用 基址L.elem + i - 1来表示,也可以用L.elemi-1表示。为什么 可以那样表示呢？因为l.elem是基地址，相当于数组头一样，指 示了一个首地址，然后对地址进行加减，形成不同元素的地址。 *是取地址所指的内容，所以*(L.elem+i-1)就是第i个数据的值了。 */ *e = *(L.elem + i - 1); / *e = L.elemi-1; return 1;/* 算法2.6，P26 返回L中第1个与e满足关系compare()的数据元素的位序。 若这样的数据元素不
6、存在，则返回值为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的元素按
7、值非递减排列。归并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
8、.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均非空 */ /* 归
9、并 */ 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, Elem
10、Type *pre_e) int i = 2; / 因为第一个数据元素无前继，从第二个数据元素开始 ElemType *p = L.elem + 1; / 找到该cur_e对应的元素并赋给p while(i L.length) return 0; else /* 将该cur_e的前驱赋给*pre_e. 对等式说明下：* 和 -是同优先级的，且它们的结合性是自右 向左的，所以先p自减1，p指向其前驱，然后将p所指向的地址 的内容赋给*pre_e。从这里要明白为什么用指针进行传值，我 给你一个地址，你把内容放进去，然后我就知道其中的值了。 这就是使用指针的用处。 */ *pre_e = *-p;
11、return 1; /* 若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继,否 则返回0*/int NextElem(SqList L,ElemType cur_e,ElemType *next_e) int i = 1; ElemType *p = L.elem; while(i L.length & *p != cur_e) i+; p+; if(i = L.length) return 0; else /* 对这个等式说明下：* 和 -是同优先级的，且它们的结合性 是自右向左的，所以先p自加1，然后将p所指向的地址的内容 赋给*next_e */ *next_e
12、= *+p; return 1; / 算法2.4 P24/ 在L中第i个位置之前插入新的数据元素e，L的长度加1.int ListInsert(SqList *L,int i,ElemType e) ElemType *newbase, *q, *p; / 输入的i不合法 if(i (*L).length + 1) return 0; / 当前存储空间已满,增加分配 if( (*L).length = (*L).listsize) / realloc改变(*L).elem所指内存的大小，原始所指内存中的 / 数据不变。 newbase = (ElemType *)realloc(*L).ele
13、m, (*L).listsize + LISTINCREMENT) * sizeof(ElemType); if( !newbase ) exit(0); (*L).elem = newbase; / 新基址 (*L).listsize += LISTINCREMENT; / 增加存储容量 / 指定插入的位置 q = (*L).elem + i - 1; / q之后的元素右移一步，以腾出位置 for(p = (*L).elem + (*L).length - 1; p = q; -p) *(p+1) = *p; *q = e; / 插入e +(*L).length; / 表长增1 return
14、 1;/* 算法2.5 P25 删除L的第i个数据元素，并用e返回其值，L的长度减1.*/int ListDelete(SqList *L,int i,ElemType *e) ElemType *p,*q; / i值不合法 if( i (*L).length) return 0; p = (*L).elem + i - 1; / p为被删除元素的位置 *e = *p; / 被删除元素的值赋给e q = (*L).elem + (*L).length-1; / 表尾元素的位置 for(+p; p = q; +p) / 被删除元素之后的元素左移 *(p-1) = *p; (*L).length-
15、; / 表长减1 return 1;/ 依次对L的每个数据元素调用函数vi()。int ListTraverse(SqList L, void( *vi )(ElemType* ) ElemType *p; int i; p = L.elem; / 对顺序表中的每一元素调用函数vi() for(i = 1; i = L.length; i+) vi(p+); printf(n); return 1;/ 判断两元素的值是否相等的函数，Union()用到，相等返回1，不相等返回0int equal(ElemType c1,ElemType c2) if(c1 = c2) return 1; els
16、e return 0;/* 算法2.1 P20 将所有在线性表Lb中但不在La中的数据元素插入到La中。*/void Union(SqList *La, SqList Lb) ElemType e; int La_len, Lb_len; int i; La_len = ListLength(*La); Lb_len = ListLength(Lb); / 依次对Lb中的元素与La的所有元素进行比较 for(i = 1; i = Lb_len; i+) / 取Lb中第i个数据元素赋给e GetElem(Lb, i, &e); / La中不存在和e相同的元素,则插入之 if( !LocateEl
17、em(*La, e, equal) ) ListInsert(La, +La_len, e); /* 算法2.2。P21 已知线性表La和Lb中的数据元素按值非递减排列。归并La和Lb得到新 的线性表Lc,Lc的数据元素也按值非递减排列。*/void MergeList(SqList La, SqList Lb, SqList *Lc) int i = 1, j = 1, k = 0; int La_len, Lb_len; ElemType ai, bj; InitList(Lc); / 创建空表Lc La_len = ListLength(La); Lb_len = ListLength(
18、Lb); while(i = La_len & j = Lb_len) / 表La和表Lb均非空 GetElem(La, i, &ai); GetElem(Lb, j, &bj); if(ai = bj) / ai更小将ai插入Lc中 ListInsert(Lc, +k, ai); +i; else / bj更小将bj插入Lc中 ListInsert(Lc, +k, bj); +j; / 表La非空且表Lb空则将La的剩余部分接到Lc中 while(i = La_len) GetElem(La, i+, &ai); ListInsert(Lc, +k, ai); / 表Lb非空且表La空 则将
19、Lb的剩余部分接到Lc中 while(j = (*L).listsize ) / 当前存储空间已满,增加分配 newbase = (ElemType *)realloc(*L).elem, (*L).listsize + LISTINCREMENT) * sizeof(ElemType); if( !newbase ) exit(0); (*L).elem = newbase; (*L).listsize += LISTINCREMENT; p = (*L).elem; / 中介，做对比用的。 for(k = 1; k *p) p+; else break; ListInsert(L, k,
20、e);/ 在L中按非升序插入新的数据元素e，L的长度加1。void InsertDescend(SqList *L,ElemType e) ElemType *newbase, *p; int k; / k为e要插入的位置 if(*L).length = (*L).listsize) newbase = (ElemType *)realloc( (*L).elem, (*L).listsize + LISTINCREMENT) * sizeof(ElemType); if( !newbase ) exit(0); (*L).elem = newbase; (*L).listsize += LI
21、STINCREMENT; p = (*L).elem; for(k = 1; k = (*L).length; k+) if(e = (*L).listsize ) newbase = (ElemType *)realloc(*L).elem, (*L).listsize + LISTINCREMENT) * sizeof(ElemType); if( !newbase ) exit(0); (*L).elem = newbase; (*L).listsize += LISTINCREMENT; q = (*L).elem; / 从表头至表尾的元素依次向后移动一位 for(p = (*L).e
22、lem + (*L).length-1; p = q; -p) *(p+1) = *p; *q = e; (*L).length+; /长度加1 return 1;/ 在L的尾部插入新的数据元素e，L的长度加1。int EndInsert(SqList *L, ElemType e) ElemType *q, *newbase; if( (*L).length = (*L).listsize) newbase = (ElemType *)realloc(*L).elem, (*L).listsize + LISTINCREMENT) * sizeof(ElemType); if(!newbas
23、e) exit(0); (*L).elem = newbase; (*L).listsize += LISTINCREMENT; q = (*L).elem+(*L).length; / q为插入位置 *q = e; (*L).length+; return 1;/ 删除L的第一个数据元素，并由e返回其值，L的长度减1。int DeleteFirst(SqList *L,ElemType *e) ElemType *p, *q; if( ListEmpty(*L) ) / 空表无法删除 return 0; p = (*L).elem; / p指向第一个元素 *e = *p; q = (*L).
24、elem + (*L).length - 1; / q指向最后一个元素 for(+p; p = q; +p) *(p-1) = *p; / 从第2个元素起，所有元素向前移动一个位置 (*L).length-; / 当前长度减1 return 1;/ 删除L的最后一个数据元素，并用e返回其值，L的长度减1 。int DeleteTail(SqList *L,ElemType *e) ElemType *p; if( !(*L).length ) / 空表 return 0; p = (*L).elem + (*L).length - 1; / 最后一个数据元素的位置 *e = *p; / 被删除
25、元素的值赋给e (*L).length-; / 表长减1 return 1;/ 删除表中值为e的元素，并返回1；如无此元素，则返回0int DeleteElem(SqList *L, ElemType e) int i = 0, / 记录与e值相同的元素的位置 j; / 先判断i的位置是否越界，然后将e与顺序表的每一个元素相比较， / 直到找到 while(i (*L).length & e != *(*L).elem + i) i+; if(i = (*L).length) / 没找到 return 0; else / 后面的元素依次前移 for(j = i; j (*L).length;
26、j+) *(*L).elem + j) = *(*L).elem + j + 1); (*L).length-; return 1; / 用e取代表L中第i个元素的值。int ReplaceElem(SqList L, int i, ElemType e) if(i L.length) / i值不合法 exit(0); *(L.elem + i - 1) = e; /替换为e return 1;/ 按非降序建立n个元素的线性表。int CreatAscend(SqList *L, int n) int i, j; /记录数据要插入的位置 ElemType e; InitList(L); printf(请输入%d个元素:（空格）n,n); scanf(%d, &e); ListInsert(L, 1, e); / 在空表中插入第1个元素 for(i = 1; i n; i+) scanf(%d,&e); /将待插入的数据与顺序表的每一个元素比较 /比期中一个小的话则退出循环 for(j
