計算機(jī)軟件技術(shù)程編基礎(chǔ)鏈表

1、順序表的 特點：運(yùn)算：簡單，時間復(fù)雜度好存儲特性：靜態(tài)規(guī)模，編譯前確定問題：程序的通用性和空間利用率之間的矛盾期望：在實際運(yùn)行過程中，根據(jù)實際問題的需要臨時確定存儲空間，涉及到動態(tài)變量動態(tài)變量：在程序運(yùn)行的過程中產(chǎn)生和釋放的變量。與之相反的是靜態(tài)變量靜態(tài)變量：在程序運(yùn)行的過程中一直存在的變量。靜態(tài)變量是出現(xiàn)在說明語句中的變量；動態(tài)變量由于是在運(yùn)行中產(chǎn)生的，因而不會事先說明如何實現(xiàn)動態(tài)變量？通過指針來實現(xiàn)：指針變量的說明，動態(tài)變量的產(chǎn)生和釋放。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright

2、2004-2011 Aspose Pty Ltd.12.3 線性鏈表及其運(yùn)算線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表，即將表中元素用鏈地址連接起來。head頭指針結(jié)點對線性表中的每一個數(shù)據(jù)元素，都需用兩部分來存儲：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于存放直接前驅(qū)或直接后繼結(jié)點的地址（指針），稱為指針域，稱這種存儲單元為結(jié)點。 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.2鏈表的存儲結(jié)構(gòu) 鏈?zhǔn)酱鎯Y(jié)構(gòu)是利用任意的存儲單元來存放線性表

3、中的元素，存儲數(shù)據(jù)的單元在內(nèi)存中可以連續(xù)，也可以零散分布。 由于線性表中各元素間存在著線性關(guān)系，每一個元素有一個直接前驅(qū)和一個直接后繼。為了表示元素間的這種線性關(guān)系，在這種結(jié)構(gòu)中不僅要存儲線性表中的元素，還要存儲表示元素之間邏輯關(guān)系的信息。所以用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示線性表中的一個元素時至少需要兩部分信息，除了存儲每一個數(shù)據(jù)元素值以外，還需存儲其后繼或前驅(qū)元素所在內(nèi)存的地址。兩部分信息一起構(gòu)成鏈表中的一個結(jié)點。結(jié)點的結(jié)構(gòu)如下所示。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011

4、 Aspose Pty Ltd.3鏈表結(jié)構(gòu)示意圖Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.4 從圖中可見，每個結(jié)點的存儲地址存放在直接前驅(qū)的指針域中。所以要訪問鏈表中數(shù)據(jù)元素C，必須由頭指針head得到第一個結(jié)點（數(shù)據(jù)A）的地址，由該結(jié)點的指針域得到第二個結(jié)點（數(shù)據(jù)B）的地址，再由其指針域得到存儲數(shù)據(jù)C的結(jié)點地址，訪問該結(jié)點的數(shù)據(jù)域就可以處理數(shù)據(jù)C了。鏈表這種順著指針鏈依次訪問數(shù)據(jù)元素的特點，表明鏈表是一種順序存儲結(jié)構(gòu)，只能順序操作鏈

5、表中元素。不能像順序表（數(shù)組）那樣可以按下標(biāo)隨機(jī)存取。 在鏈表存儲結(jié)構(gòu)中，不要求存儲空間的連續(xù)性，數(shù)據(jù)元素之間的邏輯關(guān)系由指針來確定。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.5每個結(jié)點由兩部分組成：data 數(shù)據(jù)域存放數(shù)據(jù)值next指針域存放后繼結(jié)點的首地址鏈表通過每個指針域?qū)個結(jié)點按邏輯次序鏈接成一個整體。&b&c&dHead&a頭指針結(jié)點&b&c&a&datanext表頭的地址由head指針提供，表尾結(jié)點沒有直接后繼，其指針域

6、應(yīng)為空指針，指針域為NULLEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.6單向鏈表 在圖所示的鏈表中，每個結(jié)點只有一個指向后繼的指針。也就是說訪問數(shù)據(jù)元素只能由鏈表頭依次到鏈表尾，而不能做逆向訪問。稱這種鏈表為單向鏈表或線性鏈表。這是一種最簡單的鏈表。 對于空鏈表，頭結(jié)點的指針域為空。圖2-8（a）為帶頭結(jié)點的空鏈 (b)為帶頭結(jié)點的單鏈表Evaluation only.Created with Aspose.Slides for .N

7、ET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.7定義鏈表結(jié)點結(jié)構(gòu)的一般形式為Struct 結(jié)構(gòu)體名 數(shù)據(jù)成員表； 結(jié)構(gòu)體名 *指針變量名；struct studentint num;float score;student *next;struct ListNode ELEM data； ListNode *next;Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.81672873

8、79486headtailEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.9/建立鏈表linklist *create()linklist *head,*p1,*p2;head=NULL; int x;cinx;struct linklistint num;float score;linklist *next;Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro

9、.Copyright 2004-2011 Aspose Pty Ltd.10p2=p1; /將新的結(jié)點作為尾結(jié)點p2-next=NULL;cinx;while(x0)p1=new(linklist);p1-num=x;cinp1-score; n=n+1;if(head=NULL)head=p1;else p2-next=p1;&p1p2p1如果是首結(jié)點呢？定義一個新結(jié)點p2return head;建立鏈表的條件Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspos

10、e Pty Ltd.11void print( ) coutnendl;/鏈表輸出形參是什么？需要知道鏈表的頭指針linklist *head如何查找鏈表？定義一個指針linklist *p1;p1=head;if(head!=NULL)docoutnum score;coutnext;while (p1!=NULL);Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.12查找運(yùn)算 的實現(xiàn) 設(shè)計思路：設(shè)置一個跟蹤鏈表結(jié)點的指針p1，初始時p1

11、指向鏈表中的第一個結(jié)點，然后順著next域依次指向每個結(jié)點，每指向一個結(jié)點就判斷其值是否等于i，若是則返回該結(jié)點地址,否則繼續(xù)往后搜索.要訪問單鏈表中第i個元素值，必須從頭指針開始遍歷鏈表，依次訪問每個結(jié)點，直到訪問到第i個結(jié)點為止。其時間復(fù)雜度為O(n)。 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.13linklist *getnode else coutinum!=i&p1-next!=NULL) p1=p1-next;j+; 如

12、果該結(jié)點不是要找的結(jié)點？if(p1-num=i) j+;coutthe node isjendl;return p1;如果該結(jié)點是要找的結(jié)點？Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.14linklist *del(linklist *head, int num)linklist *p1,*p2;if(head!=NULL) p1=head; else coutnextP1-next刪除條件Evaluation only.Create

13、d with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.15if(p1-num=num) if(p1=head)head=p1-next;elsep2-next=p1-next;n=n-1; else coutnumnextP1-nextwhile(p1-num!=num&p1-next!=NULL) p2=p1;p1=p1-next; 如果該結(jié)點不是要找的結(jié)點？找到該結(jié)點如何刪除？Evaluation only.Created with Aspose.Slides for .NET 3.5

14、 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.16線性鏈表的插入：在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的線性表中插入一個新結(jié)點在頭指針head的線性鏈表中包含元素x的結(jié)點之前加入一個新結(jié)點void inslst(linklist *head, int x)linklist *p1,*p2;p1=new(linklist);cinp1-nump1-score;if(head=NULL)head=p1;p1-next=NULL;p2=getnode(head,x);/尋找包含元素x的結(jié)點nextnextp1P2-nextp2p1-next=p2-next;/將結(jié)點p1插

15、入到結(jié)點p2后p2-next=p1;Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.17在插入和刪除算法中，都是先查詢確定操作位置，然后再進(jìn)行插入和刪除操作。所以其時間復(fù)雜度均為O(n)。另外在算法中實行插入和刪除操作時沒有移動元素的位置，只是修改了指針的指向，所以采用鏈表存儲方式要比順序存儲方式的效率高Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Co

16、pyright 2004-2011 Aspose Pty Ltd.18循環(huán)鏈表循環(huán)鏈表是單鏈表的另一種形式，是一個首尾相接的鏈表。特點：最后一個結(jié)點的指針域不空，而是指向頭結(jié)點，整個鏈表連成環(huán)狀，從表中任意結(jié)點出發(fā)均可到達(dá)其他結(jié)點。&b&c&d&b&chead&b&c&dhead&b&cheadEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.19headhead空循環(huán)鏈表判斷表空的條件：head-next=head判斷指針指向結(jié)點為表尾結(jié)點

17、的條件：p-next=headEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.20 帶頭結(jié)點的單循環(huán)鏈表的操作算法和帶頭結(jié)點的單鏈表的操作算法很相似，差別僅在于算法中的循環(huán)條件不同。在循環(huán)單鏈表上實現(xiàn)上述基本運(yùn)算的改動如下： 1初始化鏈表initlist(head)創(chuàng)建的頭結(jié)點指針域next不為空，而是指向自身head-next=headEvaluation only.Created with Aspose.Slides for .NET

18、3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.212線性表查找運(yùn)算*getnode(linklist *head, int i)函數(shù)、鏈表元素輸出運(yùn)算print(linklist *head)函數(shù)中，循環(huán)遍歷是否進(jìn)行的條件由p!=NULL改為p!=head;其余函數(shù)運(yùn)算沒有變化，請自行寫出相關(guān)函數(shù)的定義。在循環(huán)鏈表中，除了有頭指針head外，有時還可加上一個尾指針tail。尾指針tail指向最后一結(jié)點，沿最后一個結(jié)點的指針又可立即找到鏈表的第一個結(jié)點。在實際應(yīng)用中，使用尾指針來代替頭指針進(jìn)行某些操作往往會更簡單?！纠繉蓚€循環(huán)鏈表首尾相接

19、進(jìn)行合并，La為第一個循環(huán)鏈表表尾指針，Lb為第二個循環(huán)鏈表表尾指針，合并后Lb為新鏈表的尾指針，head指向整個合并后的鏈表?！窘狻克惴ㄋ悸罚?對兩個單循環(huán)鏈表La，Lb進(jìn)行的連接操作，是將Lb的第一個數(shù)據(jù)結(jié)點接到La的尾部。操作時需要從La的頭指針開始找到La的尾結(jié)點，其時間復(fù)雜性為O(n)。而在循環(huán)鏈表中若采用尾指針La，Lb來標(biāo)識，則時間性能將變?yōu)镺(1)。其連接過程如圖2-14所示。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.

20、22圖 兩個循環(huán)鏈表首尾相接進(jìn)行合并 (a)連接前p=La-next;q=Lb-next(b)連接后La-next=q;Lb-next=p;.a1a2aian.b1b2bibnLaLbpqLbLa.a1a2aian.b1b2bibnEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.23雙向鏈表nextdataprior雙向鏈表的結(jié)點結(jié)構(gòu)struct dlnode ELEM data； dlnode *next, *prior;對結(jié)點p而言，后

21、繼結(jié)點的地址p-next;前驅(qū)結(jié)點的地址p-priordataEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.24pp1p0P-prior-nextP-next-priorP-priorP-nextEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.25sp1p0P1-prior-next=

22、sP1-prior=ss-prior=p1-priors-next=p1雙向鏈表中結(jié)點的插入將結(jié)點s的插入結(jié)點p1之前Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.26pP-nextP-prior雙向鏈表中結(jié)點的刪除P-prior-next=p-nextP-next-prior=p-priordelete PEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro

23、.Copyright 2004-2011 Aspose Pty Ltd.27應(yīng)用舉例 一元多項式相加 假設(shè)用單鏈表表示多項式：A(x)=12+7x+8x10+5x17 ，B(x)=8x+15x7-6x10，頭指針Ah與Bh分別指向這兩個鏈表，如圖2-21所示： 對兩個多項式進(jìn)行相加運(yùn)算，其結(jié)果為C(x)= 12+15x+15 x7+2x10+5x17。如圖所示。圖 合并以前的鏈表 圖 2-22 合并以后的鏈表8115760Bh12071810517Ah151157210517012ChEvaluation only.Created with Aspose.Slides for .NET 3.5

24、 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.28 對兩個一元多項式進(jìn)行相加操作的運(yùn)算規(guī)則是：假設(shè)指針qa和qb分別指向多項式A(x)和B(x)中當(dāng)前進(jìn)行比較的某個結(jié)點，則需比較兩個結(jié)點數(shù)據(jù)域的指數(shù)項，有三種情況：(1) 指針qa所指結(jié)點的指數(shù)值指針qb所指結(jié)點的指數(shù)值時，則保留qa指針?biāo)赶虻慕Y(jié)點，qa指針后移；(2) 指針qa所指結(jié)點的指數(shù)值指針qb所指結(jié)點的指數(shù)值時，則將qb指針?biāo)赶虻慕Y(jié)點插入到qa所指結(jié)點前，qb指針后移；(3) 指針qa所指結(jié)點的指數(shù)值指針qb所指結(jié)點的指數(shù)值時，將兩個結(jié)點中的系數(shù)相加。若和不為零，則修改qa所指結(jié)點的

25、系數(shù)值，同時釋放qb所指結(jié)點；反之，從多項式A (x)的鏈表中刪除相應(yīng)結(jié)點，并釋放指針qa和qb所指結(jié)點。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.29多項式相加算法：struct polynode *add_poly(polynode *Ah, polynode *Bh)polynode *qa,*qb,*s,*r,*Ch;qa=Ah;qb=Bh; /qa和qb分別指向兩個鏈表的第一結(jié)點r=qa;Ch=Ah;/將鏈表Ah作為相加后的

26、結(jié)果鏈表while(qa!=NULL&qb!=NULL) /兩鏈表均非空 if(qa-exp=qb-exp) /兩者指數(shù)值相等 x=qa-coef+qb-coef; if(x!=0) qa-coef=x;r-next=qa;r=qa; s=qb+;free(s);qa+; /相加后系數(shù)不為零時 elses=qa+;free(s);s=qb+;free(s); /相加后系數(shù)為零時 else if(qa-expexp) r-next=qa;r=qa;qa+; /多項式Ah的指數(shù)值小 elser-next=qb;r=qb;qb+;/多項式Bh的指數(shù)值小 Evaluation only.Created

27、 with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.30鏈棧top棧頂鏈表的頭部作棧頂是最方便的鏈表的頭指針叫做棧頂指針只允許在表頭進(jìn)行插入和刪除運(yùn)算struct linkstackint num;float score;linkstack *next;Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.31/置空棧linkstack *i

28、nit_linkstack()return NULL;/判斷?？読nt empty_linkstack(linkstack *top)if(top=NULL) return 1;else return 0;/入棧linkstack *push_linkstack(linkstack *top, linkstack *stud)stud-next=top;top=stud;n=n+1;return top;topstudtoptopEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2

29、011 Aspose Pty Ltd.32/出棧linkstack *pop_linkstack(linkstack *top, linkstack *stud)if(top=NULL) return NULL;elsestud=top;top=top-next;n=n-1;return top;toptopstudEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.33帶鏈的隊列rearfront先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)只允許在表頭刪除，表尾插入的

30、單鏈表struct qnodeint num;struct qnode *next;struct lqueueqnode *front,*rear;Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.34lqueue *init_lqueue()lqueue *l;qnode *q;l=new(lqueue);q=new(qnode);q-next=NULL;l-front=l-rear=q;return l;創(chuàng)建一個空隊列frontrearn

31、extstruct qnodeint num;struct qnode *next;struct lqueueqnode *front,*rear;Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.35void in_lqueue(lqueue *l, qnode *q)q-next=NULL;/入隊frontrearnextnext只能在表尾插入結(jié)點l-rear-next=q;隊尾結(jié)點的指針域指向新結(jié)點l-rear=q;rear存入新結(jié)點地

32、址Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.36/出隊刪除表頭結(jié)點frontrearnextnextnextqnode *out_lqueue(lqueue *l,) qnode *qreturn q;判斷隊空的條件if(l-rear=l-front) return NULL;取出隊首結(jié)點地址q=l-front-next;l-front-next=q-next;隊首結(jié)點地址給下一個結(jié)點Evaluation only.Created w

33、ith Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.37作業(yè)：P153 2.10 試寫出逆轉(zhuǎn)單鏈表的算法 2.9 試寫出循環(huán)鏈表長度的算法上機(jī)： 星期三晚上7：00 （ 3月27日）Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro.Copyright 2004-2011 Aspose Pty Ltd.38作業(yè)講評：2.10 試寫出逆轉(zhuǎn)單鏈表的算法 如何定義一個新結(jié)點struct linklistint num;float score;linklist *next;如何建立一個新