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

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

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

struct lst {intnum; structlst*next；

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

head頭結(jié)點

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

head頭結(jié)點

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

head頭結(jié)點

結(jié)點1結(jié)點2尾結(jié)點\0101103105移動p，即使p指向下一個結(jié)點p

head頭結(jié)點

結(jié)點1結(jié)點2尾結(jié)點\0101103105移動p，即使p指向下一個結(jié)點p

head頭結(jié)點

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

head頭結(jié)點

結(jié)點1結(jié)點2尾結(jié)點\0101103105移動p，即使p指向下一個結(jié)點p

head頭結(jié)點

結(jié)點1結(jié)點2尾結(jié)點\0101103105移動p，即使p指向下一個結(jié)點pp=p->next;

head頭結(jié)點

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

head頭結(jié)點

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

head頭結(jié)點

結(jié)點1結(jié)點2尾結(jié)點\0101103105移動p，即使p指向下一個結(jié)點不存在，所以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）編寫myinsert()函數(shù)，并用此函數(shù)代替對應(yīng)的空函數(shù)后運行程序

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

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

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

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

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

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

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

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

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

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

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

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

head頭結(jié)點結(jié)點1尾結(jié)點結(jié)點2新結(jié)點s101103105\0104插入新結(jié)點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;}