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

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

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

struct lst {intnum; structlst*next；

};typedefstructlstLST;可用LST代替structlst（2）編寫主函數，并先用空函數占被調 函數的位置后測試#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()函數，并用此函數代替對應的空函數后運行程序開拓頭結點，并用頭指針head指向它head=(LST*)malloc(sizeof(LST));head頭結點numnexthead頭結點qnumnext使指針變量q也指向該頭結點q=head;（3）編寫mycreat()函數，并用此函數代替對應的空函數后運行程序head頭結點qpnumnext結點1numnext開拓新的結點，并使指針變量p指向它p=(LST*)malloc(sizeof(LST));（3）編寫mycreat()函數，并用此函數代替對應的空函數后運行程序head頭結點qnumnext結點1numnext連接新結點和當前鏈表的最終結點q->next=p;p（3）編寫mycreat()函數，并用此函數代替對應的空函數后運行程序head頭結點qnumnext結點1numnext將數據賜予新結點的num成員p->num=m;101p（3）編寫mycreat()函數，并用此函數代替對應的空函數后運行程序head頭結點qnumnext結點1numnext使q指向新鏈表的最終一個結點101p（3）編寫mycreat()函數，并用此函數代替對應的空函數后運行程序head頭結點qnumnext結點1numnext使q指向新鏈表的最終一個結點q=p;101p（3）編寫mycreat()函數，并用此函數代替對應的空函數后運行程序head頭結點numnext結點1numnext新結點numnext開拓新的結點，并使指針變量p指向它101pq（3）編寫mycreat()函數，并用此函數代替對應的空函數后運行程序head頭結點numnext結點1numnext新結點numnext開拓新的結點，并使指針變量p指向它101pqp=(LST*)malloc(sizeof(LST));（3）編寫mycreat()函數，并用此函數代替對應的空函數后運行程序head頭結點numnext結點1numnext新結點numnext連接新結點和當前鏈表的最終結點q->next=p;101qp（3）編寫mycreat()函數，并用此函數代替對應的空函數后運行程序head頭結點numnext結點1numnext新結點numnext將數據賜予新結點的num成員p->num=m;101q103p（3）編寫mycreat()函數，并用此函數代替對應的空函數后運行程序head頭結點numnext結點1numnext新結點numnext使q指向新鏈表的最終一個結點101q103p（3）編寫mycreat()函數，并用此函數代替對應的空函數后運行程序head頭結點numnext結點1numnext新結點numnext使q指向新鏈表的最終一個結點q=p;101q103p（3）編寫mycreat()函數，并用此函數代替對應的空函數后運行程序head頭結點numnext結點1numnext新結點numnext鏈表的最終一個結點設為尾結點q->next=NULL;101q103p\0（3）編寫mycreat()函數，并用此函數代替對應的空函數后運行程序返回鏈表頭結點的地址returnhead;head頭結點numnext結點1numnext新結點numnext101q103p\0（3）編寫mycreat()函數，并用此函數代替對應的空函數后運行程序LST*mycreat(){int m=0;LST*head=NULL,*p=NULL,*q=NULL;head=(LST*)malloc(sizeof(LST));q=head;printf("建立鏈表，請輸入數值：\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()函數，并用此函數 代替對應的空函數后運行程序

head頭結點

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

head頭結點

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

head頭結點

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

head頭結點

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

head頭結點

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

head頭結點

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

head頭結點

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

head頭結點

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

head頭結點

結點1結點2尾結點\0101103105p

head頭結點

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

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

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

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

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

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

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

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

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

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

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

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

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

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