数据结构-刘波-2

《数据结构-刘波-2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

数据结构第二章线性表主讲人:刘波

1本章教学目标掌握线性表的逻辑结构及相关概念掌握线性表的两种存储结构:顺序表和链表掌握顺序表上各种基本运算的实现过程掌握链表上各种基本运算的实现过程

2线性结构的特点存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个之外,数据元素集合中的每个元素均只有一个前驱除最后一个之外,数据元素集合中的每个元素均只有一个后继例如:(a1,a2,a3,…,an-1,an)

3线性表的类型定义线性表:是n个数据元素的有限序列线性表的长度:线性表中元素的个数抽象数据类型线性表的定义除了以上定义的基本操作外,还可以有更复杂的操作,如:将两个表合并成一个表;将一个表拆成两个表;复制一个线性表

4ADTList{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R={|ai-1,ai∈D,i=1,2,…,n}基本操作：InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。

5ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE,否则返回FALSE。Listlenght(L)初始条件：线性表L已存在。操作结果：返回L中数据元素个数。GetElem(L,i,&e)初始条件：线性表L已存在,1≤i≤ListLength(L)。操作结果：用e返回L中第i个数据元素的值。

6LocateElem(L,e,compare())初始条件：线性表L已存在,compare()是数据元素判定函数。操作结果：返回L中第1个与e满足关系compare()的数据元素的位序，若这样的数据元素不存在，则返回值为0。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L中的数据元素，且不是第一，则用pre_e返回它的前驱,否则操作失败,pre_e无定义。NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L中的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。

7ListInsert(&L,i,e)初始条件：线性表L已存在,1≤i≤ListLength(L)+1。操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空,1≤i≤ListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ListTraverse(L,visit())初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。}ADTList

8线性表的表示(存储结构)顺序表示链式表示

9线性表的顺序表示和实现把线性表中的所有元素,按照其逻辑顺序依次存储到计算机中的从指定存储位置开始的一块连续的存储空间中.是一种紧凑结构Loc(ai+1)=loc(ai)+sizeof(ElemType)顺序表示意图是一种随机存储的结构通常用数组来描述顺序存储结构

10顺序表示意图

11线性表的动态分配顺序存储结构#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;//存储空间起始地址intlength;//当前元素个数intlistsize;//当前分配的存储容量(以sizeof(ElemType)为单位)}SqList;

12顺序表基本运算的实现初始化(构造一个空线性表L)StatusInitList_sq(SqList&L){L.elem=((ElemType)*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}

13顺序表基本运算的实现(2)求长度(返回L中数据元素个数)intListLength(SqListL){return(L.length);}

14顺序表基本运算的实现(3)显示顺序表Voiddisplay(SqListL){if(L.length==0)printf(“空表”);elsefor(j=0;j

15顺序表基本运算的实现(4)取表中第i个元素ElemTypeGetElem(SqListL,inti,ElemType&e){if(i<0||i>L.length-1)printf(“i参数不正确“）;elsee=L.elem[i-1];return(e);}

16顺序表基本运算的实现(5)按值查找e元素的位序，没找到返回0intLocateElem(SqListL,ElemTypee){inti=1;while(i

17顺序表基本运算的实现(6)插入操作(在第i个元素前插入一个元素)StatusListInsert_sq(SqList&L,inti,ElemTypee){if(i<1||i>L.length+1)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为插入位置

18插入操作(续）For(p=&(L.elem[L.length-1];p>=q;--p)//插入位置及之后的元素右移*(p+1)=*p;*q=e;//插入e++L.length;returnOK;}时间复杂度：O(n)

19顺序表基本运算的实现(7)删除操作(删除第i个元素)StatusListDelete_Sq(SqList&L,inti,ElemType&e){if((i<1)||(i>L.length_Sq(L))returnERROR;p=&(L.elem[i-1]);//被删除元素的位置e=*p;q=L.elem+L.length-1;//表尾元素的位置for(++p;p<=q;++p)//被删除元素之后的元素左移*(p-1)=*p;--L.length;returnOK;}时间复杂度：O(n)

20顺序表基本运算的实现(8)顺序表的合并VoidMergeList_Sq(SqListLa,SqListLb,SqList&Lc)//La和Lb均为元素递增顺序表,将La和Lb合并为递增顺序表Lc{pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;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;

21While(pa<=pa_last&&pb<=pb_last){if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}While(pa<=pa_last)*pc++=*pa++;//插入La的剩余元素While(pb<=pb_last)*pc++=*pb++;//插入Lb的剩余元素}

22顺序表的优缺点优点数据元素可以随机存取占用较少存储空间缺点需要一组地址连续的存储单元在插入或删除操作时，需移动大量元素。

23线性表的链式表示和实现线性链表的结点数据元素ai的存储映像,包括两个域：数据域和指针域n个结点链结成一个链表单链表（线性链表）：只包含一个指针域头结点：单链表的第一个结点之前附设的一个结点最后一个结点的指针为“空”（NULL）数据元素之间的逻辑关系是由结点中的指针指示的。数据域指针域数据域指针域

24线性表链式存储结构示意图

25线性表的单链表存储结构typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;headd^cba

26链表的基本运算(1)创建单链表voidCreateList_L(LinkListL,intn){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));scanf(&p->data);p->next=L->next;//将p插入表头结点L后L->next=p;}}问题:如果要将新结点插入到链表尾，如何改算法？

27链表的基本运算(2)求长度（头结点不计在内）intListLength(LinklistL){n=0;p=L->next;while(p!=NULL){n++;p=p->next;}return(n);}

28链表的基本运算(3)取第i个元素statusGetElem_L(LinklistL,inti,ElemType&e){LinklistP=L->next;intj=1;while(P&&jnext;++j;}if(!P||j>i)returnERROR;e=P->data;returnOK;}

29链表的基本运算(4)显示操作voiddisplay(LinklistL)//显示L的所有元素{intn=ListLength(L);LinklistP=L->next;if(n==0)printf(“空表/n”);elseif(n==1)printf(P->data);else{for(i=1;idata);P=P->next;}printf(P->data);}}

30链表的基本运算(5)插入结点StatusListInsert_L(LinkList&L,inti,ElemTypee){//在第i个元素前插入一个元素p=L;j=0;while(p&&jnext;++j}//找第i-1个结点if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));//生成新结点s->data=e;s->next=p->next;//插入L中p->next=s;returnOK;}

31链表的基本运算(6)删除结点StatusListDelete_L(LinkList&L,inti,ElemType&e){//删除第i个结点P=L;j=0;While(p->next&&jnext;++j;}If(!(p->next)||j>i-1)returnERROR;q=p->next;p->next=q->next;//删除结点e=q->data;free(q);ReturnOK;}

32链表的基本运算(7)有序表合并(表元素按值非递减排列)voidMergeList_L(LinkListLa,LinkListLb,LinkListLc){pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;free(Lb);}

33链表的基本运算(8)有序表求交集(表元素按值非递减排列)voidIntersectionList_L(LinkListLa,LinkListLb,LinkListLc){pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data==pb->data){pc=pa;pa=pa->next;}elseif(pa->datadata){pc->next=pa->next;free(pa);pa=pc->next;}elsepb=pb->next;}

34有序表求交集(续）pc->next=NULL;while(pa){pc=pa;pa=pa->next;free(pc);}pb=Lb;//从Lb头结点开始while(pb){pc=pb;pb=pb->next;free(pc);}}

35链表的基本运算(9)有序表求差集voidSubList_L(LinkListLa,LinkListLb,LinkListLc){pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data==pb->data){pc->next=pa->next;free(pa);pa=pc->next;}elseif(pa->datadata){pc=pa;pa=pa->next;}elsepb=pb->next;}

36有序表求差集（续）pb=Lb;while(pb)//从Lb头结点开始{pc=pb;pb=pb->next;free(pc);}}

37线性表的静态链表存储结构#defineMAXSIZE1000typedefstruct{ElemTypedata;//数据元素intcur;//下一个结点在链表中的相对位置（位序）}Component,SLinkList[MAXSIZE];

38例：SlinklistS;s[0]:头结点；s[0].cur:指示第一个结点在数组中的位置,设i=s[0].cur,则:s[i].data存储线性表的第一个数据元素;k=s[i].cur:s[i]下一个结点的位置

39动态链表：用指针描述的链表静态链表：用数组描述的链表静态链表操作示例intLocateElem_SL(SLinkListS,ElemTypee){//定位操作i=S[0].cur;while(i&&S[i].data!=e)i=S[i].cur;returni;}

40其他形式链表循环链表（circularlinkedlist)表中最后一个结点的指针域指向头结点与非循环链表的操作基本相同，只是对表尾的判断作了改变。P->next=h;双向链表（doublelinkedlist)每个结点中有两个指针域，一个指向直接后继，另一个指向直接前驱便于向前查找

41双向链表的存储结构typedefstructDuLNode{structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList;head

42双链表的基本操作插入操作算法statusListInsert_DuL(DULinkList&L,inti,ElemTypee)//在第i个元素前插入元素e{if(!(p=GetElemP_Dul(L,i))//p为第i个元素结点returnERROR;//p=Nullif(!(s=(DuLinkList)malloc(sizeof(DuLnode)))returnERROR;//存储申请失败s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnOK}

43DuLNodeGetElemP_DuL(DuLinkListL,inti){P=L->next;j=1;while(P&&jnext;j++;}if(!P||j>i)returnNULL;returnP;}

44双链表的基本操作(2)删除操作算法StatusListDelete_DuL(DuLinklist&L,inti,ElemType&e)//e保留要删除的元素{if(!P=GetElemP_DuL(L,i)))returnERRORe=P->data;P->prior->next=P->next;P->next->prior=P->prior;free(P);returnOK;}

45链表存储结构小结优点不需要一大块地址连续的存储单元在插入或删除元素时，不需要移动大量元素。采用动态链表不需要固定最大长度。缺点占用较大存储空间不可以随机访问数据元素链表的存储结构不唯一

46线性表的应用一元多项式的表示及操作一元多项式的线性表示(1)Pn(x)=P0+P1x+P2x2+……+Pnxn其中：P0，P1，P2，……Pn可能为0线性表P=（P0，P1，P2，……Pn）(2)Pn(x)=P1xe1+P2xe2+……+Pmxem其中：P1，P2，……Pm不为00≤e1

47例1：P(x)=1+2x+7x2+8X3+5x4+10x5(1)P=(1,2,7,8,5,10)(2)P=((1,0),(2,1),(7,2),(8,3),(5,4),(10,5))例2：P(x)=8+3x4+5x10(1)P=(8,0,0,0,3,0,0,0,0,0,5)(2)P=((8,0),(3,4),(5,10))

48一元多项式的存储表示顺序表链表注意：链表方式灵活，一般采用链表方式例：P(x)=3+4x3+15x5+9x8P-1304315598Λ

49抽象数据类型一元多项式的定义ADTPolynomial{数据对象：D={ai|aiTermSet,i=1,2,…m,m≥0,TermSet为(实数，整数）形式}数据关系：R1={|ai-1,aiD}基本操作：Createpolyn(&P,m);PrintPolyn(P);AddPolyn(&Pa,&Pb);SubtractPolyn(&Pa,&Pb);MultiplyPolyn(&Pa,&Pb);}

50抽象数据类型Polynomial的实现typedefstruct{floatcoef;intexpn;}term,ElemType;typedefLinkListpolynomial;//基本操作原型说明voidCreatPolyn(polynomial&P,intm);voidPrintPolyn(polynomialP);intPolynLength(polynomialP);voidAddPolyn(polynomial&Pa,polynomial&Pb);voidSubtractPolyn(polynomial&Pa,polynomial&Pb);voidMultiPolyn(polynomial&Pa,polynomial&Pb);

51基本操作的算法描述比较两个多项式项intcmp(terma,termb){if(a.expn>b.expn)return1;if(a.expn=b.expn)return0;if(a.expn

52基本操作的算法描述(2)创建一个多项式creatpolyn(Polynomial&P,intm){P=(Polynomial)malloc(sizeof(Lnode))Q=P;(&P->data).coef=0;(&P->data).expn=-1;//建立头结点for(i=1;i<=m;i++){L=(polynomial)malloc(sizeof(Lnode))scanf((&L->data).coef);scanf((&L->data).expn);P->next=L;P=L;}L->next=NULL;P=Q;}

53基本操作的算法描述(3)两个多项式相加voidAddPolyn(polynnomial&Pa,polynnomial&Pb){ha=Pa;hb=Pb;qa=Pa->next;qb=Pb->next;while(qa&&qb){a=qa->data;b=qb->data;

54switch(*cmp(a,b)){case–1://a.expnnext;//ha始终为qa前驱break;case0://a.expn=b.expnsum=a.coef+b.coef;if(sum!=0){(&qa->data).coef=sum;ha=qa;qa=qa->next;FreeNode(qb);qb=NextPos(Pb,hb);}else{//sum=0;DelFirst(ha,qa);FreeNode(qa);DelFirst(hb,qb);FreeNode(qb);qb=NextPos(Pb,hb);qa=NextPos(pa,ha);}break;

55case1://a.expn>b.expnInsFirst(ha,qb);//在ha后插入qbDelFirst(hb,qb);//在Pb中删去已插入Pa中的qbqb=NextPos(Pb,hb);ha=NextPos(pa,ha);break;}//switch-end}//while-endif(!ListEmpty(Pb))Append(Pa,qb);//Pa链接Pb的剩余结点freeNode(hb);//释放Pb的头结点（位置始终未变）}

56补充例题假设顺序表：C.elem[]=(a1,a2,…,am,b1,b2,…,bn)设计算法：将C中元素的两部分互换为：C1.elem[]=(b1,b2,…,bn,a1,a2,…,am)

57算法思路将C中两部分元素互换可以通过元素的逆置来实现。先将C中所有元素逆置，使之成为C1.elem=(bn,bn-1…,b1,am,…,a2,a1)，然后将(bn,bn-1…,b1)逆置为(b1,b2,…,bn)，将(am,…,a2,a1)逆置为(a1,a2,…,am)，这样便得到最终结果：C1.elem[]=(b1,b2,…,bn,a1,a2,…,am)。

58voidchange(SqList&L,intn,intm){reverse(L,0,m+n-1);reverse(L,0,n-1);reverse(L,n,n+m-1);}voidreverse(SqList&L,ints,intt){//逆置顺序表中的子表ElemTypex;for(i=s,j=t;i

59关于实验实验内容见实验安排表实验报告格式实验目标实验内容程序代码调试分析及测试结果

60C语言基本结构(1)头文件说明,函数结果代码定义(2)类型定义(3)函数定义函数类型函数名(参数){变量定义;语句序列;}(4)主程序{变量定义;输入数据或调用创建函数;主要操作语句序列或函数调用;输出函数或调用输出函数;}

61程序示例#include“stdoi.h”#include“stdlib.h”#include“malloc.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE–1#defineOVERFLOW–2typedefintStatus

62//链表定义P28TypedefstructLnode{intdata;structLnode*next;}Lnode,*LinkList;

63//创建链表P30VoidCreateList_L(LinkiListL,intn){LinkListP;inti;L=(LinkList)malloc(sizeof(Lnode));L->next=NULL;for(i=n;i>0;i--){P=(LinkList)malloc(sizeof(Lnode));printf(“Pleaseinputdata:

64”);scanf(“%d”,&P->data);P->next=L->next;L->next=P;}}

65//求链表长度IntListLength(LinkListL){intn=0;LinkListP=L->next;while(P!=NULL){n++;P=P->next;}return(n);}

66//主程序Main(){LinkListL;intn,Len;printf(“inputdatanumber:

67”)scanf(“%d”,&n);CreateList_L(L,n);Len=List_Length(L);printf(“Thelengthofthelinkis:%d

68”,Len);}

69作业2.2~2.92.11,2.15,2.16,2.21*,2.22*