第十章

動態數組與鏈表內存分配方式有三種：（1）從靜態存儲區域分配。（2）在棧上創建。

（3）從堆上分配，亦稱動態內存分配。

內存在程序編譯的時候就已經分配好，這塊內存在程序的整個運行期間都存在。例如全局變量，static變量。

在執行函數時，函數內局部變量的存儲單元都可以在棧上創建，函數執行結束時這些存儲單元自動被釋放。效率很高，但是分配的內存容量有限。

用malloc等函數申請任意多少的內存，程序員自己負責在何時用free函數釋放內存。動態內存的生存期從malloc等函數執行開始，到free函數被調用結束，若沒有free函數，則到整個程序運行結束為止。使用非常靈活，但問題也最多。引入問題1.求某班級（30人）中所有學生的成績平均分。floata[30]2.求任意一個班級（人數不定）中所有學生的成績平均分。方法：求最大班級人數（假設100），floata[100]解決辦法：能不能根據我輸入的班級人數，來自動的確定數組長度。缺點：浪費內存空間靜態分配動態分配動態存儲分配函數malloc函數(memoryallocation)

void*malloc(intn);calloc函數(countallocation)void*calloc(intcount,intn);free函數

voidfree(void*ptr);realloc函數(reallocation)

void*realloc(void*p,intn);使用時包含malloc.h或stdlib.hint*p,n;Scanf(“%d”,&n);p=malloc(n);

(int*)inta[10];

40int*p,count,n;Scanf(“%d%d”,&count,&n);p=calloc(count,n);(int*)104int*p,n;Scanf(“%d”,&n);p=malloc(n);p=realloc(p,40);(int*)10(int*)free(p)#include<stdio.h>#include<malloc.h>voidmain(){float*p,s=0;intnum,i;scanf("%d",&num);p=(float*)malloc(num);for(i=0;i<num;i++)scanf("%f",p+i);

for(i=0;i<num;i++)printf("%6.2f",*(p+i));

for(i=0;i<num;i++)s=s+(*(p+i));printf("\n%f",s/num);}2.求任意一個班級（人數不定）中所有學生的成績平均分。free函數voidfree(void*ptr);#include<stdlib.h>#include<string.h>#include<stdio.h>voidmain(){char*str;str=(char*)malloc(10*sizeof(char));strcpy(str,"china");printf("Stringis%s\n",str);free(str);printf("Stringis%s\n",str);}#include<stdlib.h>#include<string.h>#include<stdio.h>voidmain(){

char*str;char*m(); str=m();printf("Stringis%s\n",str);}char*m(){char*str;str=(char*)malloc(10*sizeof(char));strcpy(str,"china");printf("Stringis%s\n",str);//free(str);//考察str所指向的空間什么時候被回收？printf("Stringis%s\n",str);returnstr}動態內存分配函數是在整個程序運行完畢時，才回收內存；但是函數的局部變量是在本函數執行完畢時就回收。使用了free函數，就可以在執行到該語句時，就能夠回收該內存空間。realloc函數void*realloc(void*p,intn);#include<stdio.h>#include<string.h>#include<malloc.h>main(){char*p;p=(char*)malloc(100);if(p)printf("MemoryAllocatedat:%x",p);elseprintf("NotEnoughMemory!\n");strcpy(p,"helloworld");p=(char*)realloc(p,600);if(p)printf("MemoryReallocatedat:%x",p);elseprintf("NotEnoughMemory!\n");free(p);}#include<stdio.h>#include<string.h>#include<malloc.h>main(){ structstu {intnum; char*name; charsex; floatscore[10]; structstu*q; }*p; p=(structstu*)malloc(sizeof(structstu)); scanf(“%s”,p->name);%出現錯誤！！！Name所指向的存儲空間不可用printf("%s",(*p).name);} p->name=“zhangsan”;“zhangsan”在常量存儲區由編譯器自動開辟空間例：跳馬。依下圖將每一步跳馬之后的位置(x,y)放到一個“結點”里，再用“鏈子穿起來”，形成一條鏈，相鄰兩結點間用一個指針將兩者連到一起。動態鏈表依上圖有7個結點x1y1每個節點既有數據(xi和yi)又有指針（下個結點的地址），用什么樣的數據類型表示每個節點x2y2x7y7x6y6structnode{intx;inty;};構造節點的數據類型structnode*next鏈表的幾個基本概念x1,y11249x2,y21356x4,y41021x3,y314751356147510210NULL12491、鏈表中的元素稱為“結點”，每個結點包括數據域和指針域；2、單向鏈表通常由一個頭指針（head)，用于指向鏈表第一個結點；3、單向鏈表有一個尾結點，該結點的指針部分為NULL。尾結點頭指針第一個結點

鏈表的基本操作（1）創建鏈表:

從無到有地建立起一個鏈表，即往空鏈表中依次插入若干結點（2）檢索鏈表:

按給定的檢索條件，查找某個結點。（3）插入操作:

在結點ki-1與ki之間插入一個新的結點k’，使鏈表的節點數增1，（4）刪除操作:刪除結點ki，使鏈表的節點數減1，(5)打印輸出1)創建鏈表1)定義三個指針變量：頭指針（head）、指向尾結點的指針（p2）、指向新開辟結點的指針（p1）2)結束輸入結點的兩個方式：1）創建的結點數已知2）創建的節點數事先未知，但通過輸入一個不存在的數作為結束狀態。3)模塊函數要返回指向結點的指針

structnode*createlist();x1,y11249x2,y21356x4,y41021x3,y314751356147510210NULL12492)打印輸出鏈表模塊函數中的形參是指向結點的指針，無需返回值voidoutputlist（structnode*);voidoutputlist(structnode*p){while(p!=NULL){printf("(%d,%d)\n",p->x,p->y);p=p->next;}}3)檢索鏈表模塊函數中的形參是指向結點的指針。voidretrieve（structnode*,intx,inty);voidretrieve(structnode*p,intx,inty){while(p){if(p->x==x&&p->y==y){printf("FOUND");return;}p=p->next;}printf("NOFOUND");}4)對鏈表的插入操作插入結點：通常是在插入一個新的結點后，仍然保持原有順序。實現關鍵：尋找插入位置插入位置共分四種情況（假設原鏈表從小到大為例）：1、要插入的鏈表是個空鏈表2、要插入的結點最小3、要插入的結點最大4、要插入的結在中間5head61015null12500084000如圖所示的鏈表；現在要插入一個結點，該結點中的數為10演示520006300010002000300040005000100080004000待插入結點p0實際上是第一個結點。這時必然有head==null。只要讓頭指針指向p0就可以了。6nullheadp0實現語句：head=p0;p0->next=null;1、要插入的鏈表是個空鏈表鏈表已建成，待插入結點p0的數據要比頭結點的數據還要小， (p0->num)<(head->num)2、要插入的結點最小6head8512nullheadp0語句為p0->next=head;head=p0;鏈表已建成，待插入結點p0的數據要比尾結點的數據還要大，3、要插入的結點最大6head81812nullp0p1->next=p0;P0->next=NULL;語句為nullp1鏈表已建成，待插入結點p0的數據大小位于已有鏈表中的中間，假設p0的數據比p2指向的數據大，比p1指向的數據小，即p0插入在p2和p1之間。

問題是：如何找到p1和p2?4、要插入的結在中間6head81213p015nullp1p2p2->next=p0;p0->next=p1;鏈表已建成，待插入結點p0的數據大小位于已有鏈表中的中間，假設p0的數據比p2指向的數據大，比p1指向的數據小，即p0插入在p2和p1之間。

問題是：如何找到p1和p2?---通過循環實現4、要插入的結在中間6head81213nullp015p1p2p1=p1->next;P2=p2->next;6head81213nullp015p1p2p1=p1->next;P2=p2->next;6head81213p015nullp1p2p2->next=p0;p0->next=p1;操作分析需要幾個臨時指針：P0:指向待插的結點;初始化：p0=(structnode*)malloc(sizeof(structnode));P1:在P1指向的結點之前插入新結點；初始化:p1=head;P2:在P2指向的結點之后插入新結點；在表尾插入在頭結點之前插入在中間插入空表p0->num<=p1->num5)對鏈表的刪除操作刪除結點原則：只是從鏈表中分離開要刪除的結點，撤消原來的鏈接關系，并釋放該結點的空間。5)對鏈表的刪除操作A1249B1356D1021C14751356147510210NULL1249p1p2p2->next=p1->nextA1249B1356D1021C14751475147510210NULL1249p1p2free(p1)考慮兩種情況：1、要刪的結點是頭指針所指的結點（第一個結點）；2、刪除的不是第一個結點