【正文】 第七章 動(dòng)態(tài)內(nèi)存分配與數(shù)據(jù)結(jié)構(gòu) 本章首先介紹程序運(yùn)行時(shí) 動(dòng)態(tài)內(nèi)存分配 （ dynamic memory allocation）的概念與方法。進(jìn)一步討論復(fù)制構(gòu)造函數(shù) . 然后學(xué)習(xí)更多有關(guān) 數(shù)據(jù)結(jié)構(gòu) 的基本知識(shí)，包括 鏈表 ，棧 ， 隊(duì) ， 二叉樹 等的基本算法和應(yīng)用。 模板 是標(biāo)準(zhǔn)C++實(shí)現(xiàn)代碼復(fù)用的有力工具，特別是有關(guān)數(shù)據(jù)結(jié)構(gòu)的算法，本章繼續(xù)使用。 （選讀） 棧與隊(duì)列的基本操作及其應(yīng)用 鏈表與鏈表的基本操作 第七章 動(dòng)態(tài)內(nèi)存分配與數(shù)據(jù)結(jié)構(gòu) 內(nèi)存 的分配與釋放 對(duì)象 與構(gòu)造函數(shù) 淺復(fù)制與深復(fù)制 靜態(tài)存儲(chǔ)分配： 通常定義變量 (或?qū)ο?)，編譯器在編譯時(shí)都可以根據(jù)該變量 (或?qū)ο?)的類型知道所需內(nèi)存空間的大小，從而系統(tǒng)在適當(dāng)?shù)臅r(shí)候?yàn)樗鼈兎峙浯_定的存儲(chǔ)空間。 動(dòng)態(tài)存儲(chǔ)分配： 有些操作對(duì)象只有在程序運(yùn)行時(shí)才能確定，這樣編譯器在編譯時(shí)就無法為他們預(yù)定存儲(chǔ)空間，只能在程序運(yùn)行時(shí)，系統(tǒng)根據(jù)運(yùn)行時(shí)的要求進(jìn)行內(nèi)存分配，稱為動(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)取得自由存儲(chǔ)區(qū) 中的一塊所需大小的存貯空間 ， 用于存貯該變量或?qū)ο?。 當(dāng)不再使用該變量或?qū)ο髸r(shí) ， 也就是它的生命結(jié)束時(shí) ， 要 顯式釋放 它所占用的存貯空間 ， 這樣系統(tǒng)就能進(jìn)行再次分配 ， 做到重復(fù)使用有限的資源 。 申請(qǐng)和釋放 自由存儲(chǔ)區(qū) 中分配的存貯空間，分別使用 new和 delete的兩個(gè)運(yùn)算符來完成，其使用的格式如下： 指針變量名 =new 類型名 (初始化式 )； delete 指針名 。 new運(yùn)算符 返回 的是一個(gè)指向所分配類型變量（對(duì)象）的指針 。對(duì)所創(chuàng)建的變量或?qū)ο?，都是通過該指針來間接操作的，而 動(dòng)態(tài)創(chuàng)建的對(duì)象本身沒有名字。 動(dòng)態(tài)分配與釋放： 內(nèi)存的分配與釋放 一般定義變量和對(duì)象時(shí)要用標(biāo)識(shí)符命名，稱 命名對(duì)象 ，而動(dòng)態(tài)的稱 無名對(duì)象 (請(qǐng)注意與棧區(qū)中的臨時(shí)對(duì)象的區(qū)別，兩者完全不同：生命期不同，操作方法不同，臨時(shí)變量對(duì)程序員是透明的 )。 自由存儲(chǔ)區(qū) 是不會(huì)自動(dòng)在分配時(shí)做初始化的（包括清零），所以必須用初始化式 (initializer)來顯式初始化。 new表達(dá)式的操作： 從自由存儲(chǔ)區(qū)分配對(duì)象，然后用括號(hào)中的值初始化該對(duì)象 。 分配對(duì)象時(shí)， new表達(dá)式調(diào)用庫操作符 new()： int *pi=new int(0)。 pi現(xiàn)在所指向的變量的存儲(chǔ)空間是由庫操作符 new()分配的，位于程序的自由存儲(chǔ)區(qū)中，并且該對(duì)象未命名。 無名對(duì)象： 內(nèi)存的分配與釋放 自由存儲(chǔ)區(qū) ０ Ｐ i 演示： １．用初始化式 (initializer)來顯式初始化 int *pi=new int(0)。 ２ ． 當(dāng) pi生命周期結(jié)束時(shí) ， 必須釋放 pi所指向的目標(biāo)： delete pi。 注意這時(shí)釋放了 pi所指的目標(biāo)的內(nèi)存空間，也就是撤銷了該目標(biāo)，稱動(dòng)態(tài)內(nèi)存釋放（ dynamic memory deallocation），但 指針 pi本身并沒有撤銷 ，該指針?biāo)純?nèi)存空間并未釋放。 內(nèi)存的分配與釋放 數(shù)組動(dòng)態(tài)分配格式： 指針變量名 =new 類型名 [下標(biāo)表達(dá)式 ]。 Delete[ ] 指向該數(shù)組的指針變量名 。 說明： 兩式中的 方括號(hào) 必須配對(duì)使用 。 如果 delete語句中少了方括號(hào) ， 因編譯器認(rèn)為該指針是指向數(shù)組第一個(gè)元素的指針 ， 會(huì)產(chǎn)生 回收不徹底 的問題 （ 只回收了第一個(gè)元素所占空間 ） ， 加了方括號(hào)后就轉(zhuǎn)化為指向數(shù)組的指針 ， 回收整個(gè)數(shù)組 。 delete [ ]的方括號(hào)中 不需要 填 數(shù)組元素?cái)?shù) ，系統(tǒng)自知。即使寫了，編譯器也忽略。 請(qǐng)注意 “下標(biāo)表達(dá)式”不是常量表達(dá)式 ，即它的值不必在編譯時(shí)確定， 可以在運(yùn)行時(shí)確定 。 內(nèi)存的分配與釋放 動(dòng)態(tài)分配數(shù)組與 標(biāo)準(zhǔn)字符串類 ： 標(biāo)準(zhǔn)字符串類 string就是采用動(dòng)態(tài)建立數(shù)組的方式解決數(shù)組溢出的問題的，例 ，在 string類對(duì)象中都是自動(dòng)完成的，在程序中不需要也不允許再顯式地為 string進(jìn)行動(dòng)態(tài)內(nèi)存的分配與釋放。 【 例 】 動(dòng)態(tài)數(shù)組的建立與撤銷 內(nèi)存的分配與釋放 動(dòng)態(tài)分配數(shù)組的特點(diǎn)： 1. 變量 n在編譯時(shí)沒有確定的值，而是在運(yùn)行中輸入， 按運(yùn)行時(shí)所需分配空間 ，這一點(diǎn)是動(dòng)態(tài)分配的優(yōu)點(diǎn)，可克服數(shù)組“大開小用”的弊端，在表、排序與查找中的算法，若用動(dòng)態(tài)數(shù)組，通用性更佳。 delete [ ]pc是將 n個(gè)字符的空間釋放，而用 delete pc則只釋放了一個(gè)字符的空間； 2. 如果有 char *pc1，令 pc1=pc，同樣可用 delete [ ] pc1 來釋放該空間。盡管 C++不對(duì)數(shù)組作邊界檢查，但 在 自由 存儲(chǔ)區(qū) 空間分配時(shí)，對(duì)數(shù)組分配空間大小是紀(jì)錄在案的 。 3. 沒有初始化式（ initializer）， 不可對(duì)數(shù)組初始化 。 內(nèi)存的分配與釋放 （選讀） 多維數(shù)組動(dòng)態(tài)分配： new 類型名 [下標(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ù)組名，但沒有指出其邊界，即最高維的元素?cái)?shù)量，就像指向字符的指針即等效一個(gè)字符串 ,不要把指向字符的指針，說成指向字符串的指針 。這與數(shù)組的嵌套定義相一致。 內(nèi)存的分配與釋放 （選讀） 比較： float(*cp) [30] [20]。 //三級(jí)指針 float (*bp) [20]。 //二級(jí)指針 cp=new float [1] [30] [20]。 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ù)組 【 例 】 動(dòng)態(tài)創(chuàng)建和刪除一個(gè) m*n個(gè)元素的數(shù)組 的分配與釋放 指針使用的要點(diǎn)： 1. 動(dòng)態(tài)分配失敗 。返回一個(gè)空指針（ NULL），表示發(fā)生了異常，堆資源不足，分配失敗。 2. 指針刪除與 自由存儲(chǔ)區(qū) 空間釋放 。刪除一個(gè)指針 p（ delete p。）實(shí)際意思是刪除了 p所指的目標(biāo)（變量或?qū)ο蟮龋?，釋放了它所占?自由存儲(chǔ)區(qū) 空間，而不是刪除ｐ本身，釋放自由存儲(chǔ)區(qū)空間后，ｐ成了 空懸指針 ?？諔抑羔樖浅绦蝈e(cuò)誤的一個(gè)根源）。建議這時(shí)將ｐ置空（ NULL）。 3. new()和 delete()是可以重載的 ，它們都是類的靜態(tài)成員函數(shù)。程序員無需顯式聲明它為靜態(tài)的，系統(tǒng)自動(dòng)定義為靜態(tài)的。本教材不討論 new()和 delete()的重載。未重載時(shí)，調(diào)用全局庫操作符 new()。 內(nèi)存的分配與釋放 4． 內(nèi)存泄漏（ memory leak）和重復(fù)釋放 。 new與 delete 是配對(duì)使用的， delete只能釋放 自由存儲(chǔ)區(qū) 空間。如果 new返回的指針值丟失，則所分配的 自由存儲(chǔ)區(qū) 空間無法回收，稱內(nèi)存泄漏，同一空間重復(fù)釋放也是危險(xiǎn)的，因?yàn)?該空間可能已另分配 ，所以必須妥善保存 new返回的指針，以保證不發(fā)生內(nèi)存泄漏，也必須保證不會(huì)重復(fù)釋放自由存儲(chǔ)區(qū) 內(nèi)存空間。 5． 動(dòng)態(tài)分配的變量或?qū)ο蟮纳?。 無名對(duì)象的生命期并不依賴于建立它的作用域，比如在函數(shù)中建立的動(dòng)態(tài)對(duì)象在函數(shù)返回后仍可使用 。但必須記住釋放該對(duì)象所占 自由存儲(chǔ)區(qū) 空間，并只能釋放一次，在函數(shù)內(nèi)建立，而在函數(shù)外釋放是一件很容易 失控 的事，往往會(huì)出錯(cuò)。 對(duì)象與構(gòu)造函數(shù) 類對(duì)象動(dòng)態(tài)建立與刪除過程： 通過 new建立的對(duì)象要調(diào)用構(gòu)造函數(shù)，通過 delete刪除對(duì)象也要調(diào)用析構(gòu)函數(shù)。 CGoods *pc。 pc=new CGoods。 //分配自由存儲(chǔ)區(qū)空間，并構(gòu)造一個(gè)無名的 CGoods對(duì)象； ……. delete pc。 //先析構(gòu)，然后將內(nèi)存空間返回給自由存儲(chǔ)區(qū)； 自由存儲(chǔ)區(qū) 對(duì)象的生命期并不依賴于建立它的作用域，所以除非程序結(jié)束， 自由存儲(chǔ)區(qū) 對(duì)象（無名對(duì)象）的生命期不會(huì)到期，并且需要顯式地用 delete語句析構(gòu)該類對(duì)象，上例執(zhí)行 delete語句時(shí)， C++自動(dòng)調(diào)用商品類的析構(gòu)函數(shù)。 對(duì)象與構(gòu)造函數(shù) 由自由存儲(chǔ)區(qū)創(chuàng)建對(duì)象數(shù)組 ， 只能調(diào)用默認(rèn)的構(gòu)造函數(shù) ， 不能調(diào)用其他任何構(gòu)造函數(shù) 。 如果沒有默認(rèn)的構(gòu)造函數(shù) ， 則不能創(chuàng)建對(duì)象數(shù)組 。 類對(duì)象初始化： new后面類（ class）類型可以有參數(shù)。這些參數(shù)即構(gòu)造函數(shù)的參數(shù)。但對(duì) 創(chuàng)建數(shù)組 ，則無參數(shù)， 只能調(diào)用默認(rèn)的構(gòu)造函數(shù) 。 【 例 】 演示自由存儲(chǔ)區(qū)對(duì)象分配和釋放。 淺復(fù)制與深復(fù)制 淺復(fù)制： 默認(rèn)復(fù)制構(gòu)造函數(shù) ，可用一個(gè)類對(duì)象初始化另一個(gè)類對(duì)象，稱為默認(rèn)的 按成員復(fù)制， 而不是對(duì)整個(gè)類對(duì)象的 按位復(fù)制。 這稱為 淺復(fù)制。 圖 淺復(fù)制 P 自 由存儲(chǔ) 區(qū)對(duì)象 自 由 存儲(chǔ)區(qū) 對(duì)象 P P 復(fù)制前 復(fù)制后 如果類中有一個(gè)數(shù)據(jù)成員為指針，該類的一個(gè)對(duì)象 obj1中的這個(gè)指針 p，指向了動(dòng)態(tài)分配的一個(gè) 自由存儲(chǔ)區(qū) 對(duì)象，（參見圖 ），如果用 obj1按成員復(fù)制了一個(gè)對(duì)象 obj2，這時(shí) 自由存儲(chǔ)區(qū) 對(duì)象。 obj1 obj1 obj2 淺復(fù)制與深復(fù)制復(fù)制 當(dāng) 淺復(fù)制 析構(gòu)時(shí)，如用默認(rèn)的析構(gòu)函數(shù)，則動(dòng)態(tài)分配的 自由存儲(chǔ)區(qū) 對(duì)象不能回收。如果在析構(gòu)函數(shù)中有“ delete p?！闭Z句，則如果先析構(gòu)函數(shù) obj1時(shí)，自由存儲(chǔ)區(qū) 對(duì)象已經(jīng)釋放，以后再析構(gòu)obj2時(shí)出現(xiàn)了二次釋放的問題。 自由存儲(chǔ)區(qū) 對(duì)象 P P 自由存儲(chǔ)區(qū) 對(duì)象 圖 深復(fù)制 深復(fù)制： 重新定義復(fù)制的構(gòu)造函數(shù)，給每個(gè)對(duì)象獨(dú)立分配一個(gè) 自由存儲(chǔ)區(qū)對(duì)象，稱 深復(fù)制 。 這時(shí)先復(fù)制對(duì)象主體，再為 obj2分配一個(gè) 自由存儲(chǔ)區(qū) 對(duì)象，最后用 obj1的 自由存儲(chǔ)區(qū) 對(duì)象復(fù)制 obj2的 自由存儲(chǔ)區(qū) 對(duì)象。 obj1 obj2 淺復(fù)制與深復(fù)制 【 例 】 定義復(fù)制構(gòu)造函數(shù) （ copy structor）和復(fù)制賦值操作符（ copy Assignment Operator）實(shí)現(xiàn)深復(fù)制。 學(xué)生類定義： class student{ char *pName。 //為了演示深復(fù)制，不用 string類 public: student()。 //默認(rèn)構(gòu)造函數(shù) student(char *pname)。 //帶參數(shù) 構(gòu)造函數(shù) student(student amp。s)。 //復(fù)制構(gòu)造函數(shù) ~student()。 //析構(gòu)函數(shù) student amp。 operator=(student amp。s)。 }。 //復(fù)制賦值操作符 檢驗(yàn) 主函數(shù) 和 運(yùn)行結(jié)果 淺復(fù)制與深復(fù)制 提示： 自由存儲(chǔ)區(qū)內(nèi)存是最常見的需要自定義復(fù)制構(gòu)造函數(shù)的資源，但不是唯一的，還有打開文件等也需要自定義復(fù)制構(gòu)造函數(shù)。 如果類對(duì)象需要?jiǎng)討B(tài)分配資源應(yīng)該由構(gòu)造函數(shù)完成，而釋放資源由析構(gòu)函數(shù)完成，這時(shí)類也需要一個(gè)自定義的復(fù)制構(gòu)造函數(shù)，實(shí)現(xiàn)對(duì)象的深復(fù)制。由此可見， 構(gòu)造函數(shù)并非僅做初始化工作 。 淺復(fù)制與深復(fù)制 思考： 深入地考慮 【 例 】 ，如果數(shù)據(jù)域還有很多其他數(shù)據(jù)，甚至有好幾個(gè)是動(dòng)態(tài)建立的 C字符串，深復(fù)制是不是太復(fù)雜了？如果使用 C++標(biāo)準(zhǔn)字符串 string作為成員對(duì)象（聚合） 是否就不需要考慮深復(fù)制了？ 的確是這樣的，準(zhǔn)確地說， string類的內(nèi)部包含動(dòng)態(tài)建立字符數(shù)組的操作，其復(fù)制構(gòu)造函數(shù)是深復(fù)制。如果在 student類中使用 string類而不是 C字符串，就不要再考慮深復(fù)制問題了。也就是說，動(dòng)態(tài)內(nèi)存分配和深復(fù)制應(yīng)該放在一個(gè)適當(dāng)?shù)膶用嫔?，一個(gè)更單純的類定義中，如 string類。在使用中，把它作為一個(gè)成員對(duì)象，就像使用 string類對(duì)象那樣。 淺復(fù)制與深復(fù)制 探討： 最后進(jìn)一步討論類的封裝。封裝的更高境界是在該類對(duì)象中一切都是完備的、自給自足的，不僅有數(shù)據(jù)和對(duì)數(shù)據(jù)的操作，還包括資源的動(dòng)態(tài)安排和釋放。在需要時(shí)可以無條件地安全使用。標(biāo)準(zhǔn)string類模板就是典型的例子。這樣的類對(duì)象，作為另一個(gè)類的成員對(duì)象使用時(shí)，就不會(huì)出任何問題。這表明 聚合