鏈表完整版本

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

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

單向鏈表

雙向鏈表

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

structstudent{intnum;floatscore;

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

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

……

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

……

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

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

newp->next=head;②遍歷指針的后繼指向新結(jié)點(diǎn)

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

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

if(head->next==head)(循環(huán)鏈表)(13)釋放結(jié)點(diǎn)之前，要處理前驅(qū)結(jié)點(diǎn)的指向。(14)移動(dòng)指針之前，要處理前驅(qū)結(jié)點(diǎn)的指向。12/19/20244.實(shí)戰(zhàn)出擊例1：函數(shù)fmax()的功能是:求出鏈表所有結(jié)點(diǎn)中,數(shù)據(jù)域值最大的結(jié)點(diǎn)的位置,并由參數(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、求最小元素位置并與表頭結(jié)點(diǎn)交換

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

1、求最小元素位置并與表頭結(jié)點(diǎn)交換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)計(jì)最大元素個(gè)數(shù)（1）在升序排序的同時(shí)記錄最大數(shù)；（2）遍歷鏈表統(tǒng)計(jì)與最大數(shù)相等的次數(shù)；12/19/2024例2：函數(shù)fun的參數(shù)是鏈表的頭指針，它完成的功能是：將鏈表中各結(jié)點(diǎn)分量data的數(shù)值為偶數(shù)的結(jié)點(diǎn)依次調(diào)到鏈表的前面。方法是：根據(jù)data的值，分為奇數(shù)偶書(shū)兩個(gè)鏈表，然后將兩個(gè)鏈表拼接在一起（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;}移動(dòng)指針之前，要處理前驅(qū)結(jié)點(diǎn)的指向。12/19/2024思考：

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

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

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

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

9head6815head104

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

9head8p16p215①①p1->data+=p2->next;②p1②p1->next=p2->next;④③釋放p2結(jié)點(diǎn):free(p2);④p1=p1->next;p2⑤⑤p2=p1->next;②③可以顛倒嗎？為什么？不可以，釋放結(jié)點(diǎn)之前，要處理前驅(qū)結(jié)點(diǎn)的指向。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個(gè)人圍成一圈，他們的編號(hào)為1-n。第一個(gè)人從1開(kāi)始順序報(bào)數(shù)，凡報(bào)到m時(shí)，該人退出圈子。其后的人再?gòu)?開(kāi)始順序報(bào)數(shù)，直到最后一個(gè)退出圈子為止。輸出依次退出圈子的人的編號(hào)。n和m的值從鍵盤(pán)上輸入，且均小于200。（2000年）鏈表上結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)為：structnode{intdata;

structnode*next;};12/19/2024p為遍歷指針；指針q指向p的前驅(qū)；count為計(jì)數(shù)器當(dāng)指針p指向的結(jié)點(diǎn)不是要?jiǎng)h除的結(jié)點(diǎn)時(shí)：pqq①①q=p;p②②p=p->next;③count++;12/19/2024當(dāng)指針p指向的結(jié)點(diǎn)是要?jiǎng)h除的結(jié)點(diǎn)時(shí)：pq①①q->next=p->next;p④②free(p);③count=0;④p=q->next;注意：使用兩個(gè)指針對(duì)循環(huán)鏈表的操作無(wú)需考慮頭和尾。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;}}}

移動(dòng)指針之前，要處理前驅(qū)結(jié)點(diǎn)的指向。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個(gè)人的序號(hào)1、2……n-1、n。報(bào)數(shù)時(shí)，若a[i]的值不為0，則參與報(bào)數(shù)；否則不參與報(bào)數(shù)。當(dāng)a[j]對(duì)應(yīng)的人退出圈子時(shí)（下標(biāo)取值n的余數(shù)為0），則將a[j]置為0。方法2：用數(shù)組實(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(“輸入出圈的號(hào)數(shù)：“)；scanf(“%d”,&m);

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

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

structnode{floatenglish,math;

structnode*next;};

求出該鏈表上的結(jié)點(diǎn)個(gè)數(shù)、英語(yǔ)的總成績(jī)和數(shù)學(xué)總成績(jī)，并在鏈?zhǔn)自黾右粋€(gè)新的結(jié)點(diǎn)，其分量english,math分別存放這兩門(mén)課程的平均成績(jī)。若鏈為空鏈時(shí)，鏈?zhǔn)撞辉黾咏Y(jié)點(diǎn)。以下函數(shù)ave的第一個(gè)參數(shù)h指向鏈?zhǔn)?，第二個(gè)參數(shù)count存放求出的結(jié)點(diǎn)個(gè)數(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