C語言鏈表詳解ppt.ppt

1、b,1,第十一章 鏈表 鏈表詳解 珍藏版,b,2,例：跳馬。依下圖將每一步跳馬之后的位置(x,y)放到一個(gè)“結(jié)點(diǎn)”里，再用“鏈子穿起來”，形成一條鏈，相鄰兩結(jié)點(diǎn)間用一個(gè)指針將兩者連到一起。,結(jié)構(gòu)的概念與應(yīng)用,b,3,依上圖有7個(gè)結(jié)點(diǎn),為了表示這種既有數(shù)據(jù)又有指針的情況，引入結(jié)構(gòu)這種數(shù)據(jù)類型。,b,4,11.7 用指針處理鏈表,鏈表是程序設(shè)計(jì)中一種重要的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，它是動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配的一種結(jié)構(gòu)。,動(dòng)態(tài)性體現(xiàn)為： 鏈表中的元素個(gè)數(shù)可以根據(jù)需要增加和減少，不像數(shù)組，在聲明之后就固定不變； 元素的位置可以變化，即可以從某個(gè)位置刪除，然后再插入到一個(gè)新的地方；,b,5,1、鏈表中的元素稱為“結(jié)點(diǎn)”

2、，每個(gè)結(jié)點(diǎn)包括兩個(gè)域：數(shù)據(jù)域和指針域； 2、單向鏈表通常由一個(gè)頭指針（head)，用于指向鏈表頭； 3、單向鏈表有一個(gè)尾結(jié)點(diǎn)，該結(jié)點(diǎn)的指針部分指向一個(gè)空結(jié)點(diǎn)(NULL) 。,Head 1249 1356 1475 1021,結(jié)點(diǎn)里的指針是存放下一個(gè)結(jié)點(diǎn)的地址,b,6,鏈表中結(jié)點(diǎn)的定義,鏈表是由結(jié)點(diǎn)構(gòu)成的， 關(guān)鍵是定義結(jié)點(diǎn); 鏈表的結(jié)點(diǎn)定義打破了先定義再使用的限制,即可以用自己定義自己； 遞歸函數(shù)的定義也違反了先定義再使用； 這是C語言程序設(shè)計(jì)上的兩大特例,b,7,鏈表的基本操作,對(duì)鏈表的基本操作有： （1）創(chuàng)建鏈表是指，從無到有地建立起一個(gè)鏈表，即往空鏈表中依次插入若干結(jié)點(diǎn)，并保持結(jié)點(diǎn)之間的前

3、驅(qū)和后繼關(guān)系。 （2）檢索操作是指，按給定的結(jié)點(diǎn)索引號(hào)或檢索條件，查找某個(gè)結(jié)點(diǎn)。如果找到指定的結(jié)點(diǎn)，則稱為檢索成功；否則，稱為檢索失敗。 （3）插入操作是指，在結(jié)點(diǎn)ki-1與ki之間插入一個(gè)新的結(jié)點(diǎn)k，使線性表的長度增1，且ki-1與ki的邏輯關(guān)系發(fā)生如下變化： 插入前，ki-1是ki的前驅(qū)，ki是ki-1的后繼；插入后，新插入的結(jié)點(diǎn)k成為ki-1的后繼、ki的前驅(qū).,b,8,（4）刪除操作是指，刪除結(jié)點(diǎn)ki，使線性表的長度減1，且ki-1、ki和ki+1之間的邏輯關(guān)系發(fā)生如下變化： 刪除前，ki是ki+1的前驅(qū)、ki-1的后繼；刪除后，ki-1成為ki+1的前驅(qū)，ki+1成為ki-1的后繼.

4、 (5)打印輸出,b,9,一個(gè)指針類型的成員既可指向其它類型的結(jié)構(gòu)體數(shù)據(jù)，也可以指向自己所在的結(jié)構(gòu)體類型的數(shù)據(jù),num Score next,next是struct student類型中的一個(gè)成員，它又指向struct student類型的數(shù)據(jù)。 換名話說：next存放下一個(gè)結(jié)點(diǎn)的地址,b,10,11.7.2 簡單鏈表,#define NULL 0 struct student long num; float score; struct student *next; ; main() struct student a, b, c, *head, *p; a.num=99101; a.score

5、=89.5; b. num=99103; b.score=90; c.num=99107 ; c.score=85; head= ,例11.7,建立和輸出一個(gè)簡單鏈表,各結(jié)點(diǎn)在程序中定義，不是臨時(shí)開辟的，始終占有內(nèi)容不放，這種鏈表稱為“靜態(tài)鏈表”,b,11,11.7.3 處理動(dòng)態(tài)鏈表所需的函數(shù),C 語言使用系統(tǒng)函數(shù)動(dòng)態(tài)開辟和釋放存儲(chǔ)單元,1.malloc 函數(shù),函數(shù)原形：void *malloc(unsigned int size); 作用：在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配 一個(gè) 長度為size的連續(xù)空間。 返回值：是一個(gè)指向分配域起始地址的指針（基本類型void）。 執(zhí)行失敗：返回NULL,b,12

6、,函數(shù)原形:void *calloc(unsigned n,unsigned size); 作用：在內(nèi)存動(dòng)態(tài)區(qū)中分配 n個(gè) 長度為size的連續(xù)空間。 函數(shù)返回值：指向分配域起始地址的指針 執(zhí)行失?。悍祷豱ull 主要用途：為一維數(shù)組開辟動(dòng)態(tài)存儲(chǔ)空間。n 為數(shù)組元素個(gè)數(shù)，每個(gè)元素長度為size,2. calloc 函數(shù),b,13,3. free 函數(shù),函數(shù)原形： void free(void *p); 作用：釋放由 p 指向的內(nèi)存區(qū)。 P:是最近一次調(diào)用 calloc 或 malloc 函數(shù)時(shí)返回的值。 free 函數(shù)無返回值 動(dòng)態(tài)分配的存儲(chǔ)單元在用完后一定要釋放，否則內(nèi)存會(huì)因申請(qǐng)空間過多引起

7、資源不足而出現(xiàn)故障。,b,14,結(jié)點(diǎn)的動(dòng)態(tài)分配,ANSI C 的三個(gè)函數(shù)(頭文件 malloc.h) void *malloc(unsigned int size) void *calloc(unsigned n, unsigned size) void free(void *p) C+ 的兩個(gè)函數(shù) new 類型（初值） delete 指針變量 /* 表示釋放數(shù)組，可有可無）*/ 使用 new 的優(yōu)點(diǎn)： 可以通過對(duì)象的大小直接分配，而不管對(duì)象的具體長度是多少（p340 例14.10）,b,15,11.7.4 建立動(dòng)態(tài)鏈表,基本方法: 三個(gè)結(jié)點(diǎn)（頭結(jié)點(diǎn)head、尾結(jié)點(diǎn) NULL 和待插入結(jié)點(diǎn) P

8、） 第一步：定義頭結(jié)點(diǎn)head、尾結(jié)點(diǎn) p2 和待插入結(jié)點(diǎn)p1，待插入的結(jié)點(diǎn)數(shù)據(jù)部分初始化； 第二步：該結(jié)點(diǎn)被頭結(jié)點(diǎn)、尾結(jié)點(diǎn)同時(shí)指向。P1=p2=(struct student*)malloc(LEN);頭指針部分為空，head=NULL; 第三步：重復(fù)申請(qǐng)待插入結(jié)點(diǎn)空間，對(duì)該結(jié)點(diǎn)的數(shù)據(jù)部分賦值（或輸入值），將該結(jié)點(diǎn)插入在最前面，或者最后面（書上在尾部插入）. P2-next=P1; P2=P1; 最后:P2-next=NULL;,*head,*p1,*p2,使用malloc(LEN),P2-next=NULL;,b,16,11.7.4 建立動(dòng)態(tài)鏈表,head,P1 p2,1.任務(wù)是開辟結(jié)點(diǎn)和

9、輸入數(shù)據(jù) 2.并建立前后相鏈的關(guān)系,待插入的結(jié)點(diǎn)p1數(shù)據(jù)部分初始化,該結(jié)點(diǎn)被頭結(jié)點(diǎn)head、尾結(jié)點(diǎn)p2同時(shí)指向.,b,17,圖11.14,head,p2,p1,head,p2,p1,(a),(b),p1重復(fù)申請(qǐng)待插入結(jié)點(diǎn)空間，對(duì)該結(jié)點(diǎn)的數(shù)據(jù)部分賦值（或輸入值）,P2-next 指向p1新開辟的結(jié)點(diǎn)。,b,18,圖11.14,head,p1,p2,(c),P2指向新結(jié)點(diǎn)p2=p1,b,19,圖11.15,p2,p1,head,p2,p1,head,(a),(b),b,20,圖11.16,p2,p1,head,p2,p1,head,b,21,例11.8 建立一個(gè)有3名學(xué)生數(shù)據(jù)的單向動(dòng)態(tài)鏈表,#de

10、fine NULL 0 #define LEN sizeof(struct student) struct student long num; float score; struct student *next; ; int n; struct student *creat(void) struct student *head; struct student*p1,*p2; n=0; p1=p2=(struct student*) malloc(LEN); scanf(%1d,%f,結(jié)構(gòu)體類型數(shù)據(jù)的長度，sizeof是“字節(jié)數(shù)運(yùn)算符”,定義指針類型的函數(shù)。帶回鏈表的起始地址,開辟長度為LEN的

11、內(nèi)存區(qū),P1,p2是指向結(jié)構(gòu)體類型數(shù)據(jù)的指針變量，強(qiáng)行轉(zhuǎn)換成結(jié)構(gòu)體類型,假設(shè)頭指向空結(jié)點(diǎn),b,22,續(xù),while(p1-num!=0) n=n+1; /*n 是結(jié)點(diǎn)的個(gè)數(shù)*/ if(n=1)head=p1; else p2-next=p1; p2=p1; p1=(struct student*)malloc(LEN); scanf(%1d,%f, /返回鏈表的頭指針,算法：p1指向新開的結(jié)點(diǎn): p1=(stuct student*)malloc(LEN); p1的所指向的結(jié)點(diǎn)連接在p2所指向結(jié)點(diǎn)后面，用p2-next=p1來實(shí)現(xiàn)。 p2 指向鏈表中最后建立的結(jié)點(diǎn)，: p2=p1;,頭指針指向

12、p1結(jié)點(diǎn),P1開辟的新結(jié)點(diǎn)鏈到了p2的后面,P1繼續(xù)開辟新結(jié)點(diǎn),給新結(jié)點(diǎn)賦值此,b,23,11.7.5 輸出鏈表,鏈表遍歷 1.單向鏈表總是從頭結(jié)點(diǎn)開始的； 2.每訪問一個(gè)結(jié)點(diǎn)，就將當(dāng)前指針向該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)移動(dòng)： p=p-next; 3.直至下一結(jié)點(diǎn)為空 P=NULL,b,24,圖 11.18,head,p,P,P,b,25,例題 9,void print (struct student *head) struct student * p; printf(nNow,These %d records are:n,n); p=head; if(head!=NULL) do printf(%ld

13、 %5.lfn,p - num,p - score); p=p - next; while(p!=NULL); ,b,26,11.7.6 對(duì)鏈表的刪除操作,刪除結(jié)點(diǎn)原則： 不改變?cè)瓉淼呐帕许樞颍皇菑逆湵碇蟹蛛x開來，撤消原來的鏈接關(guān)系。 兩種情況： 1、要?jiǎng)h的結(jié)點(diǎn)是頭指針?biāo)傅慕Y(jié)點(diǎn)則直接操作； 2、不是頭結(jié)點(diǎn)，要依次往下找。 另外要考慮：空表和找不到要?jiǎng)h除的結(jié)點(diǎn),b,27,鏈表中結(jié)點(diǎn)刪除,需要由兩個(gè)臨時(shí)指針： P1: 判斷指向的結(jié)點(diǎn)是不是要?jiǎng)h除的結(jié)點(diǎn)（用于尋找）； P2: 始終指向P1的前面一個(gè)結(jié)點(diǎn)；,b,28,圖11.19,(a),(B),b,29,圖11.20,head,p1,（a）,(b

14、),head,p2,p1,原鏈表 P1指向頭結(jié)點(diǎn),P2指向p1指向的結(jié)點(diǎn)。P1指向下移一個(gè)結(jié)點(diǎn)。,b,30,圖11.20,head,p1,head,p2,p1,(c),(d),經(jīng)判斷后，第1個(gè)結(jié)點(diǎn)是要?jiǎng)h除的結(jié)點(diǎn)，head指向第2個(gè)結(jié)點(diǎn)，第1個(gè)結(jié)點(diǎn)脫離。,經(jīng)P1找到要?jiǎng)h除的結(jié)點(diǎn)后使之脫離。,b,31,例 題 10,struct student *del( struct student *head, long num ) struct student *p1, *p2; if(head=NULL) printf(nlist null!n); goto end; p1=head; while(num

15、!=p1-num ,找到了,沒找到,b,32,11.7.7 對(duì)鏈表的插入操作,插入結(jié)點(diǎn)：將一個(gè)結(jié)點(diǎn)插入到已有的鏈表中 插入原則： 1、插入操作不應(yīng)破壞原鏈接關(guān)系 2、插入的結(jié)點(diǎn)應(yīng)該在它該在的位置 實(shí)現(xiàn)方法： 應(yīng)該有一個(gè)插入位置的查找子過程 共有三種情況： 1、插入的結(jié)最小 2、插入的結(jié)點(diǎn)最大 3、插入的結(jié)在中間,b,33,操 作 分 析,同刪除一樣，需要幾個(gè)臨時(shí)指針： P0: 指向待插的結(jié)點(diǎn);初始化：p0=數(shù)組stu; P1: 指向要在P1之前插入結(jié)點(diǎn)；初始化: p1=head; P2: 指向要在P2之后插入結(jié)點(diǎn)； 插入操作：當(dāng)符合以下條件時(shí)：p0-num 與 p1-num 比較找位置 if(

16、p0-nump1-num),b,34,圖11.22,head,p1,（a）,p0,b,35,圖11.22,p1,(b),b,36,例 題 11,struct student insert(struct student *head,struct student *stud) struct student *p0,*p1,*p2; p1=head; p0=stud; if( head=NULL; ) head=p0;p0-next=NULL; else while( p0-nump1-num) ,原來的鏈表是空表,P0指向要插的結(jié)點(diǎn),使p0指向的結(jié)點(diǎn)作為頭結(jié)點(diǎn),使p2指向剛才p1指向的結(jié)點(diǎn),插到原

17、來第一個(gè)結(jié)點(diǎn)之前,插到p2指向的結(jié)點(diǎn)之后,插到最后的結(jié)點(diǎn)之后,鏈接,b,37,head,課堂舉例：已有一個(gè)如圖所示的鏈表； 它是按結(jié)點(diǎn)中的整數(shù)域從小到大排序的，現(xiàn)在要插入一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)中的數(shù)為10,待插入結(jié)點(diǎn),此結(jié)點(diǎn)已插入鏈表,b,38,分析：按三種情況 1、第一種情況，鏈表還未建成（空鏈表），待插入結(jié)點(diǎn)p實(shí)際上是第一個(gè)結(jié)點(diǎn)。這時(shí)必然有head=null。只要讓頭指針指向 p 就可以了。語句為,head p,head = p; p-next = null;,2、第二種情況，鏈表已建成，待插入結(jié)點(diǎn) p 的數(shù)據(jù)要比頭結(jié)點(diǎn)的數(shù)據(jù)還要小，這時(shí)有 (p-num )num) 當(dāng)然p結(jié)點(diǎn)要插在head結(jié)點(diǎn)

18、前。,b,39,head,head,p,p-next=head; head=p;,語句為,null,b,40,3、第三種情況，鏈表已建成，待插入結(jié)點(diǎn) p 的數(shù)據(jù)比頭結(jié)點(diǎn)的數(shù)據(jù)大，需要找到正確的插入位置。這時(shí)，可以借助兩個(gè)結(jié)構(gòu)指針r 和 g，利用循環(huán)比較來找到正確位置。然后將結(jié)點(diǎn) p 插入到鏈表中正確的位置。 參見下面的圖示,b,41,head,p,g,r,說明：這種情況下，p 結(jié)點(diǎn)已經(jīng)與鏈表的第一個(gè)結(jié)點(diǎn)比較過了，所以從鏈表的下一個(gè)結(jié)點(diǎn)開始比較。138，繼續(xù)比較。,b,42,head,p,g,r,說明：1312，繼續(xù)比較。,b,43,head,p,g,r,null,說明：13next = p;

19、p-next = g;,b,44,/ 結(jié)構(gòu)7.c #include / 預(yù)編譯命令 #include / 內(nèi)存空間分配 #define null 0 / 定義空指針常量 #define LEN sizeof(struct numST) / 定義常量，表示結(jié)構(gòu)長度 struct numST / 結(jié)構(gòu)聲明 int num; / 整型數(shù) struct numST *next; / numST結(jié)構(gòu)指針 ;,參考程序,b,45,/ 被調(diào)用函數(shù)insert()，兩個(gè)形參分別表示鏈表和待插入的結(jié)點(diǎn) void insert (struct numST *phead, struct numST *p) / 函數(shù)

20、體開始 struct numST *q,*r; / 定義結(jié)構(gòu)指針q,r if (*phead)=null) / 第一種情況，鏈表為空 *phead = p; / 鏈表頭指向p return; / 完成插入操作，返回 else / 鏈表不為空 / 第二種情況，p結(jié)點(diǎn)num值小于鏈表頭結(jié)點(diǎn)的num值 if ( (*phead)-num p-num) / 將p結(jié)點(diǎn)插到鏈表頭部 p-next = *phead;/ 將p的next指針指向鏈表頭(*phead) *phead = p; / 將鏈表頭賦值為p return; / 返回 ,b,46,/ 第三種情況，循環(huán)查找正確位置 r = *phead; /

21、 r賦值為鏈表頭 q = (*phead)-next; / q賦值為鏈表的下一個(gè)結(jié)點(diǎn) while (q!=null) / 利用循環(huán)查找正確位置 / 判斷當(dāng)前結(jié)點(diǎn)num是否小于p結(jié)點(diǎn)的num if (q-num num) r = q; / r賦值為q，即指向q所指的結(jié)點(diǎn) q = q-next;/ q指向鏈表中相鄰的下一個(gè)結(jié)點(diǎn) else / 找到了正確的位置 break; / 退出循環(huán) / 將p結(jié)點(diǎn)插入正確的位置 r-next = p; p-next = q; ,b,47,/ 被調(diào)用函數(shù)，形參為ST結(jié)構(gòu)指針，用于輸出鏈表內(nèi)容 void print(struct numST *head) int k

22、=0; / 整型變量，用于計(jì)數(shù) struct numST * r; / 聲明r為ST結(jié)構(gòu)指針 r=head; / r賦值為head，即指向鏈表頭 while(r != null) / 當(dāng)型循環(huán)，鏈表指針不為空則繼續(xù) / 循環(huán)體開始 k=k+1; / 計(jì)數(shù)加1 printf(%d %dn,k,r-num); r=r-next; / 取鏈表中相鄰的下一個(gè)結(jié)點(diǎn) / 循環(huán)體結(jié)束 ,b,48,void main() / 主函數(shù)開始 / 函數(shù)體開始 struct numST *head, *p; / ST型結(jié)構(gòu)指針 head = null; / 分配兩個(gè)ST結(jié)構(gòu)的內(nèi)存空間，用于構(gòu)造鏈表 head = (s

23、truct numST *) malloc(LEN); head-next = (struct numST *) malloc(LEN); / 為鏈表中的兩個(gè)結(jié)點(diǎn)中的num賦值為5和10 head-num = 5; head-next-num = 10; head-next-next = null; / 鏈表尾賦值為空 / 構(gòu)造一個(gè)結(jié)點(diǎn)p，用于插入鏈表 p = (struct numST *) malloc(LEN); p-num = 8; p-next = null; insert( / 調(diào)用print函數(shù)，輸出鏈表內(nèi)容 / 主函數(shù)結(jié)束,b,49,說明：函數(shù)insert()的第一個(gè)形參為st

24、ruct numST*類型，即“指針的指針”。調(diào)用時(shí)送入的實(shí)參是鏈表頭指針的地址，即程序中的 char name10; char sex; char job; union int class; char position10; category; person2; main() int n,i; for(i=0;iSun、Sat最大。 （4）枚舉元素的值也是可以人為改變的：在定義時(shí)由程序指定。 例如，如果enum weekdays Sun=, Mon ,Tue, Wed, Thu, Fri, Sat；則Sun=，Mon=，從Tue=2開始，依次增。,b,61,例 題 13,/*file1.c文

25、件1*/ main() extern enter-string(char str80); extern delete-string(char str,char ch); extern print-string(char str); char c; char str80; enter_string(str); scanf(%c,b,62,續(xù),for(i=0;ix,p-y); p=p-next; / p指向下一個(gè)結(jié)點(diǎn) i=i+1; / 計(jì)數(shù)加1 while(p!=null); / 未到達(dá)鏈表尾部，則繼續(xù)循環(huán) / 主函數(shù)結(jié)束,b,71,用結(jié)構(gòu)數(shù)組，利用鍵盤輸入結(jié)點(diǎn)中的數(shù)據(jù)。重點(diǎn)看 scanf(“%d

26、”, 結(jié)構(gòu)數(shù)組，數(shù)組中的元素為結(jié)構(gòu)類型的數(shù)據(jù)，如n8,/ 結(jié)構(gòu)2.c #include / 預(yù)編譯命令 #define null 0 / 定義空指針常量 struct TM / 定義TM結(jié)構(gòu) int x,y; / 整型變量x,y struct TM *next; / 指向TM結(jié)構(gòu)的指針 ;,b,72,void main() / 主函數(shù) / 主函數(shù)開始 int i,a,b; / 聲明整型變量i,a,b / 聲明TM型結(jié)構(gòu)數(shù)組n8，TM結(jié)構(gòu)指針head,p struct TM n8,*head,*p; for(i=1;inext = head;,head,tail,q,b,84,5、刪結(jié)點(diǎn)的函數(shù)s

27、elect(int mm) mm為形式參數(shù)，從1至m報(bào)數(shù)，凡報(bào)到mm者刪除其所在的結(jié)點(diǎn)。 設(shè)計(jì)兩個(gè)指針p和q。一開始讓q指向鏈表的尾部q=tail。讓p指向q的下一個(gè)結(jié)點(diǎn)。開始時(shí)讓p指向1#猴所在的結(jié)點(diǎn)。用一個(gè)累加器x，初始時(shí)x=0，從1#猴所在結(jié)點(diǎn)開始讓x=x+1=1，如果mm是1的話，1#猴所在的p結(jié)點(diǎn)就要被刪除。有三條語句 printf(“被刪掉的猴子號(hào)為%d號(hào)n”,p-num); q-next = p-next; free(p);,head,tail,q,p,演示,b,85,這里free(p)是釋放p結(jié)點(diǎn)所占用的內(nèi)存空間的語句。如果mm不是1而是3，程序會(huì)在do-while循環(huán)中，讓x

28、加兩次1，q和p一起移動(dòng)兩次，p指向3#所在結(jié)點(diǎn)，q指向2#所在結(jié)點(diǎn)，之后仍然用上述三條語句刪去3#所在的結(jié)點(diǎn)。,head,q,p,q,p,p,q,演示,b,86,這個(gè)do-while循環(huán)的退出條件是q=q-next。即當(dāng)只剩下一個(gè)結(jié)點(diǎn)時(shí)才退出循環(huán)。當(dāng)然猴王非其莫屬了。這時(shí)，讓頭指針head指向q，head是全局變量，在主程序最后輸出猴王時(shí)要用head-num。,參考程序如下：,head,q,b,87,#include / 預(yù)編譯命令 #include / 內(nèi)存空間分配 #define null 0 / 定義空指針常量 / 定義常量，表示結(jié)構(gòu)長度 #define LEN sizeof(struct mon) struct mon / 結(jié)構(gòu)聲明 int num; / 整型數(shù)，用于記錄猴子號(hào) struct mon *next; / mon結(jié)構(gòu)指針 ; struct mon *head, *tail; / mon結(jié)構(gòu)指針，全局變量,b,88,void cre