C語言鏈表的建立、插入和刪除_第1頁
C語言鏈表的建立、插入和刪除_第2頁
C語言鏈表的建立、插入和刪除_第3頁
C語言鏈表的建立、插入和刪除_第4頁
C語言鏈表的建立、插入和刪除_第5頁
已閱讀5頁,還剩5頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

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

2、表,下面將逐一介紹。7.4.1 單鏈表圖7 - 3是單鏈表的結(jié)構(gòu)。 單鏈表有一個頭節(jié)點h e a d,指向鏈表在內(nèi)存的首地址。鏈表中的每一個節(jié)點的數(shù)據(jù)類型為結(jié)構(gòu)體類型,節(jié)點有兩個成員:整型成員(實際需要保存的數(shù)據(jù))和指向下一個結(jié)構(gòu)體類型節(jié)點的指針即下一個節(jié)點的地址(事實上,此單鏈表是用于存放整型數(shù)據(jù)的動態(tài)數(shù)組)。鏈表按此結(jié)構(gòu)對各節(jié)點的訪問需從鏈表的頭找起,后續(xù)節(jié)點的地址由當(dāng)前節(jié)點給出。無論在表中訪問那一個節(jié)點,都需要從鏈表的頭開始,順序向后查找。鏈表的尾節(jié)點由于無后續(xù)節(jié)點,其指針域為空,寫作為n u l l。圖7 - 3還給出這樣一層含義,鏈表中的各節(jié)點在內(nèi)存的存儲地址不是連續(xù)的,其各節(jié)點的地

3、址是在需要時向系統(tǒng)申請分配的,系統(tǒng)根據(jù)內(nèi)存的當(dāng)前情況,既可以連續(xù)分配地址,也可以跳躍式分配地址??匆幌骆湵砉?jié)點的數(shù)據(jù)結(jié)構(gòu)定義:struct nodeint num;struct node *p; ;在鏈表節(jié)點的定義中,除一個整型的成員外,成員p是指向與節(jié)點類型完全相同的指針。在鏈表節(jié)點的數(shù)據(jù)結(jié)構(gòu)中,非常特殊的一點就是結(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)建一個空表。3 ) 利用m a l l o c ( )函數(shù)向系統(tǒng)申請分配一個節(jié)點。4 ) 將新節(jié)點的指針成員賦值

4、為空。若是空表,將新節(jié)點連接到表頭;若是非空表,將新節(jié)點接到表尾。5 ) 判斷一下是否有后續(xù)節(jié)點要接入鏈表,若有轉(zhuǎn)到3 ),否則結(jié)束。 單鏈表的輸出過程有以下幾步1) 找到表頭。2) 若是非空表,輸出節(jié)點的值成員,是空表則退出。3 ) 跟蹤鏈表的增長,即找到下一個節(jié)點的地址。4) 轉(zhuǎn)到2 )。例7-5 創(chuàng)建一個存放正整數(shù)(輸入- 9 9 9做結(jié)束標志)的單鏈表,并打印輸出。#include /包*含ma l l o c ( ) 的頭文件*/#include struct node /*鏈表節(jié)點的結(jié)構(gòu)* /int num;struct node *next; ;m a i n ( )struct

5、 node *creat(); / *函數(shù)聲明* /void print();struct node *head; / * 定義頭指針* /head=null;/*建一個空表*/head=creat(head);/*創(chuàng)建單鏈表*/print(head);/*打印單鏈表*/*/ struct node*creat(structnode*head)函/數(shù)*返回的是與節(jié)點相同類型的指針*/struct node*p1,*p2;p1=p2=(structnode*)malloc(sizeof(structnode);申請/*新節(jié)點*/scanf(%d,&p1-num);/*輸入節(jié)點的值*/p1-nex

6、t=null;/*將新節(jié)點的指針置為空*/while(p1-num0)/*輸入節(jié)點的數(shù)值大于0*/if(head=null)head=p1;/*空表,接入表頭*/elsep2-next=p1;/*非空表,接到表尾*/p2=p1;p1=(structnode*)malloc(sizeof(structnode);申/請*下一個新節(jié)點*/scanf(%d,&p1-num);/*輸入節(jié)點的值*/return head;/*返回鏈表的頭指針*/*/void print(struct node*head)輸/*出以head為頭的鏈表各節(jié)點的值*/struct node *temp;temp=head;/

7、*取得鏈表的頭指針*/while(temp!=null)/*只要是非空表*/printf(%6d,temp-num);/*輸出鏈表節(jié)點的值*/temp=temp-next;/*跟蹤鏈表增長*/ 在鏈表的創(chuàng)建過程中,鏈表的頭指針是非常重要的參數(shù)。因為對鏈表的輸出和查找都要從鏈表的頭開始,所以鏈表創(chuàng)建成功后,要返回一個鏈表頭節(jié)點的地址,即頭指針。 7.4.2 單鏈表的插入與刪除在鏈表這種特殊的數(shù)據(jù)結(jié)構(gòu)中,鏈表的長短需要根據(jù)具體情況來設(shè)定,當(dāng)需要保存數(shù)據(jù)時向系統(tǒng)申請存儲空間,并將數(shù)據(jù)接入鏈表中。對鏈表而言,表中的數(shù)據(jù)可以依此接到表尾或連結(jié)到表頭,也可以視情況插入表中;對不再需要的數(shù)據(jù),將其從表中刪除

8、并釋放其所占空間,但不能破壞鏈表的結(jié)構(gòu)。這就是下面將介紹的鏈表的插入與刪除。1. 鏈表的刪除在鏈表中刪除一個節(jié)點,用圖7 - 4描述如下:例7-6 創(chuàng)建一個學(xué)生學(xué)號及姓名的單鏈表,即節(jié)點包括學(xué)生學(xué)號、姓名及指向下一個節(jié)點的指針,鏈表按學(xué)生的學(xué)號排列。再從鍵盤輸入某一學(xué)生姓名,將其從鏈表中刪除。首先定義鏈表的結(jié)構(gòu):struct從圖7 - 4中看到,從鏈表中刪除一個節(jié)點有三種情況,即刪除鏈表頭節(jié)點、刪除鏈表的中間節(jié)點、刪除鏈表的尾節(jié)點。題目給出的是學(xué)生姓名,則應(yīng)在鏈表中從頭到尾依此查找各節(jié)點,并與各節(jié)點的學(xué)生姓名比較,若相同,則查找成功,否則,找不到節(jié)點。由于刪除的節(jié)點可能在鏈表的頭,會對鏈表的頭

9、指針造成丟失,所以定義刪除節(jié)點的函數(shù)的返回值定義為返回結(jié)構(gòu)體類型的指針。struct node *delet(head,pstr)以/*he a d 為頭指針,刪除ps t r 所在節(jié)點*/ struct node *head;char *pstr;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-nex

10、t!=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 ) ; / *釋放被刪節(jié)點* /e l s ep-next=temp-next; /表*中節(jié)點*/pr

11、intf(delete string :%sn,temp-str);f r e e ( t e m p ) ;else printf(nno find string!n);沒/找* 到要刪除的字符串*/ r e t u r n ( h e a d ) ; / *返回表頭指針* /2. 鏈表的插入首先定義鏈表的結(jié)構(gòu):structint num; /*學(xué)生學(xué)號* /char str20; /*姓名* /struct node *next; ;在建立的單鏈表中,插入節(jié)點有三種情況,如圖7 - 5所示。 插入的節(jié)點可以在表頭、表中或表尾。假定我們按照以學(xué)號為順序建立鏈表,則插入的節(jié)點依次與表中節(jié)點相比

12、較,找到插入位置。由于插入的節(jié)點可能在鏈表的頭,會對鏈表的頭指針造成修改,所以定義插入節(jié)點的函數(shù)的返回值定義為返回結(jié)構(gòu)體類型的指針。節(jié)點的插入函數(shù)如下:struct node *insert(head,pstr,n) / *插入學(xué)號為n、姓名為p s t r 的節(jié)點* /struct node *head; / *鏈表的頭指針* /char *pstr; int n;struct node *p1,*p2,*p3;p1=(struct node*)malloc(sizeof(struct node)分;配/*一個新節(jié)點*/s t r c p y ( p 1 - s t r , p s t r

13、) ; / * 寫入節(jié)點的姓名字串* /p 1 - n u m = n ; / * 學(xué)號* /p 2 = h e a d ;if (head=null) / * 空表* /head=p1; p1-next=null;/ *新節(jié)點插入表頭* /e l s e /*非空表* /while(np2-num&p2-next!=null)/ *輸入的學(xué)號小于節(jié)點的學(xué)號,并且未到表尾* /p 3 = p 2 ;p 2 = p 2 - n e x t ; / * 跟蹤鏈表增長* /if (nnum) / *找到插入位置* / if (head=p2) / * 插入位置在表頭* /h e a d = p 1

14、;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 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)建包含學(xué)號、姓名節(jié)點的單鏈表。其節(jié)點數(shù)任意個,表以學(xué)號為序,低學(xué)號的在前,高學(xué)號的在后,以輸入姓名為空作結(jié)束。在此鏈表中,要求刪除一個給定姓名的節(jié)點,并插入一個給定學(xué)號和姓名的節(jié)點。# in

15、clude stdlib.h# include malloc. hstruct node /*節(jié)點的數(shù)據(jù)結(jié)構(gòu)* /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; /*做空

16、表* /head=creat (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); /*輸入學(xué)號* /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); /*輸入被刪姓名* /head=del

17、et(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

18、(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 l ;pl=(struct node *)malloc(sizeof(struct node);printf (input num, name: n);printf(exit:double times enter!n); g e t s ( t

19、e m p ) ;gets(pl -str);p1-num=atoi (temp);p 1 - 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;p1=(struct node*)malloc(sizeof(struc

20、t 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 ;elsep 3 - n e x t = p l ;p l - n e x t = p 2 ;e

21、lsep 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 (head, pstr)struct node *head;char *pstr;struct node *temp,*p;t e m p = h e a d ;if (head=null)printf(nlist is null!n);els

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論