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

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

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

3、班級(jí)（求任意一個(gè)班級(jí)（人數(shù)不定人數(shù)不定）中所有學(xué)生的成績(jī)）中所有學(xué)生的成績(jī)平均分。平均分。方法：求最大班級(jí)人數(shù)（假設(shè)方法：求最大班級(jí)人數(shù)（假設(shè)100），），float a100 解決辦法：能不能根據(jù)我輸入的班級(jí)人數(shù)，來自動(dòng)的確解決辦法：能不能根據(jù)我輸入的班級(jí)人數(shù)，來自動(dòng)的確定數(shù)組長(zhǎng)度。定數(shù)組長(zhǎng)度。 缺點(diǎn)：浪費(fèi)內(nèi)存空間缺點(diǎn)：浪費(fèi)內(nèi)存空間靜態(tài)分配靜態(tài)分配動(dòng)態(tài)分配動(dòng)態(tài)分配動(dòng)態(tài)存儲(chǔ)分配函數(shù)動(dòng)態(tài)存儲(chǔ)分配函數(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);使用時(shí)包含使用時(shí)包含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. 求任意一個(gè)班級(jí)（求任意一個(gè)班級(jí)（人數(shù)不定人數(shù)不定）中所有學(xué)生的成績(jī)平均分。中所有學(xué)生的成績(jī)平均分。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所指向的空間什么時(shí)候被回收？所指向的空間什么時(shí)候被回收？ printf(String is %sn,str);return str 動(dòng)態(tài)內(nèi)存分配函數(shù)是在整個(gè)程序運(yùn)行完畢動(dòng)態(tài)內(nèi)存分配函數(shù)是在整個(gè)程序運(yùn)行完畢時(shí)，才回收內(nèi)存；但是函數(shù)的局部變量是時(shí)，才回收內(nèi)存；但是函數(shù)的局部變量是在本函數(shù)執(zhí)行完畢時(shí)就回收。使用了在本函數(shù)執(zhí)行完畢時(shí)就回收。使用了free函數(shù)，就可以在執(zhí)行到該語句時(shí)，就能夠

8、函數(shù)，就可以在執(zhí)行到該語句時(shí)，就能夠回收該內(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)錯(cuò)誤！出現(xiàn)錯(cuò)誤！Name所指向的存儲(chǔ)空間不可用所指向的存儲(chǔ)空間不可用 printf(%s,(*p).name); p-name=“zh

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

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

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

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

14、態(tài)。輸入一個(gè)不存在的數(shù)作為結(jié)束狀態(tài)。3)3)模塊函數(shù)要返回指向結(jié)點(diǎn)的指針模塊函數(shù)要返回指向結(jié)點(diǎn)的指針 struct nodestruct node* * createlist(); createlist();x1,y1x1,y11249x2,y2x2,y21356x4,y4x4,y41021x3,y3x3,y314751356147510210NULL12492)2)打印輸出鏈表打印輸出鏈表模塊函數(shù)中的形參是指向結(jié)點(diǎn)的指針，無需返回值模塊函數(shù)中的形參是指向結(jié)點(diǎn)的指針，無需返回值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é)點(diǎn)的指針。模塊函數(shù)中的形參是指向結(jié)點(diǎn)的指針。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) 對(duì)鏈表的插入操作對(duì)鏈表的插入操作插入結(jié)點(diǎn)：插入結(jié)點(diǎn)：通常是在插入一個(gè)新的結(jié)點(diǎn)后，仍然保持原通常是在插入一個(gè)新的結(jié)點(diǎn)后，仍然保持原有順序。有順序。實(shí)現(xiàn)關(guān)鍵：實(shí)現(xiàn)關(guān)鍵： 尋找插入位置尋找插入位置插入位置共分四種情況插入位置共分四種情況（假設(shè)原鏈表從小到大為例）：（假設(shè)原鏈表從小到大為例）：1 1、要插入的鏈表是個(gè)空鏈表、要插入的鏈表是個(gè)空鏈表2 2、要插入的結(jié)點(diǎn)最小、要插入的結(jié)點(diǎn)最小3 3、要插入的結(jié)點(diǎn)最大、要插入的結(jié)點(diǎn)最大4 4、要插入的結(jié)在中間、要插入的結(jié)在中間5 5head6 610101515nullnull121

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

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

19、句為語句為nullp1 鏈表已建成，待插入結(jié)點(diǎn)鏈表已建成，待插入結(jié)點(diǎn) 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é)點(diǎn)鏈表已建成，待插入結(jié)點(diǎn) 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)實(shí)現(xiàn)通過循環(huán)實(shí)現(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; 操操 作作 分分 析析需要幾個(gè)臨時(shí)指針：需要幾個(gè)臨時(shí)指針：P0: P0: 指向待插的結(jié)點(diǎn)指向待插的結(jié)點(diǎn); ;初始化：初始化： p0=(struct nodep0=(struct node* * )malloc(sizeof(struct node); )malloc(sizeof(struct node);P1: P1: 在在P1P1指向的結(jié)點(diǎn)之前插入新結(jié)點(diǎn)；初始化指向的結(jié)點(diǎn)之前插入新結(jié)點(diǎn)；初始化: : p1=head;p1=head;P2: P2: 在在P2P2指向的結(jié)點(diǎn)之后插入新結(jié)點(diǎn)；指向的結(jié)點(diǎn)之后插入新結(jié)點(diǎn)；在表尾插入在表尾插入在頭結(jié)點(diǎn)在頭結(jié)點(diǎn)之前插入之前插入在中間插入在

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