(6.43)-第42課（9.4節(jié)-用指針處理鏈表）

用指針處理鏈表結(jié)構(gòu)體和共同體引例：選擇合適的數(shù)據(jù)結(jié)構(gòu)來(lái)存放一批學(xué)生的學(xué)號(hào)及考試成績(jī)，以便進(jìn)一步處理分析：由于學(xué)生人數(shù)未知，用靜態(tài)數(shù)據(jù)結(jié)構(gòu)不合適。用鏈表處理較恰當(dāng)概念：鏈表是一種常見的重要的數(shù)據(jù)結(jié)構(gòu)。它是動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配的一種結(jié)構(gòu)用鏈表處理該問題的基本思路：將各學(xué)生的數(shù)據(jù)進(jìn)行離散存放，來(lái)一個(gè)學(xué)生就分配一小塊內(nèi)存（結(jié)點(diǎn)）。并將各結(jié)點(diǎn)用指針依次連接起來(lái)鏈表有一個(gè)“頭指針”變量，它存放一個(gè)地址，該地址指向鏈表中的第一個(gè)元素鏈表中每一個(gè)元素稱為“結(jié)點(diǎn)”每個(gè)結(jié)點(diǎn)都應(yīng)包括兩個(gè)部分：數(shù)據(jù)域：用戶需要用的實(shí)際數(shù)據(jù)指針域：下一個(gè)結(jié)點(diǎn)的地址結(jié)點(diǎn)1結(jié)點(diǎn)2結(jié)點(diǎn)nNULLhead……頭指針head指向第一個(gè)結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)應(yīng)包含下一結(jié)點(diǎn)的開始地址。對(duì)于兩個(gè)相鄰的結(jié)點(diǎn)p1、p2，p1是p2的直接前驅(qū)結(jié)點(diǎn)，p2是p1的直接后繼結(jié)點(diǎn)最后一個(gè)結(jié)點(diǎn)中的指針為空，稱為“鏈尾”，其指針部分存放NULL這樣的鏈表稱為單向鏈表NULLhead……p1p2a1a2∧anhead…帶頭結(jié)點(diǎn)的線性鏈表a1a2∧ana3head…不帶頭結(jié)點(diǎn)的線性鏈表鏈表中的結(jié)點(diǎn)必須是結(jié)構(gòu)體類型，其中一個(gè)成員是指針類型，這個(gè)指針類型指向它所在的結(jié)構(gòu)體類型例如：structstudent{intnum;floatscore;structstudent*next;};

num

score

next數(shù)據(jù)域指針域鏈表的基本操作創(chuàng)建鏈表：從無(wú)到有地建立起一個(gè)鏈表，即往空鏈表中依次插入若干結(jié)點(diǎn)，并保持結(jié)點(diǎn)之間的前驅(qū)和后繼關(guān)系遍歷鏈表：從頭結(jié)點(diǎn)開始，逐個(gè)訪問鏈表里的每個(gè)結(jié)點(diǎn)，完成相關(guān)操作插入結(jié)點(diǎn)：在結(jié)點(diǎn)ki-1與ki之間插入一個(gè)新的結(jié)點(diǎn)k’，使結(jié)點(diǎn)個(gè)數(shù)增1，且ki-1與ki的邏輯關(guān)系發(fā)生如下變化：插入前，ki-1是ki的前驅(qū)，ki是ki-1的后繼；插入后，新插入的結(jié)點(diǎn)k’成為ki-1的后繼、ki的前驅(qū)刪除結(jié)點(diǎn)：刪除結(jié)點(diǎn)ki，使結(jié)點(diǎn)個(gè)數(shù)減1，且ki-1、ki和ki+1之間的邏輯關(guān)系發(fā)生如下變化：刪除前，ki是ki+1的前驅(qū)、ki-1的后繼；刪除后，ki-1成為ki+1的前驅(qū)，ki+1成為ki-1的后繼建立動(dòng)態(tài)鏈表n=n+1n==1head=p1p2

next=p1真假(把p1所指結(jié)點(diǎn)作為第一個(gè)結(jié)點(diǎn))(把p1所指結(jié)點(diǎn)連接到表尾)p2=p1(p2移到表尾）再開辟一個(gè)新結(jié)點(diǎn)，使p1指向它讀入一個(gè)學(xué)生數(shù)據(jù)給p1所指結(jié)點(diǎn)表尾結(jié)點(diǎn)的指針變量置NULL開辟一個(gè)新結(jié)點(diǎn)，并使p1,p2指向它讀入一個(gè)學(xué)生數(shù)據(jù)給p1所指向的結(jié)點(diǎn)head=NULL,n=0當(dāng)讀入的p1

num不是零算法分析程序?qū)崿F(xiàn)#include<stdio.h>#include<stdlib.h>#defineNULL0#defineLENsizeof(structstudent)structstudent{intnum;floatscore;structstudent*next;};//聲明結(jié)點(diǎn)類型intn;//n為全局變量，用于存儲(chǔ)鏈表中結(jié)點(diǎn)的個(gè)數(shù)structstudent*creat(void)//定義函數(shù)，此函數(shù)返回一個(gè)指向鏈表頭的指針{structstudent*head,*p1,*p2;n=0;p1=p2=(structstudent*)malloc(LEN);//開辟一個(gè)新單元scanf(“%d,%f”,&p1

num,&p1

score);//輸人第1個(gè)學(xué)生的學(xué)號(hào)和成績(jī)head=NULL;while(p1

num!=0){n=n+1;if(n==1)head=p1;elsep2

next=p1;p2=p1;p1=(structstudent*)malloc(LEN);scanf(“%d,%f”,&p1

num,&p1

score);//輸人其他學(xué)生的學(xué)號(hào)和成績(jī)}p2

next=NULL;return(head);}輸出鏈表（遍歷）p=head，使p指向第一個(gè)結(jié)點(diǎn)

輸出p所指向的結(jié)點(diǎn)p=p

next當(dāng)p指的不是表尾算法分析假真p指向的不是尾結(jié)點(diǎn)程序?qū)崿F(xiàn)voidprint(structstudent*head)//定義print函數(shù)

{structstudent*p;//在函數(shù)中定義structstudent類型的變量pprintf("\nNow,These%drecordsare:\n",n);p=head;//使p指向第一個(gè)結(jié)點(diǎn)

if(head!=NULL)//若不是空表

do{printf("%d%5.1f\n",p->num,p->score);//輸出一個(gè)結(jié)點(diǎn)中的學(xué)號(hào)與成績(jī)

p=p->next;//p指向下一個(gè)結(jié)點(diǎn)

}while(p!=NULL);//當(dāng)p不是“空地址”

}不改變?cè)瓉?lái)的排列順序，只是從鏈表中分離開來(lái)，撤消原來(lái)的鏈接關(guān)系刪除結(jié)點(diǎn)

算法分析程序?qū)崿F(xiàn)structstudent*del(structstudent*head,intnum){structstudent*p1,*p2;if(head==NULL)//若是空鏈表{printf(“\nlistnull!\n”);return(head);;}p1=head;//使p1指向第一個(gè)結(jié)點(diǎn)

//p1指向的不是所要找的結(jié)點(diǎn)且后面還有結(jié)點(diǎn)while(num!=p1

num&&p1

next!=NULL){p2=p1;p1=p1

next;}//p1后移一個(gè)結(jié)點(diǎn)

if(num==p1

num)//若找到了{(lán)if(p1==head)//若p1指向的是首結(jié)點(diǎn),把第二個(gè)結(jié)點(diǎn)地址賦予headhead=p1

next;else//否則將下一結(jié)點(diǎn)地址賦給前一結(jié)點(diǎn)的指針項(xiàng)p2

next=p1

next;printf(“delete:%d\n”,num);n=n-1;}//結(jié)點(diǎn)數(shù)減1else//若找不到該結(jié)點(diǎn)

printf(“%ldnotbeenfound!\n”,num);return(head);}將一個(gè)結(jié)點(diǎn)插入到已有的鏈表中。插入操作不應(yīng)破壞原鏈接關(guān)系；插入的結(jié)點(diǎn)應(yīng)該在它該在的位置插入結(jié)點(diǎn)

算法分析否程序?qū)崿F(xiàn)structstudent*insert(structstudent*head,structstudent*stud){structstudent*p0,*p1,*p2;p1=head;//使p1指向第一個(gè)結(jié)點(diǎn)p0=stud;//p0指向要插入的結(jié)點(diǎn)if(head==NULL)//原來(lái)的鏈表是空表{head=p0;p0

next=NULL;}//使p0指向的結(jié)點(diǎn)作為頭結(jié)點(diǎn)else{while((p0

num>p1

num)&&(p1

next!=NULL))

{

p2=p1;//使p2指向剛才p1指向的結(jié)點(diǎn)p1=p1

next;}

//p1后移一個(gè)結(jié)點(diǎn)if(p0

num<=p1

num)

{

if(head==p1)head=p0;

//插到原來(lái)第一個(gè)結(jié)點(diǎn)之前elsep2

next=p0;//插到p2指向的結(jié)點(diǎn)之后p0

next=p1;}

else{p1

next=p0;p0

next=NULL;}//插到最后的結(jié)點(diǎn)之后}n=n+1;//結(jié)點(diǎn)數(shù)加1return(head);}主函數(shù)voidmain(){structstudent*head,*stu;intdel_num;printf("inputrecords:\n");head=creat();//調(diào)用create函數(shù)，創(chuàng)建鏈表print(head);//調(diào)用print函數(shù)，輸出鏈表printf(“\n輸入要?jiǎng)h除的學(xué)號(hào):");scanf("%d",&del_num);//輸入要?jiǎng)h除的學(xué)號(hào)

while(del_num!=0)//可以多次刪除，直到輸入的學(xué)號(hào)等于0為止

{head=del(head,del_num);//調(diào)用del函數(shù)，刪除相應(yīng)的結(jié)點(diǎn)

print(head);printf("輸入要?jiǎng)h除的學(xué)號(hào):");scanf("%d",&del_num);}printf(“\n輸入要插入的學(xué)生信息:");stu=(structstudent*)malloc(LEN);//創(chuàng)建新節(jié)點(diǎn)scanf(“%d,%f”,&stu->num,&stu->score);//輸入要插入的學(xué)生信息

while