C語(yǔ)言程序設(shè)計(jì)：鏈表部分

1、 鏈表的組成鏈表的組成：n頭指針：存放一個(gè)地址，該地址指向一個(gè)元素頭指針：存放一個(gè)地址，該地址指向一個(gè)元素 n結(jié)點(diǎn)：用戶(hù)需要的實(shí)際數(shù)據(jù)和鏈接節(jié)點(diǎn)的指針結(jié)點(diǎn)：用戶(hù)需要的實(shí)際數(shù)據(jù)和鏈接節(jié)點(diǎn)的指針n鏈表鏈表* *P285： 所有結(jié)點(diǎn)為相同結(jié)構(gòu)體類(lèi)型 至少一個(gè)成員為指針至少一個(gè)成員為指針，該指針基類(lèi) 型與鏈表結(jié)點(diǎn)的類(lèi)型相同 （1）建立鏈表）建立鏈表 （2）輸出鏈表中各結(jié)點(diǎn)的值）輸出鏈表中各結(jié)點(diǎn)的值 （3）在鏈表中插入一個(gè)結(jié)點(diǎn)）在鏈表中插入一個(gè)結(jié)點(diǎn) （4）刪除鏈表中的一個(gè)結(jié)點(diǎn)）刪除鏈表中的一個(gè)結(jié)點(diǎn) 數(shù)組與鏈表的比較數(shù)組與鏈表的比較數(shù)組數(shù)組static int a10=1,2,3;3a01a1a2a32a

2、4a5a6a8a7a9 定義數(shù)組必須事先定義數(shù)組的長(zhǎng)度，定義數(shù)組必須事先定義數(shù)組的長(zhǎng)度，若使用時(shí)不需要這么多的存儲(chǔ)空間，若使用時(shí)不需要這么多的存儲(chǔ)空間，必將浪費(fèi)內(nèi)存必將浪費(fèi)內(nèi)存鏈表鏈表struct student int num; float score; struct student *next; a,b,c,d;struct student *next;a.numa.scorea.nextb.numb.scoreb.nextc.numc.scorec.nextd.numd.scored.nextheadstruct student *head;a.next=&b;b.next=&a

3、mp;c;c.next=&d;d.next=Null;Null1、數(shù)組對(duì)數(shù)據(jù)在內(nèi)存的分配是靜態(tài)的、數(shù)組對(duì)數(shù)據(jù)在內(nèi)存的分配是靜態(tài)的 鏈表對(duì)數(shù)據(jù)在內(nèi)存中的分配是動(dòng)態(tài)的鏈表對(duì)數(shù)據(jù)在內(nèi)存中的分配是動(dòng)態(tài)的2、malloc(size) 函數(shù)可在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配到一個(gè)長(zhǎng)度函數(shù)可在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配到一個(gè)長(zhǎng)度為為size的連續(xù)空間。若成功返回值為該空間的起始地址。的連續(xù)空間。若成功返回值為該空間的起始地址。3、calloc(n,size) 函數(shù)可在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配到函數(shù)可在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配到n個(gè)長(zhǎng)度個(gè)長(zhǎng)度為為size的連續(xù)空間。若成功返回值為分配域空間的起始地址。的連續(xù)空間。若成

4、功返回值為分配域空間的起始地址。4、free(prt) 函數(shù)釋放由指針函數(shù)釋放由指針prt指向的內(nèi)存區(qū)為動(dòng)態(tài)存儲(chǔ)區(qū)指向的內(nèi)存區(qū)為動(dòng)態(tài)存儲(chǔ)區(qū)#include 用結(jié)構(gòu)體建立鏈表：用結(jié)構(gòu)體建立鏈表：structstruct student student intint num num； floatfloat score score； structstruct student student * *next next ； ; ; 其中成員其中成員numnum和和scorescore用來(lái)存放結(jié)點(diǎn)中的有用數(shù)據(jù)用來(lái)存放結(jié)點(diǎn)中的有用數(shù)據(jù)（用戶(hù)需要用到的數(shù)據(jù)），（用戶(hù)需要用到的數(shù)據(jù)），nextnext是是指針類(lèi)

5、型指針類(lèi)型的成的成員，它指向員，它指向struct studentstruct student類(lèi)型數(shù)據(jù)（這就是類(lèi)型數(shù)據(jù)（這就是nextnext所在的結(jié)構(gòu)體類(lèi)型）所在的結(jié)構(gòu)體類(lèi)型）運(yùn)行結(jié)果：1010189.51010390.01010785.0例例:建立一個(gè)如圖建立一個(gè)如圖所示的所示的靜態(tài)鏈表，它由靜態(tài)鏈表，它由3個(gè)學(xué)生個(gè)學(xué)生數(shù)據(jù)的結(jié)點(diǎn)組成。輸出各數(shù)據(jù)的結(jié)點(diǎn)組成。輸出各結(jié)點(diǎn)中的數(shù)據(jù)。結(jié)點(diǎn)中的數(shù)據(jù)。#include #define NULL 0 struct student long num; float score; struct student *next; ;main() struct st

6、udent a,b,c,*head,*p; a. num=10101; a.score=89.5; b. num=10103; b.score=90; c. num=10107; c.score=85; head=&a; a.next=&b; b.next=&c; c.next=NULL; p=head; do printf(%ld %5.1fn,p-num,p-score); p=p-next; while(p!=NULL); #include struct lst intnum; struct lst * next ； ; 能指向能指向 struct lst 類(lèi)型變

7、量類(lèi)型變量 abcnum nextnum nextnum nexta.num = 1;a.next = &b;b.num = 2;b.next = &c;c.num = 3;c.next = NULL;p = &a;printf (%4d, p - num );main( ) struct lst a, b, c, *p;1230p1abcnum nextnum nextnum nexta.num = 1;a.next = &b;b.num = 2;b.next = &c;c.num = 3;c.next = NULL;p = &a;printf

8、 (%4d, p - num );main( )p = p - next;printf (%4d, p - num );1230p12 struct lst a, b, c, *p;需創(chuàng)建的單向鏈表結(jié)構(gòu)需創(chuàng)建的單向鏈表結(jié)構(gòu) head頭結(jié)點(diǎn)頭結(jié)點(diǎn) 結(jié)點(diǎn)結(jié)點(diǎn)1結(jié)點(diǎn)結(jié)點(diǎn)2尾結(jié)點(diǎn)尾結(jié)點(diǎn)101103105 0 所謂建立動(dòng)態(tài)鏈表是指所謂建立動(dòng)態(tài)鏈表是指在程序執(zhí)行過(guò)程中在程序執(zhí)行過(guò)程中從無(wú)到有從無(wú)到有地建立起一個(gè)鏈表，即一個(gè)一個(gè)地開(kāi)辟結(jié)點(diǎn)和輸入各結(jié)地建立起一個(gè)鏈表，即一個(gè)一個(gè)地開(kāi)辟結(jié)點(diǎn)和輸入各結(jié)點(diǎn)數(shù)據(jù)，并建立起前后相鏈的關(guān)系點(diǎn)數(shù)據(jù)，并建立起前后相鏈的關(guān)系#include#includestruct node

9、 int num; struct node *next; ;main()struct node *p1,*p2,*p3;p1=(struct node *) malloc(sizeof(struct node);p2=(struct node *) malloc(sizeof(struct node);p3=(struct node *) malloc(sizeof(struct node);p1-num=1;p2-num=2;p3-num=3;p1-next=p2;p2-next=p3;printf(%dn,p1-num+p1-next-num);#include #include main

10、（ ） int *p=NULL;p = (int *) malloc (2);if ( p != NULL )printf (%4d, *p );free ( p );p = (int *) malloc ( sizeof(int) );if ( p != NULL )printf (%4dn, *p );free ( p );p38*p = 6;6*p = 38;38*p(int *)sizeofp2=p1;n鏈表的操作鏈表的操作鏈表建立鏈表建立heada.numa.scorea.nextp1p2p1指向新建立的結(jié)點(diǎn)指向新建立的結(jié)點(diǎn)p2指向當(dāng)前結(jié)點(diǎn)指向當(dāng)前結(jié)點(diǎn)b.numb.scoreb.ne

11、xtp1p2c.numc.scorec.nextp1p2d.numd.scored.nextp1p2p2- next=Null;Nullp1=(struct student *)malloc(sizeof(struct student);head=p1;p1=(struct student *)malloc(sizeof(struct student);p2-next=p1;p2=p1;p1=(struct student *)malloc(sizeof(struct student);p2-next=p1;p2=p1;p1=(struct student *)malloc(sizeof(st

12、ruct student);p2-next=p1;p2=p1;對(duì)鏈表的刪除對(duì)鏈表的刪除刪除的結(jié)點(diǎn)為頭結(jié)點(diǎn)刪除的結(jié)點(diǎn)為頭結(jié)點(diǎn)a.numa.scorea.nextb.numb.scoreb.nextc.numc.scorec.nextd.numd.scored.nextNullheadp2p2=head;head=p2-next;heada.numa.scorea.nextb.numb.scoreb.nextc.numc.scorec.nextd.numd.scored.nextNullhead刪除鏈表中非頭尾結(jié)點(diǎn)刪除鏈表中非頭尾結(jié)點(diǎn)p1=head;尋找要?jiǎng)h除的結(jié)點(diǎn)：尋找要?jiǎng)h除的結(jié)點(diǎn)：p2=p1;

13、p1=p1-next;p1p2p1p2p1刪除該結(jié)點(diǎn)刪除該結(jié)點(diǎn)p2-next=p1-next;a.numa.scorea.nextb.numb.scoreb.nextc.numc.scorec.nextd.numd.scored.nextNullhead刪除尾結(jié)點(diǎn)：刪除尾結(jié)點(diǎn)：for ( p1=head;p1-next!=Null;p1=p1-next) p2=p1;p1p2p2-next=Null;Nulln對(duì)鏈表進(jìn)行插入操作對(duì)鏈表進(jìn)行插入操作b.numb.scoreb.nextc.numc.scorec.nextd.numd.scored.nextNulla.numa.scorea.nex

14、tp0head插入頭結(jié)點(diǎn)插入頭結(jié)點(diǎn)p1headp0-next=p1;head=p0;p1插入尾結(jié)點(diǎn)插入尾結(jié)點(diǎn)d.numd.scored.nextp0b.numb.scoreb.nextc.numc.scorec.nextheada.numa.scorea.nextNullfor (p1=head;p1-next!=Null;p1=p1-next);p1p1-next=p0;Nullc.nextp0-next=Null;p2p1p2插入中間結(jié)點(diǎn)插入中間結(jié)點(diǎn)c.numc.scorec.nextp0尋找插入點(diǎn)：尋找插入點(diǎn)：p2=p1-next;p1=p2;p1p2插入新結(jié)點(diǎn)：插入新結(jié)點(diǎn)：a.numa

15、.scorea.nextb.numb.scoreb.nextd.numd.scored.nextNullheadp0-next=p2;p1-next=p0;例例： 寫(xiě)一寫(xiě)一函數(shù)函數(shù)建立一個(gè)有建立一個(gè)有3名學(xué)生數(shù)據(jù)的名學(xué)生數(shù)據(jù)的單向動(dòng)態(tài)單向動(dòng)態(tài)鏈表。鏈表。n解題思路：解題思路：u定義定義3個(gè)指針變量：個(gè)指針變量：head,p1和和p2，它們都是用來(lái)，它們都是用來(lái)指向指向struct Student類(lèi)型數(shù)據(jù)類(lèi)型數(shù)據(jù)u用用malloc函數(shù)開(kāi)辟第一個(gè)結(jié)點(diǎn)，并使函數(shù)開(kāi)辟第一個(gè)結(jié)點(diǎn)，并使p1和和p2指向指向它它p1=p2=(struct Student*)malloc(LEN);p1p2n解題思路：解題思

16、路：u讀入一個(gè)學(xué)生的數(shù)據(jù)給讀入一個(gè)學(xué)生的數(shù)據(jù)給p1所指的第一個(gè)結(jié)點(diǎn)所指的第一個(gè)結(jié)點(diǎn)p1scanf(%ld,%f,&p1-num,&p1-score);p21010189.5n解題思路：解題思路：u讀入一個(gè)學(xué)生的數(shù)據(jù)給讀入一個(gè)學(xué)生的數(shù)據(jù)給p1所指的第一個(gè)結(jié)點(diǎn)所指的第一個(gè)結(jié)點(diǎn)u使使head也指向新開(kāi)辟的結(jié)點(diǎn)也指向新開(kāi)辟的結(jié)點(diǎn)headp1p2scanf(%ld,%f,&p1-num,&p1-score);1010189.5n解題思路：解題思路：u再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)headp1p21010

17、189.5n解題思路：解題思路：u再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.5p1=(struct Student*)malloc(LEN);scanf(%ld,%f,&p1-num,&p1-score);1010390n解題思路：解題思路：u使第一個(gè)結(jié)點(diǎn)的使第一個(gè)結(jié)點(diǎn)的next成員指向第二個(gè)結(jié)點(diǎn)成員指向第二個(gè)結(jié)點(diǎn)，即，即連接第一個(gè)結(jié)點(diǎn)與第二個(gè)結(jié)點(diǎn)連接第一個(gè)結(jié)點(diǎn)與第二個(gè)結(jié)點(diǎn)u使使p2指向剛才建立的結(jié)點(diǎn)指向剛才建立的結(jié)點(diǎn)headp1p21010189.5p2-next=p1;1010390n

18、解題思路：解題思路：u使第一個(gè)結(jié)點(diǎn)的使第一個(gè)結(jié)點(diǎn)的next成員指向第二個(gè)結(jié)點(diǎn)成員指向第二個(gè)結(jié)點(diǎn)，即，即連接第一個(gè)結(jié)點(diǎn)與第二個(gè)結(jié)點(diǎn)連接第一個(gè)結(jié)點(diǎn)與第二個(gè)結(jié)點(diǎn)u使使p2指向剛才建立的結(jié)點(diǎn)指向剛才建立的結(jié)點(diǎn)headp1p21010189.5p2-next=p1;1010390p2=p1;n解題思路：解題思路：u再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.51010390n解題思路：解題思路：u再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)headp1p2101

19、0189.51010390p1=(struct Student*)malloc(LEN);scanf(%ld,%f,&p1-num,&p1-score);1010785n解題思路：解題思路：u使第使第二二個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的next成員指向第成員指向第三三個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)，即，即連接第二個(gè)結(jié)點(diǎn)與第三個(gè)結(jié)點(diǎn)連接第二個(gè)結(jié)點(diǎn)與第三個(gè)結(jié)點(diǎn)u使使p2指向剛才建立的結(jié)點(diǎn)指向剛才建立的結(jié)點(diǎn)headp1p21010189.510103901010785p2-next=p1;n解題思路：解題思路：u使第使第二二個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的next成員指向第成員指向第三三個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)，即，即連接第二個(gè)結(jié)點(diǎn)與第三個(gè)結(jié)點(diǎn)

20、連接第二個(gè)結(jié)點(diǎn)與第三個(gè)結(jié)點(diǎn)u使使p2指向剛才建立的結(jié)點(diǎn)指向剛才建立的結(jié)點(diǎn)headp1p21010189.510103901010785p2-next=p1;p2=p1;n解題思路：解題思路：u再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.5101039010107850n解題思路：解題思路：u再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.5101039010107850p1=(struct Student*)malloc(L

21、EN);scanf(%ld,%f,&p1-num,&p1-score);n解題思路：解題思路：u輸入的學(xué)號(hào)為輸入的學(xué)號(hào)為0，表示建立鏈表的過(guò)程完成，該，表示建立鏈表的過(guò)程完成，該結(jié)點(diǎn)不應(yīng)連接到鏈表中結(jié)點(diǎn)不應(yīng)連接到鏈表中headp1p21010189.5101039010107850NULLp2-next=NULL;#include #include #define LEN sizeof(struct Student)struct Student long num; float score; struct Student *next;int n;struct Student類(lèi)型數(shù)

22、據(jù)的長(zhǎng)度類(lèi)型數(shù)據(jù)的長(zhǎng)度main() struct Student *pt; pt=creat(); printf(“nnum:%ld nscore:%5.1fn”, pt-num,pt-score); struct Student *creat(void) struct Student *head,*p1,*p2; n=0; p1=p2=( struct Student*) malloc(LEN); scanf(“%ld,%f”,&p1-num,&p1-score); head=NULL; while(p1-num!=0) n=n+1; if(n=1) head=p1; else p2-next=p1; p2=p1; p1=(struct Student*)malloc(LEN); scanf(“%ld,%f”,&p1-num,&p1-score); p2-next=NULL; return head;p1總是總是開(kāi)辟開(kāi)辟新新結(jié)點(diǎn)結(jié)點(diǎn)p2總是總是指向最后結(jié)點(diǎn)指向最后結(jié)點(diǎn)用用p2和和p1連接連