第10章動態(tài)數(shù)組與鏈表

1、第十章 動態(tài)數(shù)組與鏈表內(nèi)存分配方式有三種：（1）從靜態(tài)存儲區(qū)域分配。）從靜態(tài)存儲區(qū)域分配。（2）在棧上創(chuàng)建。）在棧上創(chuàng)建。 （3） 從堆上分配，亦稱動態(tài)內(nèi)存分配。從堆上分配，亦稱動態(tài)內(nèi)存分配。 內(nèi)存在程序編譯的時候就已經(jīng)分配內(nèi)存在程序編譯的時候就已經(jīng)分配好，這塊內(nèi)存在程序的整個運行期間好，這塊內(nèi)存在程序的整個運行期間都存在。例如全局變量，都存在。例如全局變量，static變量。變量。 在執(zhí)行函數(shù)時，函數(shù)內(nèi)局部變在執(zhí)行函數(shù)時，函數(shù)內(nèi)局部變量的存儲單元都可以在棧上創(chuàng)建，量的存儲單元都可以在棧上創(chuàng)建，函數(shù)執(zhí)行結(jié)束時這些存儲單元自動函數(shù)執(zhí)行結(jié)束時這些存儲單元自動被釋放。被釋放。 效率很高，但是分配的內(nèi)

2、存容效率很高，但是分配的內(nèi)存容量有限。量有限。 用用malloc等函數(shù)申請任意多少的內(nèi)存，等函數(shù)申請任意多少的內(nèi)存，程序員自己負(fù)責(zé)在何時用程序員自己負(fù)責(zé)在何時用free函數(shù)釋放函數(shù)釋放內(nèi)存。內(nèi)存。 動態(tài)內(nèi)存的生存期從動態(tài)內(nèi)存的生存期從malloc等函數(shù)等函數(shù)執(zhí)行開始，到執(zhí)行開始，到free函數(shù)被調(diào)用結(jié)束，若函數(shù)被調(diào)用結(jié)束，若沒有沒有free函數(shù)，則到整個程序運行結(jié)束函數(shù)，則到整個程序運行結(jié)束為止。使用非常靈活，但問題也最多。為止。使用非常靈活，但問題也最多。引入問題引入問題1. 求某班級（求某班級（30人人）中所有學(xué)生的成績平均分。）中所有學(xué)生的成績平均分。 float a302. 求任意一個

3、班級（求任意一個班級（人數(shù)不定人數(shù)不定）中所有學(xué)生的成績）中所有學(xué)生的成績平均分。平均分。方法：求最大班級人數(shù)（假設(shè)方法：求最大班級人數(shù)（假設(shè)100），），float a100 解決辦法：能不能根據(jù)我輸入的班級人數(shù)，來自動的確解決辦法：能不能根據(jù)我輸入的班級人數(shù)，來自動的確定數(shù)組長度。定數(shù)組長度。 缺點：浪費內(nèi)存空間缺點：浪費內(nèi)存空間靜態(tài)分配靜態(tài)分配動態(tài)分配動態(tài)分配動態(tài)存儲分配函數(shù)動態(tài)存儲分配函數(shù) malloc函數(shù)(memory allocation) void *malloc(int n);calloc函數(shù)(count allocation) void *calloc(int count,i

4、nt n);free函數(shù) void free(void *ptr);realloc函數(shù)(reallocation) void *realloc(void *p,int n);使用時包含使用時包含malloc.h或或stdlib.hint *p,n;Scanf(“%d”,&n);p= malloc(n); (int*)int a10; 40int *p,count,n;Scanf(“%d%d”,&count,&n);p= calloc(count,n);(int*)10 4int *p,n;Scanf(“%d”,&n);p= malloc(n);p= reallo

5、c(p,40);(int*)10(int*)free(p)#include #include void main() float *p,s=0;int num,i; scanf(%d,&num); p=(float*)malloc(num); for (i=0;inum;i+) scanf(%f,p+i); for (i=0;inum;i+) printf(%6.2f,*(p+i); for (i=0;inum;i+) s=s+(*(p+i); printf(n%f,s/num);2. 求任意一個班級（求任意一個班級（人數(shù)不定人數(shù)不定）中所有學(xué)生的成績平均分。中所有學(xué)生的成績平均分。f

6、ree函數(shù) void free(void *ptr);#include#include#includevoid main() char *str; str=(char *)malloc(10*sizeof(char); strcpy(str,china); printf(String is %sn,str); free(str); printf(String is %sn,str); #include#include#includevoid main() char *str; char* m();str=m();printf(String is %sn,str);char* m()char *

7、 str;str=(char *)malloc(10*sizeof(char); strcpy(str,china); printf(String is %sn,str); / free(str); /考察考察str所指向的空間什么時候被回收？所指向的空間什么時候被回收？ printf(String is %sn,str);return str 動態(tài)內(nèi)存分配函數(shù)是在整個程序運行完畢動態(tài)內(nèi)存分配函數(shù)是在整個程序運行完畢時，才回收內(nèi)存；但是函數(shù)的局部變量是時，才回收內(nèi)存；但是函數(shù)的局部變量是在本函數(shù)執(zhí)行完畢時就回收。使用了在本函數(shù)執(zhí)行完畢時就回收。使用了free函數(shù)，就可以在執(zhí)行到該語句時，就能夠

8、函數(shù)，就可以在執(zhí)行到該語句時，就能夠回收該內(nèi)存空間?；厥赵搩?nèi)存空間。reallocrealloc函數(shù)函數(shù)void *realloc(void *p,int n); #include #include #include main() char *p; p=(char *)malloc(100); if(p) printf(Memory Allocated at: %x,p); else printf(Not Enough Memory!n); strcpy(p,hello world); p=(char *)realloc(p,600); if(p) printf(Memory Realloca

9、ted at: %x,p); else printf(Not Enough Memory!n); free(p); #include #include #include main() struct stu int num; char *name; char sex; float score10; struct stu *q; *p; p=(struct stu *)malloc(sizeof(struct stu); scanf(“%s”,p-name);%出現(xiàn)錯誤！出現(xiàn)錯誤！Name所指向的存儲空間不可用所指向的存儲空間不可用 printf(%s,(*p).name); p-name=“zh

10、angsan”;“zhangsan”在常量存儲區(qū)由編譯在常量存儲區(qū)由編譯器自動開辟空間器自動開辟空間例：跳馬。依下圖將每一步跳馬之后的位置例：跳馬。依下圖將每一步跳馬之后的位置(x,y)(x,y)放放到一個到一個“結(jié)點結(jié)點”里，再用里，再用“鏈子穿起來鏈子穿起來”，形成，形成一條鏈，相鄰兩結(jié)點間用一個指針將兩者連到一一條鏈，相鄰兩結(jié)點間用一個指針將兩者連到一起。起。動態(tài)鏈表動態(tài)鏈表 0 1 2 3 4 5 6 7 8 4 3 2 1 結(jié)點結(jié)點 1 2 3 4 5 6 7 依上圖有依上圖有7個結(jié)點個結(jié)點x1x1y1y1每個節(jié)點既有數(shù)據(jù)每個節(jié)點既有數(shù)據(jù)(xi(xi和和yi)yi) 又有指針（下個結(jié)

11、點的地址），又有指針（下個結(jié)點的地址），用什么樣的數(shù)據(jù)類型表示每個節(jié)點用什么樣的數(shù)據(jù)類型表示每個節(jié)點x2x2y2y2x7x7y7y7x6x6y6y6 struct nodeint x;int y;構(gòu)造節(jié)點的數(shù)據(jù)類型構(gòu)造節(jié)點的數(shù)據(jù)類型struct node *next鏈表的幾個基本概念鏈表的幾個基本概念x1,y1x1,y11249x2,y2x2,y21356x4,y4x4,y41021x3,y3x3,y314751356147510210NULL12491、鏈表中的元素稱為、鏈表中的元素稱為“結(jié)點結(jié)點”，每個結(jié)點包括，每個結(jié)點包括數(shù)據(jù)域數(shù)據(jù)域和和指針域指針域；2、單向鏈表通常由一個、單向鏈表通常

12、由一個頭指針頭指針（head)，用于指向鏈表，用于指向鏈表第一個第一個結(jié)點結(jié)點；3、單向鏈表有一個、單向鏈表有一個尾結(jié)點尾結(jié)點，該結(jié)點的指針部分為，該結(jié)點的指針部分為NULL 。尾結(jié)點尾結(jié)點頭指針頭指針第一個結(jié)點第一個結(jié)點鏈表的基本操作鏈表的基本操作（1 1）創(chuàng)建鏈表創(chuàng)建鏈表: : 從無到有地建立起一個鏈表，即往空鏈表中依次插入若干結(jié)點從無到有地建立起一個鏈表，即往空鏈表中依次插入若干結(jié)點（2 2）檢索鏈表檢索鏈表: : 按給定的檢索條件，查找某個結(jié)點。按給定的檢索條件，查找某個結(jié)點。（3 3）插入操作插入操作: : 在結(jié)點在結(jié)點ki-1ki-1與與kiki之間插入一個新的結(jié)點之間插入一個新的

13、結(jié)點kk，使鏈表的節(jié)點數(shù)增，使鏈表的節(jié)點數(shù)增1 1，（4 4）刪除操作刪除操作: : 刪除結(jié)點刪除結(jié)點kiki，使鏈表的節(jié)點數(shù)減，使鏈表的節(jié)點數(shù)減1 1， (5)(5)打印輸出打印輸出1) 1) 創(chuàng)建鏈表創(chuàng)建鏈表1)1)定義定義三個三個指針變量：頭指針（指針變量：頭指針（headhead）、指向尾結(jié)）、指向尾結(jié)點的指針（點的指針（p2p2）、指向新開辟結(jié)點的指針（）、指向新開辟結(jié)點的指針（p1p1）2)2)結(jié)束輸入結(jié)點的結(jié)束輸入結(jié)點的兩個兩個方式：方式： 1 1）創(chuàng)建的結(jié)點數(shù)已知）創(chuàng)建的結(jié)點數(shù)已知 2 2）創(chuàng)建的節(jié)點數(shù)事先未知，但通過）創(chuàng)建的節(jié)點數(shù)事先未知，但通過 輸入一個不存在的數(shù)作為結(jié)束狀

14、態(tài)。輸入一個不存在的數(shù)作為結(jié)束狀態(tài)。3)3)模塊函數(shù)要返回指向結(jié)點的指針模塊函數(shù)要返回指向結(jié)點的指針 struct nodestruct node* * createlist(); createlist();x1,y1x1,y11249x2,y2x2,y21356x4,y4x4,y41021x3,y3x3,y314751356147510210NULL12492)2)打印輸出鏈表打印輸出鏈表模塊函數(shù)中的形參是指向結(jié)點的指針，無需返回值模塊函數(shù)中的形參是指向結(jié)點的指針，無需返回值void void outputlist outputlist（struct nodestruct node* * )

15、; );void outputlist(struct node *p)while(p!=NULL)printf(%d,%d)n,p-x,p-y);p=p-next;3)3)檢索鏈表檢索鏈表模塊函數(shù)中的形參是指向結(jié)點的指針。模塊函數(shù)中的形參是指向結(jié)點的指針。void retrievevoid retrieve（struct nodestruct node* *,int x,int y );,int x,int y );void retrieve (struct node *p,int x,int y) while(p) if(p-x=x&p-y=y) printf(FOUND); ret

16、urn; p=p-next; printf(NO FOUND);4) 4) 對鏈表的插入操作對鏈表的插入操作插入結(jié)點：插入結(jié)點：通常是在插入一個新的結(jié)點后，仍然保持原通常是在插入一個新的結(jié)點后，仍然保持原有順序。有順序。實現(xiàn)關(guān)鍵：實現(xiàn)關(guān)鍵： 尋找插入位置尋找插入位置插入位置共分四種情況插入位置共分四種情況（假設(shè)原鏈表從小到大為例）：（假設(shè)原鏈表從小到大為例）：1 1、要插入的鏈表是個空鏈表、要插入的鏈表是個空鏈表2 2、要插入的結(jié)點最小、要插入的結(jié)點最小3 3、要插入的結(jié)點最大、要插入的結(jié)點最大4 4、要插入的結(jié)在中間、要插入的結(jié)在中間5 5head6 610101515nullnull121

17、2500050008 840004000 如圖所示的鏈表；現(xiàn)在要插入一個結(jié)點，該結(jié)點中如圖所示的鏈表；現(xiàn)在要插入一個結(jié)點，該結(jié)點中 的數(shù)為的數(shù)為1010演示演示5 5200020006 63000300010002000300040005000100080004000 待插入結(jié)點待插入結(jié)點p0p0實際上是第一個結(jié)點。這時必然有實際上是第一個結(jié)點。這時必然有head=nullhead=null。只要讓頭指針指向。只要讓頭指針指向 p0p0 就可以了。就可以了。6nullheadp0實現(xiàn)語句：實現(xiàn)語句：head = p0;p0-next = null;1 1、要插入的鏈表是個空鏈表、要插入的鏈表是

18、個空鏈表 鏈表已建成，待插入結(jié)點鏈表已建成，待插入結(jié)點 p0 p0 的數(shù)據(jù)要比頭結(jié)的數(shù)據(jù)要比頭結(jié)點的數(shù)據(jù)還要小，點的數(shù)據(jù)還要小，(p0-num )num)(p0-num )num)2 2、要插入的結(jié)點最小、要插入的結(jié)點最小6head8512nullheadp0語句為語句為p0-next=head;p0-next=head;head=p0;head=p0; 鏈表已建成，待插入結(jié)點鏈表已建成，待插入結(jié)點 p0 p0 的數(shù)據(jù)要比尾結(jié)的數(shù)據(jù)要比尾結(jié)點的數(shù)據(jù)還要大，點的數(shù)據(jù)還要大，3 3、要插入的結(jié)點最大、要插入的結(jié)點最大6head81812nullp0p1-next=p0;P0-next=NULL;語

19、句為語句為nullp1 鏈表已建成，待插入結(jié)點鏈表已建成，待插入結(jié)點 p0 p0 的數(shù)據(jù)大小位于的數(shù)據(jù)大小位于已有鏈表中的中間，已有鏈表中的中間， 假設(shè)假設(shè)p0 p0 的數(shù)據(jù)比的數(shù)據(jù)比p2p2指向的數(shù)據(jù)大，比指向的數(shù)據(jù)大，比p1p1指向指向的數(shù)據(jù)小，即的數(shù)據(jù)小，即p0p0插入在插入在p2p2和和p1p1之間。之間。 問題是：如何找到問題是：如何找到p1p1和和p2?p2?4 4、要插入的結(jié)在中間、要插入的結(jié)在中間6head81213p015nullp1p2p2-next = p0;p0-next = p1; 鏈表已建成，待插入結(jié)點鏈表已建成，待插入結(jié)點 p0 p0 的數(shù)據(jù)大小位于的數(shù)據(jù)大小位于

20、已有鏈表中的中間，已有鏈表中的中間， 假設(shè)假設(shè)p0 p0 的數(shù)據(jù)比的數(shù)據(jù)比p2p2指向的數(shù)據(jù)大，比指向的數(shù)據(jù)大，比p1p1指向指向的數(shù)據(jù)小，即的數(shù)據(jù)小，即p0p0插入在插入在p2p2和和p1p1之間。之間。 問題是：如何找到問題是：如何找到p1p1和和p2?p2? - -通過循環(huán)實現(xiàn)通過循環(huán)實現(xiàn)4 4、要插入的結(jié)在中間、要插入的結(jié)在中間6head81213nullp015p1p2p1=p1-next ;P2=p2-next;6head81213nullp015p1p2p1=p1-next ;P2=p2-next;6head81213p015nullp1p2p2-next = p0;p0-nex

21、t = p1; 操操 作作 分分 析析需要幾個臨時指針：需要幾個臨時指針：P0: P0: 指向待插的結(jié)點指向待插的結(jié)點; ;初始化：初始化： p0=(struct nodep0=(struct node* * )malloc(sizeof(struct node); )malloc(sizeof(struct node);P1: P1: 在在P1P1指向的結(jié)點之前插入新結(jié)點；初始化指向的結(jié)點之前插入新結(jié)點；初始化: : p1=head;p1=head;P2: P2: 在在P2P2指向的結(jié)點之后插入新結(jié)點；指向的結(jié)點之后插入新結(jié)點；在表尾插入在表尾插入在頭結(jié)點在頭結(jié)點之前插入之前插入在中間插入在

22、中間插入空表空表p0-numnum5) 5) 對鏈表的刪除操作對鏈表的刪除操作刪除結(jié)點原則：刪除結(jié)點原則： 只是從鏈表中只是從鏈表中分離分離開要刪除的結(jié)點，撤消原來的鏈接開要刪除的結(jié)點，撤消原來的鏈接關(guān)系，并釋放該結(jié)點的空間。關(guān)系，并釋放該結(jié)點的空間。5) 5) 對鏈表的刪除操作對鏈表的刪除操作 A A1249 B B1356 D D1021 C C14751356147510210 NULL1249p1p2p2-next = p1-next A A1249 B B1356 D D1021 C C14751475147510210 NULL1249p1p2free(p1)考慮兩種情況：考慮兩種情況：