數(shù)據(jù)結(jié)構(gòu)04線性表

1、第二章 線性表提綱 2.4 循環(huán)鏈表 2.5 雙向鏈表 2.6 鏈表應(yīng)用12.4 循環(huán)鏈表（1） 問題的提出 單鏈表22.4.1 循環(huán)鏈表概念循環(huán)鏈表(Circular Linked List)是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。是將單鏈表的表中最后一個(gè)結(jié)點(diǎn)指針指向鏈表的表頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，這樣從表中任一結(jié)點(diǎn)出發(fā)都可找到表中其他的結(jié)點(diǎn)。帶頭結(jié)點(diǎn)的單循環(huán)鏈表如下圖所示a1a2anai head head32.4.2 循環(huán)鏈表應(yīng)用例：在鏈表上實(shí)現(xiàn)將兩個(gè)線性表(a1,a2,an)和(b1,b2,bn)鏈結(jié)成一個(gè)線性表（ a1,a2,an , b1,b2,bn ）42.4.2 循環(huán)鏈表應(yīng)用圖1 學(xué)生

2、成績(jī)表C語(yǔ)言算法linklist *connect(linklist *ra,linklist *rb) linklist *p; p=ra-next; ra-next=rb-next-next; free(rb-next); rb-next=p; return rb; 52.4.2 循環(huán)鏈表應(yīng)用_約瑟夫問題抽取關(guān)鍵信息：n個(gè)人圓桌編號(hào)k報(bào)到m的人出列數(shù)據(jù)結(jié)構(gòu)模擬：循環(huán)表第一次報(bào)數(shù)時(shí)，需要用到表頭62.4.2 循環(huán)鏈表應(yīng)用_約瑟夫問題Procedure JOESEHU(list,n,m,k)listnil/創(chuàng)建空表for i 1 to n do/建立n個(gè)節(jié)點(diǎn)的單鏈表call GETNODE(p

3、)/申請(qǐng)一個(gè)新空間節(jié)點(diǎn)data(p) iif list=nillist = pelselink（r） p/r是尾節(jié)點(diǎn)指針r pendlink(p) list/最后節(jié)點(diǎn)指向頭節(jié)點(diǎn)/循環(huán)鏈表建立完成72.4.2 循環(huán)鏈表應(yīng)用_約瑟夫問題/下面遍歷剛建立的循環(huán)表，查找起始報(bào)數(shù)人員p list/指針p指向頭節(jié)點(diǎn)for i 1 to k-1 do /跳過前面k-1個(gè)節(jié)點(diǎn)r pp link( r )end/此時(shí)p指向第一報(bào)數(shù)節(jié)點(diǎn)while link(p)p do /最后一個(gè)節(jié)點(diǎn)判斷for i 1 to m-1 do /遍歷計(jì)數(shù)，查詢第個(gè)節(jié)點(diǎn)r pp=link(p)end/此時(shí)，r指向第m-1節(jié)點(diǎn)，p指向m

4、節(jié)點(diǎn)link（r） link(p) /刪除了p指向的節(jié)點(diǎn)print(data(p) /call RET(p)p link( r)endprint(data(p)end82.5 雙向鏈表循環(huán)鏈表的不足刪除節(jié)點(diǎn)、插入節(jié)點(diǎn)時(shí)，為了獲得某節(jié)點(diǎn)的直接前驅(qū)，都要從表頭遍歷鏈表解決問題的辦法雙向鏈表92.5 雙向鏈表在雙向鏈表中，每一個(gè)結(jié)點(diǎn)除了數(shù)據(jù)域外，還包含兩個(gè)指針域，一個(gè)指針（next）指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)，另一個(gè)指針（prior）指向它的前驅(qū)結(jié)點(diǎn)雙向鏈表的C結(jié)構(gòu)定義如下： typedef struct Dnode datatype data; struct Dnode *prior,*next; DL

5、inkList; DLinkList *head;102.5 雙向鏈表a0a1 an-1 head(c) 非空的雙循環(huán)鏈表雙鏈表一般由頭指針唯一確定，增加頭結(jié)點(diǎn)也能使雙鏈表上的某些運(yùn)算變的方便，將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來(lái)也能構(gòu)成循環(huán)鏈表，稱之為雙（向）循環(huán)鏈表。如下圖所示：112.5 雙向鏈表 若p為指向雙向鏈表中的某一個(gè)結(jié)點(diǎn)ai的指針，則雙鏈表結(jié)構(gòu)的對(duì)稱性可用下式刻化： p-prior-next p= p-next-prior 在雙向鏈表中，有些操作如：求長(zhǎng)度、取元素、定位等，因僅需涉及一個(gè)方向的指針，故它們的算法與線性鏈表的操作相同；但在插入、刪除時(shí)，則需同時(shí)修改兩個(gè)方向上的指針，兩者的操作

6、的時(shí)間復(fù)雜度均為O(n)。雙向鏈表的插入和刪除操作 （1）在雙向鏈表中插入一個(gè)結(jié)點(diǎn) 在雙向鏈表的第i個(gè)元素前插入一個(gè)結(jié)點(diǎn)時(shí)，可用指針p指該結(jié)點(diǎn)（稱p結(jié)點(diǎn)），先將新結(jié)點(diǎn)的prior指向p結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，其次將p結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的next指向新結(jié)點(diǎn)，然后將新結(jié)點(diǎn)的next指向p結(jié)點(diǎn)，最后將p結(jié)點(diǎn)的prior指向新結(jié)點(diǎn)。操作過程如下圖所示。122.5 雙向鏈表(a)插入前 （b）插入后 圖 在雙向鏈表中插入結(jié)點(diǎn)ai-1ai s x p ai-1 aip s x 132.5 雙向鏈表 節(jié)點(diǎn)插入算法： procedure InsertData(list,x,item)q=rlink( list) /q

7、是第一個(gè)節(jié)點(diǎn)while (q!=list and data(q)x) /查詢x節(jié)點(diǎn)q=rlink(q)endif q=list thenprint(“x不存在”);returncall GETNODE(p)/生成新節(jié)點(diǎn)pdata(p)=item/賦值數(shù)據(jù)llink(p)=q/新節(jié)點(diǎn)左指針指向Xrlink(p)=rlink(q)/新節(jié)點(diǎn)右指針指向 x節(jié)點(diǎn)的右節(jié)點(diǎn)rlink(q) = p/X節(jié)點(diǎn)右指針指向新節(jié)點(diǎn)llink(rlink(q)=p/原來(lái)X節(jié)點(diǎn)的右節(jié)點(diǎn)的左指針指向新節(jié)點(diǎn)end142.5 雙向鏈表 節(jié)點(diǎn)刪除算法： procedure DeleteData(list,x)q=rlink( l

8、ist) /q是第一個(gè)節(jié)點(diǎn)while (q!=list and data(q)x) /查詢x節(jié)點(diǎn)q=rlink(q)endif q=list thenprint(“x不存在”);returnrlink(llink(p)=rlink(p)llink(rlink(q)=llink(p)end15 2.6 鏈表應(yīng)用 一元多項(xiàng)式的表示及相加符號(hào)多項(xiàng)式的表示及其操作是線性表處理的典型用例，在數(shù)學(xué)上，一個(gè)一元多項(xiàng)式Pn(x) 可以表示為 ： Pn(x)= anxn +a2x2+a1x+a0 (最多有n+1項(xiàng))aixi是多項(xiàng)式的第i項(xiàng)（0in），其中ai為系數(shù)，x為變量，i為指數(shù)。它有n+1個(gè)系數(shù)，因此，在

9、計(jì)算機(jī)里，它可用一個(gè)線性表P來(lái)表示：P=（ an, a2,a1, ，a0）假設(shè)Qn(x)是一元m次多項(xiàng)式，同樣可用線性表Q來(lái)示：Q=（ bm, b2,b1, ， b0）若mn，則兩個(gè)多項(xiàng)式相加的結(jié)果Rn(x)= Pn(x)+ Qn(x)可用線性表R來(lái)表示：R=（ an , am+1 , am+ bm , , a2+b2,a1+ b1,a0+ b0 ）可以對(duì)P、Q和R采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈表存儲(chǔ)結(jié)構(gòu)。使用順序存儲(chǔ)結(jié)構(gòu)可以使多項(xiàng)式相加的算法十分簡(jiǎn)單。但是，當(dāng)多項(xiàng)式中存在大量的零系數(shù)時(shí)，這種表示方式就會(huì)浪費(fèi)在量存儲(chǔ)空間。為了有效而合理地利用存儲(chǔ)空間，可以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)表示多項(xiàng)式。16 2.

10、6 鏈表應(yīng)用 ATTACH算法： procedure ATTACH(co, ex,r)/co,ex分別為多項(xiàng)式中某項(xiàng)的系數(shù)和指數(shù)，r為結(jié)果鏈表最后節(jié)點(diǎn)的指針call GETNODE(w) /生成新節(jié)點(diǎn)exp(w) excoef(w) colink( r) wr wend172.6 鏈表應(yīng)用 多項(xiàng)式相加算法： procedure PADD(A,B,C)p Aq Bcall GETNODE(C )r Cwhile (p nil and qnil) docase:exp(p)=exp(q): /指數(shù)相同的情況下x=coef(q)+coef(p)if (x0)call ATTACH(x,exp(p),r)plink(p)q link(q)182.6 鏈表應(yīng)用case:exp(p)exp(q): /B當(dāng)前項(xiàng)的指數(shù)更大call ATTACH(coef(q),exp(q),r)q link(q)else:call ATTACH(coef(p),exp(p),r)p link(p)end /end caseend /end while 192.6 鏈表應(yīng)用while (pnil) do /將A(x)的剩余項(xiàng)加入Ccall ATTACH(coef(p),exp(p),r)p link(p)end /end case