數(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)酱鎯Y(jié)構(gòu)。是將單鏈表的表中最后一個結(jié)點指針指向鏈表的表頭結(jié)點，整個鏈表形成一個環(huán)，這樣從表中任一結(jié)點出發(fā)都可找到表中其他的結(jié)點。帶頭結(jié)點的單循環(huán)鏈表如下圖所示a1a2anai head head32.4.2 循環(huán)鏈表應(yīng)用例：在鏈表上實現(xiàn)將兩個線性表(a1,a2,an)和(b1,b2,bn)鏈結(jié)成一個線性表（ a1,a2,an , b1,b2,bn ）42.4.2 循環(huán)鏈表應(yīng)用圖1 學(xué)生

2、成績表C語言算法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個人圓桌編號k報到m的人出列數(shù)據(jù)結(jié)構(gòu)模擬：循環(huán)表第一次報數(shù)時，需要用到表頭62.4.2 循環(huán)鏈表應(yīng)用_約瑟夫問題Procedure JOESEHU(list,n,m,k)listnil/創(chuàng)建空表for i 1 to n do/建立n個節(jié)點的單鏈表call GETNODE(p

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

4、節(jié)點link（r） link(p) /刪除了p指向的節(jié)點print(data(p) /call RET(p)p link( r)endprint(data(p)end82.5 雙向鏈表循環(huán)鏈表的不足刪除節(jié)點、插入節(jié)點時，為了獲得某節(jié)點的直接前驅(qū)，都要從表頭遍歷鏈表解決問題的辦法雙向鏈表92.5 雙向鏈表在雙向鏈表中，每一個結(jié)點除了數(shù)據(jù)域外，還包含兩個指針域，一個指針（next）指向該結(jié)點的后繼結(jié)點，另一個指針（prior）指向它的前驅(qū)結(jié)點雙向鏈表的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é)點也能使雙鏈表上的某些運算變的方便，將頭結(jié)點和尾結(jié)點鏈接起來也能構(gòu)成循環(huán)鏈表，稱之為雙（向）循環(huán)鏈表。如下圖所示：112.5 雙向鏈表 若p為指向雙向鏈表中的某一個結(jié)點ai的指針，則雙鏈表結(jié)構(gòu)的對稱性可用下式刻化： p-prior-next p= p-next-prior 在雙向鏈表中，有些操作如：求長度、取元素、定位等，因僅需涉及一個方向的指針，故它們的算法與線性鏈表的操作相同；但在插入、刪除時，則需同時修改兩個方向上的指針，兩者的操作

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

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

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

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

10、6 鏈表應(yīng)用 ATTACH算法： procedure ATTACH(co, ex,r)/co,ex分別為多項式中某項的系數(shù)和指數(shù)，r為結(jié)果鏈表最后節(jié)點的指針call GETNODE(w) /生成新節(jié)點exp(w) excoef(w) colink( r) wr wend172.6 鏈表應(yī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)前項的指數(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)的剩余項加入Ccall ATTACH(coef(p),exp(p),r)p link(p)end /end case