C語言鏈表詳解ppt.ppt

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

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

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

4、 (5)打印輸出,b,9,一個指針類型的成員既可指向其它類型的結構體數據，也可以指向自己所在的結構體類型的數據,num Score next,next是struct student類型中的一個成員，它又指向struct student類型的數據。 換名話說：next存放下一個結點的地址,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,建立和輸出一個簡單鏈表,各結點在程序中定義，不是臨時開辟的，始終占有內容不放，這種鏈表稱為“靜態(tài)鏈表”,b,11,11.7.3 處理動態(tài)鏈表所需的函數,C 語言使用系統(tǒng)函數動態(tài)開辟和釋放存儲單元,1.malloc 函數,函數原形：void *malloc(unsigned int size); 作用：在內存的動態(tài)存儲區(qū)中分配 一個 長度為size的連續(xù)空間。 返回值：是一個指向分配域起始地址的指針（基本類型void）。 執(zhí)行失?。悍祷豊ULL,b,12

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

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

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

9、輸入數據 2.并建立前后相鏈的關系,待插入的結點p1數據部分初始化,該結點被頭結點head、尾結點p2同時指向.,b,17,圖11.14,head,p2,p1,head,p2,p1,(a),(b),p1重復申請待插入結點空間，對該結點的數據部分賦值（或輸入值）,P2-next 指向p1新開辟的結點。,b,18,圖11.14,head,p1,p2,(c),P2指向新結點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 建立一個有3名學生數據的單向動態(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,結構體類型數據的長度，sizeof是“字節(jié)數運算符”,定義指針類型的函數。帶回鏈表的起始地址,開辟長度為LEN的

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

12、p1結點,P1開辟的新結點鏈到了p2的后面,P1繼續(xù)開辟新結點,給新結點賦值此,b,23,11.7.5 輸出鏈表,鏈表遍歷 1.單向鏈表總是從頭結點開始的； 2.每訪問一個結點，就將當前指針向該結點的下一個結點移動： p=p-next; 3.直至下一結點為空 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 對鏈表的刪除操作,刪除結點原則： 不改變原來的排列順序，只是從鏈表中分離開來，撤消原來的鏈接關系。 兩種情況： 1、要刪的結點是頭指針所指的結點則直接操作； 2、不是頭結點，要依次往下找。 另外要考慮：空表和找不到要刪除的結點,b,27,鏈表中結點刪除,需要由兩個臨時指針： P1: 判斷指向的結點是不是要刪除的結點（用于尋找）； P2: 始終指向P1的前面一個結點；,b,28,圖11.19,(a),(B),b,29,圖11.20,head,p1,（a）,(b

14、),head,p2,p1,原鏈表 P1指向頭結點,P2指向p1指向的結點。P1指向下移一個結點。,b,30,圖11.20,head,p1,head,p2,p1,(c),(d),經判斷后，第1個結點是要刪除的結點，head指向第2個結點，第1個結點脫離。,經P1找到要刪除的結點后使之脫離。,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 對鏈表的插入操作,插入結點：將一個結點插入到已有的鏈表中 插入原則： 1、插入操作不應破壞原鏈接關系 2、插入的結點應該在它該在的位置 實現方法： 應該有一個插入位置的查找子過程 共有三種情況： 1、插入的結最小 2、插入的結點最大 3、插入的結在中間,b,33,操 作 分 析,同刪除一樣，需要幾個臨時指針： P0: 指向待插的結點;初始化：p0=數組stu; P1: 指向要在P1之前插入結點；初始化: p1=head; P2: 指向要在P2之后插入結點； 插入操作：當符合以下條件時：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指向要插的結點,使p0指向的結點作為頭結點,使p2指向剛才p1指向的結點,插到原

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

18、前。,b,39,head,head,p,p-next=head; head=p;,語句為,null,b,40,3、第三種情況，鏈表已建成，待插入結點 p 的數據比頭結點的數據大，需要找到正確的插入位置。這時，可以借助兩個結構指針r 和 g，利用循環(huán)比較來找到正確位置。然后將結點 p 插入到鏈表中正確的位置。 參見下面的圖示,b,41,head,p,g,r,說明：這種情況下，p 結點已經與鏈表的第一個結點比較過了，所以從鏈表的下一個結點開始比較。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,/ 結構7.c #include / 預編譯命令 #include / 內存空間分配 #define null 0 / 定義空指針常量 #define LEN sizeof(struct numST) / 定義常量，表示結構長度 struct numST / 結構聲明 int num; / 整型數 struct numST *next; / numST結構指針 ;,參考程序,b,45,/ 被調用函數insert()，兩個形參分別表示鏈表和待插入的結點 void insert (struct numST *phead, struct numST *p) / 函數

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

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

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

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

24、ruct numST*類型，即“指針的指針”。調用時送入的實參是鏈表頭指針的地址，即程序中的 char name10; char sex; char job; union int class; char position10; category; person2; main() int n,i; for(i=0;iSun、Sat最大。 （4）枚舉元素的值也是可以人為改變的：在定義時由程序指定。 例如，如果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指向下一個結點 i=i+1; / 計數加1 while(p!=null); / 未到達鏈表尾部，則繼續(xù)循環(huán) / 主函數結束,b,71,用結構數組，利用鍵盤輸入結點中的數據。重點看 scanf(“%d

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

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

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