C語言課件第17部分動態(tài)存儲空間管理與鏈表

第十七章動態(tài)存儲空間管理與鏈表9/22/20241一、動態(tài)存儲分配及常見函數說明隱式和顯式9/22/202421.引例要處理學生成績，需要用數組存放。但編程時并不知道運行時需要處理多少學生成績，每次處理的成績項數也可能不同。intn;...scanf("%d",&n);doublescores[n];/*不行！*/.../*讀入數據，然后處理*/不能用變量說明scores大?。ū仨氺o態(tài)確定）。9/22/20243教師：林友芳2.問題的本質及解決方案問題的本質程序運行中需要使用存儲，有時程序對存儲的需求量在寫程序時不能確定。可能解決方案1）分析問題，定義適當大小的數組。若分析正確，一般都能處理。但數據很多時程序就不能用。2）定義盡可能大的數組以滿足任何需要。浪費大量存儲資源。如有多個這種數組就更難辦。系統可能無法容納幾個大數組，但實際上它們并不同時需要很大空間。解決的辦法是“動態(tài)存儲分配”。在程序運行中做存儲分配工作。9/22/20244教師：林友芳3.動態(tài)存儲分配動態(tài)存儲分配根據運行中的需要分配存儲，取得存儲塊使用，稱為動態(tài)存儲分配。在運行中根據需要動態(tài)進行。動態(tài)存儲塊具有起始地址，地址可以存儲在指針里，因此可以借助于指針保存存儲空間地址。用指針指向存儲塊，間接使用被指存儲。訪問動態(tài)分配存儲是指針的最重要用途。9/22/20245教師：林友芳4.動態(tài)存儲釋放及存儲堆動態(tài)釋放不用的動態(tài)存儲塊應交還系統，動態(tài)申請的內存空間必須由程序代碼以顯式的方式主動釋放。動態(tài)分配、釋放由動態(tài)存儲管理系統完成，這是程序運行系統的子系統，管理著稱作堆（英文heap）的存儲區(qū)。大部分常規(guī)語言都有這種機制。9/22/20246教師：林友芳5.C語言的動態(tài)存儲管理機制用標準庫函數實現stdlib.hmalloc.h存儲分配函數malloc()，原型：void*malloc(size_tn);/*size_t是某整型*/功能分配一塊不小于n的存儲，返回其地址。無法滿足時返回空指針值。9/22/20247教師：林友芳例intn;double*data;...scanf("%d",&n);data=(double*)malloc(n*sizeof(double));if(data==NULL){..../*分配未完成時的處理*/}..data[i]..*(data+j)../*正常處理*/9/22/20248教師：林友芳malloc說明malloc使用注意事項：的返回值（void*）應通過類型強制轉為特定指針類型后賦給指針變量。分配存儲塊大小應該用sizeof計算動態(tài)分配必須檢查成功與否動態(tài)分配的塊大小也是確定的。越界使用（尤其是越界賦值）是嚴重錯誤，可能導致程序或系統垮臺9/22/20249教師：林友芳6.calloc帶計數和清0的存儲分配函數calloc，原型：void*calloc(size_tn,size_tsize);size是元素大小，n是個數。分配一塊存儲，足夠存n個大小為size的元素，并把元素全部清0；無法分配時返回空指針值。前面的存儲分配問題也可用下面語句實現data=(double*)calloc(n,sizeof(double));主要差別malloc對所分配的區(qū)域不做任何事情，calloc對整個區(qū)域自動清0。9/22/202410教師：林友芳7.空間釋放函數：free為保證動態(tài)存儲的有效使用，動態(tài)分配塊不再用時應釋放。動態(tài)存儲塊的釋放只能通過調用free完成。Memoryleak函數原型voidfree(void*p);功能free釋放p指的存儲塊。注意該塊必須是通過動態(tài)存儲分配得到的，不要對并非指向動態(tài)分配塊的指針用本操作p值為空時什么也不做執(zhí)行free(p)后p值未變，被指塊可能已變。不允許再間接訪問已釋放存儲塊9/22/202411教師：林友芳8.分配調整函數realloc函數原型void*realloc(void*p,size_tn);功能更改已有分配。p指原分配塊，n是新大小要求。返回大小至少為n的存儲塊指針，新塊與原塊一致：新塊小時保存原塊n范圍內數據；新塊大時原數據存在，新增部分不初始化。分配成功后原塊可能改變。無法滿足時返回空指針，原塊不變。常用寫法(防止分配失敗導致原存儲塊丟失)：q=(double*)realloc(p,m*sizeof(double));if(q==NULL){/*未成功，p仍指原塊，特殊處理*/}else{p=q;/*令p指向新塊，正常處理*/...9/22/202412教師：林友芳二、動態(tài)存儲空間管理如果動態(tài)申請了許多同類型緩沖區(qū)，該如何管理？9/22/202413方法1：指針數組（地址數組）設置一段內存空間，例如數組，用來保存存儲空間的起始地址。數組中每個元素用來保存某種類型的存儲空間的地址，等于每個元素都是一個指針變量。int*pnarr[10];//定義一個長度為10的整型指針數組（整型地址數組）char*psz[5];//定義一個長度為5的字符指針數組。0x0012ff7d0x0012ff80…0x0012fe12其中每個元素都用來保存某種類型的存儲空間的地址9/22/202414教師：林友芳例如設一個班最多有50人，但每個班的人數不定，為了表示這50用戶，可以定義如下指針數組structUserAccount*Accounts[50];完成如下功能初始化指針數組將新生成的某個班用戶加入班級用戶集，并存放在空位置上。將某個班指定用戶號的用戶刪除給某個班所有女生發(fā)m元補助將新生成的某個班用戶插入到指定位置i上，i后面的用戶順序往后退。9/22/202415教師：林友芳指針數組結構示例0x0012ff6dNULL0x0012ff800x0012ce000x0012fe12…08120001張帥帥110108…M0.1008120099李美美350108…F500.0008120002趙小飛360108…M20.0008120007羅小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…長度為50空指針，可能曾被刪除后續(xù)元素或空或不空Accounts9/22/202416教師：林友芳功能實現初始化指針數組voidInitAccounts(structUserAccount*Accounts[],intnLen){for(inti=0;i<nLen;i++)

Accounts[i]=NULL;}尋找一個空位置返回，-1表示無空位置intFindEmptyPlace(structUserAccount*Accounts[],intnLen){…}//可以有不同的搜索策略NULLNULL…9/22/202417教師：林友芳功能實現（續(xù)）將新用戶放在空位置上，不成功返回-1，成功返回位置號intAddNewAccountAtAnyEmptyPlace(structUserAccount*Accounts[],intnLen,structUserAccount*pUser){intnPlace; if((nPlace=FindEmptyPlace(Accounts,nLen))==-1)return-1;

Accounts[nPlace]=pUser;//完成放置操作returnnPlace;//返回位置}9/22/202418教師：林友芳功能示例0x0012ff6dNULL0x0012ff800x0012ce000x0012fe12…08120001張帥帥110108…M0.1008120099李美美350108…F500.0008120002趙小飛360108…M20.0008120007羅小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…長度為50Accounts08120100孫悟空110105…M600.100x0012ff300x0012ff30新找到的空位新結點孫悟空報到9/22/202419教師：林友芳功能實現（續(xù)）將指定用戶號的用戶刪除，返回該用戶原來所在位置intDeleteAccountByNumber(structUserAccount*Accounts[],intnLen,char*pszUserNO){inti;for(i=0;i<nLen;i++)//找到指定用戶{if((Accounts[i]!=NULL)&&(strcmp(pszUserNO,Accounts[i]->szUserNO)==0)){

free(Accounts[i]);//釋放空間

Accounts[i]=NULL;//將當前位置置空 returni;}}return-1;}用戶結構體指針數組數組長度用戶號字符串比較函數9/22/202420教師：林友芳刪除功能示例0x0012ff6d0x0012ff300x0012ff800x0012ce000x0012fe12…08120001張帥帥110108…M0.1008120099李美美350108…F500.0008120002趙小飛360108…M20.0008120007羅小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…Accounts08120100孫悟空110105…M600.100x0012ff30NULL把孫悟空位置找到把孫悟空開除:DeleteAccountByNumber(Accounts,50,“08120100”)釋放存儲空間9/22/202421教師：林友芳功能實現（續(xù)）給指定性別的群體充值，返回充值人數intChargeByGender(structUserAccount*Accounts[],intnLen,charcGender,doubledAmount){intnCounter=0;//計數器for(inti=0;i<nLen;i++)//遍歷所有的用戶{

if((NULL!=Accounts[i])&&(Accounts[i]->cGender==cGender)){Accounts[i]->dBalance+=dAmount;nCounter++;}}returnnCounter;}ChargeByGender(Accounts,50,‘F’,10.0);//婦女節(jié)發(fā)補助9/22/202422教師：林友芳方法2：鏈接結構采用鏈式數據結構一環(huán)扣一扣，通過一個元素保存的其它元素的地址找到其它元素。通過鏈接結構實現動態(tài)數據增加元素：在鐵鏈的某個位置加一鐵環(huán)刪除元素：去掉鐵鏈的某一鐵環(huán)問題鐵鏈中的每一鐵環(huán)是一樣的嗎？普通的鐵鏈是單向的還是雙向的？有沒有一些特殊的鐵鏈，比如有多個分叉的？鐵鏈可以跟銅鏈拴一起嗎？鐵鏈的頭部可以拴在柱子上嗎？9/22/202423教師：林友芳鏈接結構實現原理鏈接結構中的元素需要保存的信息與結點本身有關的信息找到其它元素所需要的信息這些信息可以組織成結構問題：如何找到其它元素？保存其它元素在內存中的地址在結構中設置指針分量，用來保存其它元素的地址的分量指針分量問題：指針的類型？需要指向元素的結構類型的指針類型如果需要指向的元素與本元素的類型相同的話，則需要定義自引用的結構類型。9/22/202424教師：林友芳鏈接結構一個結構元素可以通過指針引用同類或不同類的結構元素，多個結構元素通過指針建立聯系。指向結構的指針稱為鏈接，形成的復雜數據結構稱為鏈接結構最簡單的鏈接結構線性鏈接形成的表，鏈接表。每個自引用結構有一個鏈接指針分量。9/22/202425教師：林友芳最簡單的鏈接結構：單向鏈表單向鏈接表就像鏈條，自引用結構是鏈表中的一個鏈節(jié)，稱為鏈表結點，結點間由指針連接形成整個結構。所有結點（結構）由動態(tài)分配創(chuàng)建。從指向表首結點的指針出發(fā)，沿鏈接可順序訪問表中各結點。該指針代表整個表。通常把最后結點的指針置空表示結束。9/22/202426教師：林友芳更復雜的引用鏈接結構9/22/202427教師：林友芳單向鏈表結構示例structUserAccount{charUserNO[15];charName[20];charID[19];charGender;doubleBalance;

structUserAccount

*pNextUser;};用來保存下一個結點的地址此處改成如下形式是否可行，為什么？structUserAccount

NextUser;9/22/202428教師：林友芳普通單向鏈表示意圖08120001張帥帥110108…M0.1008120002趙小飛360108…M20.0008120007羅小花410108…F88.2008120099李美美350108…F500.00NULL…HeadTail9/22/202429教師：林友芳三、鏈表9/22/2024301.需求設有某系統的用戶信息結構體，其中用戶ID長度為10用戶姓名長度不超過10需要處理的用戶數據不定，假設某程序需要以鏈表方式處理用戶的數據9/22/202431教師：林友芳普通單向鏈表示意DataDataDataDataNULL…HeadTail9/22/202432教師：林友芳鏈表結點結構聲明方法1:structUserInfoNode{ charszID[11]; //ID charszName[11]; //姓名structUserInfoNode*pNextUser; //下個用戶指針};方法2：typedefstructUserInfoNodeUSERNODE,*USERPOINTER;structUserInfoNode{ charszID[11]; //ID charszName[11]; //姓名USERPOINTER*pNextUser; //下個用戶指針};9/22/202433教師：林友芳更好的方法：基本信息單獨說明//用戶基本信息結構聲明structUserInfo{ charszID[11]; //ID，11個字符 charszName[11]; //姓名，11個字符};或typedefstruct{ charszID[11]; //ID，11個字符 charszName[11]; //姓名，11個字符}USERINFO;9/22/202434教師：林友芳更常見合理的聲明方法方法3：structUserLinkNode{structUserInfoData; //數據structUserLinkNode*pNextUser;//};structUserInfoUserInfoArr[100];或typedefstruct{USERINFOData; //數據結點structUserLinkNode*pNextUser;//}USERLINKNODE;9/22/202435教師：林友芳增加一個鏈表描述信息結點NumberHeadTailDataDataDataDataNULL…LinkInfoNode關于鏈表整體描述信息結點9/22/202436教師：林友芳描述結點結構說明示例structUserLink{ structUserLinkNode*pHead;//頭指針 structUserLinkNode*pTail;//尾指針 intnNumber; //鏈表中的結點計數};或typedefstruct{ USERLINKNODE*pHead;//頭指針 USERLINKNODE*pTail;//尾指針 intnNumber; //鏈表中的結點計數}USERLINK;9/22/202437教師：林友芳可以增加一個不用的頭結點NumberHeadTailDataDataDataNULL…LinkInfoNode目的在于寫程序方便，簡化一些鏈表操作，數據結構課程中會有進一步的闡述不用的頭結點9/22/202438教師：林友芳關于后面的操作的假定鏈表為單向鏈表沒有設置空的頭結點設置有信息描述結點，記錄如下信息頭結點尾結點鏈表中結點個數9/22/202439教師：林友芳在鏈表中增加一個節(jié)點有幾種增加方式將新結點作為最后一個元素增加到鏈表的尾部，將新結點作為第一個元素增加到鏈表的頭部將新結點按照某種次序要求插入到指定位置9/22/202440教師：林友芳加到尾部如果鏈表為空，則需要做一些初始化工作，將新的結點當成頭結點和尾結點如果鏈表不為空，則將該結點作為尾結點的下一個結點，修改尾結點指針。如果沒有記錄尾結點指針，則需要從頭結點開始找到最后一個結點。pHeadpTailDataDataNULL……pNewNode

NULL

9/22/202441教師：林友芳示例代碼，加到尾部intAddUserToTail(structUserLink*pUsers,//鏈表描述信息指針 structUserLinkNode*pNewUser//新結點指針){ if(pUsers==NULL||pNewUser==NULL)return-1; if(pUsers->nNumber<=0){//如果還沒有元素 pUsers->pHead=pNewUser; pUsers->pTail=pUsers->pHead;//頭尾指針指向同一個結點 } else{//把結點信息附到鏈表尾部 pUsers->pTail->pNext=pNewUser;//加到尾到 pUsers->pTail=pNewUser; //修改尾結點指針 } pUsers->pTail->pNext=NULL;//最后一個結點的后繼置空 pUsers->nNumber++;//計數加1 return0;}9/22/202442教師：林友芳加到頭部如果鏈表為空，則需要做一些初始化工作，將新的結點當成頭結點和尾結點如果鏈表不為空，需要將新結點的下一個結點置為原來的頭結點，并把新結點作為頭結點pHeadpTailDataDataNULL……NULLpNewNode

9/22/202443教師：林友芳示例代碼，加到頭部intAddUserToHead(structUserLink*pUsers,//鏈表描述信息指針 structUserLinkNode*pNewUser//新結點指針){ if(pUsers==NULL||pNewUser==NULL)return-1; if(pUsers->nNumber<=0){//如果還沒有元素 pUsers->pHead=pNewUser; pUsers->pTail=pUsers->pHead;//頭尾指針指向同一個結點 pNewUser->pNext=NULL; } else{//把結點信息附到鏈表頭部 pUsers->pNewUser->pNext=pUsers->pHead;//加到頭部 pUsers->pHead=pNewUser; //修改頭結點指針 } pUsers->nNumber++;//計數加1 return0;}9/22/202444教師：林友芳在鏈表中插入一個新結點基本操作q->pNext=p->pNext;p->pNext=q;其它用于保持鏈表指針完整性的操作。^^功能示意ppqqrr插入前插入后9/22/202445教師：林友芳去除鏈表中的某個結點基本操作p->pNext=q->pNext;外圍附加操作，用于保證鏈