数据结构C语言版 线性表的动态分配顺序存储结构表示和实现文库.doc

/*数据结构C语言版 线性表的动态分配顺序存储结构表示和实现P22-26 编译环境：Dev-C+ 日期：2011年2月9日 */#include #include #include typedef int ElemType;/ 定义数据结构元素的数据类型#define LIST_INIT_SIZE 10/ 线性表存储空间的初始分配量#define LISTINCREMENT 5/ 线性表存储空间的分配增量/ 线性表的动态分配顺序存储结构typedef structElemType *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;elsereturn 0;/ 返回L中数据元素个数。int ListLength(SqList L)/ L.length刚好记录了当前顺序表的长度，直接返回return L.length;/ 用e返回L中第i个数据元素的值，第i个数据元素就是L. GetElem(SqList L,int i,ElemType *e)/ 首先进行异常处理if(i 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()的数据元素的位序。若这样的数据元素不存在，则返回值为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;elsereturn 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对应的元素并赋给pwhile(i L.length)return 0;else/*将该cur_e的前驱赋给*pre_e.对等式说明下：* 和 -是同优先级的，且它们的结合性是自右向左的，所以先p自减1，p指向其前驱，然后将p所指向的地址的内容赋给*pre_e。从这里要明白为什么用指针进行传值，我给你一个地址，你把内容放进去，然后我就知道其中的值了。这就是使用指针的用处。*/*pre_e = *-p;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)return0;else/*对这个等式说明下：* 和 -是同优先级的，且它们的结合性是自右向左的，所以先p自加1，然后将p所指向的地址的内容赋给*next_e*/*next_e = *+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).elem,(*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;/ 表长增1return 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;/ 被删除元素的值赋给eq = (*L).elem + (*L).length-1;/ 表尾元素的位置for(+p; p = q; +p)/ 被删除元素之后的元素左移*(p-1) = *p;(*L).length-;/ 表长减1return 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;elsereturn 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个数据元素赋给eGetElem(Lb, i, &e);/ La中不存在和e相同的元素,则插入之if( !LocateElem(*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);/ 创建空表LcLa_len = ListLength(La);Lb_len = ListLength(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空 则将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+;elsebreak;ListInsert(L, k, 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 += LISTINCREMENT;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).elem + (*L).length-1; p = q; -p)*(p+1) = *p;*q = e;(*L).length+;/长度加1return 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(!newbase)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).elem + (*L).length - 1;/ q指向最后一个元素for(+p; p = q; +p)*(p-1) = *p;/ 从第2个元素起，所有元素向前移动一个位置(*L).length-;/ 当前长度减1return 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;/ 被删除元素的值赋给e(*L).length-;/ 表长减1return 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; 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;/替换为ereturn 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 = 0; j (*L).length; j+)if(e = *(*L).elem+j)break;/ 将e插表中的第j+1个位置ListInsert(L, j+1, e);return 1;/按非升序建立n个元素的线性表。int CreatDescend(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 = 0;j = *(*L).elem + j)break;ListInsert(L, j + 1, e);return 1;/ 进行测试/ 数据元素判定函数(平方关系)int comp(ElemType c1, ElemType c2)if(c1 = c2*c2)return 1;elsereturn 0;/ ListTraverse()调用的函数(类型要一致)void visit(ElemType *c)printf(%d ,*c);/ ListTraverse()调用的另一函数(元素值加倍)void dbl(ElemType *c)*c *= 2;int main()SqList L;SqList La, Lb, Lc;ElemType e, e0, d;int i;int j, k, n;int a4 = 3, 5, 8, 11,b7 = 2, 6, 8, 9, 11, 15, 20;/ 初始化操作i = InitList(&L);printf(初始化L后：L.elem=%u L.length=%d L.listsize=%dnn,L.elem, L.length, L.listsize);/ 通过插入操作创建一个顺序表for(j=1;j=5;j+)ListInsert(&L, 1, j);printf(在L的表头依次插入15后：*L.elem=);for(j =1 ; j = 5; j+)printf(%d ,*(L.elem+j-1);printf(n);printf(L.elem=%u L.length=%d L.listsize=%dnn,L.elem, L.length, L.listsize);/ 判断顺序表是否为空表i = ListEmpty(L);printf(L是否空：i=%d(1:是 0:否)nn,i);/ 清空顺序表i = ClearList(&L);printf(清空L后：L.elem=%u L.length=%d L.listsize=%dnn,L.elem,L.length,L.listsize);i = ListEmpty(L);printf(L是否空：i=%d(1:是 0:否)nn,i);/ 再次通过插入操作创建一个新的顺序表for(j = 1; j = 10; j+)ListInsert(&L,j,j);printf(在L的表尾依次插入110后：*L.elem=);for(j = 1; j = 10; j+)printf(%d ,*(L.elem+j-1);printf(n);printf(L.elem=%u L.length=%d L.listsize=%dnn,L.elem, L.length, L.listsize);/ 插入一个数的操作ListInsert(&L, 1, 0);printf(在L的表头插入0后：*L.elem=);/ 求当前顺序表的长度,并打印顺序表, ListLength(L)返回元素个数for(j = 1; j = ListLength(L); j+)printf(%d ,*(L.elem+j-1);printf(n);printf(L.elem = %u(有可能改变) L.length = %d(改变)L.listsize = %d(改变)nn,L.elem, L.length, L.listsize);/ 取得顺序表的第5个数并用e返回GetElem(L, 5, &e);printf(第5个元素的值为：%dnn,e);/ 返回第一个与j满足关系compare的数据元素的位序/ 在这里举了两个例子，一个符合，一个不符合的for(j = 3; j = 4; j+)k = LocateElem(L, j, comp);if(k)printf(第%d个元素的值为%d的平方nn, k, j);elseprintf(没有值为%d的平方的元素nn, j);/ 求前驱的操作,在这里举了两个例子，一个符合，一个不符合的（即头）for(j = 1; j = 2; j+)GetElem(L, j, &e0);/ 把第j个数据赋给e0i = PriorElem(L,e0,&e);/ 求e0的前驱if(i = 0)printf(元素%d无前驱nn,e0);elseprintf(元素%d的前驱为：%dnn,e0,e);/ 求后继操作，在这里同样举了两个例子，一个符合，一个不符合的（即尾）for(j = ListLength(L)-1; j = k; j-)/ 删除第j个数据i = ListDelete(&L, j, &e);if(i = 0)printf(删除第%d个数据失败nn,j);elseprintf(删除的元素值为：%dnn,e);/ 对顺序表的所有元素调用函数visitprintf(依次输出L的元素：);ListTraverse(L,visit);/对顺序表的所有元素调用函数dblprintf(nL的元素值加倍后：);/ 依次对元素调用dbl()，元素值乘2ListTraverse(L,dbl);/ 显示链表ListTraverse(L,visit);printf(n);/ 销毁顺序表DestroyList(&L);printf(销毁L后：L.elem=%u L.length=%d L.listsize=%dnnn,L.elem,L.length,L.listsize);/ 创建两个表并进行合并i = InitList(&La);if(1 = i)for(j = 1; j = 5; j+)ListInsert(&La, j, j);printf(La= );ListTraverse(La, visit);InitList(&Lb);for(j = 1;j = 5; j+)i = ListInsert(&Lb, j, 2 * j);printf(Lb= );ListTraverse(Lb, visit);/ 将两个表进行合并。Union(&La, Lb);printf(La与Lb合并后新的La= );ListTraverse(La, visit);printf(n);InitList( &La );for(j = 1; j = 4; j+)ListInsert(&La, j, aj-1);printf(La= );ListTraverse(La, visit);InitList( &Lb );for(j = 1; j 2): );scanf(%d,&n);CreatDescend(&L,n);printf(依次输出L的元素：);ListTraverse(L,visit);printf(n);/ 按非升序插入元素10InsertDescend(&L,10);printf(按非升序插入元素10后，线性表L为：);ListTraverse(L,visit);printf(n);printf(请输入要删除的元素的值: );scanf(%d,&e);i = DeleteElem(&L,e);if(i)printf(成功删除%dn,e);elseprintf(不存在元素%d!n,e);printf(线性表L为：);ListTraverse(L,vis