数据结构04线性表

第二章线性表提纲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语言算法linklist*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)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)//删除了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双向链表a0a1……an-1head(c)非空的双循环链表双链表一般由头指针唯一确定，增加头结点也能使双链表上的某些运算变的方便，将头结点和尾结点链接起来也能构成循环链表，称之为双（向）循环链表。如下图所示：2.5双向链表若p为指向双向链表中的某一个结点ai的指针，则双链表结构的对称性可用下式刻化：p-prior-next＝p=p-next-prior在双向链表中，有些操作如：求长度、取元素、定位等，因仅需涉及一个方向的指针，故它们的算法与线性链表的操作相同；但在插入、删除时，则需同时修改两个方向上的指针，两者的操作的时间复杂度均为O(n)。双向链表的插入和删除操作（1）在双向链表中插入一个结点在双向链表的第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=rlink(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双向链表节点删除算法：procedureDeleteData(list,x)q=rlink(list)//q是第一个节点while(q!=listanddata(q)x)//查询x节点q=rlink(q)endifq=listthen[print(“x不存在”);returnrlink(llink(p))=rlink(p)llink(rlink(q))=llink(p)end2.6链表应用一元多项式的表示及相加符号多项式的表示及其操作是线性表处理的典型用例，在数学上，一个一元多项式Pn(x)可以表示为：Pn(x)=anxn+a2x2+a1x+…+a0(最多有n+1项)aixi是多项式的第i项（0≤i≤n），其中ai为系数，x为变量，i为指数。它有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采用顺序存储结构，也可以采用链表存储结构。使用顺序存储结构可以使多项式相加的算法十分简单。但是，当多项式中存在大量的零系数时，这种表示方式就会浪费在量存储空间。为了有效而合理地利用存储空间，可以用链式存储结构来表示多项式。2.6链表应用ATTACH算法：procedureATTACH(co,ex,r)//co,ex分别为多项式中某项的系数和指数，r为结果链表最后节点的指针callGETNODE(w)//生成新节点exp(w)excoef(w)colink(r)wrwend2.6链表应用多项式相加算法：procedurePADD(A,B,C)pAqBcallGETNODE(C)rCwhile(pnilandqnil)docase::exp(p)=exp(q)://指数相同的情况下x=coef(q)+coef(p)if(x0)callATTACH(x,exp(p),r)plink(p)qlink(q)2.6链表应用case::exp(p)exp(q)://B当前项的指数更大callATTACH(coef(q),exp(q),r)qlink(q)else:callATTACH(coef(p),exp(p),r)plink(p)end//endcaseend//endwhile2.6链表应用while(pnil)do//将A(x)的剩余项加入CcallATTACH(coef(p),exp(p),r)plink(p)end//endcase//将B(x)的剩余项加入Cwhile(qnil)docallATTACH(coef(q),exp(q),r)qlink(q)end//endcaselink(r)nil//最后指针为空//释放最初为C链表申请的空节点tCclink(t)callRET(t)end2.6链表应用讨论一元多项式加法的其它存储方法及算法