数据结构04线性表.ppt

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

1、第二章线性表提纲2.4循环链表2.5双向链表2.6链表应用2.4循环链表（1）问题的提出单链表2.4.1循环链表概念循环链表(CircularLinkedList)是另一种形式的链式存储结构。是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，这样从表中任一结点出发都可找到表中其他的结点。带头结点的单循环链表如下图所示a1a2anaiheadhead2.4.2循环链表应用例：在链表上实现将两个线性表(a1,a2,…,an)和(b1,b2,…,bn)链结成一个线性表（a1,a2,…,an,b1,b2,…,bn）2.4.2循环链表应用图1学生成绩表C语言算法linkl

2、ist*connect(linklist*ra,linklist*rb){linklist*p;p=ra->next;ra->next=rb->next->next;free(rb->next);rb->next=p;returnrb;}2.4.2循环链表应用_约瑟夫问题抽取关键信息：n个人圆桌编号k报到m的人出列数据结构模拟：循环表第一次报数时，需要用到表头2.4.2循环链表应用_约瑟夫问题ProcedureJOESEHU(list,n,m,k)listnil//创建空表fori1tondo//建立n个节点的单链表callGETNODE(p)//申请一个新空间节点data(p)

3、iiflist=nillist=pelselink（r）p//r是尾节点指针rpendlink(p)list//最后节点指向头节点//循环链表建立完成2.4.2循环链表应用_约瑟夫问题//下面遍历刚建立的循环表，查找起始报数人员plist//指针p指向头节点fori1tok-1do//跳过前面k-1个节点rpplink(r)end//此时p指向第一报数节点whilelink(p)<>pdo//最后一个节点判断fori1tom-1do//遍历计数，查询第个节点rpp=link(p)end//此时，r指向第m-1节点，p指向m节点link（r）link(p)//删除

4、了p指向的节点print(data(p))//callRET(p)plink(r)endprint(data(p))end2.5双向链表循环链表的不足删除节点、插入节点时，为了获得某节点的直接前驱，都要从表头遍历链表解决问题的办法双向链表2.5双向链表在双向链表中，每一个结点除了数据域外，还包含两个指针域，一个指针（next）指向该结点的后继结点，另一个指针（prior）指向它的前驱结点双向链表的C结构定义如下：typedefstructDnode{datatypedata;structDnode*prior,*next;}DLinkList;DLinkList*head;2.5双

5、向链表a0a1……an-1head(c)非空的双循环链表双链表一般由头指针唯一确定，增加头结点也能使双链表上的某些运算变的方便，将头结点和尾结点链接起来也能构成循环链表，称之为双（向）循环链表。如下图所示：2.5双向链表若p为指向双向链表中的某一个结点ai的指针，则双链表结构的对称性可用下式刻化：p->prior->next＝p=p->next->prior在双向链表中，有些操作如：求长度、取元素、定位等，因仅需涉及一个方向的指针，故它们的算法与线性链表的操作相同；但在插入、删除时，则需同时修改两个方向上的指针，两者的操作的时间复杂度均为O(n)。双向链表的插入和删除操作（1）在双向

6、链表中插入一个结点在双向链表的第i个元素前插入一个结点时，可用指针p指该结点（称p结点），先将新结点的prior指向p结点的前一个结点，其次将p结点的前一个结点的next指向新结点，然后将新结点的next指向p结点，最后将p结点的prior指向新结点。操作过程如下图所示。2.5双向链表(a)插入前（b）插入后图在双向链表中插入结点ai-1ais∧x∧pai-1aip①②③④sx2.5双向链表节点插入算法：procedureInsertData(list,x,item)q=rlink(list)//q是第一个节点while(q!=listanddata(q)<>x)//查询x节点q=r

7、link(q)endifq=listthen[print(“x不存在”);return]callGETNODE(p)//生成新节点pdata(p)=item//赋值数据llink(p)=q//新节点左指针指向Xrlink(p)=rlink(q)//新节点右指针指向x节点的右节点rlink(q)=p//X节点右指针指向新节点llink(rlink(q))=p//原来X节点的右节点的左指针指向新节点end2.5双向链表节点删除算法：procedureDelet