第9章-動(dòng)態(tài)鏈表

9.4.3建立動(dòng)態(tài)鏈表所謂建立動(dòng)態(tài)鏈表是指在程序執(zhí)行過(guò)程中從無(wú)到有地建立起一個(gè)鏈表，即一個(gè)一個(gè)地開(kāi)拓結(jié)點(diǎn)和輸入各結(jié)點(diǎn)數(shù)據(jù)，并建立起前后相鏈的關(guān)系。9.4.3建立動(dòng)態(tài)鏈表

例9.9寫(xiě)一函數(shù)建立一個(gè)有3名學(xué)生數(shù)據(jù)的單向動(dòng)態(tài)鏈表。解題思路：定義3個(gè)指針變量：head,p1和p2，它們都是用來(lái)指向structStudent類(lèi)型數(shù)據(jù)structStudent*head,*p1,*p2;解題思路：用malloc函數(shù)開(kāi)拓第一個(gè)結(jié)點(diǎn)，并使p1和p2指向它p1p1=p2=(structStudent*)malloc(LEN);p2解題思路：讀入一個(gè)學(xué)生的數(shù)據(jù)給p1所指的第一個(gè)結(jié)點(diǎn)p1scanf("%ld,%f",&p1->num,&p1->score);p21010189.5解題思路：讀入一個(gè)學(xué)生的數(shù)據(jù)給p1所指的第一個(gè)結(jié)點(diǎn)使head也指向新開(kāi)拓的結(jié)點(diǎn)headp1p2scanf("%ld,%f",&p1->num,&p1->score);1010189.5解題思路：再開(kāi)拓另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.5解題思路：再開(kāi)拓另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.5p1=(structStudent*)malloc(LEN);scanf("%ld,%f",&p1->num,&p1->score);1010390解題思路：使第一個(gè)結(jié)點(diǎn)的next成員指向其次個(gè)結(jié)點(diǎn)，即連接第一個(gè)結(jié)點(diǎn)與其次個(gè)結(jié)點(diǎn)使p2指向剛才建立的結(jié)點(diǎn)headp1p21010189.5p2->next=p1;1010390解題思路：使第一個(gè)結(jié)點(diǎn)的next成員指向其次個(gè)結(jié)點(diǎn)，即連接第一個(gè)結(jié)點(diǎn)與其次個(gè)結(jié)點(diǎn)使p2指向剛才建立的結(jié)點(diǎn)headp1p21010189.5p2->next=p1;1010390p2=p1;解題思路：再開(kāi)拓另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.51010390解題思路：再開(kāi)拓另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.51010390p1=(structStudent*)malloc(LEN);scanf("%ld,%f",&p1->num,&p1->score);1010785解題思路：使其次個(gè)結(jié)點(diǎn)的next成員指向第三個(gè)結(jié)點(diǎn)，即連接其次個(gè)結(jié)點(diǎn)與第三個(gè)結(jié)點(diǎn)使p2指向剛才建立的結(jié)點(diǎn)headp1p21010189.510103901010785p2->next=p1;解題思路：使其次個(gè)結(jié)點(diǎn)的next成員指向第三個(gè)結(jié)點(diǎn)，即連接其次個(gè)結(jié)點(diǎn)與第三個(gè)結(jié)點(diǎn)使p2指向剛才建立的結(jié)點(diǎn)headp1p21010189.510103901010785p2->next=p1;p2=p1;解題思路：再開(kāi)拓另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.5101039010107850…解題思路：再開(kāi)拓另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.5101039010107850…p1=(structStudent*)malloc(LEN);scanf("%ld,%f",&p1->num,&p1->score);解題思路：輸入的學(xué)號(hào)為0，表示建立鏈表的過(guò)程完成，該結(jié)點(diǎn)不應(yīng)連接到鏈表中headp1p21010189.5101039010107850…NULLp2->next=NULL;#include<stdio.h>#include<stdlib.h>#defineLENsizeof(structStudent)structStudent{longnum;floatscore;structStudent*next;};intn;structStudent類(lèi)型數(shù)據(jù)的長(zhǎng)度structStudent*creat(void){structStudent*head,*p1,*p2;n=0;p1=p2=(structStudent*)malloc(LEN);scanf(“%ld,%f”,&p1->num,&p1->score);head=NULL;while(p1->num!=0){n=n+1; if(n==1)head=p1; elsep2->next=p1; p2=p1; p1=(structStudent*)malloc(LEN); scanf(“%ld,%f”,&p1->num,&p1->score); }p2->next=NULL;return(head);}p1總是開(kāi)拓新結(jié)點(diǎn)p2總是指向最終結(jié)點(diǎn)用p2和p1連接兩個(gè)結(jié)點(diǎn)intmain(){structStudent*pt;pt=creat();printf(“\nnum:%ld\nscore:%5.1f\n”,pt->num,pt->score);return0;}9.4.4輸出鏈表例9.10編寫(xiě)一個(gè)輸出鏈表的函數(shù)print。100167.5100387100599NULLp解題思路：輸出p所指的結(jié)點(diǎn)使p后移一個(gè)結(jié)點(diǎn)p100167.5100387100599NULLprintf("%ld%5.1f\n",p->num,p->score);100167.5100387100599NULLp=p->next;解題思路：輸出p所指的結(jié)點(diǎn)使p后移一個(gè)結(jié)點(diǎn)printf("%ld%5.1f\n",p->num,p->score);p100167.5100387100599NULL解題思路：輸出p所指的新結(jié)點(diǎn)使p后移一個(gè)結(jié)點(diǎn)printf("%ld%5.1f\n",p->num,p->score);p100167.5100387100599NULLp=p->next;解題思路：輸出p所指的新結(jié)點(diǎn)使p后移一個(gè)結(jié)點(diǎn)printf("%ld%5.1f\n",p->num,p->score);p100167.5100387100599NULLp=p->next;解題思路：輸出p所指的新結(jié)點(diǎn)使p后移一個(gè)結(jié)點(diǎn)printf("%ld%5.1f\n",p->num,p->score);p相當(dāng)于p=NULL;voidprint(structStudent*p){printf("\nThese%drecordsare:\n",n);if(p!=NULL)do{printf("%ld%5.1f\n",p->num,p->score);p=p->next;}while(p!=NULL);}例9.11調(diào)用函數(shù)完成鏈表的建立、輸出各結(jié)點(diǎn)的值、插入和刪除一個(gè)結(jié)點(diǎn)的功能具體要求：調(diào)用mycreat函數(shù)，建立鏈表調(diào)用myinsert函數(shù)，插入一個(gè)結(jié)點(diǎn)調(diào)用mydelete函數(shù)，刪除值為m的結(jié)點(diǎn)調(diào)用myprint函數(shù)，輸出各結(jié)點(diǎn)（1）聲明結(jié)構(gòu)體類(lèi)型：

struct lst {intnum; structlst*next；

};typedefstructlstLST;可用LST代替structlst（2）編寫(xiě)主函數(shù)，并先用空函數(shù)占被調(diào) 函數(shù)的位置后測(cè)試#include<stdio.h>#include<stdlib.h>typedefstructlst{intnum;structlst*next；}LST;LST*mycreat(){}voidmyprint(){}voidmyinsert(){}intmydelete(){}intmain() {LST*head=NULL;intk=0,m=0,choose=0;head=mycreat(); printf("新建鏈表為：");myprint(head);printf(“請(qǐng)選擇：1.插入2.刪除”);scanf("%d",&choose);switch(choose){case1:printf("插入點(diǎn):");scanf("%d",&m);myinsert(head,m);printf(“插入點(diǎn)后:”);myprint(head);break;case2:printf("刪除點(diǎn):");scanf("%d",&m);k=mydelete(head,m);if(k==1){printf("刪除點(diǎn)后:");myprint(head);}elseprintf(“不存在\n");break;}return0;}（3）編寫(xiě)mycreat()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序開(kāi)拓頭結(jié)點(diǎn)，并用頭指針head指向它head=(LST*)malloc(sizeof(LST));head頭結(jié)點(diǎn)numnexthead頭結(jié)點(diǎn)qnumnext使指針變量q也指向該頭結(jié)點(diǎn)q=head;（3）編寫(xiě)mycreat()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序head頭結(jié)點(diǎn)qpnumnext結(jié)點(diǎn)1numnext開(kāi)拓新的結(jié)點(diǎn)，并使指針變量p指向它p=(LST*)malloc(sizeof(LST));（3）編寫(xiě)mycreat()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序head頭結(jié)點(diǎn)qnumnext結(jié)點(diǎn)1numnext連接新結(jié)點(diǎn)和當(dāng)前鏈表的最終結(jié)點(diǎn)q->next=p;p（3）編寫(xiě)mycreat()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序head頭結(jié)點(diǎn)qnumnext結(jié)點(diǎn)1numnext將數(shù)據(jù)賜予新結(jié)點(diǎn)的num成員p->num=m;101p（3）編寫(xiě)mycreat()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序head頭結(jié)點(diǎn)qnumnext結(jié)點(diǎn)1numnext使q指向新鏈表的最終一個(gè)結(jié)點(diǎn)101p（3）編寫(xiě)mycreat()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序head頭結(jié)點(diǎn)qnumnext結(jié)點(diǎn)1numnext使q指向新鏈表的最終一個(gè)結(jié)點(diǎn)q=p;101p（3）編寫(xiě)mycreat()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序head頭結(jié)點(diǎn)numnext結(jié)點(diǎn)1numnext新結(jié)點(diǎn)numnext開(kāi)拓新的結(jié)點(diǎn)，并使指針變量p指向它101pq（3）編寫(xiě)mycreat()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序head頭結(jié)點(diǎn)numnext結(jié)點(diǎn)1numnext新結(jié)點(diǎn)numnext開(kāi)拓新的結(jié)點(diǎn)，并使指針變量p指向它101pqp=(LST*)malloc(sizeof(LST));（3）編寫(xiě)mycreat()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序head頭結(jié)點(diǎn)numnext結(jié)點(diǎn)1numnext新結(jié)點(diǎn)numnext連接新結(jié)點(diǎn)和當(dāng)前鏈表的最終結(jié)點(diǎn)q->next=p;101qp（3）編寫(xiě)mycreat()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序head頭結(jié)點(diǎn)numnext結(jié)點(diǎn)1numnext新結(jié)點(diǎn)numnext將數(shù)據(jù)賜予新結(jié)點(diǎn)的num成員p->num=m;101q103p（3）編寫(xiě)mycreat()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序head頭結(jié)點(diǎn)numnext結(jié)點(diǎn)1numnext新結(jié)點(diǎn)numnext使q指向新鏈表的最終一個(gè)結(jié)點(diǎn)101q103p（3）編寫(xiě)mycreat()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序head頭結(jié)點(diǎn)numnext結(jié)點(diǎn)1numnext新結(jié)點(diǎn)numnext使q指向新鏈表的最終一個(gè)結(jié)點(diǎn)q=p;101q103p（3）編寫(xiě)mycreat()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序head頭結(jié)點(diǎn)numnext結(jié)點(diǎn)1numnext新結(jié)點(diǎn)numnext鏈表的最終一個(gè)結(jié)點(diǎn)設(shè)為尾結(jié)點(diǎn)q->next=NULL;101q103p\0（3）編寫(xiě)mycreat()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序返回鏈表頭結(jié)點(diǎn)的地址returnhead;head頭結(jié)點(diǎn)numnext結(jié)點(diǎn)1numnext新結(jié)點(diǎn)numnext101q103p\0（3）編寫(xiě)mycreat()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序LST*mycreat(){int m=0;LST*head=NULL,*p=NULL,*q=NULL;head=(LST*)malloc(sizeof(LST));q=head;printf("建立鏈表，請(qǐng)輸入數(shù)值：\n");printf("Inputm:"); scanf("%d",&m);while(m!=-1){p=(LST*)malloc(sizeof(LST));q->next=p;p->num=m;q=p;printf("Inputm:");scanf("%d",&m);}q->next=NULL;returnhead;}（4）編寫(xiě)myprint()函數(shù)，并用此函數(shù) 代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序

head頭結(jié)點(diǎn)

結(jié)點(diǎn)1結(jié)點(diǎn)2尾結(jié)點(diǎn)\0101103105使指針p指向鏈表中結(jié)點(diǎn)1pp=head->next;

head頭結(jié)點(diǎn)

結(jié)點(diǎn)1結(jié)點(diǎn)2尾結(jié)點(diǎn)\0101103105輸出p所指結(jié)點(diǎn)的num成員值pprintf("%5d",p->num);101

head頭結(jié)點(diǎn)

結(jié)點(diǎn)1結(jié)點(diǎn)2尾結(jié)點(diǎn)\0101103105移動(dòng)p，即使p指向下一個(gè)結(jié)點(diǎn)p

head頭結(jié)點(diǎn)

結(jié)點(diǎn)1結(jié)點(diǎn)2尾結(jié)點(diǎn)\0101103105移動(dòng)p，即使p指向下一個(gè)結(jié)點(diǎn)p

head頭結(jié)點(diǎn)

結(jié)點(diǎn)1結(jié)點(diǎn)2尾結(jié)點(diǎn)\0101103105輸出p所指結(jié)點(diǎn)的num成員值pprintf("%5d",p->num);103

head頭結(jié)點(diǎn)

結(jié)點(diǎn)1結(jié)點(diǎn)2尾結(jié)點(diǎn)\0101103105移動(dòng)p，即使p指向下一個(gè)結(jié)點(diǎn)p

head頭結(jié)點(diǎn)

結(jié)點(diǎn)1結(jié)點(diǎn)2尾結(jié)點(diǎn)\0101103105移動(dòng)p，即使p指向下一個(gè)結(jié)點(diǎn)pp=p->next;

head頭結(jié)點(diǎn)

結(jié)點(diǎn)1結(jié)點(diǎn)2尾結(jié)點(diǎn)\0101103105輸出p所指結(jié)點(diǎn)的num成員值pprintf("%5d",p->num);105移動(dòng)p，即使p指向下一個(gè)結(jié)點(diǎn)

head頭結(jié)點(diǎn)

結(jié)點(diǎn)1結(jié)點(diǎn)2尾結(jié)點(diǎn)\0101103105p

head頭結(jié)點(diǎn)

結(jié)點(diǎn)1結(jié)點(diǎn)2尾結(jié)點(diǎn)\0101103105移動(dòng)p，即使p指向下一個(gè)結(jié)點(diǎn)不存在，所以p=NULLp=p->next;voidmyprint(LST*head) {LST*p=NULL;p=head->next; if(p==NULL)printf("鏈表為空表!"); else do {printf("%5d",p->num); p=p->next; }while(p!=NULL); printf("\n");}（5）編寫(xiě)myinsert()函數(shù)，并用此函數(shù)代替對(duì)應(yīng)的空函數(shù)后運(yùn)行程序

head頭結(jié)點(diǎn)結(jié)點(diǎn)1尾結(jié)點(diǎn)結(jié)點(diǎn)2新結(jié)點(diǎn)s101103105\0指針s去開(kāi)拓需插入的結(jié)點(diǎn)s=(LST*)malloc(sizeof(LST));

head頭結(jié)點(diǎn)結(jié)點(diǎn)1尾結(jié)點(diǎn)結(jié)點(diǎn)2新結(jié)點(diǎn)s101103105\0104需插入的數(shù)值賜予新結(jié)點(diǎn)的num成員s->num=m;

head頭結(jié)點(diǎn)結(jié)點(diǎn)1尾結(jié)點(diǎn)結(jié)點(diǎn)2新結(jié)點(diǎn)s101103105\0104qpq指向頭結(jié)點(diǎn)q=head;p指向結(jié)點(diǎn)1p=head->next;

head頭結(jié)點(diǎn)結(jié)點(diǎn)1尾結(jié)點(diǎn)結(jié)點(diǎn)2新結(jié)點(diǎn)s101103105\0104qp推斷是否找到插入點(diǎn)if(p->num<=m)

head頭結(jié)點(diǎn)結(jié)點(diǎn)1尾結(jié)點(diǎn)結(jié)點(diǎn)2新結(jié)點(diǎn)s101103105\0104qpq、p都移到下一個(gè)結(jié)點(diǎn)

head頭結(jié)點(diǎn)結(jié)點(diǎn)1尾結(jié)點(diǎn)結(jié)點(diǎn)2新結(jié)點(diǎn)s101103105\0104qq、p都移到下一個(gè)結(jié)點(diǎn)q=q->next;p

head頭結(jié)點(diǎn)結(jié)點(diǎn)1尾結(jié)點(diǎn)結(jié)點(diǎn)2新結(jié)點(diǎn)s101103105\0104qq、p都移到下一個(gè)結(jié)點(diǎn)q=q->next;p=p->next;p

head頭結(jié)點(diǎn)結(jié)點(diǎn)1尾結(jié)點(diǎn)新結(jié)點(diǎn)s101103105\0104q推斷是否找到插入點(diǎn)if(p->num<=m)p結(jié)點(diǎn)2

head頭結(jié)點(diǎn)結(jié)點(diǎn)1尾結(jié)點(diǎn)結(jié)點(diǎn)2新結(jié)點(diǎn)s101103105\0104qpq、p都移到下一個(gè)結(jié)點(diǎn)

head頭結(jié)點(diǎn)結(jié)點(diǎn)1尾結(jié)點(diǎn)結(jié)點(diǎn)2新結(jié)點(diǎn)s101103105\0104qq、p都移到下一個(gè)結(jié)點(diǎn)pq=q->next;

head頭結(jié)點(diǎn)結(jié)點(diǎn)1尾結(jié)點(diǎn)結(jié)點(diǎn)2新結(jié)點(diǎn)s101103105\0104pq、p都移到下一個(gè)結(jié)點(diǎn)q=q->next;p=p->next;q

head頭結(jié)點(diǎn)結(jié)點(diǎn)1尾結(jié)點(diǎn)結(jié)點(diǎn)2新結(jié)點(diǎn)s101103105\0104推斷是否找到插入點(diǎn)if(p->num<=m)pq

head頭結(jié)點(diǎn)結(jié)點(diǎn)1尾結(jié)點(diǎn)結(jié)點(diǎn)2新結(jié)點(diǎn)s101103105\0104插入新結(jié)點(diǎn)s->next=p;pq->next=s;qvoidmyinsert(LST*head,intm){LST*p=NULL,*q=NULL,*s=NULL;s=(LST*)malloc(sizeof(LST));s->num=m;q=head;p=head->next;while(p!=NULL)if(p->num<=m){q=q->next;p=p->next;}