第04講循環(huán)鏈表

1、 一、循環(huán)鏈表一、循環(huán)鏈表 二、雙向鏈表二、雙向鏈表 三、鏈表的應(yīng)用三、鏈表的應(yīng)用難點難點HaHbpapbqbqa（1）Ha的指數(shù)小的指數(shù)?。?）Hb的指數(shù)小的指數(shù)小（3）Ha與與Hb的指數(shù)相等的指數(shù)相等1）系數(shù)相加不為）系數(shù)相加不為02）系數(shù)相加為）系數(shù)相加為01、已知一個單鏈表，編寫一個刪除其值為、已知一個單鏈表，編寫一個刪除其值為x的的結(jié)點的前趨結(jié)點的結(jié)點的前趨結(jié)點的。1)若若x在第一個在第一個Position nextPtr-data=x2)若若x在中間在中間 nextPtr-next-data=x3)若若x不存在不存在 nextPtr-next=NULLheada1a2a3a4tmp

2、PtrnextPtr整個鏈表形成一個環(huán)，從表中任一結(jié)整個鏈表形成一個環(huán)，從表中任一結(jié)點出發(fā)均可找到表中其它結(jié)點。點出發(fā)均可找到表中其它結(jié)點。（1）表中最后一個結(jié)點的指針指向第一個結(jié)點或）表中最后一個結(jié)點的指針指向第一個結(jié)點或表頭結(jié)點（如有表頭結(jié)點的話）。表頭結(jié)點（如有表頭結(jié)點的話）。（2）循環(huán)鏈表的運算與線性鏈表基本一致。但兩）循環(huán)鏈表的運算與線性鏈表基本一致。但兩者判斷是否到表尾的條件不同。者判斷是否到表尾的條件不同。headhead非空循環(huán)鏈表非空循環(huán)鏈表空循環(huán)鏈表空循環(huán)鏈表rearrear簡單循環(huán)鏈表類簡單循環(huán)鏈表類注意與單鏈表算法實現(xiàn)的區(qū)別注意與單鏈表算法實現(xiàn)的區(qū)別兩個單循環(huán)鏈表（用尾

3、指針表示）的鏈接示意圖兩個單循環(huán)鏈表（用尾指針表示）的鏈接示意圖rarbp思考思考: : 如何將其合并如何將其合并? ?p=rb-next; rb-next=ra-next;ra-next=p-next;幾個方法的實現(xiàn)幾個方法的實現(xiàn)幾個方法的實現(xiàn)幾個方法的實現(xiàn)幾個方法的實現(xiàn)幾個方法的實現(xiàn)幾個方法的實現(xiàn)幾個方法的實現(xiàn)例例2.5 用循環(huán)鏈表求解約瑟夫問題用循環(huán)鏈表求解約瑟夫問題例例2.5 用循環(huán)鏈表求解約瑟夫問題用循環(huán)鏈表求解約瑟夫問題例例2.5 用循環(huán)鏈表求解約瑟夫問題用循環(huán)鏈表求解約瑟夫問題單鏈表的每個結(jié)點再增加一個指向其單鏈表的每個結(jié)點再增加一個指向其前趨的指針域前趨的指針域 back，這樣

4、形成的鏈表有兩條不這樣形成的鏈表有兩條不同方向的鏈，稱之為雙（向）鏈表。同方向的鏈，稱之為雙（向）鏈表。雙鏈表一般也由頭指針雙鏈表一般也由頭指針head唯一確定。唯一確定。每一結(jié)點均有：每一結(jié)點均有： 數(shù)據(jù)域（數(shù)據(jù)域（data） 左鏈域（左鏈域（back）指向前趨結(jié)點）指向前趨結(jié)點. 右鏈域（右鏈域（next）指向后繼。）指向后繼。 是一種對稱結(jié)構(gòu)（既有前趨，又有后繼）。是一種對稱結(jié)構(gòu)（既有前趨，又有后繼）。 雙向鏈表結(jié)點結(jié)構(gòu)雙向鏈表結(jié)點結(jié)構(gòu)struct DblNode ElemType data; DblNode * back; DblNode * next; ; 雙向鏈表舉例雙向鏈表舉例雙

5、向鏈表結(jié)點的插入雙向鏈表結(jié)點的插入597pq nnewPtrnewPtr-back = nextPtrback = nextPtr-back newPtr-next=nexPtrback newPtr-next=nexPtrn用一條語句實現(xiàn)即：用一條語句實現(xiàn)即：newPtr=new DblNode(e,tmpPtr,nextPtrnewPtr=new DblNode(e,tmpPtr,nextPtr); );nnextPtrnextPtr-back-next = newPtr nextPtr-back=newPtrback-next = newPtr nextPtr-back=newPtrne

6、xtPtrtmpPtrnewPtr雙向鏈表結(jié)點的刪除雙向鏈表結(jié)點的刪除 p 597ntmpPtrtmpPtr-backback-next = tmpPtrnext = tmpPtr-nextnextntmpPtrtmpPtr-nextnext-back = tmpPtrback = tmpPtr-backbacktmpPtr在鏈表結(jié)構(gòu)中保存當前位置和元素個數(shù)在鏈表結(jié)構(gòu)中保存當前位置和元素個數(shù) 線性表的三種鏈式存儲結(jié)構(gòu)特點：線性表的三種鏈式存儲結(jié)構(gòu)特點：實現(xiàn)較一致，處實現(xiàn)較一致，處理亦簡單，但效率低下。理亦簡單，但效率低下。原因：原因：許多應(yīng)用程序是按順序處理線性表的中數(shù)據(jù)許多應(yīng)用程序是按順序處

7、理線性表的中數(shù)據(jù)元素的，也就是處理完一個數(shù)據(jù)元素后再處理下一元素的，也就是處理完一個數(shù)據(jù)元素后再處理下一個數(shù)據(jù)元素，也可能要幾次引用同一個數(shù)據(jù)元素，個數(shù)據(jù)元素，也可能要幾次引用同一個數(shù)據(jù)元素，比如在訪問下一個數(shù)據(jù)元素之前做比如在訪問下一個數(shù)據(jù)元素之前做GetElem和和SetElem操作，對于這類應(yīng)用程序，前面的鏈表實現(xiàn)操作，對于這類應(yīng)用程序，前面的鏈表實現(xiàn)效率低下。效率低下。解決：解決：在鏈表結(jié)構(gòu)中保存當前位置和元素個數(shù)。在鏈表結(jié)構(gòu)中保存當前位置和元素個數(shù)。 假設(shè)一個單循環(huán)鏈表，其結(jié)點含有三個域假設(shè)一個單循環(huán)鏈表，其結(jié)點含有三個域back、data、next。其中。其中data為數(shù)據(jù)域；為數(shù)

8、據(jù)域；back為指針域，它的值為空指針（為指針域，它的值為空指針（NULL）；）；next為為指針域，它指向后繼結(jié)點。請設(shè)計算法，將此指針域，它指向后繼結(jié)點。請設(shè)計算法，將此表改成雙向循環(huán)鏈表。表改成雙向循環(huán)鏈表?！疚靼搽娮涌萍即髮W(xué)【西安電子科技大學(xué) 1999軟考軟考 五（五（10分）分）】 a b z La a b z Lavoid StoDouble(SimpleLinkList &la) while(La-next-back=NULL) La-next-back=La; La=La-next; 算法中沒有設(shè)置變量記住單循環(huán)鏈表的起始結(jié)點，算法中沒有設(shè)置變量記住單循環(huán)鏈表的起始結(jié)點，至少省

9、去了一個指針變量。當算法結(jié)束時，至少省去了一個指針變量。當算法結(jié)束時，La恢復(fù)到指恢復(fù)到指向剛開始操作的結(jié)點，這是本算法的優(yōu)點所在。向剛開始操作的結(jié)點，這是本算法的優(yōu)點所在。haqpa-14 151 7-3 0（1）pa所指結(jié)點的指數(shù)要減所指結(jié)點的指數(shù)要減1（2）pa所指結(jié)點的系數(shù)所指結(jié)點的系數(shù)=系數(shù)系數(shù)*指數(shù)指數(shù)（3）若）若pa所指結(jié)點的指數(shù)為所指結(jié)點的指數(shù)為0，則要刪除該結(jié)點，則要刪除該結(jié)點void derivative(SimpleCircLinkList &ha) Node *q, *pa; q=ha; pa=ha-next; while( (1) ) if( (2) ) (3) ;

10、delete pa; pa= (4) ; else pa-coef (5) ; pa-exp (6) ; q=(7) ; pa= (8) ; void derivative(SimpleCircLinkList &ha) Node *q, *pa; q=ha; pa=ha-next; while( pa!=ha ) /pa-exp!=-1 if( pa-exp=0 ) q-next=pa-next ; delete pa; pa= q-next ; else pa-coef *=pa-exp ; pa-exp - - ; q=pa ; pa= pa-next ; 一線性表存儲在帶頭結(jié)點的雙向循

11、環(huán)鏈表中，一線性表存儲在帶頭結(jié)點的雙向循環(huán)鏈表中，L為頭指針。如下算法：為頭指針。如下算法：（1）說明該算法的功能。（）說明該算法的功能。（2）在空缺處填寫）在空缺處填寫相應(yīng)的語句。相應(yīng)的語句。 【北京理工大學(xué)【北京理工大學(xué) 1999 第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 7 （8分）分）】void unknown (BNODETP &L) p=L-next; q=p-next; r=q-next； while (q!=L) while (p!=L) & (p-dataq-data) p=p-back； q-back-next=r；(1) ； q-next=p-next；q-back=p； (2

12、) ；(3) ； q=r；p=q-back； (4) ； void unknown (BNODETP &L) p=L-next; q=p-next; r=q-next； while (q!=L) while (p!=L) & (p-dataq-data) p=p-back； q-back-next=r； r-back=q-back ； q-next=p-next；q-back=p； p-next-back=q ； p-next=q ； q=r；p=q-back； r=r-next； 將雙循環(huán)鏈表結(jié)點的數(shù)據(jù)按值從小到大排序。將雙循環(huán)鏈表結(jié)點的數(shù)據(jù)按值從小到大排序。設(shè)有一頭指針為設(shè)有一頭指針為L的

13、帶有表頭結(jié)點的非循環(huán)雙向鏈表，的帶有表頭結(jié)點的非循環(huán)雙向鏈表，其每個結(jié)點中除有其每個結(jié)點中除有back（前驅(qū)指針），（前驅(qū)指針），data（數(shù)據(jù)）（數(shù)據(jù)）和和next（后繼指針）域外，還有一個訪問頻度域（后繼指針）域外，還有一個訪問頻度域freq。在鏈表被起用前，其值均初始化為零。每當在鏈表中進在鏈表被起用前，其值均初始化為零。每當在鏈表中進行一次行一次Locate(L,x)運算時，令元素值為運算時，令元素值為x的結(jié)點中的結(jié)點中freq域的值增域的值增1，并使此鏈表中結(jié)點保持按訪問頻度非增，并使此鏈表中結(jié)點保持按訪問頻度非增（遞減）的順序排列，同時最近訪問的結(jié)點排在頻度相（遞減）的順序排列，同

14、時最近訪問的結(jié)點排在頻度相同的結(jié)點的最后，以便使頻繁訪問的結(jié)點總是靠近表頭。同的結(jié)點的最后，以便使頻繁訪問的結(jié)點總是靠近表頭。試編寫符合上述要求的試編寫符合上述要求的Locate(L,x)運算的算法，該運運算的算法，該運算為函數(shù)過程，返回找到結(jié)點的地址，類型為指針型。算為函數(shù)過程，返回找到結(jié)點的地址，類型為指針型。【清華大學(xué)【清華大學(xué) 考研考研 1997 二（二（10分）分） 】查找是否存在查找是否存在x不存在則結(jié)束程序不存在則結(jié)束程序若存在若存在頻度增頻度增1將將x結(jié)點刪除結(jié)點刪除向前找合適的插入位置向前找合適的插入位置將將x結(jié)點插入結(jié)點插入分析分析DLinkNode *Locate(DLinkNode &L, ElemType &x) DLinkNode *p=L-next, q; while(p!=NULL & p-data!=x) p=p-next; if(p=NULL) coutfreq+; p-next-back=p-back; p-back-next=p-n