數(shù)據(jù)結(jié)構(gòu) c語言版 第2版 教學(xué)課件 ppt 李云清 楊慶紅 揭安全 第03章_線性表（ii）

1、數(shù)據(jù)結(jié)構(gòu),李云清 楊慶紅 揭安全,高等學(xué)校精品課程,人民郵電出版社,（第2版）,數(shù)據(jù)結(jié)構(gòu),揭安全,江西省高等學(xué)校精品課程,E_mail: jieanquan@163.com,江西師范大學(xué)計算機(jī)信息工程學(xué)院,第3章 線性表的鏈?zhǔn)酱鎯?鏈?zhǔn)酱鎯?單鏈表,帶頭結(jié)點(diǎn)的單鏈表,循環(huán)單鏈表,,,,雙鏈表,鏈?zhǔn)綏?鏈?zhǔn)疥犃?線性表的存儲方式除了常用的順序存儲外，采用鏈?zhǔn)椒绞酱鎯σ彩且环N常見的方式。本章將介紹一般線性表的幾種鏈?zhǔn)酱鎯崿F(xiàn)方式，如單

2、鏈表、帶頭結(jié)點(diǎn)單鏈表、循環(huán)單鏈表、雙鏈表以及特殊的線性表------棧和隊列的鏈?zhǔn)酱鎯崿F(xiàn)。,3.1鏈?zhǔn)酱鎯?數(shù)據(jù)結(jié)構(gòu)的存儲方式必須體現(xiàn)它的邏輯關(guān)系 。在鏈?zhǔn)酱鎯Ψ绞较?，實現(xiàn)中除存放一個結(jié)點(diǎn)的信息外，還需附設(shè)指針，用指針體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系。如果一個結(jié)點(diǎn)有多個后繼或多個前驅(qū)，那么可以附設(shè)相應(yīng)個數(shù)的指針，一個結(jié)點(diǎn)附設(shè)的指針指向的是這個結(jié)點(diǎn)的某個前驅(qū)或后繼。,線性結(jié)構(gòu)中，每個結(jié)點(diǎn)最多只有一個前驅(qū)和一個后繼，這里暫且設(shè)定更關(guān)心它的后繼，這樣

3、在存儲時除了存放該結(jié)點(diǎn)的信息外，只要附設(shè)一個指針即可，該指針指向它的后繼結(jié)點(diǎn)的存放位置。每個結(jié)點(diǎn)的存儲形式是：,例，數(shù)據(jù)的邏輯結(jié)構(gòu)B=（K，R）其中 K={k1,k2,k3,k4,k5} R={r} R={,,,}是一個線性結(jié)構(gòu)，它的鏈?zhǔn)酱鎯θ鐖D所示,為了清晰，上圖可以更簡潔地用下圖表示。,3.2 單鏈表,單鏈表是線性表鏈?zhǔn)酱鎯Φ囊环N形式，其中的結(jié)點(diǎn)一般含有兩個域，一個是存放數(shù)據(jù)信息的info域，另一個是指

4、向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)的存放地址的指針域next。一個單鏈表必須有一個首指針指向單鏈表中的第一個結(jié)點(diǎn)。,,◎,,◎,,◎,數(shù)據(jù)域,指針域,…,節(jié)點(diǎn),直觀化的描述方法：,單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。例如：若頭指針名是head，則把鏈表稱為表head。,,head,,(a) 非空表,head=NULL,(b) 非空表,3.2.2單鏈表的實現(xiàn),單鏈表結(jié)構(gòu)的C語言描述如下：/????????????????????

5、?????????????????????//? 鏈表實現(xiàn)的頭文件,文件名slnklist.h   ?//?????????????????????????????????????????/ typedef int datatype; typedef struct link_node{ datatype info; struct link_node ?next; }node;,單鏈表

6、幾個基本操作的具體實現(xiàn)：,建立一個空的單鏈表 /???????????????????????????????????????????????????//? 函數(shù)功能:建立一個空的單鏈表 ?//? 函數(shù)參數(shù):無 ?//? 函數(shù)返回值:指向node類型變量的指針 ?//? 文件名:slnklist.c,函數(shù)名:init() ?//?

7、??????????????????????????????????????????????????/ node ?init() /?建立一個空的單鏈表?/ { return NULL; }算法3.1 建立一個空的單鏈表,輸出單鏈表中各個結(jié)點(diǎn)的值 void display(node ?head){ node ?p; p=head; if(!p) printf(&

8、quot;\n單鏈表是空的！"); else { printf("\n單鏈表各個結(jié)點(diǎn)的值為:\n"); while(p) { printf("%5d",p->info);p=p->next;} } } 算法3.2輸出單鏈表中各個結(jié)點(diǎn)的值,在單鏈表中查找一個值為x的結(jié)點(diǎn) node ?fin

9、d(node ?head,int i) { int j=1; node ?p=head; if(inext;j++; } return p; }算法3.3 在單鏈表中查找一個值為x的結(jié)點(diǎn),單鏈表的插入過程見下圖所示 ：,,(2) head=p;,(1),(1) p->next=head;,(a) 在單鏈表的最前面插入一個值為x的新結(jié)點(diǎn),單鏈表的插入過程見下圖所示 ：,,∧,,,,,,head,

10、(2),,(2) head=p;,(a) 在單鏈表的最前面插入一個值為x的新結(jié)點(diǎn),(1),(1) p->next=head;,單鏈表的插入過程見下圖所示 ：,,(b) 在q所指的結(jié)點(diǎn)后插入一個p所指的值為x的新結(jié)點(diǎn),(1) p->next=q->next;,(1),單鏈表的插入過程見下圖所示 ：,head,,,,,,(b) 在q所指的結(jié)點(diǎn)后插入一個p所指的值為x的新結(jié)點(diǎn),(1) p->next=q->nex

11、t;,p,q,(2) q->next=p;,(1),(2),/?????????????????????????????????????????????????????//? 函數(shù)功能:單鏈表第i個結(jié)點(diǎn)后插入值為x的新結(jié)點(diǎn)    ?//? 函數(shù)參數(shù):指向node類型變量的指針head   ?//? datatype

12、類型變量x,int型變量I ?//? 函數(shù)返回值:指向node類型變量的指針   ?//? 文件名:slnklist.c,函數(shù)名:insert()    ?//?????????????????????????????????????????????????????/ node ?insert(node ?head,d

13、atatype x,int i) { node ?p,?q; q=find(head,i);/?查找第i個結(jié)點(diǎn)?/ if(!q&&i!=0) printf("\n找不到第%d個結(jié)點(diǎn),不能插入%d！",i,x); else{ p=(node?)malloc(sizeof(node));/?分配空間?/ p->info=

14、x;/?設(shè)置新結(jié)點(diǎn)?/,if(i==0){/* 插入的結(jié)點(diǎn)作為單鏈表的第一個結(jié)點(diǎn)*/ p->next=head;/?插入(1)?/ head=p;/?插入(2)?/ } else { p->next=q->next;/?插入(1)?/

15、 q->next=p;/?插入(2)?/ } } return head; }算法3.4 在單鏈表中第i個結(jié)點(diǎn)后插入一個值為x的新結(jié)點(diǎn),刪除操作見下圖所示：,∧,,,,,,,head,(1) head=head->next;,(a) 刪除單鏈表的最前面的（第一個）結(jié)點(diǎn),(2) free(p),,刪除操作見下圖所示：,∧,,,,,head,(1) head=h

16、ead->next;,(a) 刪除單鏈表的最前面的（第一個）結(jié)點(diǎn),(2) free(p),(b) 刪除p指向的結(jié)點(diǎn)，pre為p的前驅(qū)結(jié)點(diǎn),(1) pre->next=p->next;,head,,,,(b) 刪除p指向的結(jié)點(diǎn)，pre為p的前驅(qū)結(jié)點(diǎn),(1) pre->next=p->next;,head,,,(1),(b) 刪除p指向的結(jié)點(diǎn)，pre為p的前驅(qū)結(jié)點(diǎn),(1) pre->next=p->

17、;next;,head,,pre,,(1),(2) free(p),/???????????????????????????????????????????????????//? 函數(shù)功能:在單鏈表中刪除一個值為x的結(jié)點(diǎn) ?//? 函數(shù)參數(shù):指向node類型變量的指針head ?//? datatype 類型變量x ?//? 函數(shù)返回值:指向node類型變量的指針

18、 ?//? 文件名:slnklist.c,函數(shù)名:dele() ?//???????????????????????????????????????????????????/ node ?dele(node ?head,datatype x) { node ?pre=NULL,?p; if(!head) {printf("單鏈表是空的！");return head;} p

19、=head; while(p&&p->info!=x)/?沒有找到并且沒有找完?/ {pre=p;p=p->next;}/?pre指向p的前驅(qū)結(jié)點(diǎn)?/ if(!pre&&p->info==x)/?要刪除的是第一個結(jié)點(diǎn)?/ head=head->next;/?刪除(1)?/,else pre->next=p->next

20、; free(p); return head; }算法3.5 在單鏈表中刪除一個值為x的結(jié)點(diǎn),鏈?zhǔn)酱鎯Φ牟迦牒蛣h除操作比順序存儲方便，但不能隨機(jī)訪問某個結(jié)點(diǎn)！,3.3 帶頭結(jié)點(diǎn)單鏈表,3.3.1帶頭結(jié)點(diǎn)單鏈表,帶頭結(jié)點(diǎn)單鏈表見下圖所示：,3.3.2帶頭結(jié)點(diǎn)單鏈表的實現(xiàn),一般的單鏈表中，第一個結(jié)點(diǎn)由head指示，而在帶頭結(jié)點(diǎn)單鏈表中，head指示的是所謂的頭結(jié)點(diǎn)，它不是存儲數(shù)據(jù)結(jié)構(gòu)中的實際結(jié)點(diǎn)，第一個實際的結(jié)點(diǎn)是

21、head->next指示的。在帶頭結(jié)點(diǎn)單鏈表的操作實現(xiàn)時要注意這一點(diǎn)。,node ?init() { node ?head; head=(node?)malloc(sizeof(node)); head->next=NULL; return head; }算法3.6 建立一個空的帶頭結(jié)點(diǎn)的單鏈表,void display(node ?head) { node ?p; p=head

22、->next;/?從第一個（實際）結(jié)點(diǎn)開始?/ if(!p) printf("\n帶頭結(jié)點(diǎn)的單鏈表是空的!"); else { printf("\n帶頭結(jié)點(diǎn)的單鏈表各個結(jié)點(diǎn)的值為:\n"); while(p) { printf("%5d",p->info);p=p->next;} } }算法3

23、.7 輸出帶頭結(jié)點(diǎn)的單鏈表中各個結(jié)點(diǎn)的值,/?????????????????????????????????????????????????????//? 函數(shù)功能:在帶頭結(jié)點(diǎn)的單鏈表中查找第i個結(jié)點(diǎn)地址?//? 函數(shù)參數(shù):指向node類型變量的指針head?//? int類型變量i?//? 函數(shù)返回值:指向node類型變量的指針head?//? 文件名hlnklis

24、t.c,函數(shù)名find()?//?????????????????????????????????????????????????????/ node ?find(node ?head,int i) { int j=0; node ?p=head; if(i<0){printf("\n帶頭結(jié)點(diǎn)的單鏈表中不存在第%d個結(jié)點(diǎn)！",i);return NULL;} else if

25、(i==0) return p;/*此時p指向的是頭結(jié)點(diǎn)*/,while(p&&i!=j)/?沒有查找完并且還沒有找到?/ { p=p->next;j++;/?繼續(xù)向后（左）查找,計數(shù)器加1?/ } return p;/?返回結(jié)果,i=0時,p指示的是頭結(jié)點(diǎn)?/ }算法3.8 在帶頭結(jié)點(diǎn)的單鏈表中查找第i個結(jié)點(diǎn),帶頭結(jié)點(diǎn)單鏈表的插入過程見圖3.7 ：,帶頭

26、結(jié)點(diǎn)的單鏈表的插入操作的具體實現(xiàn)見算法3.9。 /????????????????????????????????????????????????????/ /? 函數(shù)功能:在帶頭結(jié)點(diǎn)的單鏈表中第i個結(jié)點(diǎn)后插入一個值為x的新結(jié)點(diǎn)          ?//? 函數(shù)參數(shù):指向node類型變量的指針head ?/

27、/? datatype 類型變量x,int型變量i ?//? 函數(shù)返回值:指向node類型變量的指針head ?//? 文件名:hlnklist.c,函數(shù)名:insert() ?//????????????????????????????????????????????????????/ node ?insert(node

28、 ?head,datatype x,int i) { node ?p,?q; q=find(head,i);/?查找?guī)ь^結(jié)點(diǎn)的單鏈表中的第i個結(jié)點(diǎn)?/ /?i=0,表示新結(jié)點(diǎn)插入在頭結(jié)點(diǎn)之后,此時q指向的是頭結(jié)點(diǎn)?/,if(!q)/?沒有找到?/ { printf("\n帶頭結(jié)點(diǎn)的單鏈表中不存在第%d個結(jié)點(diǎn)！不能插入%d！",i,x);return head;}

29、 p=(node?)malloc(sizeof(node));/?為準(zhǔn)備插入的新結(jié)點(diǎn)分配空間?/ p->info=x;/?為新結(jié)點(diǎn)設(shè)置值x?/ p->next=q->next;/?插入(1)?/ q->next=p;/?插入(2),當(dāng)i=0時,由于q指向的是頭結(jié)點(diǎn),本語句等價于head>next=p ?/ return head; }算

30、法3.9 在帶頭結(jié)點(diǎn)的單鏈表中第i個結(jié)點(diǎn)后插入一個值為x的新結(jié)點(diǎn),帶頭結(jié)點(diǎn)單鏈表的刪除過程見圖3.8。,,,,∧,,,,,,,head ×,q,,(1) head->next=q->next;,(a) 刪除帶頭結(jié)點(diǎn)單鏈表的最前面的（第一個）實際結(jié)點(diǎn),(1) (1),,node ?dele(node ?head,datatype x) { node ?pre=

31、head,?q;/?首先pre指向頭結(jié)點(diǎn)?/ q=head->next;/?q從帶頭結(jié)點(diǎn)的第一個實際結(jié)點(diǎn)開始找值為x的結(jié)點(diǎn)?/ while(q&&q->info!=x)/?沒有查找完并且還沒有找到?/ {pre=q;q=q->next;}/?繼續(xù)查找,pre指向q的前驅(qū)?/ if (q) {pre->next=q->next;/?刪除?/

32、 free(q);}/?釋放空間?/ return head; }算法3.10 在帶頭結(jié)點(diǎn)的單鏈表中刪除一個值為x的結(jié)點(diǎn),算法設(shè)計題：1、用單鏈表作為存儲結(jié)構(gòu)，實現(xiàn)線性表（a0,a1,…, an-1）就地逆置的操作，所謂就地指輔助空間應(yīng)為O(1)。2、設(shè)單鏈表L是一個遞減有序表，試寫一算法將X插入其中后仍保持L的有序性。3、寫一算法將單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)果表中各結(jié)點(diǎn)值均不相同。4

33、、設(shè)計一個算法，對單鏈表按結(jié)點(diǎn)值從小到大對結(jié)點(diǎn)進(jìn)行排序。,算法設(shè)計題：5、設(shè)計一個算法，將兩個有序單鏈表合并成一個有序的單鏈表。6、設(shè)計一個算法，求兩個單鏈表表示的集合的交集，并將結(jié)果用一個新的單鏈表保存并返回。,10,,^,,p,鏈表插入排序演示,50,,,10,,^,,,,head,^,,s,^,50,,10,,^,,,,head,^,,s,^,q=head->next,while ( q && q->

34、;datadata ) { },pre=q; q=q->next;,循環(huán)結(jié)束時，將s結(jié)點(diǎn)加在pre與q所指示的結(jié)點(diǎn)之間！,50,,10,,^,,,,head,^,,s,^,q=head->next,while ( q && q->datadata ) {

35、 },pre=q; q=q->next;,s->next=q;pre->next=s;,50,,10,,^,,,,head,^,q=head->next,while ( q && q->datadata ) { },pre=q; q=q->next;,s->next=q;pre->next

36、=s;,,50,,40,,,10,,^,,,,head,^,q=head->next,while ( q && q->datadata ) { },pre=q; q=q->next;,s->next=q;pre->next=s;,,,,,算法設(shè)計題：多相式相加問題:A(x)=7+3x+9x8+5x17B(x

37、)=8x+22x7-9x8,3.4 循環(huán)單鏈表,3.4.1 循環(huán)單鏈表,循環(huán)單鏈表類型的描述 （略）,3.4.2循環(huán)單鏈表的實現(xiàn),單鏈表中某個結(jié)點(diǎn)p是表中最后一個結(jié)點(diǎn)的特征是p->next==NULL。對于一個循環(huán)單鏈表，若首指針為head，表中的某個結(jié)點(diǎn)p是最后一個結(jié)點(diǎn)的特征應(yīng)該是p->next==head。 循環(huán)單鏈表的頭文件和單鏈表的相同。,建立一個空的循環(huán)單鏈表 /????????

38、??????????????????????????????????????????//? 函數(shù)功能:建立一個空的循環(huán)單鏈表 ?//? 函數(shù)參數(shù):無 ?//? 函數(shù)返回值:指向node類型變量的指針 ?//? 文件名:clnklist.c,函數(shù)名init() ?//??????????????????????????????????????????????

39、????/ node ?init()/?建立一個空的循環(huán)單鏈表?/ { return NULL; }算法3.11 建立一個空的循環(huán)單鏈表,/??????????????????????????????????????????????????????//? 函數(shù)功能:獲得循環(huán)單鏈表的最后一個結(jié)點(diǎn)的存儲地址 ?//? 函數(shù)參數(shù):指向node類型變量的指針變量head ?//? 函數(shù)返回值:

40、指向node類型變量的指針 ?//? 文件名:clnklist.c,函數(shù)名:rear() ?//??????????????????????????????????????????????????????/ node ?rear(node ?head) { node ?p; if(!head)/?循環(huán)單鏈表為空?/ p=NULL; else {

41、 p=head;/?從第一個結(jié)點(diǎn)開始?/ while(p->next!=head)/?沒有到達(dá)最后一個結(jié)點(diǎn)?/ p=p->next;/?繼續(xù)向后?/,} return p; }算法3.12 獲得循環(huán)單鏈表的最后一個結(jié)點(diǎn)的存儲地址,/??????????????????????????????????????????????????

42、???//? 函數(shù)功能:輸出循環(huán)單鏈表中各個結(jié)點(diǎn)的值 ?//? 函數(shù)參數(shù):指向node類型變量的指針變量head ?//? 函數(shù)返回值:空 ?//? 文件名:clnklist.c,函數(shù)名:display() ?//????

43、?????????????????????????????????????????????????/ void display(node ?head) { node ?p; if(!head) printf("\n循環(huán)單鏈表是空的！\n"); else { printf("\n循環(huán)單鏈表各個結(jié)點(diǎn)的值分別為:\n"); printf(&qu

44、ot;%5d",head->info);/?輸出非空表中第一個結(jié)點(diǎn)的值?/,p=head->next;/?p指向第一個結(jié)點(diǎn)的下一個結(jié)點(diǎn)?/ while(p!=head)/?沒有回到第一個結(jié)點(diǎn)?/ { printf("%5d",p->info); p=p->next; } } }算法3.

45、13 輸出循環(huán)單鏈表中各個結(jié)點(diǎn)的值,/?????????????????????????????????????????????????????//? 函數(shù)功能:循環(huán)單鏈表中查找值為x的結(jié)點(diǎn)的存儲地址 ?//? 函數(shù)參數(shù):指向node類型變量的指針變量head   ?//? datatype類型的變量x  

46、 ?//? 函數(shù)返回值:指向node類型變量的指針   ?//? 文件名:clnklist.c,函數(shù)名:find()   ?//?????????????????????????????????????????????????????/ node ?find(node ?head,datatype x) { /?查找一個值

47、為x的結(jié)點(diǎn)?/ node ?q; if(!head)/?循環(huán)單鏈表是空的?/ { printf("\n循環(huán)單鏈表是空的！無法找指定結(jié)點(diǎn)！"); return NULL;,} q=head;/? q指向循環(huán)單鏈表的第一個結(jié)點(diǎn),準(zhǔn)備查找?/ while(q->next!=head&&q->info!=x)/?沒有查找到并且沒有

48、查找完整個表?/ q=q->next;/?繼續(xù)查找?/ if(q->info==x) return q; else return NULL; }算法3.14 在循環(huán)單鏈表中查找一個值為x的結(jié)點(diǎn),循環(huán)單鏈表的插入過程如圖 ：,,,,,,,,,head ×,p,,(2) (1),(2),,re

49、ar,(a) 在循環(huán)單鏈表的最前面插入一個值為x的新結(jié)點(diǎn),,,,,(3) (3)×,,(1) p->next=head;,(2) head=p;,(3) rear->next=p;,循環(huán)單鏈表的插入過程如圖 ：,,,,head,,,(2) (1),(2)×,q p,,,(b) 循環(huán)單鏈表，在q所指的結(jié)點(diǎn)后插入一個p所指的值為x的新結(jié)點(diǎn),(1) p->next=q->

50、;next;,,,,,,,(2) q->next=p;,/???????????????????????????????????????????????????????//? 函數(shù)功能:循環(huán)單鏈表第i個結(jié)點(diǎn)后插入值為x的新結(jié)點(diǎn) ?//? 函數(shù)參數(shù):指向node類型變量的指針變量head  ?//? datatype類型的變量x,int類型的變量I  

51、  ?//? 函數(shù)返回值:指向node類型變量的指針?//? 文件名:clnklist.c,函數(shù)名:insert()  ?//???????????????????????????????????????????????????????/ node ?insert(node ?head,datatype x,int i) {/*i為0時表示將值為x的結(jié)點(diǎn)插入作為循環(huán)單鏈表的

52、第一個結(jié)點(diǎn)*/ node ?p,?q,*myrear; int j; p=(node?)malloc(sizeof(node)); /?分配空間?/ p->info=x;/?設(shè)置新結(jié)點(diǎn)的值?/ if(i<0)/?如果i小于0,則輸出出錯信息?/ {printf("\n無法找到指定的插入位置！"); free(p);return head;},if(

53、i==0&&!head)/?插入前循環(huán)單鏈表如果是空的,則新結(jié)點(diǎn)的指針域應(yīng)指向它自己?/ { p->next=p;head=p;return head;} if(i==0&&head)/*在非空的循環(huán)單鏈表最前面插入*/ { myrear=rear(head);/?找到循環(huán)單鏈表的最后一個結(jié)點(diǎn)?/ p->next=head;/?插

54、入(1)?/ head=p; /?插入(2)?/ myrear->next=p;/?插入(3)最后一個結(jié)點(diǎn)的指針域指向新插入的表中第一個結(jié)點(diǎn)?/ return head;} if(i>0&&!head) {printf("\n無法找到指定的插入位置！"); free(p);return head;} if(i>

55、0&&head){/*在非空的循環(huán)單鏈表中插入值為x的結(jié)點(diǎn),并且插入的結(jié)點(diǎn)不是第一個結(jié)點(diǎn)*/,q=head;/?準(zhǔn)備從表中第一個結(jié)點(diǎn)開始查找?/ j=1;/?計數(shù)開始?/ while(i!=j&&q->next!=head)/?沒有找到并且沒有找遍整個表?/ {

56、 q=q->next;j++;/?繼續(xù)查找,計數(shù)器加1?/ } if(i!=j) /? 找不到指定插入位置,即i的值超過表中結(jié)點(diǎn)的個數(shù),則不進(jìn)行插入?/ { printf("\n表中不存在第%d個結(jié)點(diǎn),無法進(jìn)行插入!\n",i); free(p);

57、 return head; } else,else {/?找到了第i個結(jié)點(diǎn),插入x?/ p->next=q->next;/?插入,修改指針(1)?/ q->next=p;/?插入,修改指針(2)?/

58、 return head; } } }算法3.15 在循環(huán)單鏈表中第i個結(jié)點(diǎn)后插入一個值為x的新結(jié)點(diǎn),循環(huán)單鏈表的刪除過程如圖 ：,,,,,,,,head ×,q,,(1) head=head->next; (2) pre->next=head;,(a) 刪除循環(huán)單鏈表的最前面的（第一個）結(jié)點(diǎn),(1) (1),,,,,,pre,

59、,(2) × (2),循環(huán)單鏈表的刪除過程如圖 ：,/?????????????????????????????????????????????????????//? 函數(shù)功能:在循環(huán)單鏈表中刪除一個值為x的結(jié)點(diǎn) ?/ /? 函數(shù)參數(shù):指向node類型變量的指針變量head ?//? datatype類型的

60、變量x ?//? 函數(shù)返回值:指向node類型變量的指針 ?//? 文件名:clnklist.c,函數(shù)名:dele() ?//?????????????????????????????????????????????????????/ node ?dele(node ?head,datatype x) {

61、 node ?pre=NULL,?q;/?q用于查找值為x的結(jié)點(diǎn),pre指向q的前驅(qū)結(jié)點(diǎn)?/ if(!head)/?表為空,則無法做刪除操作?/ { printf("\n循環(huán)單鏈表為空,無法做刪除操作！"); return head; },q=head;/?從第1個結(jié)點(diǎn)開始準(zhǔn)備查找?/ while(q->next!=head&&a

62、mp;q->info!=x)/?沒有找遍整個表并且沒有找到?/ { pre=q; q=q->next;/?pre為q的前驅(qū),繼續(xù)查找?/ }/?循環(huán)結(jié)束后,pre為q的前驅(qū)?/ if(q->info!=x)/?沒找到?/ { printf("沒有找到值為%d的結(jié)點(diǎn)！",x); } e

63、lse/?找到了,下面要刪除q?/ { if(q!=head){pre->next=q->next;free(q);} else,if(head->next==head){free(q);head=NULL;} else { pre=head->next; while(pre->next!

64、=q) pre=pre->next;/*找q的前驅(qū)結(jié)點(diǎn)位置*/ head=head->next; pre->next=head; free(q); } } return head; }算法3.16 在循環(huán)單鏈表中刪除一個值為x的結(jié)點(diǎn),3．循環(huán)單鏈表的整體插入與刪除操作,圖3.12 一個循環(huán)單鏈表

65、整體插入到一個單鏈表前部的圖示,3.5 雙鏈表,3.5.1 雙鏈表,前面的各種鏈?zhǔn)奖碇校粋€結(jié)點(diǎn)的指針域是指向它的后繼結(jié)點(diǎn)的，如果需要找一個結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)，則必須從表首指針開始查找，當(dāng)某個結(jié)點(diǎn)pre的指針域指向的是結(jié)點(diǎn)p時，即pre->next==p時，則說明pre是p的前驅(qū)結(jié)點(diǎn)。如果常常需要知道一個結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)，上述的鏈?zhǔn)奖硎遣贿m合的。既然單鏈表中每個結(jié)點(diǎn)有一個指針域指向它的后繼結(jié)點(diǎn)，那自然地想到再增設(shè)一個指針域指

66、向它的前驅(qū)結(jié)點(diǎn)，這就構(gòu)成了雙鏈表。,雙鏈表的結(jié)點(diǎn)包括三個域，一個是存放數(shù)據(jù)信息的info域，另外兩個是指針域，這里用llink和rlink表示，llink指向它的前驅(qū)結(jié)點(diǎn)，rlink指向它的后繼結(jié)點(diǎn)。,雙鏈表的一般情形如圖所示：,雙鏈表類型的描述（略！）,3.5.2 雙鏈表的實現(xiàn),雙鏈表結(jié)構(gòu)的C語言描述如下：/???????????????????????????????????????//? 雙鏈表的頭文件,文件名dlnklist

67、.h  ?//???????????????????????????????????????/ typedef int datatype; typedef struct dlink_node{ datatype info; struct dlink_node ?llink,?rlink; }dnode;,/??????????????????????????????????????????????

68、????//? 函數(shù)功能:輸出雙鏈表中各個結(jié)點(diǎn)的值 ?//? 函數(shù)參數(shù):指向dnode類型變量的指針head ?//? 函數(shù)返回值:空 ?//? 文件名:dlnklist.c,函數(shù)名:display() ?//??????????????????????????????????????????????????/ void display(dnode ?head) { dno

69、de ?p; printf("\n"); p=head; if(!p) printf("\n雙鏈表是空的!\n"); else { printf("\n雙鏈表中各個結(jié)點(diǎn)的值為:\n"); while(p) { printf("%5d",p->info);p=p->rlink;} } }

70、 算法3.18 輸出雙鏈表中各個結(jié)點(diǎn)的值,dnode ?find(dnode ?head,int i) { int j=1; dnode ?p=head; if(irlink;j++;/?繼續(xù)沿著右指針向后查找,計數(shù)器加1?/ } if(!p){printf("\n第%d個結(jié)點(diǎn)不存在!\n",i);return NULL;} return p; }算法3.1

71、9 查找雙鏈表中第i個結(jié)點(diǎn),雙鏈表插入過程如下圖所示：,雙鏈表插入過程如下圖所示：,,∧,,,,,,,,,head,(1) p->rlink=q->rlink; (2) p->llink=q; (3) q->rlink->llink=p; (4) q->rlink=p;,,,,,,,,,(2) (4) (3) (1),q,,x,,,p,,,(4)××(3),,

72、(b) 在雙鏈表中q所指結(jié)點(diǎn)的后面插入一個值為x的新結(jié)點(diǎn),,雙鏈表插入過程如下圖所示：,,∧,,,,,,,,,(1) p->rlink=q->rlink (=NULL); (2) p->llink=q; (4) q->rlink=p;,,,(2) (4) (1),q,x,∧

73、,,p,,,(c) 在雙鏈表中q所指結(jié)點(diǎn)（是最后一個結(jié)點(diǎn)）的后面插入一個值為x的新結(jié)點(diǎn),head,,,/?????????????????????????????????????????????????????//? 函數(shù)功能:雙鏈表第i個結(jié)點(diǎn)后插入值為x的新結(jié)點(diǎn) ?//? 函數(shù)參數(shù):指向dnode類型變量的指針head ?//? datatype類型的變量x, int

74、類型的變量 ?//? 函數(shù)返回值:指向dnode類型變量的指針 ?//? 文件名:dlnklist.c,函數(shù)名:insert() ?//?????????????????????????????????????????????????????/dnode *insert(dnode *head,datatype x,int i) { dnode