C語言鏈表專題復習

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

2、單鏈表、 循環(huán)鏈表、雙向鏈表，下面只介紹單向鏈表。741 單鏈表圖7 - 3是單鏈表的結構。I 口曲I汕00 III 剛 II 河I圖圧3單醫(yī)表單鏈表有一個頭節(jié)點h e a d，指向鏈表在內(nèi)存的首地址。鏈表中的每一個節(jié)點 的數(shù)據(jù)類型為結構體類型，節(jié)點有兩個成員：整型成員（實際需要保存的數(shù)據(jù)） 和指向下一個結構體類型節(jié)點的指針即下一個節(jié)點的地址（事實上，此單鏈表 是用于存放整型數(shù)據(jù)的動態(tài)數(shù)組）。鏈表按此結構對各節(jié)點的訪問需從鏈表的頭 找起，后續(xù)節(jié)點的地址由當前節(jié)點給出。無論在表中訪問那一個節(jié)點，都需要 從鏈表的頭開始，順序向后查找。鏈表的尾節(jié)點由于無后續(xù)節(jié)點，其指針域為 空，寫作為N U L L

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

4、m a l l o c （）函數(shù)向系統(tǒng)申請分配一個節(jié)點。將新節(jié)點的指針成員賦值為空。若是空表，將新節(jié)點連接到表頭；若是非判斷一下是否有后續(xù)節(jié)點要接入鏈表，若有轉到 3 ) ，否則結束。 單鏈表的輸出過程有以下幾步找到表頭。 若是非空表，輸出節(jié)點的值成員，是空表則退出。跟蹤鏈表的增長，即找到下一個節(jié)點的地址。轉到 2 ) ?？毡?，將新 節(jié)點接到表尾。5 ) 1)2)3 )4) 下列是用尾插法創(chuàng)建鏈表 新開辟的節(jié)點總是插在表末 例 7-5 創(chuàng)建一個存放正整數(shù)(輸入負數(shù)時做結束標志)的單鏈表，并打印輸 出。的頭文件 */#include <stdlib.h> /包*含 ma l l o

5、c ( )#include <stdio.h>struct node /* 鏈表節(jié)點的結構 * /函數(shù)聲明 * /定義頭指針 * /*/ int num; struct node *next; ; m a i n ( ) struct node *creat(); / * void print(); struct node *head; / * head=NULL;/* 建一個空表head=creat(head);/* 創(chuàng)建單鏈表 */ print(head);/* 打印單鏈表 */函/ 數(shù)* 返回的是與節(jié)點相同類型的指針/*/ struct node*creat(structno

6、de*head)*/申請/* 新節(jié)點 */申/ 請*下一個新節(jié)點 */struct node*p1,*p2; p1=p2=(structnode*)malloc(sizeof(structnode); scanf("%d",&p1->num);/* 輸入節(jié)點的值 */ p1->next=NULL;/* 將新節(jié)點的指針置為空 */ while(p1->num>0)/* 輸入節(jié)點的數(shù)值大于 0*/ if(head=NULL)head=p1;/* 空表，接入表頭 */ elsep2->next=p1;/* 非空表，接到表尾 */ p2=p1;

7、p1=(structnode*)malloc(sizeof(structnode); scanf("%d",&p1->num);/* 輸入節(jié)點的值 */ return head;/* 返回鏈表的頭指針 */ /*/輸/*出以head為頭的鏈表各節(jié)點的值*/void prin t(struct no de*head)struct node *temp;temp=head;/*取得鏈表的頭指針*/ while(temp匸NULL)/*只要是非空表*/printf("%6d",temp->num);/*輸出鏈表節(jié)點的值 */temp=tem

8、p->next;/* 跟蹤鏈表增長 */ 在鏈表的創(chuàng)建過程中，鏈表的頭指針是非常重要的參數(shù)。因為對鏈表的輸出和 查找都要從鏈表的頭開始，所以鏈表創(chuàng)建成功后，要返回一個鏈表頭節(jié)點的地 址，即頭指針。丄5M45eT-2*1234567創(chuàng)建空衷：bead 申館新節(jié)點：ahull僅孟的創(chuàng)建過程用圖示抑下：第二步.第五也P 一卩若是變表.搟新節(jié)點按到姦頭:headPlr2若呈非空表.日dP2->ue7tr= P i. p2-pl head 申iH新節(jié)點：plNULLplXULLKULLpMMJLL若數(shù)伯為負，則I結束：否則轉列第三步：下列是用頭插法創(chuàng)建鏈表 新開辟的結點總是作為表頭結點 程序

9、清單位：#i nclude <stdio.h>#i nclude <stdlib.h>struct node int num;struct node *n ext; ;struct node *creat(struct node *head) struct node *top; /*top為新開辟的結點 */top=(struct node *)malloc(sizeof(struct no de); scanf( “ (”，&top->num);while(t op->num>=0)原來的第一個結點接在新開辟的結點后面*/top->n

10、ext=head; /*head=top; /* 新開辟結點作表頭結點，也就是說插在表頭 */ top=(struct node *)malloc(sizeof(struct node);scanf( “%d” ,&top->num); return head; 7.4.2 單鏈表的插入與刪除 在鏈表這種特殊的數(shù)據(jù)結構中，鏈表的長短需要根據(jù)具體情況來設定，當需要 保存數(shù)據(jù)時向系統(tǒng)申請存儲空間，并將數(shù)據(jù)接入鏈表中。對鏈表而言，表中的 數(shù)據(jù)可以依此接到表尾或連結到表頭，也可以視情況插入表中；對不再需要的 數(shù)據(jù)，將其從表中刪除并釋放其所占空間，但不能破壞鏈表的結構。這就是下 面將介紹的

11、鏈表的插入與刪除。鏈表按學生的學號排列。再從鍵盤輸入某一學生姓名，1. 鏈表的刪除 在鏈表中刪除一個節(jié)點，用圖 7 - 4 描述如下： 例 7-6 創(chuàng)建一個學生學號及姓名的單鏈表，即節(jié)點包括學生學號、姓名及指 向下一個節(jié)點的指針， 將其從鏈表中刪除。從鏈表中刪除一個節(jié)點有三種情況，即刪除鏈表頭節(jié)點、 刪除鏈表的尾節(jié)點。題目給出的是學生姓名，則應在鏈首先定義鏈表的結構： 從圖 7 - 4 中看到， 刪除鏈表的中間節(jié)點、 表中從頭到尾依此查找各節(jié)點，并與各節(jié)點的學生姓名比較，若相同，則查找 成功，否則，找不到節(jié)點。由于刪除的節(jié)點可能在鏈表的頭，會對鏈表的頭指 針造成丟失，所以定義刪除節(jié)點的函數(shù)的返

12、回值定義為返回結構體類型的指針。 struct node *delet(struct node *head,char *pstr) /*he a d 為頭指針，刪除 ps t r 所在節(jié)點 */ 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&&te

13、mp->next!=NULL) / * 若節(jié)點的字符串與輸入字符串不同，并且未到鏈表尾 p = t e m p ;跟蹤鏈表的增長，即指針后移 * /找到字符串 * /t e m p = t e m p - > n e x t ; / * if(strcmp(temp->str,pstr)=0 ) / * if(temp=head) / *表頭節(jié)點 * /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 ) ; / *釋

14、放被刪節(jié)點 * /e l s ep->next=temp->next; /* 表中節(jié)點 */ prin tf("delete stri ng :%sn",te mp->str); f r e e ( t e m p ); else prin tf("nno find stri ng!n");r e t u r n ( h e a d ) ; / *2.鏈表的插入 首先定義鏈表的結構：struct int num; /*學生學號* /char str20; /* 姓名 * / struct node *n ext;在建立的單鏈表中，插入節(jié)

15、點有三種情況，如圖在*頭摘入節(jié)鄭擊中1head/*沒找到要刪除的字符串*/返回表頭指針* / 7 - 5所示。I |NLT-L|血也,P2» jNITL|plIi匸£在套尾權入節(jié)點pl* p2-：iifi!xt=pl. phguaeXULL 典I 十 I I I 一國單橈裘中啃入節(jié)點插入的節(jié)點可以在表頭、表中或表尾。假定我們按照以學號為順序建立鏈表， 則插入的節(jié)點依次與表中節(jié)點相比較，找到插入位置。由于插入的節(jié)點可能在 鏈表的頭，會對鏈表的頭指針造成修改，所以定義插入節(jié)點的函數(shù)的返回值定 義為返回結構體類型的指針。節(jié)點的插入函數(shù)如下：struct node *insert(

16、head,pstr,n) / *插入學號為 n、姓名為 p s t r 的節(jié)點* /struct node *head; / * 鏈表的頭指針 * /char *p str;int n;分；配/* 一個新節(jié)點*/ 寫入節(jié)點的姓名字串*/ struct n ode *p 1,* p2,* p3;p 1=(struct no de*)malloc(sizeof(struct no de)s t r c p y ( p 1 - > s t r , p s t r ) ; / *p 1 - > n u m = n ; / *學號 * /p 2 = h e a d ;if (head=NUL

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

18、 2 ; e l s e /* 插入位置在表中 p 3 - > n e x t = p 1 ; p 1 - > n e x 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. 實例例 7 - 7 創(chuàng)建包含學號、姓名節(jié)點的單鏈表。其節(jié)點數(shù)任意個，表以學號為序，低學號 的在前，高學號的在后，以輸入姓名為空作結束。在此鏈表中，要求刪除一個 給定姓名的節(jié)點，并插入一個給定學號和姓名的

19、節(jié)點。# include "stdlib.h"# include "malloc. h" struct node /* 節(jié)點的數(shù)據(jù)結構 * / int num;char str20; 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 (

20、head); / *調(diào)用函數(shù)創(chuàng)建以 head 為頭的鏈表 * /p r i n t ( h e a d )； / * 調(diào)用函數(shù)輸出節(jié)點 * /printf("n input inserted num,name:n");gets(str); /*輸入學號 * /n=atoi (str); gets(str); /*輸入姓名 * /head=insert (head, str, n);將/* 節(jié)點插入鏈表 */print (head) ； / * 調(diào)用函數(shù)輸出節(jié)點 */ printf("n input deleted name:n");gets(str);

21、/*輸入被刪姓名 * /head=delet(head,str); /調(diào) *用函數(shù)刪除節(jié)點 */print (head); /*調(diào)用函數(shù)輸出節(jié)點 * /r e t u r n ; / * * *創(chuàng)建鏈表 * * * * * * * * * * * * /struct node *creat(struct node *head) char temp30;struct node *pl,*p2;pl=p2=(struct node*) malloc(sizeof(struct node); printf ("input num, name: n;") printf("

22、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)>0 if (head=NULL) head=pl ；else p2->next=p1;P 2 = p l ；pl=(struct node *)malloc(sizeof(struct node); printf ("input num, name: n")

23、;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é)點 * * * * * * * * * * /struct node *insert (head, pstr,n);struct node *head; char *pstr; int n; struct node *pl,*p2,*p3; p

24、1=(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 e while (n>p2->num&&p2->next!=NULL) p 3 = P 2 p 2 = p 2 - > n e x t ; if (n<=p2->num)

25、 if (head=p2) h e a d = p l ;p l - > n e x t = p 2 ; else p 3 - > n e x t = p l ; p l - > n e x t = p 2 ; else p 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é)點 * * * * * * * * * * * * * /struct node *delet (struct node *head, char *pstr) st

26、ruct 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)!=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=

27、 head) h e a d = h e a d - > n e x t ; f r e e ( t e m p ) ; else p->next =temp->next; printf("delete string :%sn",temp->str); f r e e ( t e m p ) ; else printf("nno find string!n"); return(head); / * * * * * * * * * *鏈表各節(jié)點的輸出 * * * * * * * * * * /，t e mvoid print (st

28、ruct 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 p - > s t r )；t e m p = t e m p - > n e x t r e t u r n ; 帶頭結點與不帶頭結點鏈表的區(qū)別： 題目中沒說明，就當不帶頭結點，除非明確規(guī)定了帶頭結點。 帶頭結點的鏈表的第一個結點沒有數(shù)據(jù)域，只有指針域。例如要計算鏈表中所 有結點數(shù)據(jù)的和，應定義一個指向結構體結點的指針，指向鏈表的第一個含數(shù) 據(jù)的結點，給它賦值時， 應是 struct node *p=head->next;其中 head 為鏈表的頭指針。因為頭結點不含數(shù)據(jù)，頭結點指向的結點才開始帶數(shù)據(jù)。如果是不帶頭結點的鏈表，第一 個結點就含數(shù)據(jù)，因此，給它賦值時，應是 struct node *p=head; 附：常見算法用鏈表實現(xiàn)1. 查找算法 例：如果有如下鏈表結構：struct st/*學生姓名 */學生成績 */ char n a