【文章內(nèi)容簡(jiǎn)介】 student類型數(shù)據(jù)（這就是 next所在的結(jié)構(gòu)體類型） 圖 1111 30 167。 用指針處理鏈表 簡(jiǎn)單鏈表 include define NULL 0 struct student {long num。 float score。 struct student *next。 }。 main() { struct student a,b,c,*head,*p。 a. num=99101。 =。 b. num=99103。 =90。 c. num=99107。 =85。 head=amp。a。 =amp。b。 =amp。c。 =NULL。 p=head。 do {printf(%ld %\n,pnum,pscore)。 p=pnext。 } while(p!=NULL)。 } 運(yùn)行結(jié)果： 31 167。 用指針處理鏈表 庫(kù)函數(shù)提供動(dòng)態(tài)地開辟和釋放存儲(chǔ)單元的有關(guān)函數(shù)： (1) malloc函數(shù) 其函數(shù)原型為 void *malloc(unsigned int size)。 其作用是內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配一個(gè)長(zhǎng)度為size的連續(xù)空間。 此函數(shù)的值（即“返回值”）是一個(gè)指向分配域起始地址的指針（類型為 void）。 如果此函數(shù)未能成功地執(zhí)行（例如內(nèi)存空間不足），則返回空指針 (NULL)。 32 167。 用指針處理鏈表 (2) calloc函數(shù) 其函數(shù)原型為 void *calloc（ unsigned ｎ，unsigned size） 。 其作用是在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配ｎ個(gè)長(zhǎng)度為 size的連續(xù)空間。 函數(shù)返回一個(gè)指向分配域起始地址的指針；如果分配不成功，返回 NULL。 用 calloc函數(shù)可以為一維數(shù)組開辟動(dòng)態(tài)存儲(chǔ)空間， n為數(shù)組元素個(gè)數(shù)，每個(gè)元素長(zhǎng)度為size 33 167。 用指針處理鏈表 (3) free函數(shù) 其函數(shù)原型為 void free（ void *p） 。 其作用是釋放由ｐ指向的內(nèi)存區(qū)，使這部分內(nèi)存區(qū)能被其他變量使用。 ｐ是最近一次調(diào)用 calloc或 malloc函數(shù)時(shí)返回的值。 free函數(shù)無返回值 . 34 167。 用指針處理鏈表 建立動(dòng)態(tài)鏈表 所謂建立動(dòng)態(tài)鏈表是指在程序執(zhí)行過程中從 無到有地建立起一個(gè)鏈表，即一個(gè)一個(gè)地開辟結(jié) 點(diǎn)和輸入各結(jié)點(diǎn)數(shù)據(jù)，并建立起前后相鏈的關(guān)系 例 寫一函數(shù)建立一個(gè)有 3名學(xué)生數(shù)據(jù)的單向動(dòng) 態(tài)鏈表 . 算法如圖 圖 1112 35 167。 用指針處理鏈表 算法的實(shí)現(xiàn)： 約定學(xué)號(hào)不會(huì)為零，如果輸入的學(xué)號(hào)為０，則表示建立鏈表的過程完成，該結(jié)點(diǎn)不應(yīng)連接到鏈表中。 如果輸入的 p1num不等于０，則輸入的是第一個(gè)結(jié)點(diǎn)數(shù)據(jù)（ n=1），令 head＝ p1，即把 p1的值賦給 head，也就是使 head也指向新開辟的結(jié)點(diǎn) p1所指向的新開辟的結(jié)點(diǎn)就成為鏈表中第一個(gè)結(jié)點(diǎn) 圖 1113 36 167。 用指針處理鏈表 算法的實(shí)現(xiàn)： 再開辟另一個(gè)結(jié)點(diǎn)并使 p1指向它，接著輸入該 結(jié)點(diǎn)的數(shù)據(jù) . 如果輸入的 p1num≠ ０，則應(yīng)鏈入第２個(gè)結(jié)點(diǎn) （ n=2), 將新結(jié)點(diǎn)的地址賦給第一個(gè)結(jié)點(diǎn)的 next成員 . 接著使ｐ２＝ｐ１，也就是使ｐ２指向剛才建 立的結(jié)點(diǎn) 圖 1114 37 167。 用指針處理鏈表 算法的實(shí)現(xiàn)： 再開辟一個(gè)結(jié)點(diǎn)并使 p1指向它，并輸入該結(jié)點(diǎn)的 數(shù)據(jù) . 在第三次循環(huán)中，由于ｎ＝３（ｎ ≠ １），又 將ｐ１的值賦給ｐ２ ｎｅｘｔ，也就是將第 ３個(gè)結(jié)點(diǎn)連接到第２個(gè)結(jié)點(diǎn)之后，并使ｐ２＝ ｐ１，使ｐ２指向最后一個(gè)結(jié)點(diǎn) . 圖 1115 38 167。 用指針處理鏈表 算法的實(shí)現(xiàn)： 再開辟一個(gè)新結(jié)點(diǎn)，并使 p1指向它，輸入該結(jié)點(diǎn)的數(shù)據(jù)。由于 p1num的值為０，不再執(zhí)行循環(huán)，此新結(jié)點(diǎn)不應(yīng)被連接到鏈表中 . 將 NULL賦給 p2next. 建立鏈表過程至此結(jié)束， p1最后所指的結(jié)點(diǎn) 未鏈入鏈表中，第三個(gè)結(jié)點(diǎn)的 next成員的值 為 NULL，它不指向任何結(jié)點(diǎn)。 圖 1116 39 167。 用指針處理鏈表 建立鏈表的函數(shù)如下 : include include define NULL 0 //令 NULL代表０，用它表示 “ 空地址 define LEN sizeof(struct student) //令 LEN代表 struct //student類型數(shù)據(jù)的長(zhǎng)度 struct student { long num。 float score。 struct student *next。 }。 int n。 //n為全局變量，本文件模塊中各函數(shù)均可使用它 40 167。 用指針處理鏈表 struct student *creat() {struct student *head。 struct student *p1,*p2。 n=0。 p1=p2=( struct student*) malloc(LEN)。 scanf(%ld,%f,amp。p1num,amp。p1score)。 head=NULL。 while(p1num!=0) { n=n+1。 if(n==1)head=p1。 else p2next=p1。 p2=p1。 p1=(struct student*)malloc(LEN)。 scanf(%ld,%f,amp。p1num,amp。p1score)。 } p2next=NULL。 return(head)。} 41 167。 用指針處理鏈表 輸出鏈表 首先要知道鏈表第一個(gè)結(jié)點(diǎn)的地址 ， 也就是要知道 head的值 。 然后設(shè)一個(gè)指針變量 p,先指向第一個(gè)結(jié)點(diǎn) ， 輸出ｐ所指的結(jié)點(diǎn) ， 然后使ｐ后移一個(gè)結(jié)點(diǎn) ， 再輸出 ， 直到鏈表的尾結(jié)點(diǎn) 。 圖 1117,1118 42 167。 用指針處理鏈表 例１ 1． 9 編寫一個(gè)輸出鏈表的函數(shù) print. void print(struct student *head) {struct student *p。 printf(\nNow,These %d records are:\n,n)。 p=head。 if(head!=NULL) do {printf(%ld %\n,pnum,pscore)。 p=pnext。 }while(p!=NULL)。 } 43 167。 用指針處理鏈表 對(duì)鏈表的刪除操作 從一個(gè)動(dòng)態(tài)鏈表中刪去一個(gè)結(jié)點(diǎn)，并不是真正從內(nèi)存中把它抹掉，而是把它從鏈表中分離開來，只要撤銷原來的鏈接關(guān)系即可。 圖 1119 44 167。 用指針處理鏈表 例 . ? 解題思路 : 從 p指向的第一個(gè)結(jié)點(diǎn)開始 ， 檢查該結(jié)點(diǎn)中的 num值是否等于輸入的要求刪除的那個(gè)學(xué)號(hào) 。 如果相等就將該結(jié)點(diǎn)刪除 ， 如不相等 ， 就將 p后移一個(gè)結(jié)點(diǎn) ， 再如此進(jìn)行下去 ，直到遇到表尾為止 。 45 167。 用指針處理鏈表 可以設(shè)兩個(gè)指針變量 p1和 p2， 先使 p1指向第一個(gè)結(jié)點(diǎn) . 如果要?jiǎng)h除的不是第一個(gè)結(jié)點(diǎn) ， 則使 p1后移指向下一個(gè)結(jié)點(diǎn) (將 p1next賦給 p1)， 在此之前應(yīng)將 p1的值賦給 p2 ， 使 p2指向剛才檢查過的那個(gè)結(jié)點(diǎn) 46 167。 用指針處理鏈表 圖 1120 47 167。 用指針處理鏈表 算法： 圖 1121 48 167。 用指針處理鏈表 刪除結(jié)點(diǎn)的函數(shù) del: struct student *del(struct student *head,long num) {struct student *p1,*p2。 if (head==NULL){printf(\nlist null!\n)。goto end。} p1=