第3章-線性表及其鏈式存儲

1、第第3 3章章 線性表的鏈式存儲線性表的鏈式存儲 鏈式存儲鏈式存儲單鏈表單鏈表帶頭結點的單鏈表帶頭結點的單鏈表循環(huán)單鏈表循環(huán)單鏈表雙鏈表雙鏈表鏈式棧鏈式棧鏈式隊列鏈式隊列線性表的存儲方式除了常用的順序存儲外，采用線性表的存儲方式除了常用的順序存儲外，采用鏈式方式存儲也是一種常見的方式。本章將介紹一般鏈式方式存儲也是一種常見的方式。本章將介紹一般線性表的幾種鏈式存儲實現方式，如單鏈表、帶頭結線性表的幾種鏈式存儲實現方式，如單鏈表、帶頭結點單鏈表、循環(huán)單鏈表、雙鏈表以及特殊的線性表點單鏈表、循環(huán)單鏈表、雙鏈表以及特殊的線性表-棧和隊列的鏈式存儲實現。棧和隊列的鏈式存儲實現。 3.1鏈式存儲鏈式存儲

2、 數據結構的存儲方式必須體現它的邏輯關系數據結構的存儲方式必須體現它的邏輯關系 。在鏈式存儲方式下，實現中除存放一個結點的信息外，在鏈式存儲方式下，實現中除存放一個結點的信息外，還需附設指針，用指針體現結點之間的邏輯關系。如還需附設指針，用指針體現結點之間的邏輯關系。如果一個結點有多個后繼或多個前驅，那么可以附設相果一個結點有多個后繼或多個前驅，那么可以附設相應個數的指針，一個結點附設的指針指向的是這個結應個數的指針，一個結點附設的指針指向的是這個結點的某個前驅或后繼。點的某個前驅或后繼。 線性結構中，每個結點最多只有一個前驅和一個后繼，這線性結構中，每個結點最多只有一個前驅和一個后繼，這里暫

3、且設定更關心它的后繼，這樣在存儲時除了存放該結點的信里暫且設定更關心它的后繼，這樣在存儲時除了存放該結點的信息外，只要附設一個指針即可，該指針指向它的后繼結點的存放息外，只要附設一個指針即可，該指針指向它的后繼結點的存放位置。每個結點的存儲形式是：位置。每個結點的存儲形式是： infonext例，數據的邏輯結構例，數據的邏輯結構B=（K，R）其中其中 K=k1,k2,k3,k4,k5 R=r R=,是一個線性結構，它的鏈式存儲如圖所示是一個線性結構，它的鏈式存儲如圖所示 存儲地址存儲地址 info nextk41006k21007k11003k5k31005為了清晰，上圖可以更簡潔地用下圖表示

4、。為了清晰，上圖可以更簡潔地用下圖表示。k1k5k2k3k4head3.2 單鏈表單鏈表 單鏈表是線性表鏈式存儲的一種形式，其中的單鏈表是線性表鏈式存儲的一種形式，其中的結點一般含有兩個域，一個是存放數據信息的結點一般含有兩個域，一個是存放數據信息的info域，域，另一個是指向該結點的后繼結點的存放地址的指針另一個是指向該結點的后繼結點的存放地址的指針域域next。一個單鏈表必須有一個首指針指向單鏈表。一個單鏈表必須有一個首指針指向單鏈表中的第一個結點。中的第一個結點。數據1指針數據2指針數據3指針數據域數據域指針域指針域節(jié)點節(jié)點直觀化的描述方法：直觀化的描述方法：單鏈表是由表頭唯一確定，因此

5、單鏈表可以用頭單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。例如：若頭指針名是指針的名字來命名。例如：若頭指針名是head，則把鏈表稱為表則把鏈表稱為表head。head(a) 非空表非空表head=NULL(b) 空表空表3.2.2單鏈表的實現單鏈表的實現 單鏈表結構的單鏈表結構的C語言描述如下：語言描述如下：/ 鏈表實現的頭文件鏈表實現的頭文件,文件名文件名linklist.h / typedef int datatype; typedef struct link_node datatype info; struct link_node next; node; typedef

6、 node * linklist;單鏈表幾個基本操作的具體實現：單鏈表幾個基本操作的具體實現：建立一個空的單鏈表建立一個空的單鏈表 / 函數功能函數功能:建立一個空的單鏈表建立一個空的單鏈表 / 函數參數函數參數:無無 / 函數返回值函數返回值:指向指向node類型變量的指針類型變量的指針 / 文件名文件名:slnklist.c,函數名函數名:init() / node init() / 建立一個空的單鏈表建立一個空的單鏈表 / return NULL; 算法算法3.1 建立一個空的單鏈表建立一個空的單鏈表 輸出單鏈表中各個結點的值輸出單鏈表中各個結點的值 void display(node

7、head) node p; p=head; if(!p) printf(n單鏈表是空的！單鏈表是空的！); else printf(n單鏈表各個結點的值為單鏈表各個結點的值為:n); while(p) printf(%5d,p-info);p=p-next; 算法算法3.2輸出單鏈表中各個結點的值輸出單鏈表中各個結點的值在單鏈表中查找第在單鏈表中查找第i個結點個結點 node find(node head,int i) int j=1; node p=head; if(inext;j+; return p; 算法算法3.3 在單鏈表中查找第在單鏈表中查找第i個結點個結點單鏈表的插入過程見下圖所

8、示單鏈表的插入過程見下圖所示 ： headpx(2) head=p;(1) p-next=head;(a) 在單鏈表的最前面插入一個值為在單鏈表的最前面插入一個值為x的新結點的新結點單鏈表的插入過程見下圖所示單鏈表的插入過程見下圖所示 ： head (2)px(2) head=p;(a) 在單鏈表的最前面插入一個值為在單鏈表的最前面插入一個值為x的新結點的新結點(1) p-next=head;單鏈表的插入過程見下圖所示單鏈表的插入過程見下圖所示 ：head (b) 在在q所指的結點后插入一個所指的結點后插入一個p所指的值為所指的值為x的新結點的新結點(1) p-next=q-next;x單鏈表

9、的插入過程見下圖所示單鏈表的插入過程見下圖所示 ：head x(b) 在在q所指的結點后插入一個所指的結點后插入一個p所指的值為所指的值為x的新結點的新結點(1) p-next=q-next;(2) q-next=p;/ 函數功能函數功能:單鏈表第單鏈表第i個結點后插入值為個結點后插入值為x的新結點的新結點 / 函數參數函數參數:指向指向node類型變量的指針類型變量的指針head / datatype 類型變量類型變量x,int型變量型變量I / 函數返回值函數返回值:指向指向node類型變量的指針類型變量的指針 / 文件名文件名:slnklist.c,函數名函數名:insert() / n

10、ode insert(node head,datatype x,int i) node p, q; q=find(head,i);/ 查找第查找第i個結點個結點 / if(!q&i!=0) printf(n找不到第找不到第%d個結點個結點,不能插入不能插入%d！,i,x); else p=(node )malloc(sizeof(node);/ 分配空間分配空間 / p-info=x;/ 設置新結點設置新結點 /if(i=0)/* 插入的結點作為單鏈表的第一個結點插入的結點作為單鏈表的第一個結點*/ p-next=head;/ 插入插入(1) / head=p;/ 插入插入(2) /

11、else p-next=q-next;/ 插入插入(1) / q-next=p;/ 插入插入(2) / return head; 算法算法3.4 在單鏈表中第在單鏈表中第i個結點后插入一個值為個結點后插入一個值為x的新結點的新結點1、申請空間、申請空間s=malloc(.)2、填入數據域、填入數據域值值s-info=ch;單鏈表應用單鏈表應用-建立單鏈表建立單鏈表方法一：堆棧方式建立單鏈表（頭插法）方法一：堆棧方式建立單鏈表（頭插法）數據1數據23、新結點鏈入表頭、新結點鏈入表頭s-next=head;4、修改表頭指針、修改表頭指針head=s;數據1數據24、修改表頭指針、修改表頭指針hea

12、d=s;單鏈表應用單鏈表應用-建立單鏈表建立單鏈表方法一：堆棧方式建立單鏈表（頭插法）方法一：堆棧方式建立單鏈表（頭插法）#include “l(fā)inklist.h”node * creatlistf() datatype data; node * head, *s; head=NULL; printf(nnPlease input the data of linklistn); scanf(%d,&data); while (data!=0) s=(node *) malloc(sizeof(node); s-info=data; s-next=head; head=s; scanf(

13、%d,&data); return head; 1、申請空間、申請空間s=malloc()2、填入數據域、填入數據域值值s-info=ch;3、新結點鏈入表尾、新結點鏈入表尾r-next=s;4、修改表尾指針、修改表尾指針r=s;方法二：隊列方式建立單鏈表（尾插法）方法二：隊列方式建立單鏈表（尾插法）數據2數據1方法二：隊列方式建立單鏈表（尾插法）方法二：隊列方式建立單鏈表（尾插法）數據2數據1關鍵一步：關鍵一步：設置一個鏈尾指針設置一個鏈尾指針r，每次將新的結點鏈在，每次將新的結點鏈在r的的后面，使其成為新的表尾結點。后面，使其成為新的表尾結點。node* creatlistr(vo

14、id) datatype data; node *head,*s,*r; head=NULL;r=NULL; scanf(%d,&data); while (data) s=(node *)malloc(sizeof(node); s-info=data; /*產生新結點產生新結點*/ if (head=NULL) head=s; /*新結點插入空表新結點插入空表*/ else r-next=s; r=s; scanf(%d,&data); /*處理表尾結點指針域處理表尾結點指針域*/以以0作為輸入結束作為輸入結束條件條件if (r!=NULL) r-next=NULL;ret

15、urn head; 刪除刪除操作見下圖所示：操作見下圖所示： headp(1) head=head-next;(a) 刪除單鏈表的最前面的（第一個）結點刪除單鏈表的最前面的（第一個）結點2) free(p刪除刪除操作見下圖所示操作見下圖所示 head(1) head=head-next;(a) 刪除單鏈表的最前面的（第一個）結點刪除單鏈表的最前面的（第一個）結點(2) free(p)(b) 刪除刪除p指向的結點，指向的結點，pre為為p的前驅結點的前驅結點(1) pre-next=p-next;head pre p(b) 刪除刪除p指向的結點，指向的結點，pre為為p的前驅結點的前驅結點(1)

16、 pre-next=p-next;head pre p(1)(b) 刪除刪除p指向的結點，指向的結點，pre為為p的前驅結點的前驅結點(1) pre-next=p-next;head pre(1)(2)free(p)/ 函數功能函數功能:在單鏈表中刪除一個值為在單鏈表中刪除一個值為x的結點的結點 / 函數參數函數參數:指向指向node類型變量的指針類型變量的指針head / datatype 類型變量類型變量x / 函數返回值函數返回值:指向指向node類型變量的指針類型變量的指針 / 文件名文件名:slnklist.c,函數名函數名:dele() / node dele(node head,

17、datatype x) node pre=NULL, p; if(!head) printf(單鏈表是空的！單鏈表是空的！);return head; p=head; while(p&p-info!=x) / 沒有找到并且沒有找完沒有找到并且沒有找完 / pre=p;p=p-next; / pre指向指向p的前驅結點的前驅結點 / if(!pre&p-info=x) / 要刪除的是第一個結點要刪除的是第一個結點 / head=head-next;/ 刪除刪除(1) /else pre-next=p-next; free(p); return head; 算法算法3.5 在單鏈表

18、中刪除一個值為在單鏈表中刪除一個值為x的結點的結點3.3 帶頭結點單鏈表帶頭結點單鏈表 3.3.1帶頭結點單鏈表帶頭結點單鏈表帶頭結點單鏈表見下圖所示：帶頭結點單鏈表見下圖所示： 數據2數據1數據3headhead(A) 空表空表(B) 非空表非空表3.3.2帶頭結點單鏈表的實現帶頭結點單鏈表的實現 一般的單鏈表中，第一個結點由一般的單鏈表中，第一個結點由head指示，而在指示，而在帶頭結點單鏈表中，帶頭結點單鏈表中，head指示的是所謂的頭結點，它指示的是所謂的頭結點，它不是存儲數據結構中的實際結點，第一個實際的結點是不是存儲數據結構中的實際結點，第一個實際的結點是head-next指示的。

19、在帶頭結點單鏈表的操作實現時指示的。在帶頭結點單鏈表的操作實現時要注意這一點。要注意這一點。 node init() node head; head=(node )malloc(sizeof(node); head-next=NULL; return head; 算法算法3.6 建立一個空的帶頭結點的單鏈表建立一個空的帶頭結點的單鏈表請修改頭插法與尾插法建表程序請修改頭插法與尾插法建表程序,以建立帶頭以建立帶頭結點的單鏈表。結點的單鏈表。 void display(node head) node p; p=head-next; / 從第一個（實際）結點開始從第一個（實際）結點開始 / if(!

20、p) printf(n帶頭結點的單鏈表是空的帶頭結點的單鏈表是空的!); else printf(n帶頭結點的單鏈表各個結點的值為帶頭結點的單鏈表各個結點的值為:n); while(p) printf(%5d,p-info);p=p-next; 算法算法3.7 輸出帶頭結點的單鏈表中各個結點的值輸出帶頭結點的單鏈表中各個結點的值/ 函數功能函數功能:在帶頭結點的單鏈表中查找第在帶頭結點的單鏈表中查找第i個結點地址個結點地址 / 函數參數函數參數:指向指向node類型變量的指針類型變量的指針head / int類型變量類型變量i / 函數返回值函數返回值:指向指向node類型變量的指針類型變量的

21、指針head / 文件名文件名hlnklist.c,函數名函數名find() / node find(node head,int i) int j=0; node p=head; if(inext;j+;/ 繼續(xù)向后（左）查找繼續(xù)向后（左）查找,計數器加計數器加1 / return p;/ 返回結果返回結果,i=0時時,p指示的是頭結點指示的是頭結點 / 算法算法3.8 在帶頭結點的單鏈表中查找第在帶頭結點的單鏈表中查找第i個結點個結點帶頭結點單鏈表的插入過程見圖帶頭結點單鏈表的插入過程見圖3.7 x (2) (1)(2)q p(b) 在在q所指的結點后插入一個所指的結點后插入一個p所指的值為

22、所指的值為x的新結點的新結點(1) p-next=q-next;(2) q-next=p;head p (2) head (2) (1)x(1) p-next=q-next;(2) q-next=p;(a) 非空帶頭結點單鏈表的最前面插入一個值為非空帶頭結點單鏈表的最前面插入一個值為x的新結點的新結點q 帶頭結點的單鏈表的插入操作的具體實現見算法帶頭結點的單鏈表的插入操作的具體實現見算法3.9。 / / 函數功能函數功能:在帶頭結點的單鏈表中第在帶頭結點的單鏈表中第i個結點后插入一個值為個結點后插入一個值為x的新結點的新結點 / 函數參數函數參數:指向指向node類型變量的指針類型變量的指針h

23、ead / datatype 類型變量類型變量x,int型變量型變量i / 函數返回值函數返回值:指向指向node類型變量的指針類型變量的指針head / 文件名文件名:hlnklist.c,函數名函數名:insert() / node insert(node head,datatype x,int i) node p, q; q=find(head,i); / 查找?guī)ь^結點的單鏈表中的第查找?guī)ь^結點的單鏈表中的第i個結點個結點 / / i=0,表示新結點插入在頭結點之后表示新結點插入在頭結點之后,此時此時q指向的是頭結點指向的是頭結點 / if(!q)/ 沒有找到沒有找到 / printf(

24、n帶頭結點的單鏈表中不存在第帶頭結點的單鏈表中不存在第%d個結點！不能個結點！不能插入插入%d！,i,x);return head; p=(node )malloc(sizeof(node);/ 為準備插入的新結點為準備插入的新結點分配空間分配空間 / p-info=x;/ 為新結點設置值為新結點設置值x / p-next=q-next; / 插入插入(1) / q-next=p;/ 插入插入(2),當當i=0時時,由于由于q指向的是頭結點指向的是頭結點,本語句等價于本語句等價于headnext=p / return head; 算法算法3.9 在帶頭結點的單鏈表中第在帶頭結點的單鏈表中第i個

25、結點后插入一個值為個結點后插入一個值為x的的新結點新結點帶頭結點單鏈表的刪除過程見圖帶頭結點單鏈表的刪除過程見圖3.8。 q(1) head-next=q-next;(a) 刪除帶頭結點單鏈表的最前面的（第一個）實際結點刪除帶頭結點單鏈表的最前面的（第一個）實際結點 (1) (1)(b) 在帶頭結點單鏈表中刪除在帶頭結點單鏈表中刪除q指向的結點，指向的結點，pre為為q的前驅結點的前驅結點(1) pre-next=q-next;pre qhead node dele(node head,datatype x) node pre=head, q;/ 首先首先pre指向頭結點指向頭結點 / q=h

26、ead-next;/ q從帶頭結點的第一個實際從帶頭結點的第一個實際結點開始找值為結點開始找值為x的結點的結點 / while(q&q-info!=x) / 沒有查找完并且還沒有找到沒有查找完并且還沒有找到 / pre=q;q=q-next; / 繼續(xù)查找繼續(xù)查找,pre指向指向q的前驅的前驅 / if (q) pre-next=q-next;/ 刪除刪除 / free(q);/ 釋放空間釋放空間 / return head; 算法算法3.10 在帶頭結點的單鏈表中刪除一個值為在帶頭結點的單鏈表中刪除一個值為x的結點的結點算法設計題：算法設計題：1、用單鏈表作為存儲結構，實現線性表（、

27、用單鏈表作為存儲結構，實現線性表（a0,a1, an-1）就地逆置的操作，所謂就地指輔助空間應為）就地逆置的操作，所謂就地指輔助空間應為O(1)。2、設單鏈表、設單鏈表L是一個遞減有序表，試寫一算法將是一個遞減有序表，試寫一算法將X插插入其中后仍保持入其中后仍保持L的有序性。的有序性。3、寫一算法將單鏈表中值重復的結點刪除，使所得的、寫一算法將單鏈表中值重復的結點刪除，使所得的結果表中各結點值均不相同。結果表中各結點值均不相同。4、設計一個算法，對單鏈表按結點值從小到大對結點、設計一個算法，對單鏈表按結點值從小到大對結點進行排序。進行排序。算法設計題：算法設計題：5、設計一個算法，將兩個有序單

28、鏈表合并成一個有序、設計一個算法，將兩個有序單鏈表合并成一個有序的單鏈表。的單鏈表。6、設計一個算法，求兩個單鏈表表示的集合的交集，、設計一個算法，求兩個單鏈表表示的集合的交集，并將結果用一個新的單鏈表保存并返回。并將結果用一個新的單鏈表保存并返回。 50 40 80 10phead鏈表插入排序演示鏈表插入排序演示 50 40 80 10pheads 50 40 80 10pheadspreq=head-next while ( q & q-datadata ) pre=q; q=q-next;循環(huán)結束時，將循環(huán)結束時，將s結點加在結點加在pre與與q所指示的結點所指示的結點之間！之間

29、！ 50 40 80 10pheadspreq=head-next while ( q & q-datadata ) pre=q; q=q-next;s-next=q;pre-next=s; 50 40 80 10pheadspreq=head-next while ( q & q-datadata ) pre=q; q=q-next;s-next=q;pre-next=s; 50 40 80 10pheadspreq=head-next while ( q & q-datadata ) pre=q; q=q-next;s-next=q;pre-next=s;算法設計題

30、：算法設計題：多相式相加問題多相式相加問題:A(x)=7+3x+9x8+5x17B(x)=8x+22x7-9x8ABC3.4 循環(huán)單鏈表循環(huán)單鏈表 3.4.1 循環(huán)單鏈表循環(huán)單鏈表 head 循環(huán)單鏈表類型的描述循環(huán)單鏈表類型的描述 （略）（略）3.4.2循環(huán)單鏈表的實現循環(huán)單鏈表的實現 單鏈表中某個結點單鏈表中某個結點p是表中最后一個結點的特征是表中最后一個結點的特征是是p-next=NULL。對于一個循環(huán)單鏈表，若首指。對于一個循環(huán)單鏈表，若首指針為針為head，表中的某個結點，表中的某個結點p是最后一個結點的特征是最后一個結點的特征應該是應該是p-next=head循環(huán)單鏈表的頭文件和單

31、鏈表的相同。循環(huán)單鏈表的頭文件和單鏈表的相同。 建立一個空的循環(huán)單鏈表建立一個空的循環(huán)單鏈表/ 函數功能函數功能:建立一個空的循環(huán)單鏈表建立一個空的循環(huán)單鏈表 / 函數參數函數參數:無無 / 函數返回值函數返回值:指向指向node類型變量的指針類型變量的指針 / 文件名文件名:clnklist.c,函數名函數名init() / node init()/ 建立一個空的循環(huán)單鏈表建立一個空的循環(huán)單鏈表 / return NULL; 算法算法3.11 建立一個空的循環(huán)單鏈表建立一個空的循環(huán)單鏈表/ 函數功能函數功能:獲得循環(huán)單鏈表的最后一個結點的存儲地址獲得循環(huán)單鏈表的最后一個結點的存儲地址 / 函

32、數參數函數參數:指向指向node類型變量的指針變量類型變量的指針變量head / 函數返回值函數返回值:指向指向node類型變量的指針類型變量的指針 / 文件名文件名:clnklist.c,函數名函數名:rear() / node rear(node head) node p; if(!head)/ 循環(huán)單鏈表為空循環(huán)單鏈表為空 / p=NULL; else p=head;/ 從第一個結點開始從第一個結點開始 / while( p-next!=head ) / 沒有到達最后一個結點沒有到達最后一個結點 / p=p-next;/ 繼續(xù)向后繼續(xù)向后 / return p; 算法算法3.12 獲得循

33、環(huán)單鏈表的最后一個結點的存儲地址獲得循環(huán)單鏈表的最后一個結點的存儲地址/ 函數功能函數功能:輸出循環(huán)單鏈表中各個結點的值輸出循環(huán)單鏈表中各個結點的值 / 函數參數函數參數:指向指向node類型變量的指針變量類型變量的指針變量head / 函數返回值函數返回值:空空 / 文件名文件名:clnklist.c,函數名函數名:display() / void display(node head) node p; if(!head) printf(n循環(huán)單鏈表是空的！循環(huán)單鏈表是空的！n); else printf(n循環(huán)單鏈表各個結點的值分別為循環(huán)單鏈表各個結點的值分別為:n); printf(%5d

34、,head-info);/ 輸出非空表中第一個結點的值輸出非空表中第一個結點的值 / p=head-next;/ p指向第一個結點的下一個結點指向第一個結點的下一個結點 / while( p!=head )/ 沒有回到第一個結點沒有回到第一個結點 / printf(%5d,p-info); p=p-next; 算法算法3.13 輸出循環(huán)單鏈表中各個結點的值輸出循環(huán)單鏈表中各個結點的值/ 函數功能函數功能:循環(huán)單鏈表中查找值為循環(huán)單鏈表中查找值為x的結點的存儲地址的結點的存儲地址 / 函數參數函數參數:指向指向node類型變量的指針變量類型變量的指針變量head / datatype類型的變量類

35、型的變量x / 函數返回值函數返回值:指向指向node類型變量的指針類型變量的指針 / 文件名文件名:clnklist.c,函數名函數名:find() / node find(node head,datatype x) / 查找一個值為查找一個值為x的結點的結點 / node q; if(!head)/ 循環(huán)單鏈表是空的循環(huán)單鏈表是空的 / printf(n循環(huán)單鏈表是空的！無法找指定結點！循環(huán)單鏈表是空的！無法找指定結點！); return NULL; q=head;/ q指向循環(huán)單鏈表的第一個結點指向循環(huán)單鏈表的第一個結點,準備查找準備查找 / while( q-next!=head&am

36、p;q-info!=x )/ 沒有查找到并且沒有沒有查找到并且沒有查找完整個表查找完整個表 / q=q-next;/ 繼續(xù)查找繼續(xù)查找 / if(q-info=x) return q; else return NULL; 算法算法3.14 在循環(huán)單鏈表中查找一個值為在循環(huán)單鏈表中查找一個值為x的結點的結點循環(huán)單鏈表的插入過程如圖循環(huán)單鏈表的插入過程如圖 ： headpx(a) 在循環(huán)單鏈表的最前面插入一個值為在循環(huán)單鏈表的最前面插入一個值為x的新結點的新結點(1) p-next=head(2) head=p;(3) rear-next=p;head xq p(b) 循環(huán)單鏈表，在循環(huán)單鏈表，在

37、q所指的結點后插入一個所指的結點后插入一個p所指的所指的值為值為x的新結點的新結點(1) p-next=q-next;(2) q-next=p;/ 函數功能函數功能:循環(huán)單鏈表第循環(huán)單鏈表第i個結點后插入值為個結點后插入值為x的新結點的新結點 / 函數參數函數參數:指向指向node類型變量的指針變量類型變量的指針變量head / datatype類型的變量類型的變量x,int類型的變量類型的變量I / 函數返回值函數返回值:指向指向node類型變量的指針類型變量的指針 / 文件名文件名:clnklist.c,函數名函數名:insert() / node insert(node head,dat

38、atype x,int i) /*i為為0時表示將值為時表示將值為x的結點插入作為循環(huán)單鏈表的第一個結點的結點插入作為循環(huán)單鏈表的第一個結點*/ node p, q,*myrear; int j; p=(node )malloc(sizeof(node); / 分配空間分配空間 / p-info=x;/ 設置新結點的值設置新結點的值 / if(inext=p;head=p;return head; if(i=0&head)/*在非空的循環(huán)單鏈表最前面插在非空的循環(huán)單鏈表最前面插入入*/ myrear=rear(head);/ 找到循環(huán)單鏈表的最后一個結點找到循環(huán)單鏈表的最后一個結點 /

39、 p-next=head;/ 插入插入(1) / head=p; / 插入插入(2) / myrear-next=p;/ 插入插入(3)最后一個結點的指針域指向新最后一個結點的指針域指向新插入的表中第一個結點插入的表中第一個結點 / return head; if(i0&!head) printf(n無法找到指定的插入位置！無法找到指定的插入位置！); free(p);return head; if(i0&head)/*在非空的循環(huán)單鏈表中插入值為在非空的循環(huán)單鏈表中插入值為x的結點的結點,并并且插入的結點不是第一個結點且插入的結點不是第一個結點*/ q=head;/ 準備從表

40、中第一個結點開始查找準備從表中第一個結點開始查找 / j=1;/ 計數開始計數開始 / while(i!=j&q-next!=head)/ 沒有找到并且沒有找遍沒有找到并且沒有找遍整個表整個表 / q=q-next;j+;/ 繼續(xù)查找繼續(xù)查找,計數器加計數器加1 / if(i!=j) / 找不到指定插入位置找不到指定插入位置,即即i的值超過表中結點的值超過表中結點的個數的個數,則不進行插入則不進行插入 / printf(n表中不存在第表中不存在第%d個結點個結點,無法進行插入無法進行插入!n,i); free(p); return head; else else / 找到了第找到了第i

41、個結點個結點,插入插入x / p-next=q-next; / 插入插入,修改指針修改指針(1) / q-next=p;/ 插入插入,修改指針修改指針(2) / return head; 算法算法3.15 在循環(huán)單鏈表中第在循環(huán)單鏈表中第i個結點后插入一個值為個結點后插入一個值為x的新結點的新結點循環(huán)單鏈表的刪除過程如圖循環(huán)單鏈表的刪除過程如圖 ： head q(1) head=head-next; (2) pre-next=head;(a) 刪除循環(huán)單鏈表的最前面的（第一個）結點刪除循環(huán)單鏈表的最前面的（第一個）結點 (1) (1)pre (2) (2)循環(huán)單鏈表的刪除過程如圖循環(huán)單鏈表的刪

42、除過程如圖 ： (1)(1)(b) 刪除刪除q指向的結點，指向的結點，pre為為q的前驅結點（的前驅結點（q指向的不是循環(huán)單指向的不是循環(huán)單鏈表的第一個結點）鏈表的第一個結點）(1) pre-next=q-next;pre qhead / 函數功能函數功能:在循環(huán)單鏈表中刪除一個值為在循環(huán)單鏈表中刪除一個值為x的結點的結點 / / 函數參數函數參數:指向指向node類型變量的指針變量類型變量的指針變量head / datatype類型的變量類型的變量x / 函數返回值函數返回值:指向指向node類型變量的指針類型變量的指針 / 文件名文件名:clnklist.c,函數名函數名:dele() /

43、 node dele(node head,datatype x) node pre=NULL, q;/ q用于查找值為用于查找值為x的結點的結點,pre指向指向q的的前驅結點前驅結點 / if(!head)/ 表為空表為空,則無法做刪除操作則無法做刪除操作 / printf(n循環(huán)單鏈表為空循環(huán)單鏈表為空,無法做刪除操作！無法做刪除操作！); return head; q=head;/ 從第從第1個結點開始準備查找個結點開始準備查找 / while(q-next!=head&q-info!=x)/ 沒有找遍整個表并且沒有找遍整個表并且沒有找到沒有找到 / pre=q; q=q-next

44、;/ pre為為q的前驅的前驅,繼續(xù)查找繼續(xù)查找 / / 循環(huán)結束后循環(huán)結束后,pre為為q的前驅的前驅 / if(q-info!=x)/ 沒找到沒找到 / printf(沒有找到值為沒有找到值為%d的結點！的結點！,x); else/ 找到了找到了,下面要刪除下面要刪除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!=q) pre=pre-next;/*找找q的前驅結的前驅結點位置點位置*/ head=hea

45、d-next; pre-next=head; free(q); return head; 算法算法3.16 在循環(huán)單鏈表中刪除一個值為在循環(huán)單鏈表中刪除一個值為x的結點的結點3循環(huán)單鏈表的整體插入與刪除操作循環(huán)單鏈表的整體插入與刪除操作圖圖3.12 一個循環(huán)單鏈表整體插入到一個單鏈表前部的圖示一個循環(huán)單鏈表整體插入到一個單鏈表前部的圖示3.5 雙鏈表雙鏈表 3.5.1 雙鏈表雙鏈表 前面的各種鏈式表中，一個結點的指針域是指向前面的各種鏈式表中，一個結點的指針域是指向它的后繼結點的，如果需要找一個結點它的后繼結點的，如果需要找一個結點p的前驅結點，的前驅結點，則必須從表首指針開始查找，當某個結點

46、則必須從表首指針開始查找，當某個結點pre的指針的指針域指向的是結點域指向的是結點p時，即時，即pre-next=p時，則說明時，則說明pre是是p的前驅結點。如果常常需要知道一個結點的前的前驅結點。如果常常需要知道一個結點的前驅和后繼結點，上述的鏈式表是不適合的。既然單鏈驅和后繼結點，上述的鏈式表是不適合的。既然單鏈表中每個結點有一個指針域指向它的后繼結點，那自表中每個結點有一個指針域指向它的后繼結點，那自然地想到再增設一個指針域指向它的前驅結點，這就然地想到再增設一個指針域指向它的前驅結點，這就構成了雙鏈表。構成了雙鏈表。 雙鏈表的結點包括三個域，一個是存放數據信息雙鏈表的結點包括三個域，

47、一個是存放數據信息的的info域，另外兩個是指針域，這里用域，另外兩個是指針域，這里用llink和和rlink表表示，示，llink指向它的前驅結點，指向它的前驅結點，rlink指向它的后繼結點。指向它的后繼結點。 雙鏈表的一般情形如圖所示：雙鏈表的一般情形如圖所示： 雙鏈表類型的描述（略?。╇p鏈表類型的描述（略！）head3.5.2 雙鏈表的實現雙鏈表的實現 雙鏈表結構的雙鏈表結構的C語言描述如下：語言描述如下：/ 雙鏈表的頭文件雙鏈表的頭文件,文件名文件名dlnklist.h / typedef int datatype; typedef struct dlink_node datatyp

48、e info; struct dlink_node llink, rlink; dnode;/ 函數功能函數功能:輸出雙鏈表中各個結點的值輸出雙鏈表中各個結點的值 / 函數參數函數參數:指向指向dnode類型變量的指針類型變量的指針head / 函數返回值函數返回值:空空 / 文件名文件名:dlnklist.c,函數名函數名:display() / void display(dnode head) dnode p; printf(n); p=head; if(!p) printf(n雙鏈表是空的雙鏈表是空的!n); else printf(n雙鏈表中各個結點的值為雙鏈表中各個結點的值為:n);

49、 while(p) printf(%5d,p-info);p=p-rlink; 算法算法3.18 輸出雙鏈表中各個結點的值輸出雙鏈表中各個結點的值dnode find(dnode head,int i) int j=1; dnode p=head; if(irlink;j+;/ 繼續(xù)沿著右指針向后查找繼續(xù)沿著右指針向后查找,計數器加計數器加1 / if(!p)printf(n第第%d個結點不存在個結點不存在!n,i);return NULL; return p; 算法算法3.19 查找雙鏈表中第查找雙鏈表中第i個結點個結點雙鏈表插入過程如下圖所示：雙鏈表插入過程如下圖所示： xhead(1)

50、p-rlink=head;p(a) 在雙鏈表的最前面插入一個值為在雙鏈表的最前面插入一個值為x的新結點的新結點(2) p-llink=NULL;(3) head-llink=p;(4) head=p;雙鏈表插入過程如下圖所示：雙鏈表插入過程如下圖所示：head (1) p-rlink=q-rlink;qxp(b) 在雙鏈表中在雙鏈表中q所指結點的后面插入一個值為所指結點的后面插入一個值為x的新結點的新結點(2) p-llink=q;(3) q-rlink-llink=p;(4) q-rlink=p;雙鏈表插入過程如下圖所示：雙鏈表插入過程如下圖所示： (1) p-rlink=q-rlink;q

51、xp(c) 在雙鏈表中在雙鏈表中q所指結點（是最后一個結點）的后面所指結點（是最后一個結點）的后面插入一個值為插入一個值為x的新結點的新結點head (2) p-llink=q; (3) q-rlink=p;/ 函數功能函數功能:雙鏈表第雙鏈表第i個結點后插入值為個結點后插入值為x的新結點的新結點 / 函數參數函數參數:指向指向dnode類型變量的指針類型變量的指針head / datatype類型的變量類型的變量x, int類型的變量類型的變量 / 函數返回值函數返回值:指向指向dnode類型變量的指針類型變量的指針 / 文件名文件名:dlnklist.c,函數名函數名:insert() /

52、dnode *insert(dnode *head,datatype x,int i) dnode *p,*q; p=(dnode*)malloc(sizeof(dnode);/*分配空間分配空間*/ p-info=x;/*設置新結點的值設置新結點的值*/ if(i=0)/*在最前面插入一個值為在最前面插入一個值為x的新結點的新結點*/ p-llink=NULL;/*新插入的結點沒有前驅新插入的結點沒有前驅*/ p-rlink=head;/*新插入的結點的后繼是原來新插入的結點的后繼是原來雙鏈表中的第一個結點雙鏈表中的第一個結點*/ if (!head)/*原表為空原表為空*/ head=p;

53、 else head-llink=p;/*原來雙鏈表中第一個結點的前驅是原來雙鏈表中第一個結點的前驅是新插入的結點新插入的結點*/ head=p;/*新結點成為雙鏈表的第一個結點新結點成為雙鏈表的第一個結點*/ return head; q=find(head,i);/*查找第查找第i個結點個結點*/ if(!q)/*第第i個結點不存在個結點不存在*/ printf(第第%d個結點不存在個結點不存在,無法進行插入無法進行插入,i);free(p);return head; if(q-rlink=NULL)/*在最后一個結點后插入在最后一個結點后插入*/ p-rlink=q-rlink; /*即

54、為即為NULL,新插入的結點沒有后繼。新插入的結點沒有后繼。插入操作（插入操作（1）*/ p-llink=q;/*插入操作（插入操作（2）*/ q-rlink=p;/*插入操（插入操（4）*/ /*注意不能和下面的一般情況一樣處理注意不能和下面的一般情況一樣處理,這里如執(zhí)這里如執(zhí)行下面的（行下面的（3）將出錯?。⒊鲥e！*/ else/*一般情況下的插入一般情況下的插入*/ p-rlink=q-rlink; /*插入操作（插入操作（1）*/ p-llink=q;/*插入操作（插入操作（2）*/ q-rlink-llink=p;/*插入操作（插入操作（3）*/ q-rlink=p;/*插入操作（

55、插入操作（4）*/ return head; 算法算法3.20 在雙鏈表中第在雙鏈表中第i個結點后插入一個值為個結點后插入一個值為x的新結點的新結點雙鏈表刪除操作圖示雙鏈表刪除操作圖示 ：head(a) 被刪除的被刪除的q是雙鏈表中唯一的一個結點是雙鏈表中唯一的一個結點qNULL(b) 被刪除的被刪除的q是雙鏈表中的第一個結點（表中不只是雙鏈表中的第一個結點（表中不只這一個結點）這一個結點）qhead(1) head=head-rlink;(2) head-llink=NULL;(1) 雙鏈表刪除操作圖示雙鏈表刪除操作圖示 ：head(c) 被刪除的被刪除的q是雙鏈表中的最后一個結點是雙鏈表中

56、的最后一個結點qq-llink-rlink=NULL;q(1) q-llink-rlink=q-rlink;(2) q-rlink-llink=q-llink;(1)(2)head(d) 被刪除的被刪除的q是雙鏈表中既非第一也非最后的一個結點是雙鏈表中既非第一也非最后的一個結點/ 函數功能函數功能:在雙鏈表中刪除一個值為在雙鏈表中刪除一個值為x的結點的結點 / 函數參數函數參數:指向指向dnode類型變量的指針類型變量的指針head / datatype類型的變量類型的變量x / 函數返回值函數返回值:指向指向dnode類型變量的指針類型變量的指針 / 文件名文件名:dlnklist.c,函數

57、名函數名:dele() / dnode dele(dnode head,datatype x) dnode q; if(!head)/ 雙鏈表為空雙鏈表為空,無法進行刪除操作無法進行刪除操作 / printf(雙鏈表為空雙鏈表為空,無法進行刪除操作無法進行刪除操作);return head; q=head; while(q&q-info!=x) q=q-rlink;/ 循環(huán)結束后循環(huán)結束后q指向的指向的是值為是值為x的結點的結點 / if(!q) printf(n沒有找到值為沒有找到值為%d的結點的結點!不做刪除操作！不做刪除操作！,x); if(q=head&head-rli

58、nk)/ 被刪除的結點是第一個結點被刪除的結點是第一個結點并且表中不只一個結點并且表中不只一個結點 / head=head-rlink; head-llink=NULL; free(q);return head; if(q=head&!head-rlink) / 被刪除的結點是第一個結點被刪除的結點是第一個結點并且表中只有這一個結點并且表中只有這一個結點 / free(q); return NULL; / 雙鏈表置空雙鏈表置空 / else if(!q-rlink) / 被刪除的結點是雙鏈表中的最后一個結點被刪除的結點是雙鏈表中的最后一個結點 / q-llink-rlink=NULL;

59、 free(q); return head; else / q是有是有2個以上結點的雙鏈表中的一個非開始、也個以上結點的雙鏈表中的一個非開始、也非終端結點非終端結點 / q-llink-rlink=q-rlink; q-rlink-llink=q-llink; free(q); return head; 算法算法3.21 在雙鏈表中刪除一個值為在雙鏈表中刪除一個值為x的結點的結點3.6 鏈式棧鏈式棧 3.6.1 鏈式棧鏈式棧 棧的鏈式存儲稱為鏈式棧。鏈式棧就是一個特殊棧的鏈式存儲稱為鏈式棧。鏈式棧就是一個特殊的單鏈表，對于這特殊的單鏈表，它的插入和刪除規(guī)的單鏈表，對于這特殊的單鏈表，它的插入和

60、刪除規(guī)定在單鏈表的同一端進行。鏈式棧的棧頂指針一般用定在單鏈表的同一端進行。鏈式棧的棧頂指針一般用top表示，鏈式棧如下圖所示。表示，鏈式棧如下圖所示。 top3.6.2 鏈式棧的實現鏈式棧的實現 / 函數功能函數功能:讀鏈式棧的讀鏈式棧的棧頂棧頂結點值結點值 / 函數參數函數參數:指向指向node類型變量的指針類型變量的指針top / 函數返回值函數返回值:datatype類型的變量類型的變量 / 文件名文件名:lnkstack.c,函數名函數名:read() / datatype read(node top) if(!top) printf(n鏈式棧是空的鏈式棧是空的!);exit(1); return (top-info); /*本函數可以調用本函數可以調用empty()函數函數*/ 算法算法3.24 取得鏈式棧的棧頂結點值取得鏈式棧的