循環(huán)鏈表和雙向鏈表

1、數(shù)據(jù)結(jié)構(gòu)與算法 -第五講王倫津 研究員循環(huán)鏈表、雙向鏈表及線性表應(yīng)用示例15、循環(huán)鏈表和雙向鏈表本講重點(diǎn)：帶頭結(jié)點(diǎn)的鏈表、循環(huán)鏈表和雙向鏈表的特征，基本運(yùn)算。對(duì)于循環(huán)鏈表要突出掌握判斷鏈表空滿的條件；雙向鏈表要強(qiáng)調(diào)插入和刪除算法的實(shí)現(xiàn)。最后通過多項(xiàng)式加法的示例，介紹線性表的應(yīng)用。2目 錄5.1帶頭結(jié)點(diǎn)的鏈表5.2循環(huán)鏈表5.3 雙向鏈表5.4 線性表的應(yīng)用示例35.1幾種特殊線性鏈表 5.1 帶頭結(jié)點(diǎn)的鏈表 有時(shí)候?yàn)榱颂幚砩系姆奖?，在線性鏈表的第一個(gè)結(jié)點(diǎn)的前面增設(shè)一個(gè)特殊的結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)邏輯上不屬于相應(yīng)的線性鏈表，它的作用主要有兩點(diǎn)，一是存貯一些有關(guān)線性表的信息（如表中結(jié)點(diǎn)總數(shù)），另

2、一是為了算法處理上的方便。 圖 51 帶頭結(jié)點(diǎn)的鏈表1020303 頭指針頭結(jié)點(diǎn)頭元素45.2 循環(huán)鏈表 圖5 2 循環(huán)單鏈表示意20(a) 不帶頭結(jié)點(diǎn)(b) 帶頭結(jié)點(diǎn)10303 在線性表中，如果我們將第1 個(gè)結(jié)點(diǎn)視為最后一個(gè)結(jié)點(diǎn)的后繼，將最后一個(gè)結(jié)點(diǎn)視為第1個(gè)結(jié)點(diǎn)的前趨，則這種線性表稱為循環(huán)線性表，相應(yīng)的鏈表稱循環(huán)線性鏈表（簡(jiǎn)稱循環(huán)鏈表）。 10203055.3 雙向鏈表 為單向鏈表的每個(gè)結(jié)點(diǎn)增設(shè)一個(gè)指向相應(yīng)結(jié)點(diǎn)的前趨的指針，使其同時(shí)包含前驅(qū)和后繼，這樣的鏈表稱為雙向鏈表（簡(jiǎn)稱雙鏈表）。雙向鏈表的結(jié)點(diǎn)的結(jié)構(gòu)如下所示： 這里各項(xiàng)含義為：info- 存放元素內(nèi)容；next-存放該元素的后繼的指針

3、（地址）；prior-存放該元素的前驅(qū)的指針（地址）；priorinfonext6循環(huán)單鏈表是單鏈表的另一種形式，其結(jié)構(gòu)特點(diǎn)是鏈表中最后一個(gè)結(jié)點(diǎn)的指針不再是結(jié)束標(biāo)記，而是指向整個(gè)鏈表的第一個(gè)結(jié)點(diǎn)，從而使單鏈表形成一個(gè)環(huán)。和單鏈表相比，循環(huán)單鏈表的長(zhǎng)處是從鏈尾到鏈頭比較方便。當(dāng)要處理的數(shù)據(jù)元素序列具有環(huán)型結(jié)構(gòu)特點(diǎn)時(shí)，適合于采用循環(huán)單鏈表。循環(huán)鏈表的插入、刪除運(yùn)算基本同單向鏈表，只是查找時(shí)判別條件不同而已；但是這種循環(huán)鏈表實(shí)現(xiàn)各種運(yùn)算時(shí)的危險(xiǎn)之處在于：鏈表沒有明顯的尾端，可能使算法進(jìn)入死循環(huán)，所以判斷條件應(yīng)該用curr.next()!=head替換單向鏈表的curr.next()!=null完成遍

4、歷所有結(jié)點(diǎn)。7（一）雙鏈表的插入 現(xiàn)設(shè)在結(jié)點(diǎn)p之前插入結(jié)點(diǎn)q，其程序片段如下。(1)q-next=p; /讓q的next指向p (2) q-prior=p-prior;(3)p-prior-next=q;(4)p-prior=q;圖5 3 雙鏈表插入pp-priorp-next(4)q(3)(2)(1)注意關(guān)鍵的四個(gè)指針域的變化8(2)(1)pp-priorp-next圖 5 4雙鏈表的刪除（二）雙鏈表刪除 現(xiàn)設(shè)刪除結(jié)點(diǎn)p所指結(jié)點(diǎn)，程序片段如下。(1) p-prior-next=p-next;(2) p-next-prior=p-prior;(3) return p; 注意：關(guān)鍵的兩個(gè)指針域的

5、變化95.4 線性表應(yīng)用示例 5.4.1 集合運(yùn)算 對(duì)集合結(jié)構(gòu)，一般可用線性表表示。所以，對(duì)集合的操作，可以在線性表上進(jìn)行。 這里只從算法角度介紹一種集合運(yùn)算-(A-B)(B-A)的實(shí)現(xiàn) 為了說明前面給出的線性表類的使用，我們的實(shí)現(xiàn)在類TLinearListSqu的基礎(chǔ)上進(jìn)行。對(duì)應(yīng)的子程序如下。 10A-BB-AAB（A-B）（B-A）=（AB）-（AB）11long DiDiff(TLinearListSqu &a, TLinearListSqu &b)/將a中的出現(xiàn)在b中的元素刪除，返回從a中刪除的元素的數(shù)/目 a和b都是前面定義的線性表類，元素類型實(shí)例化為long。 long i,j,

6、k; j=0; for (i=0; i 0 ) /如在a中，則從a中將其刪除 a.Delete(k+1); j-;Else a.Insert(b.Get(i),1);j+ return j; 先在B表中取得元素i的值，然后根據(jù)該值，查找屬于A表中的第一個(gè)等于該值的序號(hào)，由于表的起始序號(hào)為0，故加1體現(xiàn)類模板的作用125.5一元多項(xiàng)式相加 (一）一元多項(xiàng)式的表示數(shù)據(jù)結(jié)構(gòu) 在數(shù)學(xué)上，一個(gè)一元n次多項(xiàng)式可表示為 Pn(x)=p0+p1x+p2x2+pnxn它由(n+1)個(gè)系數(shù)序列p0、p1、pn 唯一地確定。因此，在計(jì)算機(jī)中，它可用一個(gè)線性表P來表示：P=(p0, p1, ,pn)其中，pi代表Pn

7、(x)中的i次項(xiàng)系數(shù)。在這種表示法中，系數(shù)所對(duì)應(yīng)的指數(shù)隱含在系數(shù)的序號(hào)中，所以值為0的系數(shù)也要列出。現(xiàn)考慮兩多項(xiàng)式進(jìn)行符號(hào)相加的問題。設(shè)Qm(x)是另一個(gè)一元m次多項(xiàng)式，它的線性表表示為 Q=(q0, q1, , qm)13 為解決0系數(shù)問題，可以不存貯0值元素。但這樣就不能利用位置關(guān)系隱含指出系數(shù)對(duì)應(yīng)的指數(shù)了，而必須顯式地給出指數(shù)。 對(duì)任一個(gè)一元n次多項(xiàng)式，若不寫出系數(shù)為0的項(xiàng)，則可表示為pn(x) = p1xe1+p2xe2+ +pnxen 這里，p1, p2, , pn均非0，e1e2 en=n。 顯然，對(duì)此形式多項(xiàng)式，可確定地用下列形式的線性表表示(p1,e1), (p2,e2), ,

8、 (pn,en) ) 該線性表每個(gè)元素是個(gè)二元組(pi,ei)，分別指出第i個(gè)非0項(xiàng)的系數(shù)和指數(shù)，二元組按指數(shù)遞增的次序排列。在這種結(jié)構(gòu)中，元素之間的次序關(guān)系僅代表元素對(duì)應(yīng)的指數(shù)的大小關(guān)系。14對(duì)這種線性表，既可用順序存貯結(jié)構(gòu)，也可用鏈?zhǔn)酱尜A結(jié)構(gòu)。但考慮到在進(jìn)行符號(hào)加法時(shí)，要經(jīng)常進(jìn)行插入與刪除操作，所以采用鏈?zhǔn)酱尜A結(jié)構(gòu)較為合適。這里，我們采用動(dòng)態(tài)鏈?zhǔn)酱尜A結(jié)構(gòu)，線性表每個(gè)元素的結(jié)構(gòu)為系數(shù)指數(shù)它的C/C+語言描述為struct TPolynomialItem float coef; int exp; 該類型在我們前面給出的線性表中，相當(dāng)于元素類型TElem，在具體使用線性表類時(shí)，應(yīng)使用TPolyn

9、omialItem實(shí)例化TElem對(duì)應(yīng)的類模板 15為處理方便，在具體存儲(chǔ)多項(xiàng)式時(shí)，我們規(guī)定： 所存儲(chǔ)的多項(xiàng)式已約簡(jiǎn)，即已合并同類項(xiàng)，不保留0系數(shù)項(xiàng)，各項(xiàng)按指數(shù)的升序排列。 (二）多項(xiàng)式加法實(shí)現(xiàn)直接操作鏈表 為操作方便，我采用帶頭結(jié)點(diǎn)的非循環(huán)鏈表，下面給出一個(gè)例子說明多項(xiàng)式的這種表示法。設(shè)有一個(gè)一元5次多項(xiàng)式： P5(x)=7+3x-9x3+x5具體鏈表表示方法如圖 55 16 一元n次多項(xiàng)式的（符號(hào)）相加，實(shí)質(zhì)上是合并同類項(xiàng)的過程，即指數(shù)相同的項(xiàng)，其系數(shù)相加，指數(shù)不同的項(xiàng)復(fù)抄。7031-9 315圖 55 一個(gè)一元5次多項(xiàng)式的鏈表表示下面考慮A(x)+B(x) A(x)的實(shí)現(xiàn)方法。即將多項(xiàng)式

10、B(x)加到多項(xiàng)式A(x)上面，這里假設(shè)各多項(xiàng)式均已約簡(jiǎn)，且各項(xiàng)已按升序排列。用高級(jí)語言實(shí)現(xiàn)時(shí)，設(shè)兩個(gè)指針p和q ，初始時(shí)它們分別指向A(x)與B(x)中當(dāng)前未被處理的結(jié)點(diǎn)中指數(shù)最小者。進(jìn)行相加的過程，實(shí)質(zhì)上是重復(fù)進(jìn)行下列幾個(gè)步驟：17（1）若pexpqexp ，則結(jié)點(diǎn)q應(yīng)為和的一個(gè)結(jié)點(diǎn)，故應(yīng)將q 從B(x)中摘除后插入到A(x)中p之前，然后q向后移一步，p 不動(dòng)。（3）若pexp=qexp,則表明p與q 所指為同類項(xiàng)，應(yīng)合并，故要將q的系數(shù)加到p的系數(shù)上。若相加結(jié)果為0，則表明和式中無此項(xiàng)，故應(yīng)從A(x) 中刪除p，從B(x) 中刪除q,并令p 與q 分別指向下一結(jié)點(diǎn)。若相加和不為0，則表

11、明相加結(jié)果應(yīng)為和式中的一個(gè)結(jié)點(diǎn)，p 后移一步，然后將q從B(x) 中摘除，令q指向下一結(jié)點(diǎn)。18下面先給出算法的偽碼。p=A的第一個(gè)元素；q=B的第一個(gè)元素；while (p存在 & q存在) if (p的指數(shù) next; 在算法運(yùn)行中，B(x)的鏈表中的結(jié)點(diǎn)，或被轉(zhuǎn)移到A(x) 鏈表上，或被刪除，運(yùn)行結(jié)束后，B(x) 鏈表就不存在了，而A(x)鏈表就是所求的和。當(dāng)然，也可以設(shè)計(jì)一個(gè)將B加到A上，但保留B，或?qū)+B之和放到另一鏈表中的算法。具體留作練習(xí)。19else if (p的指數(shù) q的指數(shù)) 將q插入到p之前； 令p0指向插入后的q，即p的當(dāng)前前驅(qū); 令q指向它原所指的下一個(gè)結(jié)點(diǎn)； el

12、se x = p的系數(shù) + q的系數(shù)之和； if (x=0) 20刪除p; 使p指向它原指結(jié)點(diǎn)的下一個(gè)； else 令p的系數(shù)為x;使p指向它原指結(jié)點(diǎn)的下一個(gè)； 刪除q;使q指向它原指結(jié)點(diǎn)的下一個(gè)； / if (p的指數(shù) q的指數(shù)) else /whileif (q不為空) 將q掛接在p之后；21該程序不斷比較A鏈和B鏈中的一對(duì)結(jié)點(diǎn)的指數(shù)值（稱其為當(dāng)前結(jié)點(diǎn)）。開始時(shí)A鏈和B鏈中參加比較的當(dāng)前結(jié)點(diǎn)都是它們的第一個(gè)元素。主循環(huán)while結(jié)束后，可能出現(xiàn)下列3種情況：A鏈和B鏈同時(shí)被處理完；只有B鏈處理完；只有A鏈處理完。對(duì)第一和第二種情況，不需要“善后”處理。對(duì)第三種情況，B鏈中尚有未被處理完的結(jié)

13、點(diǎn)，需將其掛接在結(jié)果鏈的尾部。循環(huán)外的“if(q 不為空）將q掛接在p之后”就是處理該情況的。 22一元n次多項(xiàng)式加法程序PolynomialAdd如下。為了能訪問到TLinearListLink的私有成員，下面的PolynomialAdd函數(shù)應(yīng)指定為TLinearListLink的友元。int PolynomialAdd(TLinearListLink &a, TLinearListLink &b)/線性表a和b的元素類型被實(shí)例化為TPolynomialItem TLinkNode *p, *p0, *q, *q0; float x; long k; k=0; p = a.head-next

14、; p0 = a.head; q = b.head-next;為什么這里對(duì)于a、b鏈表需要兩個(gè)指針？23 while (p!=NULL & q!=NULL) if (p-exp exp) p0 = p; /永遠(yuǎn)使p0保持為p的前驅(qū)，以方便對(duì)在p前插入，或刪除p p = p-next; k+; else if (p-exp q-exp ) q0 = q; /在下面用q0操作原q q = q-next; /q先行一步 q0-next = p; p0-next = q0; / 以上兩句，將q0插入到p0之后（即p之前） k+; 24else x = p-coef + q-coef; if (x=0)

15、 p0-next = p-next; delete p; /以上兩句，將p從表中刪除并將其所指對(duì)象釋放 p = p0-next; /令p指向相對(duì)于它原指的下一個(gè) / if (x=0) else p-coef = x; p0 = p; 25p = p-next; / if (x=0) else q0 = q;q = q-next; delete q0; /將q所指結(jié)點(diǎn)從表中刪除并釋放，令q新指向原所指的下一個(gè) / if (p-exp q-exp ) else /whileif (q!=NULL) p0-next = q;b.head-next = NULL; /此時(shí)，b中已只剩第一個(gè)結(jié)點(diǎn)（頭），

16、為其置空表標(biāo)志return k; /返回結(jié)果鏈表中的元素個(gè)數(shù)26為了進(jìn)一步說明上述程序，舉一個(gè)程序運(yùn)行的例子，其各次循環(huán)的運(yùn)行結(jié)果如圖5-6所示（a）A(x)=p5(x)=7+3x2-9x3+x5，進(jìn)入循環(huán)前（b ) B(x)=3x+9x3+x5-X8，進(jìn)入循環(huán)前27（d）B(x)：第一次進(jìn)入循環(huán)后，q保持不變（c）A(x)：第一次進(jìn)入循環(huán)后，p 后移（e）A(x)：第二次進(jìn)入循環(huán)后，q被插入到p 前28（f）B(x):第二次進(jìn)入循環(huán)后，q被插入到p 前,q重新指向下一個(gè)（g）A(x)：第三次進(jìn)入循環(huán)后，p 后移（h）B(x)：第三次進(jìn)入循環(huán)后，q保持不變29（i）A(x)：第四次進(jìn)入循環(huán)后，

17、p 被刪除，重新指向下一個(gè)（j）B(x)：第四次進(jìn)入循環(huán)后，q 被刪除，重新指向下一個(gè)（k）A(x)：第五次進(jìn)入循環(huán)后，p 與q合并，p重新指向下一個(gè)(空）30（l）B(x)：第五次進(jìn)入循環(huán)后，q 合并到p，然后被刪除，重新指向下一個(gè)（m ）A(x)：退出循環(huán)后，q后面掛接了p的前驅(qū)的尾（n）B(x)：退出循環(huán)后，q掛接到了p的前驅(qū)的后面31（三）多項(xiàng)式加法實(shí)現(xiàn)借助抽象操作 下面在前面給出的TLinearListSqu類(對(duì)TLunearListLink也相同)的基礎(chǔ)上實(shí)現(xiàn)一元多項(xiàng)式相加。 首先，定義表示多項(xiàng)式的元素的類型。多項(xiàng)式的元素類型已不是象long、float等那樣的簡(jiǎn)單類型，所以必須

18、考慮如何兼容基本操作中使用的賦值（=）運(yùn)算、恒等運(yùn)算（=）和輸出運(yùn)算（coef = i1.coef; /定義多項(xiàng)式項(xiàng)賦值為指數(shù)和系數(shù)分別賦值 this-exp = i1.exp; return i1; ;ostream& operator (ostream& oo, TPolynomialItem &i1)/重載標(biāo)準(zhǔn)輸出算符，以支持Print() ooi1.coef,i1.exp ; return oo;33有了上面的定義，我們可以寫出多項(xiàng)式加法程序了：long PolynomialAdd(TLinearListSqu &a, TLinearListSqu &b) long currE1, c

19、urrE2, k; TPolynomialItem e1,e2; k=0; /記錄最終元素個(gè)數(shù) currE1=0; /記錄線性表a的元素序號(hào) currE2=0; /記錄線性表b的元素序號(hào) while (currE1 a.len & currE2b.len) e1=a.Get(currE1); /按序號(hào)取對(duì)應(yīng)元素內(nèi)容 e2=b.Get(currE2);34if (e1.exp e2.exp) a.Insert(e2,currE1+1); currE1+; b.Delete(currE2+1); k+; else e1.coef = e1.coef + e2.coef; 35if (e1.coef=0) a.Delete(currE1+1);else a.Set(currE1,e1);