【正文】 第七章 動(dòng)態(tài)內(nèi)存分配 本章首先介紹程序運(yùn)行時(shí) 動(dòng)態(tài)內(nèi)存分配 （ dynamic memory allocation）的概念與方法。到目前為止，本教材介紹的程序設(shè)計(jì)中，變量和對(duì)象在 內(nèi)存中的分配 都是編譯器在 編譯程序時(shí)安排 好了的，這帶來(lái)了極大的不便，如數(shù)組必須大開(kāi)小用，指針必須指向一個(gè)已經(jīng)存在的變量或?qū)ο?。?dòng)態(tài)內(nèi)存分配解決了這個(gè)問(wèn)題。本章將進(jìn)一步討論拷貝構(gòu)造函數(shù)；還要學(xué)習(xí)更多有關(guān) 數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)，包括 棧 ， 隊(duì) ， 二叉樹(shù) 等的基本算法和應(yīng)用。模板 是標(biāo)準(zhǔn) C++實(shí)現(xiàn)代碼復(fù)用的有力工具，特別是有關(guān)數(shù)據(jù)結(jié)構(gòu)的算法。本章繼續(xù)使用模板介紹算法。 堆內(nèi)存分配 MFC對(duì)象和 Windows對(duì)象的關(guān)系 棧與隊(duì)列的基本操作及其應(yīng)用 鏈表與鏈表的基本操作 第七章 動(dòng)態(tài)內(nèi)存分配 圖書(shū)流通管理系統(tǒng)設(shè)計(jì) ——鏈表類(lèi)應(yīng)用 堆內(nèi)存分配 堆對(duì)象與構(gòu)造函數(shù) 淺拷貝與深拷貝 C/C++定義了 4個(gè)內(nèi)存區(qū)間：代碼區(qū)，全局變量與靜態(tài)變量區(qū)，局部變量區(qū)即棧區(qū)， 動(dòng)態(tài)存儲(chǔ)區(qū)，即堆（ heap）區(qū)或自由存儲(chǔ)區(qū)（ free store） 。 通常定義變量（或?qū)ο螅?，編譯器在編譯時(shí)都可以根據(jù)該變量（或?qū)ο螅┑念?lèi)型知道所需內(nèi)存空間的大小，從而系統(tǒng)在適當(dāng)?shù)臅r(shí)候?yàn)樗麄兎峙浯_定的存儲(chǔ)空間。這種內(nèi)存分配稱(chēng)為 靜態(tài)存儲(chǔ)分配 有些操作對(duì)象只有在程序運(yùn)行時(shí)才能確定，這樣編譯器在編譯時(shí)就無(wú)法為他們預(yù)定存儲(chǔ)空間，只能在程序運(yùn)行時(shí)，系統(tǒng)根據(jù)運(yùn)行時(shí)的要求進(jìn)行內(nèi)存分配，這種方法稱(chēng)為 動(dòng)態(tài)存儲(chǔ)分配 。所有動(dòng)態(tài)存儲(chǔ)分配都在堆區(qū)中進(jìn)行。 堆內(nèi)存的分配與釋放 當(dāng)程序運(yùn)行到需要一個(gè)動(dòng)態(tài)分配的變量或?qū)ο髸r(shí) ， 必須向系統(tǒng) 申請(qǐng)取得 堆中的一塊所需大小的存貯空間 ， 用于存貯該變量或?qū)ο?。 當(dāng)不再使用該變量或?qū)ο髸r(shí) ， 也就是它的生命結(jié)束時(shí) ， 要 顯式釋放 它所占用的存貯空間 ， 這樣系統(tǒng)就能對(duì)該堆空間進(jìn)行再次分配 ， 做到重復(fù)使用有限的資源 。 在 C++中 ， 申請(qǐng)和釋放堆中分配的存貯空間 ， 分別使用new和 delete的兩個(gè)運(yùn)算符來(lái)完成 ， 其使用的格式如下： 指針變量名 =new 類(lèi)型名 (初始化式 )； delete 指針名 。 new運(yùn)算符 返回 的是一個(gè)指向所分配類(lèi)型變量（對(duì)象）的 指針 。對(duì)所創(chuàng)建的變量或?qū)ο?，都是通過(guò)該指針來(lái)間接操作的，而 動(dòng)態(tài)創(chuàng)建的對(duì)象本身沒(méi)有名字。 堆內(nèi)存的分配與釋放 一般定義變量和對(duì)象時(shí)要用標(biāo)識(shí)符命名，稱(chēng) 命名對(duì)象 ，而動(dòng)態(tài)的稱(chēng) 無(wú)名對(duì)象 (請(qǐng)注意與棧區(qū)中的臨時(shí)對(duì)象的區(qū)別，兩者完全不同：生命期不同，操作方法不同，臨時(shí)變量對(duì)程序員是透明的 )。堆區(qū)是不會(huì)自動(dòng)在分配時(shí)做初始化的（包括清零），所以必須用初始化式 (initializer)來(lái)顯式初始化。 new表達(dá)式的操作序列如下： 從堆區(qū)分配對(duì)象，然后用括號(hào)中的值初始化該對(duì)象 。從堆區(qū)分配對(duì)象時(shí)， new表達(dá)式調(diào)用庫(kù)操作符new()。例如： int *pi=new int(0)。 它與下列代碼序列 大體 等價(jià)： int ival=0。 int *pi=amp。ival。 只是 pi現(xiàn)在所指向的變量是由庫(kù)操作符 new()分配的，位于程序的堆區(qū)中，并且該 對(duì)象未命名 。 堆內(nèi)存的分配與釋放 堆 ０ Ｐ i 下面看演示： １．用初始化式 (initializer)來(lái)顯式初始化 int *pi=new int(0)。 ２ ． 當(dāng) pi生命周期結(jié)束時(shí) ， 必須釋放 pi所指向的目標(biāo)： delete pi。 注意這時(shí)釋放了 pi所指的目標(biāo)的內(nèi)存空間，也就是撤銷(xiāo)了該目標(biāo)，稱(chēng)動(dòng)態(tài)內(nèi)存釋放（ dynamic memory deallocation），但 指針 pi本身并沒(méi)有撤銷(xiāo) ，它自己仍然存在，該指針?biāo)純?nèi)存空間并未釋放。 堆內(nèi)存的分配與釋放 對(duì)于數(shù)組進(jìn)行動(dòng)態(tài)分配的格式為： 指針變量名 =new 類(lèi)型名 [下標(biāo)表達(dá)式 ]。 delete [ ] 指向該數(shù)組的指針變量名 。 兩式中的 方括號(hào) 是非常重要的，兩者必須配對(duì)使用，如果delete語(yǔ)句中少了方括號(hào)，因編譯器認(rèn)為該指針是指向數(shù)組第一個(gè)元素的指針，會(huì)產(chǎn)生 回收不徹底 的問(wèn)題（ 只回收了第一個(gè)元素所占空間 ）， 加了方括號(hào)后就轉(zhuǎn)化為指向數(shù)組的指針，回收整個(gè)數(shù)組 。 delete [ ]的方括號(hào)中 不需要 填數(shù)組元素?cái)?shù) ，系統(tǒng)自知。即使寫(xiě)了，編譯器也忽略。 請(qǐng)注意 “下標(biāo)表達(dá)式”不是常量表達(dá)式 ，即它的值不必在編譯時(shí)確定， 可以在運(yùn)行時(shí)確定 。 堆內(nèi)存的分配與釋放 【 例 】 動(dòng)態(tài)數(shù)組的建立與撤銷(xiāo) include include void main(){ int n。 char *pc。 cout請(qǐng)輸入動(dòng)態(tài)數(shù)組的元素個(gè)數(shù) endl。 cinn。 //在運(yùn)行時(shí)確定， 可輸入 17 pc=new char[n]。 //申請(qǐng) 17個(gè)字符（可裝 8個(gè)漢字和一個(gè)結(jié)束符）的內(nèi)存空間 strcpy(pc,堆內(nèi)存的動(dòng)態(tài)分配 )。 coutpcendl。 delete []pc。//釋放 pc所指向的 n個(gè)字符的內(nèi)存空間 return 。 } 堆內(nèi)存的分配與釋放 動(dòng)態(tài)分配數(shù)組有三個(gè)特點(diǎn)： 1. 變量 n在編譯時(shí)沒(méi)有確定的值，而是在運(yùn)行中輸入， 按運(yùn)行時(shí)所需分配堆空間 ，這一點(diǎn)是動(dòng)態(tài)分配的優(yōu)點(diǎn)，可克服數(shù)組“大開(kāi)小用”的弊端，在表、排序與查找中的算法，若用動(dòng)態(tài)數(shù)組，通用性更佳。 delete []pc是將 n個(gè)字符的空間釋放，而用 delete pc則只釋放了一個(gè)字符的空間； 2. 如果有一個(gè) char *pc1，令 pc1=p，同樣可用 delete [] pc1來(lái)釋放該空間。盡管 C++不對(duì)數(shù)組作邊界檢查，但在堆空間分配時(shí)，對(duì)數(shù)組分配空間大小是紀(jì)錄在案的 。 3. 沒(méi)有初始化式（ initializer）， 不可對(duì)數(shù)組初始化 。 堆內(nèi)存的分配與釋放 多維數(shù)組動(dòng)態(tài)分配： new 類(lèi)型名 [下標(biāo)表達(dá)式 1] [下標(biāo)表達(dá)式 2]……。 建立一個(gè)動(dòng)態(tài)三維數(shù)組 float (*cp)[30][20] 。 //指向一個(gè) 30行 20列數(shù)組的指針 cp=new float [15] [30] [20]。 //建立由 15個(gè) 30*20數(shù)組組成的數(shù)組； 注意 cp等效于三維數(shù)組名，但沒(méi)有指出其邊界，即最高維的元素?cái)?shù)量，就像指向字符的指針即等效一個(gè)字符串 ,不要把指向字符的指針，說(shuō)成指向字符串的指針。這與數(shù)組的嵌套定義相一致。 堆內(nèi)存的分配與釋放 比較： float(*cp) [30] [20]。 //三級(jí)指針； float (*bp) [20]。 //二級(jí)指針； cp=new float [1] [20] [30]。 bp=new float [30] [20]。 兩個(gè)數(shù)組都是由 600個(gè)浮點(diǎn)數(shù)組成，前者是只有一個(gè)元素的三維數(shù)組 ，每個(gè)元素為 30行 20列的二維數(shù)組，而另一個(gè)是有 30個(gè)元素的二維數(shù)組 ，每個(gè)元素為 20個(gè)元素的一維數(shù)組。刪除這兩個(gè)動(dòng)態(tài)數(shù)組可用下式： delete [] cp。 //刪除（釋放）三維數(shù)組； delete [] bp。 //刪除（釋放）二維數(shù)組； 堆內(nèi)存的分配與釋放 【 例 】 動(dòng)態(tài)創(chuàng)建和刪除一個(gè) m*n個(gè)元素的數(shù)組。采用 指針數(shù)組方式 來(lái)完成二維數(shù)組的動(dòng)態(tài)創(chuàng)建。 const int m=4。 //行數(shù) const int n=6。 //列數(shù) 先看二維數(shù)組的動(dòng)態(tài)創(chuàng)建： void main(){ double **data。 data = new double*[m]。 //設(shè)置行 if ((data ) == 0){ cout Couuld not allocate. Bye ...。exit(1)。} for(int j=0。jm。j++){ data[j] = new double[n]。 //設(shè)置列 if (data[j] == 0){ cout Couuld not allocate. Bye ...。exit(1)。} } for (int i=0。im。i++) for (int j=0。jn。j++) data[i][j]=i*n+j。//初始化數(shù)組元素 display(data)。 de_allocate(data)。 return。 } 堆內(nèi)存的分配與釋放 再 看二維數(shù)組的撤銷(xiāo)與內(nèi)存釋放： void de_allocate(double **data){ for (int i=0。im。i++) delete[] data[i]。 //注意撤銷(xiāo)次序，先列后行，與設(shè)置相反 delete[] data。 } 在 VC++平臺(tái)上演示本例 。 指針使用的幾個(gè)問(wèn)題： １．動(dòng)態(tài)分配失敗。 返回一個(gè)空指針（ NULL），表示 發(fā)生了異常，堆資源不足，分配失敗。 ２．指針刪除與堆空間釋放。刪除一個(gè)指針 p（ delete p。） 實(shí)際意思是刪除了 p所指的目標(biāo)（變量或?qū)ο蟮龋?，釋放了它所占的堆空間，而不是刪除ｐ本身，釋放堆空間后，ｐ成了 空懸指針 。 堆內(nèi)存的分配與釋放 ３． 內(nèi)存泄漏（ memory leak）和重復(fù)釋放 。 new與 delete 是配對(duì)使用的， delete只能釋放堆空間。如果new返回的指針值丟失，則所分配的堆空間無(wú)法回收，稱(chēng)內(nèi)存泄漏，同一空間重復(fù)釋放也是危險(xiǎn)的，因?yàn)?該空間可能已另分配 ，所以必須妥善保存 new返回的指針，以保證不發(fā)生內(nèi)存泄漏，也必須保證不會(huì)重復(fù)釋放堆內(nèi)存空間。 ４．動(dòng)態(tài)分配的變量或?qū)ο蟮纳凇?無(wú)名對(duì)象的生命期并不依賴(lài)于建立它的作用域，比如在函數(shù)中建立的動(dòng)態(tài)對(duì)象在函數(shù)返回后仍可使用。 我們也稱(chēng)堆空間為自由空間（ free store）就是這個(gè)原因。 但必須記住釋放該對(duì)象所占堆空間，并只能釋放一次，在函數(shù)內(nèi)建立，而在函數(shù)外釋放是一件很容易 失控 的事，往往會(huì)出錯(cuò)。 堆對(duì)象與構(gòu)造函數(shù) 通過(guò) new建立的對(duì)象要調(diào)用構(gòu)造函數(shù)，通過(guò) deletee刪除對(duì)象也要調(diào)用析構(gòu)函數(shù)。 CGoods *pc。 pc=new CGoods。 //分配堆空間，并構(gòu)造一個(gè)無(wú)名的 CGoods對(duì)象； ……. delete pc。 //先析構(gòu) ，然后將內(nèi)存空間返回給堆； 堆對(duì)象的生命期并不依賴(lài)于建立它的作用域，所以除非程序結(jié)束，堆對(duì)象（無(wú)名對(duì)象）的生命期不會(huì)到期，并且需要顯式地用 delete語(yǔ)句析構(gòu)堆對(duì)象，上面的堆對(duì)象在執(zhí)行 delete語(yǔ)句時(shí)， C++自動(dòng)調(diào)用其析構(gòu)函數(shù)。 正因?yàn)闃?gòu)造函數(shù)可以有參數(shù)，所以 new后面類(lèi)（ class）類(lèi)型也可以有參數(shù)。這些參數(shù)即構(gòu)造函數(shù)的參數(shù)。但對(duì)創(chuàng)建數(shù)組，則無(wú)參數(shù)，并只調(diào)用缺省的構(gòu)造函數(shù)。見(jiàn)下例類(lèi)說(shuō)明： 堆對(duì)象與構(gòu)造函數(shù) class CGoods{ char Name[21]。 int Amount。 float Price。 float Total value。 public: CGoods(){}。 //缺省構(gòu)造函數(shù) 。 //因已有構(gòu)造函數(shù) ， 系統(tǒng)不會(huì)自動(dòng)生成 ， 必須顯式說(shuō)明 。 CGoods(char* name,int amount ,float price){ strcpy(Name,name)。 Amount=amount。 Price=price。 Total_value=price*amount。 } …… } 堆對(duì)象與構(gòu)造函數(shù) 下面注意如何使用： void main(){ int n。 CGoods *pc,*pc1,*pc2。 pc=new CGoods(“夏利 2022”， 10， 118000)。 //調(diào)用三參數(shù)構(gòu)造函數(shù) pc1=new CGoods()。 //調(diào)用缺省構(gòu)造函數(shù) cout’輸入商品類(lèi)數(shù)組元素?cái)?shù) ’ endl。 cinn。 pc2=new CGoods[n]。 //動(dòng)態(tài)建立數(shù)組 ， 不能初始化 ， 調(diào)用 n次缺省構(gòu)造函數(shù) …… delete pc。 delete pc1。 delete []pc2。 } 堆對(duì)象與構(gòu)造函數(shù) 這里再次強(qiáng)調(diào)： 由堆區(qū)創(chuàng)建對(duì)象數(shù)組 ， 只能調(diào)用缺省的構(gòu)造函數(shù) ， 不能調(diào)用其他任何構(gòu)造函數(shù) 。 如果沒(méi)有缺省的構(gòu)造函數(shù) ， 則不能創(chuàng)建對(duì)象數(shù)組 。 淺拷貝與深拷貝 缺省拷貝構(gòu)造函數(shù) ，可用一個(gè)類(lèi)對(duì)象初始化另一個(gè)類(lèi)對(duì)象，稱(chēng)為缺省的 按成員