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

第十章

動態(tài)數(shù)組與鏈表內(nèi)存分配方式有三種：（1）從靜態(tài)存儲區(qū)域分配。（2）在棧上創(chuàng)建。

（3）從堆上分配，亦稱動態(tài)內(nèi)存分配。

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

在執(zhí)行函數(shù)時，函數(shù)內(nèi)局部變量的存儲單元都可以在棧上創(chuàng)建，函數(shù)執(zhí)行結(jié)束時這些存儲單元自動被釋放。效率很高，但是分配的內(nèi)存容量有限。

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

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

voidfree(void*ptr);realloc函數(shù)(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.求任意一個班級（人數(shù)不定）中所有學(xué)生的成績平均分。free函數(shù)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}動態(tài)內(nèi)存分配函數(shù)是在整個程序運行完畢時，才回收內(nèi)存；但是函數(shù)的局部變量是在本函數(shù)執(zhí)行完畢時就回收。使用了free函數(shù)，就可以在執(zhí)行到該語句時，就能夠回收該內(nèi)存空間。realloc函數(shù)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);%出現(xiàn)錯誤?。?！Name所指向的存儲空間不可用printf("%s",(*p).name);} p->name=“zhangsan”;“zhangsan”在常量存儲區(qū)由編譯器自動開辟空間例：跳馬。依下圖將每一步跳馬之后的位置(x,y)放到一個“結(jié)點”里，再用“鏈子穿起來”，形成一條鏈，相鄰兩結(jié)點間用一個指針將兩者連到一起。動態(tài)鏈表依上圖有7個結(jié)點x1y1每個節(jié)點既有數(shù)據(jù)(xi和yi)又有指針（下個結(jié)點的地址），用什么樣的數(shù)據(jù)類型表示每個節(jié)點x2y2x7y7x6y6structnode{intx;inty;};構(gòu)造節(jié)點的數(shù)據(jù)類型structnode*next鏈表的幾個基本概念x1,y11249x2,y21356x4,y41021x3,y314751356147510210NULL12491、鏈表中的元素稱為“結(jié)點”，每個結(jié)點包括數(shù)據(jù)域和指針域；2、單向鏈表通常由一個頭指針（head)，用于指向鏈表第一個結(jié)點；3、單向鏈表有一個尾結(jié)點，該結(jié)點的指針部分為NULL。尾結(jié)點頭指針第一個結(jié)點

鏈表的基本操作（1）創(chuàng)建鏈表:

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

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

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

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

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

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