鏈表完整版本

將新結點插入p的后面①②newp思考題：1、分別寫出①②對應的語句2、①②是否可以顛倒？為什么？3、如果①②可以顛倒需要增加什么條件？4、如果鏈表為空怎么辦？5、如果新結點為鏈表頭怎么辦？6、如果新結點為鏈表尾怎么辦？12/19/2024鏈表

12/19/2024內(nèi)容提綱

單向鏈表

雙向鏈表

實戰(zhàn)出擊循環(huán)鏈表注意的問題12/19/20241.單向鏈表8910189.58910390head89105808910775

structstudent{intnum;floatscore;

structstudent*next;}head;12/19/20241.1鏈表建立初始狀態(tài)（p鏈表尾結點指針，newp為新結點指針）最終狀態(tài)p……p12/19/20241.1鏈表建立（續(xù)）p①p②③直到=-1為止①尾的后繼指向新結點②改變尾結點③產(chǎn)生新結點12/19/20241.2鏈表遍歷初始狀態(tài)（p為遍歷指針）最終狀態(tài)pp循環(huán)：當!=x做p=p.next

指出其中的錯誤12/19/20241.3鏈表插入初始狀態(tài)（p為遍歷指針，newp為新結點指針）最終狀態(tài)p12/19/20241.3鏈表插入（續(xù)1）①②③①遍歷指針定位②新結點后繼指向遍歷結點的后繼③遍歷指針的后繼指向新結點12/19/20241.4鏈表刪除q①②③①遍歷指針p定位②遍歷結點的后繼指向刪除結點的后繼③釋放刪除結點q12/19/20241.4刪除鏈表（續(xù)）思考題：1、如果鏈表為空怎么辦？2、如果新結點為鏈表頭怎么辦？3、如果新結點為鏈表尾怎么辦？12/19/20242.雙向鏈表priordatenext結點結構head

……

雙向鏈表12/19/20242.1雙向鏈表插入head

……

pnewp新結點插入到p結點的后面①②③④注意：先連后斷12/19/20242.1雙向鏈表刪除刪除p結點head

p①②③③釋放刪除結點p①p結點前驅(qū)指向p結點的后繼②p結點后繼指向p結點的前驅(qū)12/19/20243.循環(huán)鏈表P->next=headp12/19/20243.1循環(huán)鏈表中間插入p①②①新結點后繼指向遍歷結點的后繼②遍歷指針的后繼指向新結點12/19/20243.2循環(huán)鏈表尾部插入p①②①新結點后繼指向頭結點

newp->next=head;②遍歷指針的后繼指向新結點

p->next=newp;12/19/20243.3循環(huán)鏈表頭部插入①②③①新結點后繼指向頭結點：newp->next=head;②頭指針指向新結點:head->=newp;③尾指針指向頭結點:p->next=head;p12/19/20243.4刪除循環(huán)鏈表中間結點p②p->next=p->next->next;或p->next=q->next;③釋放q結點:free(q);刪除p的后繼結點①q=p->next;q②①12/19/20243.5刪除循環(huán)鏈表尾結點pq①②①q=p->next;②p->next=head;③釋放q結點:free(q);注意：引入q結點必要性12/19/20243.6刪除循環(huán)鏈表頭結點pq①q=p->next;或q=head;①②②p->next=head->next;③④釋放q結點:free(q);③head=q->next;12/19/20244.注意的問題(1)必須畫圖(2)產(chǎn)生新結點：p=(structnode*)malloc(sizeof(structnode));(3)指針域不一定是next，一般取名為link,point(4)指向后繼：p=p->next;(5)尾結點：if(p->next==NULL);或if(!p->next)(非循環(huán)鏈表)

if(p->next==head)(循環(huán)鏈表)(6)頭結點：if(p==head)(7)#defineNULL012/19/20244.注意的問題（續(xù)）(8)初始化：p=head;(9)非空鏈表：while(p){……}(10)頭指針不要輕易移動(11)指向后繼：p=p->next;(12)唯一結點：if(h->next==NULL);(非循環(huán)鏈表)

if(head->next==head)(循環(huán)鏈表)(13)釋放結點之前，要處理前驅(qū)結點的指向。(14)移動指針之前，要處理前驅(qū)結點的指向。12/19/20244.實戰(zhàn)出擊例1：函數(shù)fmax()的功能是:求出鏈表所有結點中,數(shù)據(jù)域值最大的結點的位置,并由參數(shù)s返回給主函數(shù).該函數(shù)的第一參數(shù)是鏈表的首指針。（98春）structnode{intdata;

structnode*next;}；12/19/2024voidfmax(structnode*head,structnode28){structnode*p;p=head;*s=p;if(p==NULL)return;while(p){if(p->data>29)*s=p;p=30;}}**s）*s->data)*s=p;p->data);12/19/2024思考：

1、求最小元素位置并與表頭結點交換

2、統(tǒng)計最大元素個數(shù)12/19/2024

1、求最小元素位置并與表頭結點交換voidfmax(structnode*head,structnode**s){structnode*p,*q;p=head;*s=p;if(p==NULL)return;while(p){if(p->data<*s->data)*s=p;p=p->next;}q->data=p->date;p->date=*s->data;*s->date=q->data;}12/19/20242、統(tǒng)計最大元素個數(shù)（1）在升序排序的同時記錄最大數(shù)；（2）遍歷鏈表統(tǒng)計與最大數(shù)相等的次數(shù)；12/19/2024例2：函數(shù)fun的參數(shù)是鏈表的頭指針，它完成的功能是：將鏈表中各結點分量data的數(shù)值為偶數(shù)的結點依次調(diào)到鏈表的前面。方法是：根據(jù)data的值，分為奇數(shù)偶書兩個鏈表，然后將兩個鏈表拼接在一起（98秋）。structnode{intdata;

structnode*next;};

12/19/2024

structnode*fun(structnode*head){structnode*p=head,*even=0,*old=0,*p1=0,*p2=0;

if(head==NULL){returnhead;}

while(p){if(p->data%2)

if(old==0{old=p;p1=p;}else{28;p1=p;}else

if(even==0{even=p;p2=p;}else{29;p2=p;}p=p->next;}

if(old)p1->next=0;

if(even){head=even;30;}elsehead=old;returnhear;}p1->next=p;p1=p;}p2->next=p;p2=p;}p2->next=old;}移動指針之前，要處理前驅(qū)結點的指向。12/19/2024思考：

1、所有素數(shù)調(diào)整到鏈表的前面

2、把滿足某一性質(zhì)的元素調(diào)整到鏈表的后面

3、鏈表反序12/19/2024例3：將鏈表上相臨的兩個結點合并成一個結點，即將第一結點與第二結點合并，將第三結點與第四結點合并，….，若鏈表上的結點個數(shù)為奇數(shù)，則最后的一個結點不合并，直接作為合并后鏈表上的最后一個結點（99春）。鏈表上結點數(shù)據(jù)結構為：structnode{intdata;

structnode*next;};12/19/2024初始狀態(tài)：24

9head6815head104

最終狀態(tài)：p1p212/19/2024合并過程：24

9head8p16p215①①p1->data+=p2->next;②p1②p1->next=p2->next;④③釋放p2結點:free(p2);④p1=p1->next;p2⑤⑤p2=p1->next;②③可以顛倒嗎？為什么？不可以，釋放結點之前，要處理前驅(qū)結點的指向。12/19/2024voidmerge(structnode*h){structnode*p1,*p2;if(27)return;p1=h;p2=h->next;while(p2){p1->data+=p2->data;p1->next=28;free(p2);if(29)p2=30;elsep2=NULL;}}

h==NULL||h->next==NULL)return;

p2->next

;

p1->next!=NULL

p1->next;12/19/2024思考：

1、兩端合并

2、相同元素合并

12/19/2024例4：有n個人圍成一圈，他們的編號為1-n。第一個人從1開始順序報數(shù)，凡報到m時，該人退出圈子。其后的人再從1開始順序報數(shù)，直到最后一個退出圈子為止。輸出依次退出圈子的人的編號。n和m的值從鍵盤上輸入，且均小于200。（2000年）鏈表上結點數(shù)據(jù)結構為：structnode{intdata;

structnode*next;};12/19/2024p為遍歷指針；指針q指向p的前驅(qū)；count為計數(shù)器當指針p指向的結點不是要刪除的結點時：pqq①①q=p;p②②p=p->next;③count++;12/19/2024當指針p指向的結點是要刪除的結點時：pq①①q->next=p->next;p④②free(p);③count=0;④p=q->next;注意：使用兩個指針對循環(huán)鏈表的操作無需考慮頭和尾。12/19/2024voidcircle(structnode*head,intm){structnode*p,*q;intcount=0;p=head;q=p;while(18){if(count!=m){count++;19p=p->next;}else{printf(“%d->”,p->data);

q->next=p->next;

free(p);

20;count=0;}}}

移動指針之前，要處理前驅(qū)結點的指向。q=p;p!=p->next)p=q->next12/19/2024main(){structnode*p,*head=0,*q;inti;head=(structnode*)malloc(sizeof(structnode));q=head;q->data=1;

for(i=2;i<8;i++){p=(structnode*)malloc(sizeof(structnode));p->data=i;q->next=p;q=p;}q->next=head;

circle(head,3);}

12/19/2024算法提示：a[0]……a[n-1]分別存放n個人的序號1、2……n-1、n。報數(shù)時，若a[i]的值不為0，則參與報數(shù)；否則不參與報數(shù)。當a[j]對應的人退出圈子時（下標取值n的余數(shù)為0），則將a[j]置為0。方法2：用數(shù)組實現(xiàn)

12/19/2024voidcircle(intn,inta[],intm){intcount=0,i=0,k=0;while(count19){if(20){i++;if(21){printf(“%d\t”,a[k]);i=0;a[k]=0;count++;}}if(++k22)k=0;}

printf(“\n”);}

<na[k]i%m==0%n==012/19/2024main(){intn,a[200],m,i;

printf(“輸入圍成一圈的人數(shù)：“)；scanf(“5d”,&n);

printf(“輸入出圈的號數(shù)：“)；scanf(“%d”,&m);

for(i=0;i<n;i++)a[i]=i+1;

circle(n,a,m);}12/19/2024例5：設已建立了一條鏈表，鏈表上結點的數(shù)據(jù)結構為：

structnode{floatenglish,math;

structnode*next;};

求出該鏈表上的結點個數(shù)、英語的總成績和數(shù)學總成績，并在鏈首增加一個新的結點，其分量english,math分別存放這兩門課程的平均成績。若鏈為空鏈時，鏈首不增加結點。以下函數(shù)ave的第一個參數(shù)h指向鏈首，第二個參數(shù)count存放求出的結點個數(shù)。

12/19/2024structnode*ave(structnode*h,int*count){structnode*p1,*p2;floatsume=0,sum=0;*count=0;

if(h==NULL)27;p1=h;while(28){sume+=p1->English;sum+=p1->math;*count=*count+1;

29;}p1=(structnode*)malloc(sizeof(structnode));p1->English=sume/*count;p2->math=summ/*count;

30;h=p1;returnh;}

return0p1p1=p1->next

p1->n