C語言新教材PPT課堂課件-補充-鏈表

1、補充指針與鏈表1 用指針處理鏈表 1.1 鏈表概述 鏈表是一種常見的重要的數(shù)據(jù)結(jié)構(gòu),是動態(tài)地進行存儲分配的一種結(jié)構(gòu)。鏈表的組成：頭指針：存放一個地址，該地址指向一個元素 結(jié)點：用戶需要的實際數(shù)據(jù)和鏈接節(jié)點的指針圖11用指針處理鏈表 用結(jié)構(gòu)體建立鏈表：struct student int num； float score； struct student *next ；; 其中成員num和score用來存放結(jié)點中的有用數(shù)據(jù)（用戶需要用到的數(shù)據(jù)），next是指針類型的成員，它指向struct student類型數(shù)據(jù)（這就是next所在的結(jié)構(gòu)體類型）圖21 用指針處理鏈表 1.2 簡單鏈表 #incl

2、ude #define NULL 0 struct student long num; float score; struct student *next; ; main() struct student a,b,c,*head,*p; a. num=99101; a.score=89.5; b. num=99103; b.score=90; c. num=99107; 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; wh

3、ile(p!=NULL); 運行結(jié)果：99101 89.599103 90.099107 85.0 1 用指針處理鏈表程序分析： 開始時使head指向a結(jié)點，a.next指向b結(jié)點，b.next指向c結(jié)點，這就構(gòu)成鏈表關(guān)系?！癱.next=NULL” 的作用是使c.next不指向任何有用的存儲單元。在輸出鏈表時要借助p，先使p指向a結(jié)點，然后輸出a結(jié)點中的數(shù)據(jù)，“p=p-next” 是為輸出下一個結(jié)點作準備。p-next的值是b結(jié)點的地址，因此執(zhí)行“p=p-next”后p就指向b結(jié)點，所以在下一次循環(huán)時輸出的是b結(jié)點中的數(shù)據(jù)。1 用指針處理鏈表 1.3處理動態(tài)鏈表所需的函數(shù) 庫函數(shù)提供動態(tài)地開

4、辟和釋放存儲單元的有關(guān)函數(shù)：malloc函數(shù)其函數(shù)原型為void *malloc(unsigned int size);其作用是在內(nèi)存的動態(tài)存儲區(qū)中分配一個長度為size的連續(xù)空間。此函數(shù)的值（即“返回值”）是一個指向分配域起始地址的指針（類型為void）。如果此函數(shù)未能成功地執(zhí)行（例如內(nèi)存空間不足），則返回空指針(NULL)。 1 用指針處理鏈表 (2) calloc函數(shù) 其函數(shù)原型為void *calloc（unsigned ，unsigned size）;其作用是在內(nèi)存的動態(tài)存儲區(qū)中分配個長度為size的連續(xù)空間。函數(shù)返回一個指向分配域起始地址的指針；如果分配不成功，返回NULL。 用c

5、alloc函數(shù)可以為一維數(shù)組開辟動態(tài)存儲空間，n為數(shù)組元素個數(shù)，每個元素長度為Size。1 用指針處理鏈表 (3) free函數(shù) 其函數(shù)原型為void free（void *p）;其作用是釋放由指向的內(nèi)存區(qū)，使這部分內(nèi)存區(qū)能被其他變量使用。是最近一次調(diào)用calloc或malloc函數(shù)時返回的值。free函數(shù)無返回值。 以前的版本提供的malloc和calloc函數(shù)得到的是指向字符型數(shù)據(jù)的指針。 ANSI 提供的malloc和calloc函數(shù)規(guī)定為void類型。 1 用指針處理鏈表 1.4 建立動態(tài)鏈表 所謂建立動態(tài)鏈表是指在程序執(zhí)行過程中從無到有地建立起一個鏈表，即一個一個地開辟結(jié)點和輸入各結(jié)

6、點數(shù)據(jù)，并建立起前后相鏈的關(guān)系例 寫一函數(shù)建立一個有3名學(xué)生數(shù)據(jù)的單向動態(tài)鏈表。算法如圖圖31 用指針處理鏈表 算法的實現(xiàn)： 我們約定學(xué)號不會為零，如果輸入的學(xué)號為，則表示建立鏈表的過程完成，該結(jié)點不應(yīng)連接到鏈表中。 如果輸入的p1-num不等于，則輸入的是第一個結(jié)點數(shù)據(jù)（n=1），令headp1，即把p1的值賦給head，也就是使head也指向新開辟的結(jié)點p1所指向的新開辟的結(jié)點就成為鏈表中第一個結(jié)點圖41 用指針處理鏈表 算法的實現(xiàn)： 再開辟另一個結(jié)點并使p1指向它，接著輸入該結(jié)點的數(shù)據(jù).如果輸入的p1-num，則應(yīng)鏈入第個結(jié)點（n=2), 將新結(jié)點的地址賦給第一個結(jié)點的next成員.接著

7、使，也就是使指向剛才建立的結(jié)點圖51 用指針處理鏈表 算法的實現(xiàn)：再開辟一個結(jié)點并使p1指向它，并輸入該結(jié)點的數(shù)據(jù)。在第三次循環(huán)中，由于（），又將的值賦給-，也就是將第個結(jié)點連接到第個結(jié)點之后，并使，使指向最后一個結(jié)點.圖6 1 用指針處理鏈表 算法的實現(xiàn)： 再開辟一個新結(jié)點，并使p1指向它，輸入該結(jié)點的數(shù)據(jù)。由于p1-num的值為，不再執(zhí)行循環(huán)，此新結(jié)點不應(yīng)被連接到鏈表中.將NULL賦給p2-next.建立鏈表過程至此結(jié)束，p1最后所指的結(jié)點未鏈入鏈表中，第三個結(jié)點的next成員的值為NULL，它不指向任何結(jié)點。圖7用指針處理鏈表 建立鏈表的函數(shù)如下: #include #include #

8、define NULL 0 /令NULL代表，用它表示“空地址#define LEN sizeof(struct student) /令LEN代表struct /student類型數(shù)據(jù)的長度 struct student long num; float score; struct student *next; ;int n; /n為全局變量，本文件模塊中各函數(shù)均可使用它用指針處理鏈表 struct student *creat() struct student *head; struct student *p1,*p2; n=0; p1=p2=( struct student*) malloc

9、(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);用指針處理鏈表 1.5 輸出鏈表 首先要知道鏈表第一個結(jié)點的地址，也就是要知道head的值。然后設(shè)一個指針變量p,先指向第一個結(jié)點，輸出所指的結(jié)點，然后使后移一個結(jié)點，再輸出，直到鏈表

10、的尾結(jié)點。 圖8,9用指針處理鏈表 例 編寫一個輸出鏈表的函數(shù)print. void print(struct student *head) struct student *p; printf(nNow,These %d records are:n,n); p=head; if(head!=NULL) do printf(%ld %5.1fn,p-num,p-score); p=p-next; while(p!=NULL); 用指針處理鏈表 1.6 對鏈表的刪除操作 從一個動態(tài)鏈表中刪去一個結(jié)點，并不是真正從內(nèi)存中把它抹掉，而是把它從鏈表中分離開來，只要撤銷原來的鏈接關(guān)系即可。圖10用指針處理

11、鏈表 例 寫一函數(shù)以刪除動態(tài)鏈表中指定的結(jié)點. 解題思路: 從p指向的第一個結(jié)點開始，檢查該結(jié)點中的num值是否等于輸入的要求刪除的那個學(xué)號。如果相等就將該結(jié)點刪除，如不相等，就將p后移一個結(jié)點，再如此進行下去，直到遇到表尾為止。用指針處理鏈表 可以設(shè)兩個指針變量p1和p2，先使p1指向第一個結(jié)點 。 如果要刪除的不是第一個結(jié)點，則使p1后移指向下一個結(jié)點(將p1-next賦給p1)，在此之前應(yīng)將p1的值賦給p2 ，使p2指向剛才檢查過的那個結(jié)點 。用指針處理鏈表 注意： 要刪的是第一個結(jié)點（的值等于的值，如圖1-0（）那樣），則應(yīng)將-賦給。這時指向原來的第二個結(jié)點。第一個結(jié)點雖然仍存在，但它

12、已與鏈表脫離，因為鏈表中沒有一個結(jié)點或頭指針指向它。雖然還指向它，它仍指向第二個結(jié)點，但仍無濟于事，現(xiàn)在鏈表的第一個結(jié)點是原來的第二個結(jié)點，原來第一個結(jié)點已“丟失” ，即不再是鏈表中的一部分了。用指針處理鏈表 注意： 如果要刪除的不是第一個結(jié)點，則將-賦給-，見圖1（）。-原來指向指向的結(jié)點（圖中第二個結(jié)點），現(xiàn)在-改為指向-所指向的結(jié)點（圖中第三個結(jié)點）。所指向的結(jié)點不再是鏈表的一部分。還需要考慮鏈表是空表（無結(jié)點）和鏈表中找不到要刪除的結(jié)點的情況。用指針處理鏈表 圖11 用指針處理鏈表 算法：圖12 用指針處理鏈表 刪除結(jié)點的函數(shù)del:struct student *del(struct

13、 student *head,long num) struct student *p1,*p2; if (head=NULL)printf(nlist null!n);goto end; p1=head; while(num!=p1-num & p1-next!=NULL) p2=p1;p1=p1-next;if(num=p1-num) if(p1=head) head=p1-next; else p2-next=p1-next; printf(delete:%ldn,num); n=n-1; else printf(%ld not been found!n,num);end;return(h

14、ead); 用指針處理鏈表 1.7對鏈表的插入操作 對鏈表的插入是指將一個結(jié)點插入到一個已有的鏈表中。為了能做到正確插入，必須解決兩個問題： 怎樣找到插入的位置； 怎樣實現(xiàn)插入。用指針處理鏈表 先用指針變量p0指向待插入的結(jié)點，p1指向第一個結(jié)點。將p0-num與p1-num相比較，如果p0-nump1- num ，則待插入的結(jié)點不應(yīng)插在p1所指的結(jié)點之前。此時將p1后移，并使p2指向剛才p1所指的結(jié)點。用指針處理鏈表 再將p1-num與p0-num比,如果仍然是p0-num大，則應(yīng)使p1繼續(xù)后移，直到p0-p1- num為止。這時將p0所指的結(jié)點插到p1所指結(jié)點之前。但是如果p1所指的已是表

15、尾結(jié)點，則p1就不應(yīng)后移了。如果p0- num比所有結(jié)點的num都大，則應(yīng)將p0所指的結(jié)點插到鏈表末尾。 如果插入的位置既不在第一個結(jié)點之前，又不在表尾結(jié)點之后，則將p0的值賦給p2-next，使p2-next指向待插入的結(jié)點，然后將p1的值賦給p0-next，使得p0-next指向p1指向的變量。 用指針處理鏈表 如果插入位置為第一個結(jié)點之前(即p1等于head時)，則將p0賦給head，將p1賦給p0-next如果要插到表尾之后，應(yīng)將p0賦給p1-next，NULL賦給p0-next圖13 用指針處理鏈表 算法：圖14 用指針處理鏈表 例 插入結(jié)點的函數(shù)insert如下。 struct s

16、tudent *insert(struct student *head, struct student *stud)struct student *p0,*p1,*p2; p1=head;p0=stud;if(head=NULL) head=p0; p0-next=NULL;elsewhile(p0-nump1-num) & (p1-next!=NULL) p2=p1; p1=p1-next; if(p0-numnum) if(head=p1) head=p0; else p2-next=p0;p0-next=p1; else p1-next=p0; p0-next=NULL; n=n+1;

17、return(head); 用指針處理鏈表 11.7.8 對鏈表的綜合操作 將以上建立、輸出、刪除、插入的函數(shù)組織在一個C程序中，用函數(shù)作主調(diào)函數(shù)。 void main() struct student *head,stu;long del_num; prinf(intput records:n) ; head=creat();print(head);printf ( n intput the deleted number:n); scanf (%ld,&del_num) ;head=del(head,del_num);print(head);printf ( n intput the del

18、eted number:n); scanf (%ld,&stu.num,&stu.score) ;head=insert(head,&stu);print(head); 用指針處理鏈表 此程序運行結(jié)果是正確的。它只刪除一個結(jié)點，插入一個結(jié)點。但如果想再插入一個結(jié)點，重復(fù)寫上程序最后4行，共插入兩個結(jié)點，運行結(jié)果卻是錯誤的。Input records：（建立鏈表）10，10，10，用指針處理鏈表 Now,these 3 records are：101010 intput the deleted number ：10103（刪除）：10Now,these 4 records are：1010 用指

19、針處理鏈表 input the inserted record （插入第一個結(jié)點）10102，90Now,these 3 records are：101010input the inserted record （插入第二個結(jié)點）10104，99Now,these 4 records are：10101010 用指針處理鏈表 出現(xiàn)以上結(jié)果的原因是： stu是一個有固定地址的結(jié)構(gòu)體變量。第一次把stu結(jié)點插入到鏈表中，第二次若再用它來插入第二個結(jié)點，就把第一次結(jié)點的數(shù)據(jù)沖掉了，實際上并沒有開辟兩個結(jié)點。為了解決這個問題，必須在每插入一個結(jié)點時新開辟一個內(nèi)存區(qū)。我們修改main函數(shù)，使之能刪除多個結(jié)

20、點（直到輸入要刪的學(xué)號為0），能插入多個結(jié)點（直到輸入要插入的學(xué)號為0）。 用指針處理鏈表 main() struct student *head,*stu; long del_num;printf(input records:n); head=creat(); print (head); printf(ninput the deleted number:); scanf(%ld,&del_num); while (del_num!=0)head=del(head,del_num);print (head);printf (input the deleted number:);scanf(%ld,&del_num); printf(ninput the inserted record:);stu=(struct student *) malloc(LEN); scanf(%ld,%f,&stu-num,&stu-score); while(stu-num!=0)head=insert(head,stu); printf(input the