清华严蔚敏《数据结构》的全部代码实现C语言.docx
- 文档编号:10551069
- 上传时间:2023-05-26
- 格式:DOCX
- 页数:107
- 大小:43.03KB
清华严蔚敏《数据结构》的全部代码实现C语言.docx
《清华严蔚敏《数据结构》的全部代码实现C语言.docx》由会员分享,可在线阅读,更多相关《清华严蔚敏《数据结构》的全部代码实现C语言.docx(107页珍藏版)》请在冰点文库上搜索。
清华严蔚敏数据结构的全部代码实现清华严蔚敏数据结构的全部代码实现C语语言言/*c1.h(程序名)*/#include#include#include/*malloc()等*/#include/*INT_MAX等*/#include/*EOF(=Z或F6),NULL*/#include/*atoi()*/#include/*eof()*/#include/*floor(),ceil(),abs()*/#include/*exit()*/*函数结果状态代码*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/*#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码,如OK等*/typedefintBoolean;/*Boolean是布尔类型,其值是TRUE或FALSE*/*algo2-1.c实现算法2.1的程序*/#includec1.htypedefintElemType;#includec2-1.h/*c2-1.h线性表的动态分配顺序存储结构*/#defineLIST_INIT_SIZE10/*线性表存储空间的初始分配量*/#defineLISTINCREMENT2/*线性表存储空间的分配增量*/typedefstructElemType*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)/*初始条件:
顺序线性表L已存在。
操作结果:
若L为空表,则返回TRUE,否则返回FALSE*/if(L.length=0)returnTRUE;elsereturnFALSE;intListLength(SqListL)/*初始条件:
顺序线性表L已存在。
操作结果:
返回L中数据元素个数*/returnL.length;StatusGetElem(SqListL,inti,ElemType*e)/*初始条件:
顺序线性表L已存在,1iListLength(L)*/*操作结果:
用e返回L中第i个数据元素的值*/if(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(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已存在,1iListLength(L)+1*/*操作结果:
在L中第i个位置之前插入新的数据元素e,L的长度加1*/ElemType*newbase,*q,*p;if(i(*L).length+1)/*i值不合法*/returnERROR;if(*L).length=(*L).listsize)/*当前存储空间已满,增加分配*/newbase=(ElemType*)realloc(*L).elem,(*L).listsize+LISTINCREMENT)*sizeof(ElemType);if(!
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已存在,1iListLength(L)*/*操作结果:
删除L的第i个数据元素,并用e返回其值,L的长度减1*/ElemType*p,*q;if(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)returnTRUE;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);/*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;elseListInsert(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);voidprint(ElemType*c)printf(%d,*c);voidmain()SqListLa,Lb,Lc;intj,a4=3,5,8,11,b7=2,6,8,9,11,15,20;InitList(&La);/*创建空表La*/for(j=1;j=4;j+)/*在表La中插入4个元素*/ListInsert(&La,j,aj-1);printf(La=);/*输出表La的内容*/ListTraverse(La,print);InitList(&Lb);/*创建空表Lb*/for(j=1;j=7;j+)/*在表Lb中插入7个元素*/ListInsert(&Lb,j,bj-1);printf(Lb=);/*输出表Lb的内容*/ListTraverse(Lb,print);MergeList(La,Lb,&Lc);printf(Lc=);/*输出表Lc的内容*/ListTraverse(Lc,print);/*algo2-3.c实现算法2.7的程序*/#includec1.htypedefintElemType;#includec2-1.h#includebo2-1.cvoidMergeList(SqListLa,SqListLb,SqList*Lc)/*算法2.7*/*已知顺序线性表La和Lb的元素按值非递减排列。
*/*归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列*/ElemType*pa,*pa_last,*pb,*pb_last,*pc;pa=La.elem;pb=Lb.elem;(*Lc).listsize=(*Lc).length=La.length+Lb.length;/*不用InitList()创建空表Lc*/pc=(*Lc).elem=(ElemType*)malloc(*Lc).listsize*sizeof(ElemType);if(!
(*Lc).elem)/*存储分配失败*/exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_last&pb=pb_last)/*表La和表Lb均非空*/*归并*/if(*pa=*pb)*pc+=*pa+;else*pc+=*pb+;while(pa=pa_last)/*表La非空且表Lb空*/*pc+=*pa+;/*插入La的剩余元素*/while(pb=pb_last)/*表Lb非空且表La空*/*pc+=*pb+;/*插入Lb的剩余元素*/voidprint(ElemType*c)printf(%d,*c);voidmain()SqListLa,Lb,Lc;intj;InitList(&La);/*创建空表La*/for(j=1;j=5;j+)/*在表La中插入5个元素*/ListInsert(&La,j,j);printf(La=);/*输出表La的内容*/ListTraverse(La,print);InitList(&Lb);/*创建空表Lb*/for(j=1;j=5;j+)/*在表Lb中插入5个元素*/ListInsert(&Lb,j,2*j);printf(Lb=);/*输出表Lb的内容*/ListTraverse(Lb,print);MergeList(La,Lb,&Lc);printf(Lc=);/*输出表Lc的内容*/ListTraverse(Lc,print);/*algo2-4.c修改算法2.7的第一个循环语句中的条件语句为开关语句,且当*/*pa=*pb时,只将两者中之一插入Lc。
此操作的结果和算法2.1相同*/#includec1.htypedefintElemType;#includec2-1.h#includebo2-1.cintcomp(ElemTypec1,ElemTypec2)inti;if(c1c2)i=1;elseif(c1=c2)i=0;elsei=-1;returni;voidMergeList(SqListLa,SqListLb,SqList*Lc)/*另一种合并线性表的方法(根据算法2.7下的要求修改算法2.7)*/ElemType*pa,*pa_last,*pb,*pb_last,*pc;pa=La.elem;pb=Lb.elem;(*Lc).listsize=La.length+Lb.length;/*此句与算法2.7不同*/pc=(*Lc).elem=(ElemType*)malloc(*Lc).listsize*sizeof(ElemType);if(!
(*Lc).elem)exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_last&pb=pb_last)/*表La和表Lb均非空*/switch(comp(*pa,*pb)/*此句与算法2.7不同*/case0:
pb+;case1:
*pc+=*pa+;break;case-1:
*pc+=*pb+;while(pa=pa_last)/*表La非空且表Lb空*/*pc+=*pa+;while(pb=pb_last)/*表Lb非空且表La空*/*pc+=*pb+;(*Lc).length=pc-(*Lc).elem;/*加此句*/voidprint(ElemType*c)printf(%d,*c);voidmain()SqListLa,Lb,Lc;intj;InitList(&La);/*创建空表La*/for(j=1;j=5;j+)/*在表La中插入5个元素*/ListInsert(&La,j,j);printf(La=);/*输出表La的内容*/ListTraverse(La,print);InitList(&Lb);/*创建空表Lb*/for(j=1;jnext=NULL;/*指针域为空*/returnOK;StatusDestroyList(LinkList*L)/*初始条件:
线性表L已存在。
操作结果:
销毁线性表L*/LinkListq;while(*L)q=(*L)-next;free(*L);*L=q;returnOK;StatusClearList(LinkListL)/*不改变L*/*初始条件:
线性表L已存在。
操作结果:
将L重置为空表*/LinkListp,q;p=L-next;/*p指向第一个结点*/while(p)/*没到表尾*/q=p-next;free(p);p=q;L-next=NULL;/*头结点指针域为空*/returnOK;StatusListEmpty(LinkListL)/*初始条件:
线性表L已存在。
操作结果:
若L为空表,则返回TRUE,否则返回FALSE*/if(L-next)/*非空*/returnFALSE;elsereturnTRUE;intListLength(LinkListL)/*初始条件:
线性表L已存在。
操作结果:
返回L中数据元素个数*/inti=0;LinkListp=L-next;/*p指向第一个结点*/while(p)/*没到表尾*/i+;p=p-next;returni;StatusGetElem(LinkListL,inti,ElemType*e)/*算法2.8*/*L为带头结点的单链表的头指针。
当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR*/intj=1;/*j为计数器*/LinkListp=L-next;/*p指向第一个结点*/while(p&jnext;j+;if(!
p|ji)/*第i个元素不存在*/returnERROR;*e=p-data;/*取第i个元素*/returnOK;intLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType)/*初始条件:
线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0)*/*操作结果:
返回L中第1个与e满足关系compare()的数据元素的位序。
*/*若这样的数据元素不存在,则返回值为0*/inti=0;LinkListp=L-next;while(p)i+;if(compare(p-data,e)/*找到这样的数据元素*/returni;p=p-next;return0;StatusPriorElem(LinkListL,ElemTypecur_e,ElemType*pre_e)/*初始条件:
线性表L已存在*/*操作结果:
若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,*/*返回OK;否则操作失败,pre_e无定义,返回INFEASIBLE*/LinkListq,p=L-next;/*p指向第一个结点*/while(p-next)/*p所指结点有后继*/q=p-next;/*q为p的后继*/if(q-data=cur_e)*pre_e=p-data;returnOK;p=q;/*p向后移*/returnINFEASIBLE;StatusNextElem(LinkListL,ElemTypecur_e,ElemType*next_e)/*初始条件:
线性表L已存在*/*操作结果:
若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,*/*返回OK;否则操作失败,next_e无定义,返回INFEASIBLE*/LinkListp=L-next;/*p指向第一个结点*/while(p-next)/*p所指结点有后继*/if(p-data=cur_e)*next_e=p-next-data;returnOK;p=p-next;returnINFEASIBLE;StatusListInsert(LinkListL,inti,ElemTypee)/*算法2.9。
不改变L*/*在带头结点的单链线性表L中第i个位置之前插入元素e*/intj=0;LinkListp=L,s;while(p&jnext;j+;if(!
p|ji-1)/*i小于1或者大于表长*/returnERROR;s=(LinkList)malloc(sizeof(structLNode);/*生成新结点*/s-data=e;/*插入L中*/s-next=p-next;p-next=s;returnOK;StatusListDelete(LinkListL,inti,ElemType*e)/*算法2.10。
不改变L*/*在带头结点的单链线性表L中,删除第i个元素,并由e返回其值*/intj=0;LinkListp=L,q;while(p-next&jnext;j+;if(!
p-next|ji-1)/*删除位置不合理*/returnERROR;q=p-next;/*删除并释放结点*/p-next=q-next;*e=q-data;free(q);returnOK;StatusListTraverse(LinkListL,void(*vi)(ElemType)/*vi的形参类型为ElemType,与bo2-1.c中相应函数的形参类型ElemType&不同*/*初始条件:
线性表L已存在*/*操作结果:
依次对L的每个数据元素调用函数vi()。
一旦vi()失败,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 华严 全部 代码 实现 语言