310计1 4-循环链表与双向链表及线性表的应用举例.ppt

《310计1 4-循环链表与双向链表及线性表的应用举例.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章　线性表（相应教材范围2.3.2-2.4）教学主题：循环链表与双向链表及线性表的应用举例教学内容：2.3.2循环链表；2.3.3双向链表；2.4一元多项式的表示及相加教学目的：掌握循环链表的概念；掌握双向链表的的表示与实现；线性表的应用举例教学重点：双向链表的的表示与实现；线性表的应用举例教学难点：双向链表的存储表示；线性表的应用举例教学课时：22.3.2循环链表循环链表（CircularlinkedList)时一种头尾相接的链表。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此从表中任一结点出发均可找到表中其它结点。单循环链表：在单链表中，将终端

2、结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。循环链表的操作和线性表基本一致，差别仅在于算法中的循环条件不是p或者p—>next是否为空，而是它们是否等于头指针。在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rear–>next)—>next和rear，显然，查找

3、时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—>next是否为空，而是判断它们是否等某一指定指针，如头指什或尾指针等。。例、在链表上实现将两个线性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)链接成一个线性表的运算。linklistconnect(linklistheada，linklistheadb){linklistp=heada—>next;heada—>next=(headb—next)—>nextfree(headb—>next);headb—

4、>next=p;return(headb);}2.3.3双链表链式存储结构的结点中只有一个指示直接后继的指针域，因此从某个结点出发只能顺时针往后寻查其它结点。若要寻查结点的直接前趋，则须从表头指针出发。双向链表(Doublelinkedlist):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：typedefstructDuLNode{ElemTypedata;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList;2.3.3双

5、链表链式存储结构的结点中只有一个指示直接后继的指针域，因此从某个结点出发只能顺时针往后寻查其它结点。若要寻查结点的直接前趋，则须从表头指针出发。双向链表(Doublelinkedlist):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：typedefstructDuLNode{ElemTypedata;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList;和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上

6、的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。设指针p指向某一结点，则双向链表结构的对称性可用下式描述：(p—>prior)—>next=p=(p—>next)—>prior，即结点*p的存储位置既存放在其前趋结点*(p—>prior)的直接后继指针域中，也存放在它的后继结点*(p—>next)的直接前趋指针域中。在双向链表中，有些操作如：ListLength、GetElem和LocateElem等仅需涉及一个方向的指针，则它们的算法描述和线性表的操作相同，但在插入、删除时有很大的不同，在双向链表中需同时修改两个方向的指针。下图2.15、2

7、.16所示为在带头结点的双链循环线性表中第i个位置之前插入元素e和删除带头结点的双链循环线性表L的第i个元素的情况。双向链表的前插操作算法如下：voiddinsertbefor(dlistnode*p，datatypex){dlistnode*q=malloc(sizeof(dlistnode));q—>data=x;q—>prior=p—>prior;q—>next=p;p—>prior—>next=q;p—>prior=q;}双向链表的删除操作算法如下：voidddeletenode(