数据结构第二章.pptx

《数据结构第二章.pptx》由会员分享，可在线阅读，更多相关《数据结构第二章.pptx（103页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.线性表的语言定义线性表是n个数据元素的有限序列。例，英文字母表(A，B，C，Z)线性表中的数据元素可以由若干个数据项组成。例，包含大量记录的登记表姓名姓名学号学号性别性别年龄年龄班级班级王晓林王晓林790631男男25计计90陈红陈红790632女女24计计902.1 线性表的定义第1页/共103页2.线性表的形式定义其中a1是头元素，an是尾元素，ai是第i个元素。ai-1是ai的直接前驱，ai是ai-1的直接后继。当2in时，ai有且只有一个直接前驱。当1in-1时，ai有且只有一个直接后继。线性表可以表示为n个数据元素的有限序列:(a1，ai-1，ai，an)第2页/共103页抽象数

2、据类型线性表List的定义:InitList(&L)结果:构造一个空的线性表L。数据对象:D=ai|aiElemSet，i=1,2,n数据关系:R1=基本操作:ADTListADTListDestroyList(&L)结果:销毁线性表L。条件:线性表L已存在。ClearList(&L)结果:将L重置为空表。条件:线性表L已存在。第3页/共103页主要基本操作包括:ListLength(L)条件:线性表L已存在结果返回L数据元素个数GetElem(L，i，&e)LocateElem(L，e，compare()PriorElem(L，cur_e，&pre_e)NextElem(L，cur_e，&n

3、ext_e)ListInsert(&L，i，e)ListEmpty(L)条件:线性表L已存在结果:若L为空表,则返回TRUE否则返回FALSEListdelete(&L，i，e)ListTraverse(L，visit()第4页/共103页一些复杂操作，如合并、拆分、复制等等均可以通过上述简单操作实现。第5页/共103页算法2.1，两个线性表La，Lb的合并。要求:扩展线性表La，将存在于Lb中而不存在于La中的数据元素插入到La中。思想:1.依次取出Lb中的数据元素进行处理2.判断该数据元素是否存在于La中3.在则取下一个数据元素，否则插入到La中第6页/共103页La_len=ListLe

4、ngth(La)；Lb_len=ListLength(Lb)；for(i=1；i=Lb_len；i+)GetElem(Lb，i，e)；if(!LocateElem(La，e，equal)ListInsert(La，+La_len，e)；voidunion(List&La，ListLb)注意基本操作的执行时间特别是LocateElem！第7页/共103页例，La=(3,13,7,9)Lb=(5,7,10)首先，La_len=4；Lb_len=3；31379La5710Lb5查找La，未找到查找La，找到查找La，未找到10第8页/共103页算法2.2，两个有序线性表La，Lb的合并。要求:线性表

5、La、Lb中的数据元素按值非递减有序排列，合并La、Lb构造Lc，使Lc中的数据元素仍按值非递减有序排列。例，La=(3,5,8,11)Lb=(2,6,8,9,11,15,20)构造Lc=(2,3,5,6,8,8,9,11,11,15,20)ij构造Lc=(2,3,5,6,8,8,9,11,11,15,20)ji构造Lc=(2,3,5,6,8,8,9,11,11,15,20)ij构造Lc=(2,3,5,6,8,8,9,11,11,15,20)思想:第9页/共103页La_len=ListLength(La)；Lb_len=ListLength(Lb)；voidMergeList(ListLa，

6、ListLb，List&Lc)InitList(Lc)；i=j=1；k=0；GetElem(La，i，a)；GetElem(Lb，j，b)；while(i=La_len)&(j=Lb_len)if(a=b)ListInsert(Lc，+k，a)；+i；elseListInsert(Lc，+k，b)；+j；/处理超长部分第10页/共103页GetElem(La，i+，a)；ListInsert(Lc，+k，a)；/如果剩余Lawhile(ilcGetElem(Lb，j+，b)；ListInsert(Lc，+k，b)；/如果剩余Lbwhile(jlc/处理超长部分第11页/共103页例，La=(3

7、,5,8)Lb=(2,6,8,9,15)构造Lc=(2,3,5,6,8,8,9,15)358La268Lb915Lcij2首先，La_len=3；Lb_len=5；3ijij5ij6ij88jij9j15j算法结束！第12页/共103页算法时间复杂度算法2.1算法2.2O(ListLength(La)ListLength(Lb)O(ListLength(La)+ListLength(Lb)前提:GetElem()和ListInsert()的执行时间与表长无关LocateElem()的执行时间与表长成正比第13页/共103页IntlocateElem_Sq(SqListL,ElemTypee,s

8、tatus(*compare)(ElemType,ElemType)i=1;p=L.elem/第一个元素的存储地址while(iL.length&!(*compare)(*p+,e)+iif(i=L.length)returni;Elsereturn0;*compare为指向函数的指针:即定义了一个指向函数的指针变量compare，此处该指针变量指向的函数带有两个参数ElemType,ElemType,返回status类型值。Statuscompare(ElemTypex,ElemTypey)returnx=y;第14页/共103页 LocateElem 函数也可以这样写：int Locate

9、Elem(SqList L,ElemType e)Status compare(ElemType,ElemType);ElemType*p;int i=1;p=L.elem;while(i=L.length&!compare(*p+,e)i+;if(i=q；-p)*(p+1)=*p；/后移元素L.listsize第24页/共103页if(iL.length+1)returnERROR；if(L.length=L.listsize)/越界处理；q=&(L.elemi-1)；/q为插入位置（位序）for(p=&L.elemL.length-1；p=q；-p)*(p+1)=*p；/后移元素*q=e；

10、/插入新元素+L.length；returnOK；StatusListInsert_Sq(Sqlist&L，inti，ElemTypee)定义一的插入算法第25页/共103页if(iL.length+1)returnERROR；if(L.length=maxsize)/越界处理；for(j=L.length-1；j=i-1;j-)L.dataj+1=L.dataj;L.datai-1=x;L.length+；returnOK；voidListInsert_Sq(Sqlist&L，inti，ElemTypee)定义二的插入算法第26页/共103页/越界处理newbase=(ElemType*)r

11、ealloc(L.elem，(L.listsize+LISTINCREMENT)*sizeof(ElemType)；if(!newbase)exit(OVERFLOW)；L.elem=newbase；L.listsize+=LISTINCREMENT；if(L.length=L.listsize)第27页/共103页例，在第4个元素之前插入元素25。451293369512345657693325插入25第28页/共103页算法时间复杂度:时间主要花在移动元素上，而移动元素的个数取决于插入元素位置。i=1，需移动n个元素；i=i，需移动ni+1个元素；i=n+1，需移动0个元素；第29页/共1

12、03页假设pi是在第i个元素之前插入一个新元素的概率则长度为n的线性表中插入一个元素所需移动元素次数的期望值为:Eis=pi(ni+1)n+1i=1设在任何位置插入元素等概率，pi=n+11Eis=(ni+1)=n+11i=1n+12nO(n)第30页/共103页算法2.5删除第i个数据元素思想:a1ai-1ai+1ana1ai-1ai+1anai1.删除第i个数据元素。2.将第i+1到n个元素均向前移动一个位置。第31页/共103页if(iL.length)returnERROR；p=&(L.elemi-1)；for(+p；p=q；+p)*(p-1)=*p；/前移e=*p；/取第i个元素的值

13、q=L.elemL.length1；取最后一个元素的地址returnOK；StatusListDelete_Sq(Sqlist&L，inti，ElemType&e)-L.length；删除算法（定义一）/取第i个元素的地址第32页/共103页if(iL.length)returnERROR；for(j=i；jl.length-1;j+)L.dataj-1=L.dataj；/前移VoidListDelete_Sq(Sqlist&L，inti，ElemType&e)L.length-；删除算法（定义二）e=L.datai;第33页/共103页算法时间复杂度:时间主要花在移动元素上，而移动元素的个数

14、取决于删除元素位置。i=1，需移动n-1个元素；i=i，需移动ni个元素；i=n，需移动0个元素；第34页/共103页例，删除第4个元素25。删除25451292533691234567533695第35页/共103页假设qi是删除第i个元素的概率则长度为n的线性表中删除一个元素所需移动元素次数的期望值为:Edl=qi(ni)ni=1设删除任何位置的元素等概率，qi=n1Edl=(ni)=n1i=1n2n-1O(n)故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低。第36页/共103页voidMergeList_sq(SqListLa,SqListLb,SqList

15、&Lc)pa=La.elem;pb=Lb.elem;/ElemType*pa,*pb,*pc,*pa_last,*pb_last;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;while(pa=pa_last&pb=pb_last)if(*pa=*pb)*pc+=*pa+;els

16、e*pc+=*pb+;while(pa=pa_last)*pc+=*pa+;while(pbnext=NULL第47页/共103页线性表的单链表结点表示a1a2a3aianL不带头结点的链表a1=L-data;Sa2=L-next-data;S=L-next;用S如何表示a2,a3呢？第48页/共103页 a1a2a3aianL带头结点的链表结点表示a1=L-next-data SS=L-next-next第49页/共103页线性表的链式存储结构的特点不可随机存取表中任意数据元素缺点:不可直接获取线性表的长度优点？数据元素的插入、删除相对顺序表的操作方便。第50页/共103页例：取线性单链表第

17、i个元素。a1a2aiLPP=P-nextji在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。第51页/共103页算法2.8:取线性单链表第i个元素。p=L-next；j=1；/初始化，p指向首元结点while(p&jnext；+j；if(!p|ji)returnERROR；e=p-data；returnOK；StatusGetElem_L(LinkListL，inti，ElemType&e)a1a2aiLPP-nextji第52页/共103页例，取第i=3个元素。ZhaoQia

18、nLiLSunp=L-nextj=1p=p-nextj=2p=p-nextj=3e=p-data=Sun时间复杂度:O(n)最多查找N次第53页/共103页在线性表ai元素之前插入元素x:xSS-next=p-next；pai-1aip-next=S；基本思想1.找到ai所在结点的前驱结点2.创建将要插入的结点3.作插入操作，指针变换怎么做？方法1.p-next=S方法2.链表的插入第54页/共103页例，在第3个元素之插入一个新元素。ZhaoQian0LiLp=L-nextj=1p=p-nextj=2Suns时间复杂度:O(n)1.找到第3个元素所在结点的前驱结点；2.创建将要插入的结点S；

19、3.作插入操作，指针变换。第55页/共103页1.找到第i个结点的前驱结点2.构造将要插入的结点3.插入新结点，指针变换算法2.9在第i个数据元素之前插入一个新的元素主要操作StatusListInsert_L(LinkList&L，inti，ElemTypex)a1ai0anLwhile(p&jnext；+j；s=(LinkList*)malloc(sizeof(LNode)；s-data=x；p-next=s；/插入新结点s-next=p-next；p第56页/共103页算法2.9在第i个数据元素之前插入一个新的元素p=L-next；j=1；/初始化，p指向首元结点returnOK；Sta

20、tusListInsert_L(LinkList&L，inti，ElemTypex)if(!p|ji-1)returnERROR；p-next=s；/插入新结点s-next=p-next；s-data=x；/建立新结点s=(LinkList*)malloc(sizeof(LNode)；while(p&jnext；+j；/找到第i个结点的前驱结点第57页/共103页删除线性表中元素b:pacbq=p-nextp-next=p-next-next/可行吗？1)p-next=q-next;q=p-next;2)怎么做？free(q)；1.确定指针2.取出要删除的结点3.指针变换3.释放内存删除结点的

21、基本思想：第58页/共103页例，删除第3个元素。ZhaoQian0LiLSunp=L-nextj=1p=p-nextj=2e=q-data=Sunq=p-next时间复杂度:O(n)1.确定指针p2.由q取出要删除的结点3.指针变换3.释放内存删除结点的基本思想：第59页/共103页算法2.10删除第i个数据元素p=L-next；j=1；returnOK；StatusListDelete_L(LinkList&L，inti，ElemType&e)if(!p-next|ji-1)returnERROR；p-next=q-next；/删除第i个结点q=p-next；e=q-data；free(q

22、)；while(p-next&jnext；+j；/找到第i个结点的前驱结点第60页/共103页单链表的特点：优点：它是一种动态结构，整个存储空间为多个链表共用；不需预先分配空间；链表上实现插入和删除运算，无须移动结点，仅需修改 指针。缺点：指针占用额外存储空间；不能随机存取，查找速度慢。第61页/共103页算法2.11利用插入操作构造一条完整的单链表。L=(LinkList)malloc(sizeof(LNode)；L-next=NULL；/建立头结点，初始化带头结点的单链p=(LinkList)malloc(sizeof(LNode)；Scanf(&p-data)；p-next=L-next

23、；L-next=p；/在表头插入新结点for(i=n；i0；-i)voidCreateList_L(LinkList&L，intn)逆位序建立单链表逆位序建立单链表 第62页/共103页aia1LanpL-next前插法建链表L-next=p;p-next=L-next第63页/共103页例，ZhaoQian0L0ppZhaoQian0Lp时间复杂度:O(n)第64页/共103页例，Zhao0pQianpZhaoQian0Lp时间复杂度:O(n)LP-next=L;L=P;第65页/共103页创建一个单链表L=(LinkList)malloc(sizeof(LNode)；L-next=NULL

24、；/建立头结点，初始化带头结点的单链p=(LinkList)malloc(sizeof(LNode)；Scanf(“%d”,&p-data)；p-next=L-next；L-next=p；/在表头插入新结点for(i=1；inext；pb=Lb-next；/分别指向第一个结点pc-next=pa?pa:pb；/处理剩余部分while(pa&pb)if(pa-datadata)pc-next=pa；pc=pa；pa=pa-next；elsepc-next=pb；pc=pb；pb=pb-next；voidMergeList_L(LinkList&La，LinkList&Lb，LinkList&Lc

25、)Lc=pc=La；free(Lb)；思想:通过比较不断后移指针合并链表。第68页/共103页21350Lb0627La6789Lcpapb,pcpapcpbLcpcpbpaLcpcpapbLcpbpapcLcpa=La-next；pb=Lb-next；Lc=pc=Lawhile(pa&pb)if(pa-datadata)pc-next=pa；pc=pa；pa=pa-next；elsepc-next=pb；pc=pb；pb=pb-next；第69页/共103页静态链表循环链表双向链表其他线性链表第70页/共103页zhaoqiansunlizhou0123456123450头结点数组序号数据元

26、素信息指向下一个元素在数组中的相对位置空表:001.静态链表某些语言不支持指针类型，通常使用一维数组描述单链表。第71页/共103页类型表示:#defineMAXSIZE1000typedefstructElemTypedata；intcur；component，SLinkListMAXSIZE；data表示数据元素信息；cur代替指针指示结点在数组中的相对位置。第72页/共103页zhaoqiansunlizhou0123456143520插入和删除操作1)在第i=4个结点前插入新元素jin添加新元素jin，并指向原第i=4个结点jin3修改第3个结点的指向找到第i-1=3个结点，记住第i=

27、4个结点的位置33 6第73页/共103页2)删除第2个结点zhaoqiansunlizhou0123456123450jin46找到第2个结点，记住下一个结点的位置找到第1个结点33修改指向第74页/共103页2.循环链表表中最后一个节点的指针域指向头结点，形成一个环。a1anHead0空表:Head从表的任意结点出发均可以找到表中的其他结点。优点:Head-next=head第75页/共103页例，取循环链表第i个元素。p=L-next；j=1；while(pL&jnext；+j；if(p=L|ji)returnERROR；e=p-data；returnOK；StatusGetElem_L

28、(LinkListL，inti，ElemType&e)操作与线性单链表基本一致，差别只是在于算法中的循环结束条件不是p是否为空，而是p是否等于头指针。第76页/共103页有时为了方便某些操作，通常在循环链表中设立尾指针。Tail1Tail2Tail1-next=pTail2-next=Tail1-nextp=Tail2-nextp例如顺次合并两个线性表。第77页/共103页3.双向链表在循环链表中寻找结点的直接后继很简单，只需要O(1)；但要寻找结点的直接前趋就要从表头指针找起，需要O(n)。双向链表的结点有两个指针域:一个指向直接后继，一个指向直接前趋。priordatanext第78页/共

29、103页 类型表示:typedefstructDuLNodeElemTypedata；structDuLNode*prior；structDuLNode*next；DuLNode，*DuLinkList；priordatanext第79页/共103页ACHeadB性质:设d是指向某个结点的指针，则有dd-next-prior=d-prior-next=d操作:只涉及单向的操作与单链基本相同，但插入、删除操作变化很大。第80页/共103页 空表:Head指令第81页/共103页1)插入Xs第一步：找到要在之前插入的结点，p记录。第一步：1.s-prior=p-prior；2.p-prior-ne

30、xt=s；3.s-next=p；4.p-prior=s；ABp一定注意指令的顺序！2134第82页/共103页2)删除ACB1.找到要删除的结点，p记录。p2.p-prior-next=p-next；3.p-next-prior=p-prior；4.free(p)；第83页/共103页数学表示:Pn(x)=p0+p1x+p2x2+pnxn计算机表示:P=(p0，p1，p2，pn)可以描述为一个由n+1个系数构成的线性表。多项式相加:设Pn(x):P=(p0，p1，p2，pn)Qm(x):Q=(q0，q1，q2，qm)mexpoqb-expo，qa所指向的结点应插入和多项式中qa-expoqb-

31、expo，qb所指向的结点应插入和多项式中qa-expoqb-expo，求和qa-coef+qb-coef和0，释放qa和qb所指结点；和0，修改qa所指结点的系数值，释放qb所指结点；Pa-113520-2head1head2-13952740Pb第89页/共103页qa=Pa-next；qb=Pb-next；case:/插入qa结点casenext=qa?qa:qb；/处理剩余部分ha=Pa；hb=Pb；第90页/共103页case:ha=qa；qa=qa-next；break；qaqb357haqaha第91页/共103页casenext=qb-next；qb=hb-next；ha=ha

32、-next；break；ha-next=qb；qb-next=qa；qaqb537ha8hbqbha第92页/共103页case0:qaqb337ha8hbqbqa2-2第93页/共103页sum=qa.coef+qb.coef；if(sum!=0.0)qa.coef=sum；elsehb-next=qb-next；Free(qb)；qb=hb-next；/释放qbha=qa；qa=hb-next；/后移qabreak；hb-next=qb-next；Free(qb)；qb=hb-next；/释放qbha-next=qa-next；Free(qa)；qa=ha-next；/释放qacase0:

33、第94页/共103页Pa-113520-2Pb-13952740，ha，hbqaqb13haqb5=50qbqa第95页/共103页两个一元多项式相乘:M(x)=A(x)B(x)=A(x)b1x+b2x+bnxe1e2en=biA(x)xeini=1第96页/共103页基本操作：插入、删除、查找、建表1：在表长大于1的单循环链表中，查找P结点的直接前驱结点，设计算法实现。思路拓展:熟练掌握基本操作，举一反三：Ha1a2a3aianqpa4a2a3a4 第97页/共103页2：链表的逆置问题。3：链表的合并问题（注意空间和时间的要求）4：结构的选择问题。5：链表的起始条件，判断条件，特点等顺序表

34、和链表逆置第98页/共103页作业1:2.编写一个程序(源码),创建一个带表头结点的单链表.要求:链表长度为大于5 并打印出来,再删除顺序表中的第3个元素并打印出删除后的结果.(3个函数+主程序)1、引入头结点的原因？引入头结点的原因？第99页/共103页1：在表长大于1的单循环链表中，查找P结点的直接前驱结点，设计算法实现。2、思考：如何逆置一个单链表？3、P182.244、设计算法：删除带表头结点的双向循环链表中所有的值为x的结点。作业2第100页/共103页约瑟夫环问题第101页/共103页学习要点:线性表的定义、结构特点线性表的顺序存储、链式存储线性表的基本操作(顺序表、单链表)第102页/共103页感谢您的观看！第103页/共103页