C語言鏈表專題復(fù)習(xí)

1、。鏈表專題復(fù)習(xí)數(shù)組作為存放同類數(shù)據(jù)的集合，給我們?cè)诔绦蛟O(shè)計(jì)時(shí)帶來很多的方便，增加了靈活性。但數(shù)組也同樣存在一些弊病。如數(shù)組的大小在定義時(shí)要事先規(guī)定，不能在程序中進(jìn)行調(diào)整，這樣一來，在程序設(shè)計(jì)中針對(duì)不同問題有時(shí)需要 3 0 個(gè)元素大小的數(shù)組，有時(shí)需要 5 0 個(gè)數(shù)組元素的大小，難于統(tǒng)一。我們只能夠根據(jù)可能的最大需求來定義數(shù)組，常常會(huì)造成一定存儲(chǔ)空間的浪費(fèi)。我們希望構(gòu)造動(dòng)態(tài)的數(shù)組，隨時(shí)可以調(diào)整數(shù)組的大小，以滿足不同問題的需要。鏈表就是我們需要的動(dòng)態(tài)數(shù)組。它是在程序的執(zhí)行過程中根據(jù)需要有數(shù)據(jù)存儲(chǔ)就向系統(tǒng)要求申請(qǐng)存儲(chǔ)空間，決不構(gòu)成對(duì)存儲(chǔ)區(qū)的浪費(fèi)。鏈表是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，其數(shù)據(jù)之間的相互關(guān)系使鏈表分成

2、三種：?jiǎn)捂湵?、循環(huán)鏈表、雙向鏈表，下面只介紹單向鏈表。7.4.1單鏈表圖 7 - 3是單鏈表的結(jié)構(gòu)。單鏈表有一個(gè)頭節(jié)點(diǎn)h e a d ，指向鏈表在內(nèi)存的首地址。鏈表中的每一個(gè)節(jié)點(diǎn)的數(shù)據(jù)類型為結(jié)構(gòu)體類型，節(jié)點(diǎn)有兩個(gè)成員：整型成員（實(shí)際需要保存的數(shù)據(jù)）和指向下一個(gè)結(jié)構(gòu)體類型節(jié)點(diǎn)的指針即下一個(gè)節(jié)點(diǎn)的地址（事實(shí)上，此單鏈表是用于存放整型數(shù)據(jù)的動(dòng)態(tài)數(shù)組） 。鏈表按此結(jié)構(gòu)對(duì)各節(jié)點(diǎn)的訪問需從鏈表的頭找起，后續(xù)節(jié)點(diǎn)的地址由當(dāng)前節(jié)點(diǎn)給出。無論在表中訪問那一個(gè)節(jié)點(diǎn)，都需要從鏈表的頭開始，順序向后查找。鏈表的尾節(jié)點(diǎn)由于無后續(xù)節(jié)點(diǎn)，其指針域?yàn)榭?，寫作?NULL 。圖 7 - 3 還給出這樣一層含義，鏈表中的各節(jié)點(diǎn)在

3、內(nèi)存的存儲(chǔ)地址不是連續(xù)的，其各節(jié)點(diǎn)的地址是在需要時(shí)向系統(tǒng)申請(qǐng)分配的，系統(tǒng)根據(jù)內(nèi)存的當(dāng)前情況，既可以連續(xù)分配地址，也可以跳躍式分配地址?？匆幌骆湵砉?jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義： struct nodeint num; struct node *p; ;在鏈表節(jié)點(diǎn)的定義中，除一個(gè)整型的成員外，成員 p 是指向與節(jié)點(diǎn)類型完全相同的指針。在鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)中，非常特殊的一點(diǎn)就是結(jié)構(gòu)體內(nèi)的指針域的數(shù)據(jù)類型使用了未定義成功的數(shù)據(jù)類型。這是在C 中唯一規(guī)定可以先使用后定義的數(shù)據(jù)結(jié)構(gòu)。? 單鏈表的創(chuàng)建過程有以下幾步：1 )定義鏈表的數(shù)據(jù)結(jié)構(gòu)。2 )創(chuàng)建一個(gè)空表。3 )利用 m a l l o c ( )函數(shù)向系統(tǒng)申請(qǐng)

4、分配一個(gè)節(jié)點(diǎn)。精選資料，歡迎下載。4 ) 將新節(jié)點(diǎn)的指針成員賦值為空。若是空表，將新節(jié)點(diǎn)連接到表頭；若是非空表，將新節(jié)點(diǎn)接到表尾。5 )判斷一下是否有后續(xù)節(jié)點(diǎn)要接入鏈表，若有轉(zhuǎn)到3 ) ，否則結(jié)束。? 單鏈表的輸出過程有以下幾步 1) 找到表頭。2) 若是非空表，輸出節(jié)點(diǎn)的值成員，是空表則退出。3 ) 跟蹤鏈表的增長(zhǎng)，即找到下一個(gè)節(jié)點(diǎn)的地址。4) 轉(zhuǎn)到2)。下列是用尾插法創(chuàng)建鏈表新開辟的節(jié)點(diǎn)總是插在表末 例 7-5 創(chuàng)建一個(gè)存放正整數(shù)（輸入負(fù)數(shù)時(shí)做結(jié)束標(biāo)志）的單鏈表，并打印輸出。#include /包* 含 ma l l o c ( )的頭文件 */#include struct node /

5、*鏈表節(jié)點(diǎn)的結(jié)構(gòu) * /int num;struct node *next; ;m a i n ( )struct node *creat(); / *函數(shù)聲明 * /void print();struct node *head; / *定義頭指針 * /head=NULL;/* 建一個(gè)空表 */head=creat(head);/*創(chuàng)建單鏈表 */print(head);/*打印單鏈表 */*/struct node*creat(structnode*head)函/ 數(shù)* 返回的是與節(jié)點(diǎn)相同類型的指針*/struct node*p1,*p2;p1=p2=(structnode*)malloc

6、(sizeof(structnode); 申請(qǐng) /* 新節(jié)點(diǎn) */ scanf(%d,&p1-num);/* 輸入節(jié)點(diǎn)的值 */ p1-next=NULL;/* 將新節(jié)點(diǎn)的指針置為空 */while(p1-num0)/*輸入節(jié)點(diǎn)的數(shù)值大于0*/if(head=NULL)head=p1;/*空表，接入表頭 */elsep2-next=p1;/*非空表，接到表尾 */p2=p1;p1=(structnode*)malloc(sizeof(structnode); 申/ 請(qǐng)* 下一個(gè)新節(jié)點(diǎn) */ scanf(%d,&p1-num);/* 輸入節(jié)點(diǎn)的值 */return head;/*返回鏈表的頭指針

7、 */精選資料，歡迎下載。/*/void print(struct node*head)輸/* 出以 head 為頭的鏈表各節(jié)點(diǎn)的值*/struct node *temp;temp=head;/* 取得鏈表的頭指針 */while(temp!=NULL)/*只要是非空表 */printf(%6d,temp-num);/* 輸出鏈表節(jié)點(diǎn)的值 */ temp=temp-next;/* 跟蹤鏈表增長(zhǎng) */ 在鏈表的創(chuàng)建過程中，鏈表的頭指針是非常重要的參數(shù)。因?yàn)閷?duì)鏈表的輸出和查找都要從鏈表的頭開始，所以鏈表創(chuàng)建成功后，要返回一個(gè)鏈表頭節(jié)點(diǎn)的地址，即頭指針。下列是用頭插法創(chuàng)建鏈表新開辟的結(jié)點(diǎn)總是作為表頭

8、結(jié)點(diǎn)程序清單位：#include #include struct node int num;struct node *next; ;struct node *creat(struct node *head) struct node *top; /*top 為新開辟的結(jié)點(diǎn) */ top=(struct node *)malloc(sizeof(struct node); scanf( “ %d”,&top-num); while(top-num=0)精選資料，歡迎下載。top-next=head;/*原來的第一個(gè)結(jié)點(diǎn)接在新開辟的結(jié)點(diǎn)后面*/head=top;/*新開辟結(jié)點(diǎn)作表頭結(jié)點(diǎn)，也就是說插在

9、表頭*/top=(struct node *)malloc(sizeof(struct node);scanf( “%d” ,&top-num);return head;7.4.2單鏈表的插入與刪除在鏈表這種特殊的數(shù)據(jù)結(jié)構(gòu)中，鏈表的長(zhǎng)短需要根據(jù)具體情況來設(shè)定，當(dāng)需要保存數(shù)據(jù)時(shí)向系統(tǒng)申請(qǐng)存儲(chǔ)空間，并將數(shù)據(jù)接入鏈表中。對(duì)鏈表而言，表中的數(shù)據(jù)可以依此接到表尾或連結(jié)到表頭，也可以視情況插入表中；對(duì)不再需要的數(shù)據(jù)，將其從表中刪除并釋放其所占空間，但不能破壞鏈表的結(jié)構(gòu)。這就是下面將介紹的鏈表的插入與刪除。1. 鏈表的刪除在鏈表中刪除一個(gè)節(jié)點(diǎn)，用圖7 - 4描述如下： 例 7-6 創(chuàng)建一個(gè)學(xué)生學(xué)號(hào)及姓名的單

10、鏈表，即節(jié)點(diǎn)包括學(xué)生學(xué)號(hào)、姓名及指向下一個(gè)節(jié)點(diǎn)的指針，鏈表按學(xué)生的學(xué)號(hào)排列。再?gòu)逆I盤輸入某一學(xué)生姓名，將其從鏈表中刪除。首先定義鏈表的結(jié)構(gòu)：從圖 7 - 4 中看到，從鏈表中刪除一個(gè)節(jié)點(diǎn)有三種情況，即刪除鏈表頭節(jié)點(diǎn)、刪除鏈表的中間節(jié)點(diǎn)、刪除鏈表的尾節(jié)點(diǎn)。題目給出的是學(xué)生姓名，則應(yīng)在鏈表中從頭到尾依此查找各節(jié)點(diǎn)，并與各節(jié)點(diǎn)的學(xué)生姓名比較，若相同，則查找成功，否則，找不到節(jié)點(diǎn)。由于刪除的節(jié)點(diǎn)可能在鏈表的頭，會(huì)對(duì)鏈表的頭指針造成丟失，所以定義刪除節(jié)點(diǎn)的函數(shù)的返回值定義為返回結(jié)構(gòu)體類型的指針。struct node *delet(struct node *head,char *pstr)/*he a

11、d為頭指針，刪除ps t r所在節(jié)點(diǎn) */struct node *temp,*p;t e m p = h e a d ; / *鏈表的頭指針 * /if (head=NULL) / *鏈表為空 * /printf(nList is null!n);else /*非空表 * /t e m p = h e a d ;while (strcmp(temp-str,pstr)!=0&temp-next!=NULL)/ *若節(jié)點(diǎn)的字符串與輸入字符串不同，并且未到鏈表尾* /p = t e m p ;t e m p = t e m p - n e x t ; / *跟蹤鏈表的增長(zhǎng)，即指針后移* /if(

12、strcmp(temp-str,pstr)=0 ) / *找到字符串 * /if(temp=head) / *表頭節(jié)點(diǎn) * /printf(delete string :%sn,temp-str);h e a d = h e a d - n e x t ;精選資料，歡迎下載。f r e e ( t e m p ) ; / *釋放被刪節(jié)點(diǎn) * /e l s ep-next=temp-next; /*表中節(jié)點(diǎn) */printf(delete string :%sn,temp-str);f r e e ( t e m p ) ;else printf(nno find string!n);/*沒找到

13、要?jiǎng)h除的字符串*/r e t u r n ( h e a d ) ; / *返回表頭指針 * /2.鏈表的插入首先定義鏈表的結(jié)構(gòu)：struct int num; /*學(xué)生學(xué)號(hào) * /char str20; /*姓名 * /struct node *next; ;在建立的單鏈表中，插入節(jié)點(diǎn)有三種情況，如圖7-5所示。插入的節(jié)點(diǎn)可以在表頭、表中或表尾。假定我們按照以學(xué)號(hào)為順序建立鏈表，則插入的節(jié)點(diǎn)依次與表中節(jié)點(diǎn)相比較，找到插入位置。由于插入的節(jié)點(diǎn)可能在鏈表的頭，會(huì)對(duì)鏈表的頭指針造成修改，所以定義插入節(jié)點(diǎn)的函數(shù)的返回值定義為返回結(jié)構(gòu)體類型的指針。節(jié)點(diǎn)的插入函數(shù)如下：struct node *inse

14、rt(head,pstr,n) / *插入學(xué)號(hào)為n、姓名為p s t r的節(jié)點(diǎn) * /struct node *head; / *鏈表的頭指針 * /char *pstr;int n; struct node *p1,*p2,*p3;p1=(struct node*)malloc(sizeof(struct node)分 ; 配 /* 一個(gè)新節(jié)點(diǎn) */精選資料，歡迎下載。s t r c p y ( p 1 - s t r , p s t r ) ; / *寫入節(jié)點(diǎn)的姓名字串 * /p 1 - n u m = n ; / *學(xué)號(hào) * /p 2 = h e a d ;if (head=NULL)

15、/ *空表 * /head=p1; p1-next=NULL;/ *新節(jié)點(diǎn)插入表頭 * /e l s e/*非空表*/while(np2-num&p2-next!=NULL)/ * 輸入的學(xué)號(hào)小于節(jié)點(diǎn)的學(xué)號(hào)，并且未到表尾* /p 3 = p 2 ;p 2 = p 2 - n e x t ; / *跟蹤鏈表增長(zhǎng) * /if (nnum) / *找到插入位置 * /if (head=p2) / *插入位置在表頭 * /h e a d = p 1 ;p 1 - n e x t = p 2 ;e l s e /* 插入位置在表中 * / p 3 - n e x t = p 1 ;p 1 - n e x

16、 t = p 2 ;e l s e /* 插入位置在表尾 * / p 2 - n e x t = p 1 ;p 1 - n e x t = N U L L ;r e t u r n ( h e a d ) ; / *返回鏈表的頭指針 * /3. 實(shí)例例7-7創(chuàng)建包含學(xué)號(hào)、姓名節(jié)點(diǎn)的單鏈表。其節(jié)點(diǎn)數(shù)任意個(gè)，表以學(xué)號(hào)為序，低學(xué)號(hào)的在前，高學(xué)號(hào)的在后，以輸入姓名為空作結(jié)束。在此鏈表中，要求刪除一個(gè)給定姓名的節(jié)點(diǎn)，并插入一個(gè)給定學(xué)號(hào)和姓名的節(jié)點(diǎn)。# include stdlib.h# include malloc. hstruct node /* 節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu) * /int num; char st

17、r20;struct node *next; ;精選資料，歡迎下載。main( ) /* 函數(shù)聲明*/ struct node *creat(); struct node *insert(); struct node *delet(); void print( );struct node *head; char str20;int n;head=NULL; /* 做空表 * /head=creat (head); / *調(diào)用函數(shù)創(chuàng)建以 head 為頭的鏈表 * /p r i n t ( h e a d )；/ * 調(diào)用函數(shù)輸出節(jié)點(diǎn) * /printf(n input inserted num,

18、name:n);gets(str); /*輸入學(xué)號(hào) * /n=atoi (str);gets(str); /*輸入姓名 * /head=insert (head, str, n);將/* 節(jié)點(diǎn)插入鏈表 */print (head)； / * 調(diào)用函數(shù)輸出節(jié)點(diǎn) */printf(n input deleted name:n);gets(str); /*輸入被刪姓名 * /head=delet(head,str); /調(diào) * 用函數(shù)刪除節(jié)點(diǎn) */print (head); /*調(diào)用函數(shù)輸出節(jié)點(diǎn) * /r e t u r n ;/*創(chuàng)建鏈表*/struct node *creat(struct no

19、de *head)char temp30;struct node *pl,*p2;pl=p2=(struct node*) malloc(sizeof(struct node);printf (input num, name: n;)printf(exit:double times Enter!n);g e t s ( t e m p ) ;gets (p1-str);pl-num=atoi (temp);p l - n e x t = N U L L ;while (strlen (pl-str)0if (head=NULL) head=pl；else p2-next=p1;P 2 = p

20、l；pl=(struct node *)malloc(sizeof(struct node);printf (input num, name: n);printf(exit:double times Enter!n);g e t s ( t e m p ) ;精選資料，歡迎下載。gets(pl -str);p1-num=atoi (temp);p1 - n e x t = N U L L ;return head;/*插入節(jié)點(diǎn)*/struct node *insert (head, pstr,n);struct node *head;char *pstr;int n;struct node *

21、pl,*p2,*p3;p1=(struct node*)malloc(sizeof(struct node);strcpy (p1-str, pstr);p 1 - n u m = n ;p 2 = h e a d ;i f ( h e a d = = N U L L )h e a d = p l ; p l - n e x t = N U L L ;e l s ewhile (np2-num&p2-next!=NULL)p 3 = P 2p 2 = p 2 - n e x t ;if (nnum)if (head=p2)h e a d = p l ;p l - n e x t = p 2 ;

22、elsep 3 - n e x t = p l ;p l - n e x t = p 2 ;elsep 2 - n e x t = p l ;p l - n e x t = N U L L ;r e t u r n ( h e a d ) ;/*刪除節(jié)點(diǎn)*/struct node *delet (struct node *head, char *pstr)struct node *temp,*p;t e m p = h e a d ;精選資料，歡迎下載struct node *p=head;。if (head=NULL)printf(nList is null!n);else t e m p

23、= h e a d ;while (strcmp(temp-str,pstr)!=O&temp-next!=NULL)p = t e m p ;t e m p = t e m p - n e x t ,i f ( s t r c m p ( t e m p - s t r , p s t r ) = = 0 )if (temp= head)h e a d = h e a d - n e x t ;f r e e ( t e m p ) ;elsep-next =temp-next;printf(delete string :%sn,temp-str);f r e e ( t e m p ) ;

24、else printf(nno find string!n);return(head);/*鏈表各節(jié)點(diǎn)的輸出 */void print (struct node *head)struct node *temp;t e m p = h e a d ;while (temp!=NULL)p r i n t f ( n % d - - - - % s n , t e m p - n u m，t e mp - s t r )；t e m p = t e m p - n e x t；r e t u r n ;帶頭結(jié)點(diǎn)與不帶頭結(jié)點(diǎn)鏈表的區(qū)別：題目中沒說明，就當(dāng)不帶頭結(jié)點(diǎn)，除非明確規(guī)定了帶頭結(jié)點(diǎn)。帶頭結(jié)點(diǎn)的

25、鏈表的第一個(gè)結(jié)點(diǎn)沒有數(shù)據(jù)域，只有指針域。例如要計(jì)算鏈表中所有結(jié)點(diǎn)數(shù)據(jù)的和，應(yīng)定義一個(gè)指向結(jié)構(gòu)體結(jié)點(diǎn)的指針，指向鏈表的第一個(gè)含數(shù)據(jù)的結(jié)點(diǎn)，給它賦值時(shí)，應(yīng)是 struct node *p=head-next; 其中 head 為鏈表的頭指針。因?yàn)轭^結(jié)點(diǎn)不含數(shù)據(jù)，頭結(jié)點(diǎn)指向的結(jié)點(diǎn)才開始帶數(shù)據(jù)。如果是不帶頭結(jié)點(diǎn)的鏈表，第一個(gè)結(jié)點(diǎn)就含數(shù)據(jù)，因此，給它賦值時(shí)，應(yīng)是精選資料，歡迎下載。附：常見算法用鏈表實(shí)現(xiàn)1. 查找算法例：如果有如下鏈表結(jié)構(gòu)： struct st char name20;/*學(xué)生姓名 */int cj;/*學(xué)生成績(jī) */struct st *next; ;如果鏈表已創(chuàng)建正確，要求輸入一個(gè)學(xué)生姓名，查找該