動(dòng)態(tài)存儲(chǔ)空間管理與鏈表

2023/1/311動(dòng)態(tài)存儲(chǔ)空間管理與鏈表2023/1/312一、動(dòng)態(tài)存儲(chǔ)分配及常見函數(shù)說(shuō)明隱式和顯式教師：林友芳32023/1/311.引例要處理學(xué)生成績(jī)，需要用數(shù)組存放。但編程時(shí)并不知道運(yùn)行時(shí)需要處理多少學(xué)生成績(jī)，每次處理的成績(jī)項(xiàng)數(shù)也可能不同。intn;...scanf("%d",&n);doublescores[n];/*不行！*/.../*讀入數(shù)據(jù)，然后處理*/不能用變量說(shuō)明scores大小（必須靜態(tài)確定）。教師：林友芳42023/1/312.問(wèn)題的本質(zhì)及解決方案問(wèn)題的本質(zhì)程序運(yùn)行中需要使用存儲(chǔ)，有時(shí)程序?qū)Υ鎯?chǔ)的需求量在寫程序時(shí)不能確定?？赡芙鉀Q方案1）分析問(wèn)題，定義適當(dāng)大小的數(shù)組。若分析正確，一般都能處理。但數(shù)據(jù)很多時(shí)程序就不能用。2）定義盡可能大的數(shù)組以滿足任何需要。浪費(fèi)大量存儲(chǔ)資源。如有多個(gè)這種數(shù)組就更難辦。系統(tǒng)可能無(wú)法容納幾個(gè)大數(shù)組，但實(shí)際上它們并不同時(shí)需要很大空間。解決的辦法是“動(dòng)態(tài)存儲(chǔ)分配”。在程序運(yùn)行中做存儲(chǔ)分配工作。教師：林友芳52023/1/313.動(dòng)態(tài)存儲(chǔ)分配動(dòng)態(tài)存儲(chǔ)分配根據(jù)運(yùn)行中的需要分配存儲(chǔ)，取得存儲(chǔ)塊使用，稱為動(dòng)態(tài)存儲(chǔ)分配。在運(yùn)行中根據(jù)需要?jiǎng)討B(tài)進(jìn)行。動(dòng)態(tài)存儲(chǔ)塊具有起始地址，地址可以存儲(chǔ)在指針里，因此可以借助于指針保存存儲(chǔ)空間地址。用指針指向存儲(chǔ)塊，間接使用被指存儲(chǔ)。訪問(wèn)動(dòng)態(tài)分配存儲(chǔ)是指針的最重要用途。教師：林友芳62023/1/314.動(dòng)態(tài)存儲(chǔ)釋放及存儲(chǔ)堆動(dòng)態(tài)釋放不用的動(dòng)態(tài)存儲(chǔ)塊應(yīng)交還系統(tǒng)，動(dòng)態(tài)申請(qǐng)的內(nèi)存空間必須由程序代碼以顯式的方式主動(dòng)釋放。動(dòng)態(tài)分配、釋放由動(dòng)態(tài)存儲(chǔ)管理系統(tǒng)完成，這是程序運(yùn)行系統(tǒng)的子系統(tǒng)，管理著稱作堆（英文heap）的存儲(chǔ)區(qū)。大部分常規(guī)語(yǔ)言都有這種機(jī)制。教師：林友芳72023/1/315.C語(yǔ)言的動(dòng)態(tài)存儲(chǔ)管理機(jī)制用標(biāo)準(zhǔn)庫(kù)函數(shù)實(shí)現(xiàn)stdlib.hmalloc.h存儲(chǔ)分配函數(shù)malloc()，原型：void*malloc(size_tn);/*size_t是某整型*/功能分配一塊不小于n的存儲(chǔ)，返回其地址。無(wú)法滿足時(shí)返回空指針值。82023/1/31例intn;double*data;...scanf("%d",&n);data=(double*)malloc(n*sizeof(double));if(data==NULL){..../*分配未完成時(shí)的處理*/}..data[i]..*(data+j)../*正常處理*/教師：林友芳92023/1/31malloc說(shuō)明malloc使用注意事項(xiàng)：的返回值（void*）應(yīng)通過(guò)類型強(qiáng)制轉(zhuǎn)為特定指針類型后賦給指針變量。分配存儲(chǔ)塊大小應(yīng)該用sizeof計(jì)算動(dòng)態(tài)分配必須檢查成功與否動(dòng)態(tài)分配的塊大小也是確定的。越界使用（尤其是越界賦值）是嚴(yán)重錯(cuò)誤，可能導(dǎo)致程序或系統(tǒng)垮臺(tái)教師：林友芳102023/1/316.calloc帶計(jì)數(shù)和清0的存儲(chǔ)分配函數(shù)calloc，原型：void*calloc(size_tn,size_tsize);size是元素大小，n是個(gè)數(shù)。分配一塊存儲(chǔ)，足夠存n個(gè)大小為size的元素，并把元素全部清0；無(wú)法分配時(shí)返回空指針值。前面的存儲(chǔ)分配問(wèn)題也可用下面語(yǔ)句實(shí)現(xiàn)data=(double*)calloc(n,sizeof(double));主要差別malloc對(duì)所分配的區(qū)域不做任何事情，calloc對(duì)整個(gè)區(qū)域自動(dòng)清0。教師：林友芳112023/1/317.空間釋放函數(shù)：free為保證動(dòng)態(tài)存儲(chǔ)的有效使用，動(dòng)態(tài)分配塊不再用時(shí)應(yīng)釋放。動(dòng)態(tài)存儲(chǔ)塊的釋放只能通過(guò)調(diào)用free完成。Memoryleak函數(shù)原型voidfree(void*p);功能free釋放p指的存儲(chǔ)塊。注意該塊必須是通過(guò)動(dòng)態(tài)存儲(chǔ)分配得到的，不要對(duì)并非指向動(dòng)態(tài)分配塊的指針用本操作p值為空時(shí)什么也不做執(zhí)行free(p)后p值未變，被指塊可能已變。不允許再間接訪問(wèn)已釋放存儲(chǔ)塊教師：林友芳122023/1/318.分配調(diào)整函數(shù)realloc函數(shù)原型void*realloc(void*p,size_tn);功能更改已有分配。p指原分配塊，n是新大小要求。返回大小至少為n的存儲(chǔ)塊指針，新塊與原塊一致：新塊小時(shí)保存原塊n范圍內(nèi)數(shù)據(jù)；新塊大時(shí)原數(shù)據(jù)存在，新增部分不初始化。分配成功后原塊可能改變。無(wú)法滿足時(shí)返回空指針，原塊不變。常用寫法(防止分配失敗導(dǎo)致原存儲(chǔ)塊丟失)：q=(double*)realloc(p,m*sizeof(double));if(q==NULL){/*未成功，p仍指原塊，特殊處理*/}else{p=q;/*令p指向新塊，正常處理*/...2023/1/3113二、動(dòng)態(tài)存儲(chǔ)空間管理如果動(dòng)態(tài)申請(qǐng)了許多同類型緩沖區(qū)，該如何管理？教師：林友芳142023/1/31方法1：指針數(shù)組（地址數(shù)組）設(shè)置一段內(nèi)存空間，例如數(shù)組，用來(lái)保存存儲(chǔ)空間的起始地址。數(shù)組中每個(gè)元素用來(lái)保存某種類型的存儲(chǔ)空間的地址，等于每個(gè)元素都是一個(gè)指針變量。int*pnarr[10];//定義一個(gè)長(zhǎng)度為10的整型指針數(shù)組（整型地址數(shù)組）char*psz[5];//定義一個(gè)長(zhǎng)度為5的字符指針數(shù)組。0x0012ff7d0x0012ff80…0x0012fe12其中每個(gè)元素都用來(lái)保存某種類型的存儲(chǔ)空間的地址教師：林友芳152023/1/31例如設(shè)一個(gè)班最多有50人，但每個(gè)班的人數(shù)不定，為了表示這50用戶，可以定義如下指針數(shù)組structUserAccount*Accounts[50];完成如下功能初始化指針數(shù)組將新生成的某個(gè)班用戶加入班級(jí)用戶集，并存放在空位置上。將某個(gè)班指定用戶號(hào)的用戶刪除給某個(gè)班所有女生發(fā)m元補(bǔ)助將新生成的某個(gè)班用戶插入到指定位置i上，i后面的用戶順序往后退。教師：林友芳162023/1/31指針數(shù)組結(jié)構(gòu)示例0x0012ff6dNULL0x0012ff800x0012ce000x0012fe12…08120001

張帥帥110108…M0.1008120099

李美美350108…F500.0008120002

趙小飛360108…M20.0008120007

羅小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…長(zhǎng)度為50空指針，可能曾被刪除后續(xù)元素或空或不空Accounts教師：林友芳172023/1/31功能實(shí)現(xiàn)初始化指針數(shù)組voidInitAccounts(structUserAccount*Accounts[],intnLen){for(inti=0;i<nLen;i++)

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

Accounts[nPlace]=pUser;//完成放置操作

returnnPlace;//返回位置}教師：林友芳192023/1/31功能示例0x0012ff6dNULL0x0012ff800x0012ce000x0012fe12…08120001

張帥帥110108…M0.1008120099

李美美350108…F500.0008120002

趙小飛360108…M20.0008120007

羅小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…長(zhǎng)度為50Accounts08120100

孫悟空110105…M600.100x0012ff300x0012ff30新找到的空位新結(jié)點(diǎn)孫悟空?qǐng)?bào)到教師：林友芳202023/1/31功能實(shí)現(xiàn)（續(xù)）將指定用戶號(hào)的用戶刪除，返回該用戶原來(lái)所在位置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;//將當(dāng)前位置置空

returni;}}return-1;}用戶結(jié)構(gòu)體指針數(shù)組數(shù)組長(zhǎng)度用戶號(hào)字符串比較函數(shù)教師：林友芳212023/1/31刪除功能示例0x0012ff6d0x0012ff300x0012ff800x0012ce000x0012fe12…08120001

張帥帥110108…M0.1008120099

李美美350108…F500.0008120002

趙小飛360108…M20.0008120007

羅小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…Accounts08120100

孫悟空110105…M600.100x0012ff30NULL把孫悟空位置找到把孫悟空開除:DeleteAccountByNumber(Accounts,50,“08120100”)釋放存儲(chǔ)空間教師：林友芳222023/1/31功能實(shí)現(xiàn)（續(xù)）給指定性別的群體充值，返回充值人數(shù)intChargeByGender(structUserAccount*Accounts[],intnLen,charcGender,doubledAmount){intnCounter=0;//計(jì)數(shù)器

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ā)補(bǔ)助教師：林友芳232023/1/31方法2：鏈接結(jié)構(gòu)采用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)一環(huán)扣一扣，通過(guò)一個(gè)元素保存的其它元素的地址找到其它元素。通過(guò)鏈接結(jié)構(gòu)實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)增加元素：在鐵鏈的某個(gè)位置加一鐵環(huán)刪除元素：去掉鐵鏈的某一鐵環(huán)問(wèn)題鐵鏈中的每一鐵環(huán)是一樣的嗎？普通的鐵鏈?zhǔn)菃蜗虻倪€是雙向的？有沒(méi)有一些特殊的鐵鏈，比如有多個(gè)分叉的？鐵鏈可以跟銅鏈拴一起嗎？鐵鏈的頭部可以拴在柱子上嗎？教師：林友芳242023/1/31鏈接結(jié)構(gòu)實(shí)現(xiàn)原理鏈接結(jié)構(gòu)中的元素需要保存的信息與結(jié)點(diǎn)本身有關(guān)的信息找到其它元素所需要的信息這些信息可以組織成結(jié)構(gòu)問(wèn)題：如何找到其它元素？保存其它元素在內(nèi)存中的地址在結(jié)構(gòu)中設(shè)置指針?lè)至?，用?lái)保存其它元素的地址的分量指針?lè)至繂?wèn)題：指針的類型？需要指向元素的結(jié)構(gòu)類型的指針類型如果需要指向的元素與本元素的類型相同的話，則需要定義自引用的結(jié)構(gòu)類型。教師：林友芳252023/1/31鏈接結(jié)構(gòu)一個(gè)結(jié)構(gòu)元素可以通過(guò)指針引用同類或不同類的結(jié)構(gòu)元素，多個(gè)結(jié)構(gòu)元素通過(guò)指針建立聯(lián)系。指向結(jié)構(gòu)的指針?lè)Q為鏈接，形成的復(fù)雜數(shù)據(jù)結(jié)構(gòu)稱為鏈接結(jié)構(gòu)最簡(jiǎn)單的鏈接結(jié)構(gòu)線性鏈接形成的表，鏈接表。每個(gè)自引用結(jié)構(gòu)有一個(gè)鏈接指針?lè)至俊＝處煟毫钟逊?62023/1/31最簡(jiǎn)單的鏈接結(jié)構(gòu)：?jiǎn)蜗蜴湵韱蜗蜴溄颖砭拖矜湕l，自引用結(jié)構(gòu)是鏈表中的一個(gè)鏈節(jié)，稱為鏈表結(jié)點(diǎn)，結(jié)點(diǎn)間由指針連接形成整個(gè)結(jié)構(gòu)。所有結(jié)點(diǎn)（結(jié)構(gòu)）由動(dòng)態(tài)分配創(chuàng)建。從指向表首結(jié)點(diǎn)的指針出發(fā)，沿鏈接可順序訪問(wèn)表中各結(jié)點(diǎn)。該指針代表整個(gè)表。通常把最后結(jié)點(diǎn)的指針置空表示結(jié)束。教師：林友芳272023/1/31更復(fù)雜的引用鏈接結(jié)構(gòu)教師：林友芳282023/1/31單向鏈表結(jié)構(gòu)示例structUserAccount{charUserNO[15];charName[20];charID[19];charGender;doubleBalance;

structUserAccount

*pNextUser;};用來(lái)保存下一個(gè)結(jié)點(diǎn)的地址此處改成如下形式是否可行，為什么？structUserAccount

NextUser;教師：林友芳292023/1/31普通單向鏈表示意圖08120001

張帥帥110108…M0.1008120002

趙小飛360108…M20.0008120007

羅小花410108…F88.2008120099

李美美350108…F500.00NULL…HeadTail2023/1/3130三、鏈表教師：林友芳312023/1/311.需求設(shè)有某系統(tǒng)的用戶信息結(jié)構(gòu)體，其中用戶ID長(zhǎng)度為10用戶姓名長(zhǎng)度不超過(guò)10需要處理的用戶數(shù)據(jù)不定，假設(shè)某程序需要以鏈表方式處理用戶的數(shù)據(jù)教師：林友芳322023/1/31普通單向鏈表示意DataDataDataDataNULL…HeadTail教師：林友芳332023/1/31鏈表結(jié)點(diǎn)結(jié)構(gòu)聲明方法1:structUserInfoNode{ charszID[11]; //ID charszName[11]; //姓名

structUserInfoNode*pNextUser; //下個(gè)用戶指針};方法2：typedefstructUserInfoNodeUSERNODE,*USERPOINTER;structUserInfoNode{ charszID[11]; //ID charszName[11]; //姓名

USERPOINTER*pNextUser; //下個(gè)用戶指針};教師：林友芳342023/1/31更好的方法：基本信息單獨(dú)說(shuō)明//用戶基本信息結(jié)構(gòu)聲明structUserInfo{ charszID[11]; //ID，11個(gè)字符

charszName[11]; //姓名，11個(gè)字符};或typedefstruct{ charszID[11]; //ID，11個(gè)字符

charszName[11]; //姓名，11個(gè)字符}USERINFO;教師：林友芳352023/1/31更常見合理的聲明方法方法3：structUserLinkNode{structUserInfoData; //數(shù)據(jù)

structUserLinkNode*pNextUser;//};structUserInfoUserInfoArr[100];或typedefstruct{USERINFOData; //數(shù)據(jù)結(jié)點(diǎn)

structUserLinkNode*pNextUser;//}USERLINKNODE;教師：林友芳362023/1/31增加一個(gè)鏈表描述信息結(jié)點(diǎn)NumberHeadTailDataDataDataDataNULL…LinkInfoNode關(guān)于鏈表整體描述信息結(jié)點(diǎn)教師：林友芳372023/1/31描述結(jié)點(diǎn)結(jié)構(gòu)說(shuō)明示例structUserLink{ structUserLinkNode*pHead;//頭指針

structUserLinkNode*pTail;//尾指針

intnNumber; //鏈表中的結(jié)點(diǎn)計(jì)數(shù)};或typedefstruct{ USERLINKNODE*pHead;//頭指針

USERLINKNODE*pTail;//尾指針

intnNumber; //鏈表中的結(jié)點(diǎn)計(jì)數(shù)}USERLINK;教師：林友芳382023/1/31可以增加一個(gè)不用的頭結(jié)點(diǎn)NumberHeadTailDataDataDataNULL…LinkInfoNode目的在于寫程序方便，簡(jiǎn)化一些鏈表操作，數(shù)據(jù)結(jié)構(gòu)課程中會(huì)有進(jìn)一步的闡述不用的頭結(jié)點(diǎn)教師：林友芳392023/1/31關(guān)于后面的操作的假定鏈表為單向鏈表沒(méi)有設(shè)置空的頭結(jié)點(diǎn)設(shè)置有信息描述結(jié)點(diǎn)，記錄如下信息頭結(jié)點(diǎn)尾結(jié)點(diǎn)鏈表中結(jié)點(diǎn)個(gè)數(shù)教師：林友芳402023/1/31在鏈表中增加一個(gè)節(jié)點(diǎn)有幾種增加方式將新結(jié)點(diǎn)作為最后一個(gè)元素增加到鏈表的尾部，將新結(jié)點(diǎn)作為第一個(gè)元素增加到鏈表的頭部將新結(jié)點(diǎn)按照某種次序要求插入到指定位置教師：林友芳412023/1/31加到尾部如果鏈表為空，則需要做一些初始化工作，將新的結(jié)點(diǎn)當(dāng)成頭結(jié)點(diǎn)和尾結(jié)點(diǎn)如果鏈表不為空，則將該結(jié)點(diǎn)作為尾結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，修改尾結(jié)點(diǎn)指針。如果沒(méi)有記錄尾結(jié)點(diǎn)指針，則需要從頭結(jié)點(diǎn)開始找到最后一個(gè)結(jié)點(diǎn)。pHeadpTailDataDataNULL……pNewNode

NULL教師：林友芳422023/1/31示例代碼，加到尾部intAddUserToTail(structUserLink*pUsers,//鏈表描述信息指針

structUserLinkNode*pNewUser//新結(jié)點(diǎn)指針){ if(pUsers==NULL||pNewUser==NULL)return-1; if(pUsers->nNumber<=0){//如果還沒(méi)有元素

pUsers->pHead=pNewUser; pUsers->pTail=pUsers->pHead;//頭尾指針指向同一個(gè)結(jié)點(diǎn)

} else{//把結(jié)點(diǎn)信息附到鏈表尾部

pUsers->pTail->pNext=pNewUser;//加到尾到

pUsers->pTail=pNewUser; //修改尾結(jié)點(diǎn)指針

} pUsers->pTail->pNext=NULL;//最后一個(gè)結(jié)點(diǎn)的后繼置空

pUsers->nNumber++;//計(jì)數(shù)加1 return0;}教師：林友芳432023/1/31加到頭部如果鏈表為空，則需要做一些初始化工作，將新的結(jié)點(diǎn)當(dāng)成頭結(jié)點(diǎn)和尾結(jié)點(diǎn)如果鏈表不為空，需要將新結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)置為原來(lái)的頭結(jié)點(diǎn)，并把新結(jié)點(diǎn)作為頭結(jié)點(diǎn)pHeadpTailDataDataNULL……NULLpNewNode

教師：林友芳442023/1/31示例代碼，加到頭部intAddUserToHead(structUserLink*pUsers,//鏈表描述信息指針

structUserLinkNode*pNewUser//新結(jié)點(diǎn)指針){ if(pUsers==NULL||pNewUser==NULL)return-1; if(pUsers->nNumber<=0){//如果還沒(méi)有元素

pUsers->pHead=pNewUser; pUsers->pTail=pUsers->pHead;//頭尾指針指向同一個(gè)結(jié)點(diǎn)

pNewUser->pNext=NULL; } else{//把結(jié)點(diǎn)信息附到鏈表頭部

pUsers->pNewUser->pNext=pUsers->pHead;//加到頭部

pUsers->pHead=pNewUser; //修改頭結(jié)點(diǎn)指針

} pUsers->nNumber++;//計(jì)數(shù)加1 return0;}教師：林友芳452023/1/31在鏈表中插入一個(gè)新結(jié)點(diǎn)基本操作q->pNext=p->pNext;p->pNext=q;其它用于保持鏈表指針完整性的操作。^^功能示意ppqqrr插入前插入后教師：林友芳462023/1/31去除鏈表中的某個(gè)結(jié)點(diǎn)基本操作p->