清华严蔚敏《数据结构》的全部代码实现C语言

1/*c1.h(程序名)*/#includestring.h#includectype.h#includemalloc.h/*malloc()等*/#includelimits.h/*INT_MAX等*/#includestdio.h/*EOF(=^Z或F6),NULL*/#includestdlib.h/*atoi()*/#includeio.h/*eof()*/#includemath.h/*floor(),ceil(),abs()*/#includeprocess.h/*exit()*//*函数结果状态代码*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/*#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码，如OK等*/typedefintBoolean;/*Boolean是布尔类型,其值是TRUE或FALSE*/2/*algo2-1.c实现算法2.1的程序*/#includec1.htypedefintElemType;#includec2-1.h/*c2-1.h线性表的动态分配顺序存储结构*/#defineLIST_INIT_SIZE10/*线性表存储空间的初始分配量*/#defineLISTINCREMENT2/*线性表存储空间的分配增量*/typedefstruct{ElemType*elem;/*存储空间基址*/intlength;/*当前长度*/intlistsize;/*当前分配的存储容量(以sizeof(ElemType)为单位)*/}SqList;#includebo2-1.c/*bo2-1.c顺序表示的线性表(存储结构由c2-1.h定义)的基本操作(12个)*/StatusInitList(SqList*L)/*算法2.3*/{/*操作结果：构造一个空的顺序线性表*/(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!(*L).elem)exit(OVERFLOW);/*存储分配失败*/(*L).length=0;/*空表长度为0*/(*L).listsize=LIST_INIT_SIZE;/*初始存储容量*/returnOK;}StatusDestroyList(SqList*L){/*初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L*/free((*L).elem);(*L).elem=NULL;(*L).length=0;(*L).listsize=0;returnOK;}StatusClearList(SqList*L){/*初始条件：顺序线性表L已存在。操作结果：将L重置为空表*/(*L).length=0;returnOK;}StatusListEmpty(SqListL)3{/*初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE*/if(L.length==0)returnTRUE;elsereturnFALSE;}intListLength(SqListL){/*初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数*/returnL.length;}StatusGetElem(SqListL,inti,ElemType*e){/*初始条件：顺序线性表L已存在，1≤i≤ListLength(L)*//*操作结果：用e返回L中第i个数据元素的值*/if(i1||iL.length)exit(ERROR);*e=*(L.elem+i-1);returnOK;}intLocateElem(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){/*初始条件：顺序线性表L已存在，compare()是数据元素判定函数(满足为1,否则为0)*//*操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。*//*若这样的数据元素不存在，则返回值为0。算法2.6*/ElemType*p;inti=1;/*i的初值为第1个元素的位序*/p=L.elem;/*p的初值为第1个元素的存储位置*/while(i=L.length&&!compare(*p++,e))++i;if(i=L.length)returni;elsereturn0;}StatusPriorElem(SqListL,ElemTypecur_e,ElemType*pre_e){/*初始条件：顺序线性表L已存在*//*操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，*//*否则操作失败，pre_e无定义*/inti=2;ElemType*p=L.elem+1;while(i=L.length&&*p!=cur_e)4{p++;i++;}if(iL.length)returnINFEASIBLE;else{*pre_e=*--p;returnOK;}}StatusNextElem(SqListL,ElemTypecur_e,ElemType*next_e){/*初始条件：顺序线性表L已存在*//*操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，*//*否则操作失败，next_e无定义*/inti=1;ElemType*p=L.elem;while(iL.length&&*p!=cur_e){i++;p++;}if(i==L.length)returnINFEASIBLE;else{*next_e=*++p;returnOK;}}StatusListInsert(SqList*L,inti,ElemTypee)/*算法2.4*/{/*初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1*//*操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1*/ElemType*newbase,*q,*p;if(i1||i(*L).length+1)/*i值不合法*/returnERROR;if((*L).length=(*L).listsize)/*当前存储空间已满,增加分配*/{newbase=(ElemType*)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));5if(!newbase)exit(OVERFLOW);/*存储分配失败*/(*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*/returnOK;}StatusListDelete(SqList*L,inti,ElemType*e)/*算法2.5*/{/*初始条件：顺序线性表L已存在，1≤i≤ListLength(L)*//*操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1*/ElemType*p,*q;if(i1||i(*L).length)/*i值不合法*/returnERROR;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--;/*表长减1*/returnOK;}StatusListTraverse(SqListL,void(*vi)(ElemType*)){/*初始条件：顺序线性表L已存在*//*操作结果：依次对L的每个数据元素调用函数vi()。一旦vi()失败，则操作失败*//*vi()的形参加'&'，表明可通过调用vi()改变元素的值*/ElemType*p;inti;p=L.elem;for(i=1;i=L.length;i++)vi(p++);printf(\n);returnOK;}Statusequal(ElemTypec1,ElemTypec2){/*判断是否相等的函数，Union()用到*/if(c1==c2)6returnTRUE;elsereturnFALSE;}voidUnion(SqList*La,SqListLb)/*算法2.1*/{/*将所有在线性表Lb中但不在La中的数据元素插入到La中*/ElemTypee;intLa_len,Lb_len;inti;La_len=ListLength(*La);/*求线性表的长度*/Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i++){GetElem(Lb,i,&e);/*取Lb中第i个数据元素赋给e*/if(!LocateElem(*La,e,equal))/*La中不存在和e相同的元素,则插入之*/ListInsert(La,++La_len,e);}}voidprint(ElemType*c){printf(%d,*c);}voidmain(){SqListLa,Lb;Statusi;intj;i=InitList(&La);if(i==1)/*创建空表La成功*/for(j=1;j=5;j++)/*在表La中插入5个元素*/i=ListInsert(&La,j,j);printf(La=);/*输出表La的内容*/ListTraverse(La,print);InitList(&Lb);/*也可不判断是否创建成功*/for(j=1;j=5;j++)/*在表Lb中插入5个元素*/i=ListInsert(&Lb,j,2*j);printf(Lb=);/*输出表Lb的内容*/ListTraverse(Lb,print);Union(&La,Lb);printf(newLa=);/*输出新表La的内容*/ListTraverse(La,print);}7/*algo2-2.c实现算法2.2的程序*/#includec1.htypedefintElemType;#includec2-1.h#includebo2-1.cvoidMergeList(SqListLa,SqListLb,SqList*Lc)/*算法2.2*/{/*已知线性表La和Lb中的数据元素按值非递减排列。*//*归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列*/inti=1,j=1,k=0;intLa_len,Lb_len;ElemTypeai,bj;InitList(Lc);/*创建空表Lc*/La_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){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}while(i=La_len)/*表La非空且表Lb空*/{GetElem(La,i++,&ai);ListInsert(Lc,++k,ai);}while(j=Lb_len)/*表Lb非空且表La空*/{GetElem(Lb,j++,&bj);ListInsert(Lc,++k,bj