《数据结构04线性表》由会员分享，可在线阅读，更多相关《数据结构04线性表（21页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表,提纲2.4 循环链表2.5 双向链表2.6 链表应用,2.4 循环链表,（1） 问题的提出单链表,2.4.1 循环链表概念,循环链表(Circular Linked List)是另一种形式的链式存储结构。是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，这样从表中任一结点出发都可找到表中其他的结点。带头结点的单循环链表如下图所示,head,head,2.4.2 循环链表应用,例：在链表上实现将两个线性表(a1,a2,an)和(b1,b2,bn)链结成一个线性表（ a1,a2,an , b1,b2,bn ）,2.4.2 循环链表应用,图1 学生成绩表,C语言
2、算法 linklist *connect(linklist *ra,linklist *rb)linklist *p;p=ra-next;ra-next=rb-next-next;free(rb-next);rb-next=p;return rb;,2.4.2 循环链表应用_约瑟夫问题,抽取关键信息：n个人圆桌编号k报到m的人出列数据结构模拟：循环表第一次报数时，需要用到表头,2.4.2 循环链表应用_约瑟夫问题,Procedure JOESEHU(list,n,m,k)listnil /创建空表for i 1 to n do /建立n个节点的单链表call GETNODE(p) /申请一个新
3、空间节点data(p) iif list=nillist = pelselink（r） p /r是尾节点指针r pendlink(p) list /最后节点指向头节点/循环链表建立完成,2.4.2 循环链表应用_约瑟夫问题,/下面遍历刚建立的循环表，查找起始报数人员 p list /指针p指向头节点for i 1 to k-1 do /跳过前面k-1个节点r pp link( r )end/此时p指向第一报数节点while link(p)p do /最后一个节点判断for i 1 to m-1 do /遍历计数，查询第个节点r pp=link(p)end/此时，r指向第m-1节点，p指向m节点
4、link（r） link(p) /删除了p指向的节点print(data(p) /call RET(p)p link( r)endprint(data(p) end,2.5 双向链表,循环链表的不足删除节点、插入节点时，为了获得某节点的直接前驱，都要从表头遍历链表 解决问题的办法双向链表,2.5 双向链表,在双向链表中，每一个结点除了数据域外，还包含两个指针域，一个指针（next）指向该结点的后继结点，另一个指针（prior）指向它的前驱结点双向链表的C结构定义如下：typedef struct Dnode datatype data;struct Dnode *prior,*next; DL
5、inkList;DLinkList *head;,2.5 双向链表,a0,a1, ,an-1,head,(c) 非空的双循环链表,双链表一般由头指针唯一确定，增加头结点也能使双链表上的某些运算变的方便，将头 结点和尾结点链接起来也能构成循环链表，称之为双（向）循环链表。如下图所示：,2.5 双向链表,若p为指向双向链表中的某一个结点ai的指针，则双链表结构的对称性可用下式刻化：p-prior-next p= p-next-prior在双向链表中，有些操作如：求长度、取元素、定位等，因仅需涉及一个方向的指针，故它们的算法与线性链表的操作相同；但在插入、删除时，则需同时修改两个方向上的指针，两者的
6、操作的时间复杂度均为O(n)。双向链表的插入和删除操作（1）在双向链表中插入一个结点在双向链表的第i个元素前插入一个结点时，可用指针p指该结点（称p结 点），先将新结点的prior指向p结点的前一个结点，其次将p结点的前一个结 点的next指向新结点，然后将新结点的next指向p结点，最后将p结点的prior 指向新结点。操作过程如下图所示。,2.5 双向链表,(a)插入前 （b）插入后图 在双向链表中插入结点,ai-1,ai,s x ,p,ai-1,ai,p, ,s x,2.5 双向链表,节点插入算法：procedure InsertData(list,x,item)q=rlink( lis
7、t) /q是第一个节点while (q!=list and data(q)x) /查询x节点q=rlink(q)end if q=list thenprint(“x不存在”);returncall GETNODE(p) /生成新节点pdata(p)=item /赋值数据llink(p)=q /新节点左指针指向Xrlink(p)=rlink(q) /新节点右指针指向 x节点的右节点rlink(q) = p /X节点右指针指向新节点llink(rlink(q)=p /原来X节点的右节点的左指针指向新节点 end,2.5 双向链表,节点删除算法：procedure DeleteData(list,x
8、)q=rlink( list) /q是第一个节点while (q!=list and data(q)x) /查询x节点q=rlink(q)end if q=list thenprint(“x不存在”);returnrlink(llink(p)=rlink(p) llink(rlink(q)=llink(p) end,2.6 链表应用,一元多项式的表示及相加 符号多项式的表示及其操作是线性表处理的典型用例，在数学上，一个一元 多项式Pn(x) 可以表示为 ：Pn(x)= anxn +a2x2+a1x+a0 (最多有n+1项) aixi是多项式的第i项（0in），其中ai为系数，x为变量，i为指数
9、。 它有n+1个系数，因此，在计算机里，它可用一个线性表P来表示： P=（ an, a2,a1, ，a0） 假设Qn(x)是一元m次多项式，同样可用线性表Q来示： Q=（ bm, b2,b1, ， b0） 若mn，则两个多项式相加的结果Rn(x)= Pn(x)+ Qn(x)可用线性表R来表示： R=（ an , am+1 , am+ bm , , a2+b2,a1+ b1,a0+ b0 ） 可以对P、Q和R采用顺序存储结构，也可以采用链表存储结构。使用顺序存 储结构可以使多项式相加的算法十分简单。但是，当多项式中存在大量的零 系数时，这种表示方式就会浪费在量存储空间。为了有效而合理地利用存储
10、空间，可以用链式存储结构来表示多项式。,2.6 链表应用,ATTACH算法：procedure ATTACH(co, ex,r)/co,ex分别为多项式中某项的系数和指数，r为结果链表最后节点的指针call GETNODE(w) /生成新节点exp(w) excoef(w) colink( r) wr w end,2.6 链表应用,多项式相加算法：procedure PADD(A,B,C)p Aq Bcall GETNODE(C )r Cwhile (p nil and qnil) docase:exp(p)=exp(q): /指数相同的情况下x=coef(q)+coef(p)if (x0)c
11、all ATTACH(x,exp(p),r)plink(p)q link(q),2.6 链表应用,case:exp(p)exp(q): /B当前项的指数更大call ATTACH(coef(q),exp(q),r)q link(q)else:call ATTACH(coef(p),exp(p),r)p link(p)end /end caseend /end while,2.6 链表应用,while (pnil) do /将A(x)的剩余项加入Ccall ATTACH(coef(p),exp(p),r)p link(p)end /end case/将B(x)的剩余项加入Cwhile (qnil) docall ATTACH(coef(q),exp(q),r)q link(q)end /end case link( r) nil /最后指针为空/释放最初为C链表申请的空节点tCc link(t)call RET(t) end,2.6 链表应用,讨论 一元多项式加法的其它存储方法及算法,
