C 程序設(shè)計(jì)課件：第七章 動(dòng)態(tài)內(nèi)存分配與數(shù)據(jù)結(jié)構(gòu)

1、第七章 動(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ù)使用。7.1自由存儲(chǔ)區(qū)內(nèi)存分配 7.4二叉樹 （選讀） 7.3 棧與隊(duì)列的基本操作及其應(yīng)用 7.2 鏈表與鏈表的基本操作 第七章 動(dòng)態(tài)內(nèi)存分配與數(shù)據(jù)結(jié)構(gòu)7.1自由存儲(chǔ)區(qū)內(nèi)存分配 7.1.1自由存儲(chǔ)區(qū)內(nèi)存的分配與釋放 7.1.2自由存儲(chǔ)區(qū)對(duì)象與構(gòu)造函數(shù) 7.1.3 淺復(fù)制與深復(fù)制 靜態(tài)存儲(chǔ)分配

2、：無(wú)論全局或局部變量(對(duì)象)，編譯器在編譯時(shí)都可以根據(jù)該變量(對(duì)象)的類型知道所需內(nèi)存空間的大小，從而系統(tǒng)在適當(dāng)?shù)臅r(shí)候?yàn)樗鼈兎峙浯_定的存儲(chǔ)空間。尤其是數(shù)組。動(dò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)存分配，稱為動(dòng)態(tài)存儲(chǔ)分配。動(dòng)態(tài)分配都在自由存儲(chǔ)區(qū)中進(jìn)行。7.1.1自由存儲(chǔ)區(qū)內(nèi)存的分配與釋放當(dāng)程序運(yùn)行到需要?jiǎng)討B(tài)分配變量或?qū)ο髸r(shí)，必須向系統(tǒng)申請(qǐng)取得自由存儲(chǔ)區(qū)中的一塊所需大小的存貯空間，用于存貯該變量或?qū)ο?。?dāng)不再使用該變量或?qū)ο髸r(shí)，也就是它的生命結(jié)束時(shí)，要顯式釋放它所占用的存貯空間，這樣系統(tǒng)就能進(jìn)行再

3、次分配，做到重復(fù)使用有限的資源。 申請(qǐng)和釋放自由存儲(chǔ)區(qū)中分配的存貯空間，分別使用new和delete的兩個(gè)運(yùn)算符來(lái)完成，其使用的格式如下：指針變量名=new 類型名(初始化式)；delete 指針名;new運(yùn)算符返回的是一個(gè)指向所分配類型變量（對(duì)象）的指針。對(duì)所創(chuàng)建的變量或?qū)ο?，都是通過該指針來(lái)間接操作的，而動(dòng)態(tài)創(chuàng)建的對(duì)象本身沒有名字。 動(dòng)態(tài)分配與釋放： 7.1.1自由存儲(chǔ)區(qū)內(nèi)存的分配與釋放一般定義變量和對(duì)象時(shí)要用標(biāo)識(shí)符命名，稱命名對(duì)象，而動(dòng)態(tài)的稱無(wú)名對(duì)象(請(qǐng)注意與棧區(qū)中的臨時(shí)對(duì)象的區(qū)別，兩者完全不同：生命期不同，操作方法不同，臨時(shí)變量對(duì)程序員是透明的)。自由存儲(chǔ)區(qū)是不會(huì)自動(dòng)在分配時(shí)做初始化的

4、（包括清零），所以必須用初始化式(initializer)來(lái)顯式初始化。new表達(dá)式的操作：從自由存儲(chǔ)區(qū)分配對(duì)象，然后用括號(hào)中的值初始化該對(duì)象。分配對(duì)象時(shí)，new表達(dá)式調(diào)用庫(kù)操作符new()： int *pi=new int(0);pi現(xiàn)在所指向的變量的存儲(chǔ)空間是由庫(kù)操作符new()分配的，位于程序的自由存儲(chǔ)區(qū)中，并且該對(duì)象未命名。 無(wú)名對(duì)象： 7.1.1自由存儲(chǔ)區(qū)內(nèi)存的分配與釋放自由存儲(chǔ)區(qū)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)存空間，

5、也就是撤銷了該目標(biāo)，稱動(dòng)態(tài)內(nèi)存釋放（dynamic memory deallocation），但指針pi本身并沒有撤銷，該指針?biāo)純?nèi)存空間并未釋放。 7.1.1自由存儲(chǔ)區(qū)內(nèi)存的分配與釋放數(shù)組動(dòng)態(tài)分配格式：指針變量名=new 類型名下標(biāo)表達(dá)式;delete 指向該數(shù)組的指針變量名;說(shuō)明：兩式中的方括號(hào)必須配對(duì)使用。如果delete語(yǔ)句中少了方括號(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á)式”

6、不是常量表達(dá)式，即它的值不必在編譯時(shí)確定，可以在運(yùn)行時(shí)確定。7.1.1自由存儲(chǔ)區(qū)內(nèi)存的分配與釋放動(dòng)態(tài)分配數(shù)組與標(biāo)準(zhǔn)字符串類： 標(biāo)準(zhǔn)字符串類string就是采用動(dòng)態(tài)建立數(shù)組的方式解決數(shù)組溢出的問題的，例7.1所做的動(dòng)態(tài)內(nèi)存分配與釋放，在string類對(duì)象中都是自動(dòng)完成的，在程序中不需要也不允許再顯式地為string進(jìn)行動(dòng)態(tài)內(nèi)存的分配與釋放?！纠?.1】動(dòng)態(tài)數(shù)組的建立與撤銷7.1.1自由存儲(chǔ)區(qū)內(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ù)組，通用

7、性更佳。delete pc是將n個(gè)字符的空間釋放，而用delete pc則只釋放了一個(gè)字符的空間；2. 如果有char *pc1，令pc1=pc，同樣可用delete pc1 來(lái)釋放該空間。盡管C+不對(duì)數(shù)組作邊界檢查，但在自由 存儲(chǔ)區(qū) 空間分配時(shí)，對(duì)數(shù)組分配空間大小是紀(jì)錄在案的。3. 沒有初始化式（initializer），不可對(duì)數(shù)組初始化。 7.1.1自由存儲(chǔ)區(qū)內(nèi)存的分配與釋放（選讀）多維數(shù)組動(dòng)態(tài)分配：new 類型名下標(biāo)表達(dá)式1 下標(biāo)表達(dá)式2;建立一個(gè)動(dòng)態(tài)三維數(shù)組float (*cp)3020 ; /指向一個(gè)30行20列數(shù)組的指針cp=new float 15 30 20; /建立由15個(gè)3

8、0*20數(shù)組組成的數(shù)組；注意cp等效于三維數(shù)組名，但沒有指出其邊界，即最高維的元素?cái)?shù)量，就像指向字符的指針即等效一個(gè)字符串,不要把指向字符的指針，說(shuō)成指向字符串的指針。這與數(shù)組的嵌套定義相一致。7.1.1自由存儲(chǔ)區(qū)內(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ù)組可用下

9、式：delete cp; /刪除（釋放）三維數(shù)組delete bp; /刪除（釋放）二維數(shù)組【例7.2】 動(dòng)態(tài)創(chuàng)建和刪除一個(gè)m*n個(gè)元素的數(shù)組7.1.1自由存儲(chǔ)區(qū)的分配與釋放指針使用的要點(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)

10、成員函數(shù)。程序員無(wú)需顯式聲明它為靜態(tài)的，系統(tǒng)自動(dòng)定義為靜態(tài)的。本教材不討論new()和delete()的重載。未重載時(shí)，調(diào)用全局庫(kù)操作符new()。7.1.1自由存儲(chǔ)區(qū)內(nèi)存的分配與釋放4內(nèi)存泄漏（memory leak）和重復(fù)釋放。new與delete 是配對(duì)使用的， delete只能釋放自由存儲(chǔ)區(qū)空間。如果new返回的指針值丟失，則所分配的自由存儲(chǔ)區(qū)空間無(wú)法回收，稱內(nèi)存泄漏，同一空間重復(fù)釋放也是危險(xiǎn)的，因?yàn)樵摽臻g可能已另分配，所以必須妥善保存new返回的指針，以保證不發(fā)生內(nèi)存泄漏，也必須保證不會(huì)重復(fù)釋放自由存儲(chǔ)區(qū)內(nèi)存空間。5動(dòng)態(tài)分配的變量或?qū)ο蟮纳?。無(wú)名對(duì)象的生命期并不依賴于建立它的作用

11、域，比如在函數(shù)中建立的動(dòng)態(tài)對(duì)象在函數(shù)返回后仍可使用。但必須記住釋放該對(duì)象所占自由存儲(chǔ)區(qū)空間，并只能釋放一次，在函數(shù)內(nèi)建立，而在函數(shù)外釋放是一件很容易失控的事，往往會(huì)出錯(cuò)。 7.1.2自由存儲(chǔ)區(qū)對(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è)無(wú)名的CGoods對(duì)象；.delete pc; /先析構(gòu)，然后將內(nèi)存空間返回給自由存儲(chǔ)區(qū)；自由存儲(chǔ)區(qū)對(duì)象的生命期并不依賴于建立它的作用域，所以除非程序結(jié)束，自由存儲(chǔ)區(qū)對(duì)象（無(wú)名對(duì)象）的生命期不會(huì)到期，并且

12、需要顯式地用delete語(yǔ)句析構(gòu)該類對(duì)象，上例執(zhí)行delete語(yǔ)句時(shí)，C+自動(dòng)調(diào)用商品類的析構(gòu)函數(shù)。7.1.2自由存儲(chǔ)區(qū)對(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ù)組，則無(wú)參數(shù)，只能調(diào)用默認(rèn)的構(gòu)造函數(shù)?！纠?.3】演示自由存儲(chǔ)區(qū)對(duì)象分配和釋放。7.1.3淺復(fù)制與深復(fù)制 淺復(fù)制：默認(rèn)復(fù)制構(gòu)造函數(shù)，可用一個(gè)類對(duì)象初始化另一個(gè)類對(duì)象，稱為默認(rèn)的按成員復(fù)制，而不是對(duì)整個(gè)類對(duì)象的按位復(fù)制。這稱為淺復(fù)制。 圖7.1 淺復(fù)制 P

13、自由存儲(chǔ)區(qū)對(duì)象自由存儲(chǔ)區(qū)對(duì)象PP 復(fù)制前復(fù)制后 如果類中有一個(gè)數(shù)據(jù)成員為指針，該類的一個(gè)對(duì)象obj1中的這個(gè)指針p，指向了動(dòng)態(tài)分配的一個(gè)自由存儲(chǔ)區(qū)對(duì)象，（參見圖7.1復(fù)制前），如果用obj1按成員復(fù)制了一個(gè)對(duì)象obj2，這時(shí)obj2.p也指向同一個(gè)自由存儲(chǔ)區(qū)對(duì)象。obj1obj1obj27.1.3淺復(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;”語(yǔ)句，則如果先析構(gòu)函數(shù)obj1時(shí)，自由存儲(chǔ)區(qū)對(duì)象已經(jīng)釋放，以后再析構(gòu)obj2時(shí)出現(xiàn)了二次釋放的問題。自由存儲(chǔ)區(qū)對(duì)象PP自由存儲(chǔ)區(qū)對(duì)象 圖7.2 深復(fù)制 深復(fù)制：重新定義復(fù)制

14、的構(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ì)象。 obj1obj27.1.3淺復(fù)制與深復(fù)制【例7.4】定義復(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(stu

15、dent &s); /復(fù)制構(gòu)造函數(shù) student(); /析構(gòu)函數(shù) student & operator=(student &s); ; /復(fù)制賦值操作符檢驗(yàn)主函數(shù)和運(yùn)行結(jié)果7.1.3淺復(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ù)并非僅做初始化工作。7.1.3淺復(fù)制與深復(fù)制思考： 深入地考慮【例7.4】，如果數(shù)據(jù)域還有很多其他數(shù)據(jù)，甚至有好幾個(gè)是動(dòng)態(tài)建立的C字符

16、串，深復(fù)制是不是太復(fù)雜了？如果使用C+標(biāo)準(zhǔn)字符串string作為成員對(duì)象（聚合）是否就不需要考慮深復(fù)制了？的確是這樣的，準(zhǔn)確地說(shuō)，string類的內(nèi)部包含動(dòng)態(tài)建立字符數(shù)組的操作，其復(fù)制構(gòu)造函數(shù)是深復(fù)制。如果在student類中使用string類而不是C字符串，就不要再考慮深復(fù)制問題了。也就是說(shuō)，動(dòng)態(tài)內(nèi)存分配和深復(fù)制應(yīng)該放在一個(gè)適當(dāng)?shù)膶用嫔?，一個(gè)更單純的類定義中，如string類。在使用中，把它作為一個(gè)成員對(duì)象，就像使用string類對(duì)象那樣。7.1.3淺復(fù)制與深復(fù)制探討： 最后進(jìn)一步討論類的封裝。封裝的更高境界是在該類對(duì)象中一切都是完備的、自給自足的，不僅有數(shù)據(jù)和對(duì)數(shù)據(jù)的操作，還包括資源的動(dòng)態(tài)

17、安排和釋放。在需要時(shí)可以無(wú)條件地安全使用。標(biāo)準(zhǔn)string類模板就是典型的例子。這樣的類對(duì)象，作為另一個(gè)類的成員對(duì)象使用時(shí)，就不會(huì)出任何問題。這表明聚合實(shí)現(xiàn)了完善的封裝。 7.2 鏈表與鏈表的基本操作 線性表是最簡(jiǎn)單，最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)是n個(gè)數(shù)據(jù)元素的有限序列（a1,a2,an）。而線性表的物理結(jié)構(gòu)包括：順序表，鏈表 。7.2.1 單鏈表基本算法 7.2.3 雙向鏈表(選讀)7.2.2單鏈表類型模板 7.2.1 單鏈表基本算法單鏈表（Singly Linked list）： 每個(gè)數(shù)據(jù)元素占用一個(gè)結(jié)點(diǎn)（Node）。一個(gè)結(jié)點(diǎn)包含兩個(gè)域，一個(gè)域存放數(shù)據(jù)元素info，其數(shù)據(jù)類型由應(yīng)

18、用問題決定；另一個(gè)存放指向該鏈表中下一個(gè)結(jié)點(diǎn)的指針link。infon-1 info2 info1 info0 head圖7.3 單鏈表結(jié)構(gòu) 單鏈表的第一個(gè)結(jié)點(diǎn)的地址可通過鏈表的表頭指針head找到。借助結(jié)點(diǎn)的指針域，可以從第一個(gè)結(jié)點(diǎn)開始順序遍歷鏈表所有結(jié)點(diǎn)。 head不可丟失，否則鏈表整個(gè)丟失，內(nèi)存發(fā)生泄漏。7.2.1 單鏈表基本算法結(jié)點(diǎn)定義如下： typedef int Datatype; /數(shù)據(jù)為整型struct node Datatype info; node *link;在C/C+中允許結(jié)構(gòu)（或?qū)ο螅┏蓡T是結(jié)構(gòu)自身的指針類型，通過指針引用自身這種類型的結(jié)構(gòu)。但結(jié)構(gòu)成員決不能是結(jié)構(gòu)自身

19、類型，即結(jié)構(gòu)不能自己定義自己，這會(huì)導(dǎo)致一個(gè)無(wú)窮遞歸的定義。 7.2.1 單鏈表基本算法單鏈表的插入與刪除： 只要改變鏈中結(jié)點(diǎn)指針的值，無(wú)需移動(dòng)表中的元素，就能實(shí)現(xiàn)插入和刪除操作。插入算法有三種情況，我們希望在單鏈表中包含數(shù)據(jù)infoi的結(jié)點(diǎn)之前插入一個(gè)新元素，則infoi可在第一個(gè)結(jié)點(diǎn)，或在中間結(jié)點(diǎn)，如未找到，則把新結(jié)點(diǎn)插在鏈尾結(jié)點(diǎn)之后。 7.2.1 單鏈表基本算法newnodeinfoxinfo0info1headhead插在鏈?zhǔn)祝?首先新結(jié)點(diǎn)的link指針指向info0所在結(jié)點(diǎn)，然后，head指向新結(jié)點(diǎn)。即：newnodelink=head；/注意：鏈表操作次序非常重要head=newno

20、de；7.2.1 單鏈表基本算法infoxinfoi-1infoipnewnode插在中間： 首先用工作指針p找到指定結(jié)點(diǎn)，而讓指針q指向緊跟其后的結(jié)點(diǎn)，令infoi-1所在結(jié)點(diǎn)的link指針指向新結(jié)點(diǎn)，而后讓新結(jié)點(diǎn)的link指向infoi所在結(jié)點(diǎn)。即：newnodelink=p；/或newnodelink=qlink；可用于插入某結(jié)點(diǎn)之后qlink=newnode；7.2.1 單鏈表基本算法infox newnodepinfon-1 插在隊(duì)尾：只要工作指針p找到隊(duì)尾，即可鏈在其后：plink=newnode；newnode.link=NULL;7.2.1 單鏈表基本算法帶表頭結(jié)構(gòu)的鏈表：研究

21、以上算法，插在鏈表第一個(gè)結(jié)點(diǎn)之前與其他結(jié)點(diǎn)之前的算法有所不同。要使算法中沒有特殊者，可以給每一個(gè)鏈表加上一個(gè)表頭結(jié)點(diǎn)，如下圖所示?？毡砣缦拢篽eadinfo0Infon-1info1head 下面分別介紹帶表頭結(jié)構(gòu)的鏈表的生成鏈表算法、鏈表查找算法、插入一個(gè)結(jié)點(diǎn)的算法和刪除一個(gè)結(jié)點(diǎn)的算法。 7.2.1 單鏈表基本算法headtailpinfo1tailpinfo0tail1. 向后生成鏈表算法：node *createdown() Datatype data;Node*head,*tail,*p; head=new node; /建立鏈表頭結(jié)點(diǎn) tail=head;while(cindata)

22、/Ctrl+z結(jié)束 p=new(node);/每輸入一個(gè)數(shù)申請(qǐng)一個(gè)結(jié)點(diǎn)p-info=data; /添入數(shù)據(jù)tail-link= p; /新結(jié)點(diǎn)接到鏈尾 tail=p; /尾指針到鏈尾 tail-link=NULL;/鏈尾加空指針，表示鏈結(jié)束 return head; /返回頭指針 7.2.1 單鏈表基本算法headinfo0 PPinfo12. 向前生成鏈表算法：node *createup() node *head,*p; Datatype data; head=new node; /建立頭結(jié)點(diǎn) head-link=NULL; while(cindata) /建立的總是第一個(gè)結(jié)點(diǎn) p=new

23、 node; p-info=data; p-link= head-link ;/新結(jié)點(diǎn)放在原鏈表前方 head-link=p; /頭結(jié)點(diǎn)放新結(jié)點(diǎn)之前 return head;7.2.1 單鏈表基本算法3.鏈表查找算法(按關(guān)鍵字)查找：node *traversal(node *head,Datatype data) node *p=head-link; while(p!=NULL&p-info!=data) p=p-link; /借助工作指針順序訪問鏈表各結(jié)點(diǎn)是鏈表最基礎(chǔ)的算法return p; /p為NULL則未找到返回值為指針p，指向鏈表中找到的結(jié)點(diǎn)。4. 在單鏈表的p結(jié)點(diǎn)后插入：注意只有

24、一種情況。void insert(node *p,Datatype x) node *q=new node; q-info=x; q-link=p-link; p-link=q;7.2.1 單鏈表基本算法5. 刪除單鏈表結(jié)點(diǎn)*p后面結(jié)點(diǎn)：void del (node *p) node *q; q=p-link; p-link=q-link; delete q; /如果要把該結(jié)點(diǎn)移入另一個(gè)鏈中，則可將q返回。7.2.2 單鏈表類型模板【例7.5_h】單鏈表類模板。定義結(jié)點(diǎn)類：templateclass List;/前向引用聲明templateclass Node T info; /數(shù)據(jù)域 Nod

25、e *link; /指針域，注意結(jié)點(diǎn)類格式，尖括號(hào)中是參數(shù)名表，類模板實(shí)例化為類public: Node(); /生成頭結(jié)點(diǎn)的構(gòu)造函數(shù) Node(const T & data); /生成一般結(jié)點(diǎn)的構(gòu)造函數(shù) void InsertAfter(Node* p); /在當(dāng)前結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn) Node* RemoveAfter(); /刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn) friend class List; /以List為友元類，List可直接訪問Node的私有函數(shù);定義鏈表類: templateclass List Node *head,*tail; /鏈表頭指針和尾指針public: List(); /構(gòu)造

26、函數(shù)，生成頭結(jié)點(diǎn)(空鏈表) List(); /析構(gòu)函數(shù) void MakeEmpty(); /清空鏈表，只余表頭結(jié)點(diǎn) Node* Find(T data); /搜索數(shù)據(jù)域與data相同的結(jié)點(diǎn)，返回該結(jié)點(diǎn)的地址 int Length(); /計(jì)算單鏈表長(zhǎng)度 void PrintList(); /打印鏈表的數(shù)據(jù)域 void InsertFront(Node* p); /可用來(lái)向前生成鏈表 void InsertRear(Node* p); /可用來(lái)向后生成鏈表 void InsertOrder(Node *p); /按升序生成鏈表 Node*CreatNode(T data); /創(chuàng)建結(jié)點(diǎn)(孤立結(jié)

27、點(diǎn)) Node*DeleteNode(Node* p); ; /刪除指定結(jié)點(diǎn)7.2.2 單鏈表類型模板7.2.2 單鏈表類型模板【例7.5】由鍵盤輸入16個(gè)整數(shù)，以這些整數(shù)作為結(jié)點(diǎn)數(shù)據(jù)，生成兩個(gè)鏈表，一個(gè)向前生成，一個(gè)向后生成，輸出兩個(gè)表。然后給出一個(gè)整數(shù)在一個(gè)鏈表中查找，找到后刪除它，再輸出該表。清空該表，再按升序生成鏈表并輸出。在本例中程序只需調(diào)用類模板中的成員函數(shù)就可以完成所有鏈表操作。【例7.6】以學(xué)生類作為鏈表的數(shù)據(jù)類，完成學(xué)生檔案的管理。7.2.2 單鏈表類型模板討論復(fù)制構(gòu)造函數(shù)： 在本例中沒有給出Node類的復(fù)制構(gòu)造函數(shù)，并非可以使用默認(rèn)的復(fù)制構(gòu)造函數(shù)，而是避開了所有使用它的情況

28、，本例中函數(shù)的參數(shù)和返回值僅使用指向Node的指針，類定義中也沒有用復(fù)制方式初始化。定義復(fù)制構(gòu)造函數(shù)與類的實(shí)際意義和使用方式有關(guān)，并非只是深復(fù)制和淺復(fù)制的問題。 通常對(duì)Node類復(fù)制的結(jié)果應(yīng)是一個(gè)孤立結(jié)點(diǎn)：template Node:Node(Node & node)info=node.data;link=NULL;link域值為NULL。該函數(shù)與Node的有參構(gòu)造函數(shù)功能基本相同?？紤]到函數(shù)的參數(shù)和返回值僅使用指向Node的指針，定義復(fù)制構(gòu)造函數(shù)已經(jīng)沒有實(shí)際意義 單鏈表的復(fù)制構(gòu)造函數(shù)和復(fù)制運(yùn)算符是一個(gè)復(fù)雜的算法，與前文所編的復(fù)制構(gòu)造函數(shù)和復(fù)制運(yùn)算符構(gòu)造相去甚遠(yuǎn)了。7.2.3 雙向鏈表（選讀）

29、 雙向鏈表引入：考慮單鏈表只能找后繼。如要找前驅(qū)，必須從表頭開始搜索。為了克服這一缺點(diǎn)，可采用雙向鏈表（Double Linked List)。雙向鏈表的結(jié)點(diǎn)有三個(gè)域：左鏈接指針（llink)，數(shù)據(jù)域（info)，右鏈接指針域(rlink)。雙向鏈表經(jīng)常采用帶頭結(jié)點(diǎn)的循環(huán)鏈表方式。 info0 infon-1. info1head(a) 非空表head(b)空表7.2.3 雙向鏈表（選讀）雙向鏈表的訪問：假設(shè)指針p指向雙向循環(huán)鏈表的某一個(gè)結(jié)點(diǎn)，那么，p-llink指示P所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，p-rlink指示后繼結(jié)點(diǎn)。p- llink-rlink指示本結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的后繼結(jié)點(diǎn)，即本結(jié)點(diǎn)，間接訪問

30、符-可以連續(xù)使用。pllink rlinkrlinkllink rlink前驅(qū)結(jié)點(diǎn) llink 本結(jié)點(diǎn) 后繼結(jié)點(diǎn) 間接訪問符的使用【例7.7】雙向鏈表類模板和結(jié)點(diǎn)類模板。7.3 棧與隊(duì)列的基本操作及其應(yīng)用 棧和隊(duì)都是特殊的線性表，限制存取位置的線性結(jié)構(gòu)，可以由順序表實(shí)現(xiàn)，也可以由鏈表實(shí)現(xiàn)。 7.3.1 棧 7.3.3隊(duì)列 7.3.2 棧的應(yīng)用（選讀） 7.3.1 棧棧的基本概念： 棧定義為只允許在表的一端進(jìn)行插入和刪除的線性表。允許進(jìn)行插入和刪除的一端叫做棧頂(top)，而另一端叫棧底(bottom)。 棧中沒有任何元素時(shí)，稱為空棧。 進(jìn)棧時(shí)最先進(jìn)棧的在最下面，最后的在最上面，后來(lái)居上。而出棧

31、時(shí)順序相反，最后進(jìn)棧的最先出棧，而最先進(jìn)棧的最后出棧。所以棧又稱作后進(jìn)先出（LIFO：Last In First Out）的線性表。 棧可以用順序表實(shí)現(xiàn)，稱順序棧；也可以用鏈表實(shí)現(xiàn)，稱鏈棧。7.3.1 棧棧的基本操作： 參見下圖，設(shè)給定棧s=(a0，a1，an-1)，稱a0為棧底，an-1為棧頂。進(jìn)棧時(shí)最先進(jìn)棧的a0在最下面，an-1在最上面。而出棧時(shí)順序相反，最后進(jìn)棧的an-1最先出棧，而最先進(jìn)棧的a0最后出棧。a0an-2a1an-1bottom進(jìn)棧toptoptoptoptop出棧圖示為順序棧。其中棧底bottom是指向棧數(shù)據(jù)區(qū)的下一單元，這樣判斷是否為空棧會(huì)更方便，只需top與bott

32、om相同就是空棧。通常只有棧頂與操作有關(guān)。7.3.1 棧templateclass Stack int top; /棧頂指針（下標(biāo)） T *elements; /動(dòng)態(tài)建立的元素 int maxSize; /棧最大容納的元素個(gè)數(shù)public: Stack(int=20); /構(gòu)造函數(shù)，棧如不指定大小，設(shè)為20元素 Stack()delete elements; void Push(const T &data); /壓棧 T Pop(); /彈出，top- T GetElem(int i); /取數(shù)據(jù)，top不變 void MakeEmpty()top= -1; /清空棧 bool IsEmpty

33、() constreturn top= -1; /判?？?bool IsFull() constreturn top=maxSize-1; /判棧滿 void PrintStack(); ; /輸出棧內(nèi)所有數(shù)據(jù)【例7.8】順序棧的類模板：7.3.1 棧void main()int i,a10=0,1,2,3,4,5,6,7,8,9,b10;Stack istack(10);for(i=0;i10;i+) istack.Push(ai);if(istack.IsFull() cout棧滿endl;istack.PrintStack();for(i=0;i10;i+) bi=istack.Pop(

34、);if(istack.IsEmpty() cout棧空endl;for(i=0;i10;i+) coutbit; /注意先進(jìn)后出coutendl;istack.Pop(); /下溢出7.3.1 ?！纠?.9_h】鏈棧的結(jié)點(diǎn)類模板： templateclass Node /鏈棧結(jié)點(diǎn)類模板T info;Node *link;public:Node(T data=0,Node *next=NULL)info=data;link=next;friend class Stack;top 鏈棧7.3.1 棧鏈棧類模板(無(wú)頭結(jié)點(diǎn)鏈表)：templateclass Stack /鏈棧類模板Node *top

35、; /棧頂指針public:Stack()top=NULL;Stack(); /析構(gòu)函數(shù)void Push(const T &data); /壓棧T Pop(); /彈出T GetTop(); /取棧頂元素void MakeEmpty(); /清空棧bool IsEmpty()return top=NULL;7.3.2 棧的應(yīng)用（選讀）順序棧和鏈棧邏輯功能是一樣，盡管這里兩個(gè)棧模板的成員函數(shù)功能選擇稍有出入，因?yàn)轫樞驐？梢噪S機(jī)訪問其中的元素，而鏈棧只能順序訪問，但邏輯上完全可以做到一樣（物理結(jié)構(gòu)不同）。順序棧必須先開一定大小內(nèi)存空間，執(zhí)行起來(lái)簡(jiǎn)單，速度快，可能溢出。鏈棧內(nèi)存空間隨用隨開，不會(huì)溢

36、出，但執(zhí)行復(fù)雜（不斷地動(dòng)態(tài)分配），速度慢。 順序棧和鏈棧比較：7.3.2 棧的應(yīng)用（選讀） ?？捎糜诒磉_(dá)式的計(jì)算。現(xiàn)考慮最簡(jiǎn)單的+、-、*、/四個(gè)運(yùn)算符和結(jié)束符組成的算術(shù)表達(dá)式，只有兩個(gè)優(yōu)先級(jí)，先*/，后+-。 為實(shí)現(xiàn)運(yùn)算符的優(yōu)先級(jí)，采用兩個(gè)棧：一個(gè)數(shù)棧，一個(gè)運(yùn)算符棧。數(shù)棧暫存操作數(shù)，運(yùn)算符棧暫存運(yùn)算符。棧的使用(表達(dá)式運(yùn)算) ： NcbaOat1deNat1deOONt1at2t1at2t3aNt3aNOOb*c-t1d/e-t2t1-t2-t3a+t3-t4N：數(shù)棧 O：運(yùn)算符 (a) (b) (c) (d) (e)設(shè)有：a+b*c-d/e=；參見上圖。從左向右掃描算術(shù)表達(dá)式，遇到操作數(shù)，

37、壓入數(shù)棧；遇到運(yùn)算符，則與運(yùn)算符棧棧頂?shù)倪\(yùn)算符比較優(yōu)先級(jí)，若新的運(yùn)算符優(yōu)先級(jí)高，或運(yùn)算符?？眨瑒t壓棧。否則將棧頂運(yùn)算符出棧，與數(shù)字棧出棧的兩個(gè)數(shù)據(jù)進(jìn)行運(yùn)算，結(jié)果壓入數(shù)棧，再將新運(yùn)算符壓棧。繼續(xù)掃描，直到遇到號(hào)，掃描結(jié)束。棧中數(shù)據(jù)繼續(xù)按前面規(guī)則出棧。 7.3.2 棧的應(yīng)用（選讀）【例7.9】模擬簡(jiǎn)單計(jì)算器，該計(jì)算器只認(rèn)+ - * / 四個(gè)運(yùn)算符，輸入為整數(shù)。表達(dá)式結(jié)束符使用號(hào)，清空棧用c字符。使用z字符表示結(jié)束。簡(jiǎn)易計(jì)算器類定義：class Calculator Stack Nstack; /使用鏈棧 Stack Ostack;public: Calculator(void); void Cal

38、(void); /計(jì)算器運(yùn)算程序 void GetTwoNum(int &Num1,int &Num2); /取數(shù) void Compute(char Opr); /讀算式 void Clear(void); ; /清除7.3.3 隊(duì)列 隊(duì)列的基本概念：隊(duì)列(Queue)也是一種限定存取位置的線性表。它只允許在表的一端插入，而在另一端刪除。允許插入的一端稱為隊(duì)尾(rear)，允許刪除的一端叫做隊(duì)頭(front)。每次在隊(duì)尾加入新元素，加入稱為進(jìn)隊(duì)，刪除稱為出隊(duì)。隊(duì)列的這種特性正好與棧相反，叫做先進(jìn)先出FIFO(First In First Out)。 a0a1a2an-1front元素移動(dòng)方向

39、rear圖7.15隊(duì)列 圖7.15所示隊(duì)列隨隊(duì)尾加入元素，隊(duì)尾(rear)不斷向后移；而隨隊(duì)頭元素的出隊(duì)，則隊(duì)頭(front)也不斷后移，即位置在變（如要位置不變，移動(dòng)元素工作量也太大）。 7.3.2 隊(duì)列rearfrontADCABDECFHGBCD進(jìn)隊(duì)A進(jìn)隊(duì)空隊(duì)DCAB出隊(duì)EFGH進(jìn)隊(duì)rearfrontrearrearrearfrontfrontfront圖7.16 順序隊(duì)列的插入和刪除 由圖可見：空隊(duì)時(shí)指針（下標(biāo)）front和rear在一起都指向隊(duì)前方，當(dāng)有元素進(jìn)隊(duì)，則rear后移；有元素出隊(duì)，則front后移，最后分配給隊(duì)的前端不再被利用。 順序表隊(duì)列的缺點(diǎn)：7.3.2 隊(duì)列順序表隊(duì)列

40、的改進(jìn)：邏輯上的循環(huán)隊(duì)列 注意，空隊(duì)時(shí)rear=front，滿隊(duì)時(shí)必須空一個(gè)位置 7.3.2 隊(duì)列 循環(huán)隊(duì)列浪費(fèi)一個(gè)位置好像太可惜，特別在該位置中存放一個(gè)很大的對(duì)象時(shí)。實(shí)際上對(duì)象很大時(shí)，總是由索引（指針）來(lái)排隊(duì)。若想利用這個(gè)空間，必然加一個(gè)標(biāo)志來(lái)表示隊(duì)空/隊(duì)滿，進(jìn)隊(duì)出隊(duì)都要判斷，使用上更不方便。 用鏈表實(shí)現(xiàn)隊(duì)列無(wú)此問題 【例7.10】順序存儲(chǔ)方式的循環(huán)隊(duì)列類模板?！纠?.11】鏈隊(duì)類模板。鏈?zhǔn)壮鲫?duì)，鏈尾入隊(duì)。無(wú)鏈表頭結(jié)點(diǎn)方式。7.4二叉樹（選讀） 樹形結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)，樹和二叉樹是常用的樹形結(jié)構(gòu)。 7.4.2 二叉樹的遍歷 7.4.1二叉樹的概念 7.4.3 排序二叉樹 7.4.1二

41、叉樹的概念 （選讀） 樹（Tree）是由n（n0）個(gè)結(jié)點(diǎn)組成的有限集合。如n=0，稱為空樹。非空樹有一個(gè)特定的結(jié)點(diǎn)，它只有直接后繼，沒有直接前驅(qū)，稱之為根（root）。除根以外的其它結(jié)點(diǎn)劃分為m（m0）個(gè)互不相交的有限集合T0，T1，Tm-1，每個(gè)集合又是一棵樹，稱為根的子樹（subtree）。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。這是一個(gè)遞歸方法定義的數(shù)據(jù)結(jié)構(gòu)。 樹的概念：7.4.1二叉樹的概念（選讀） ABCDEFGIHJLKONM0層1層2層3層深度圖7.18 樹的示意圖 結(jié)點(diǎn)，包括數(shù)據(jù)項(xiàng)和多個(gè)指針項(xiàng)，指針項(xiàng)數(shù)目并不固定，且無(wú)次序。結(jié)點(diǎn)的度，結(jié)點(diǎn)所擁有的子樹數(shù)

42、量。葉結(jié)點(diǎn)，度為0的結(jié)點(diǎn)，如G，I，J，K，L，M，N，O結(jié)點(diǎn)。分支結(jié)點(diǎn)，度1的結(jié)點(diǎn)。孩子結(jié)點(diǎn)，若結(jié)點(diǎn)x有子樹，則子樹根結(jié)點(diǎn)即為x的孩子結(jié)點(diǎn)。樹的術(shù)語(yǔ)：7.4.1二叉樹的概念（選讀） ABCDEFGIHJLKONM0層1層2層3層深度圖7.18 樹的示意圖 雙親結(jié)點(diǎn)，若結(jié)點(diǎn)x有孩子，它即為孩子的雙親。兄弟結(jié)點(diǎn)，同一雙親的結(jié)點(diǎn)互稱為兄弟。結(jié)點(diǎn)的層次，從根到該結(jié)點(diǎn)所經(jīng)路徑上的分支條數(shù)。樹的深度,樹中結(jié)點(diǎn)的層次數(shù)。樹的度，樹中結(jié)點(diǎn)度的最大值。 樹的術(shù)語(yǔ)：7.4.1二叉樹的概念（選讀） 二叉樹（Binary Tree）是另一種獨(dú)立的樹形結(jié)構(gòu)。二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或?yàn)榭眨蚴怯梢粋€(gè)根結(jié)點(diǎn)及

43、兩棵樹分別稱為左子樹和右子樹的（注意有左右之分）互不相交的二叉樹組成，其中左右子樹分別可以為空子樹或均為空樹。這也是一個(gè)遞歸的定義。二叉樹的特點(diǎn)是：每個(gè)結(jié)點(diǎn)最多兩個(gè)孩子，并且子樹有左右之分。二叉樹的基本性質(zhì)：1二叉樹的第i層上最多有2i-1(i=1)個(gè)結(jié)點(diǎn)；2深度為h的二叉樹中最多有2h-1個(gè)結(jié)點(diǎn)；3在任一棵二叉樹中，有n0個(gè)葉子結(jié)點(diǎn)，有n2個(gè)度為2的 結(jié)點(diǎn)，則有n0=n2+1。樹的概念：7.4.1二叉樹的概念（選讀） 【例7.12】畫出有三個(gè)結(jié)點(diǎn)的所有二叉樹。解：結(jié)果見圖7.19，共5種。圖7.19 5種不同的三結(jié)點(diǎn)二叉樹 7.4.1二叉樹的概念（選讀） 滿二叉樹和完全二叉樹：分別如圖7.2

44、0和圖7.21，完全二叉樹已有的結(jié)點(diǎn)排序與滿二叉樹相同。 123456798101114131215圖7.20 滿二叉樹 12345679810圖7.21 完全二叉樹 7.4.1二叉樹的概念（選讀） 下面給出鏈?zhǔn)絻?chǔ)存方式的二叉樹。每個(gè)結(jié)點(diǎn)有三個(gè)域：數(shù)據(jù)域、左孩子指針和右孩子指針，見圖7.22。 lchildrchildinfo圖7.22 二叉樹結(jié)點(diǎn) 7.4.1二叉樹的概念（選讀） 二叉樹類結(jié)點(diǎn)類模板定義：templateclass BinaryTree;templateclass Node Node *lchild,*rchild; T info;public: Node() lchild=N

45、ULL; rchild=NULL; Node(T data,Node *left=NULL , Node *right=NULL) info=data; lchild=left; rchild=right; 7.4.1二叉樹的概念（選讀） T Getinfo()return info; /取得結(jié)點(diǎn)數(shù)據(jù) void setinfo(const T &data)info=data; /修改結(jié)點(diǎn)數(shù)據(jù) Node *Getleft()return lchild; /取得左子樹 Node *Getright()return rchild; /取得右子樹 void setleft(Node *left)lch

46、ild=left; /設(shè)置左指針 void setrightNode *right)rchild=right; /設(shè)置右指針 friend class BinaryTree; /二叉樹類說(shuō)明為友元類7.4.2 二叉樹的遍歷（選讀） 二叉樹的遍歷(binary tree traversal)：定義：遵從某種次序，查巡二叉樹的所有結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)都被訪問一次，而且僅訪問一次。所謂“訪問”指對(duì)結(jié)點(diǎn)施行某些操作，但不破壞它原來(lái)的數(shù)據(jù)結(jié)構(gòu)。遍歷二叉樹有不同次序，規(guī)定先左后右，令L，R，V分別代表遍歷一個(gè)結(jié)點(diǎn)的左右子樹和訪問該結(jié)點(diǎn)的操作，有三種方式：前序遍歷（VLR）中序遍歷（LVR）后序遍歷（LRV） 7

47、.4.2 二叉樹的遍歷（選讀） 遍歷實(shí)例：前序遍歷訪問次序?yàn)锳BDEGCFH。 圖7.23 二叉樹遍歷 中序遍歷結(jié)果為D B G E A F H C。后序遍歷結(jié)果為D G E B H F C A。 7.4.2 二叉樹的遍歷（選讀） 【例7.13】二叉樹類模板（其中二叉樹生成借用二叉排序樹，見下節(jié)）。特別注意插入結(jié)點(diǎn)時(shí)，第二參數(shù)為指針的引用！否則不能建立樹。為什么？請(qǐng)讀者自己思考。本例采用簡(jiǎn)單的接口函數(shù)，而把較復(fù)雜的算法作為私有函數(shù)。 templateclass BinaryTree Node *root; /二叉樹的根指針 void InOrder(Node *Current); /中序遍歷

48、void PreOrder(Node *Current); /前序遍歷 void PostOrder(Node *Current); /后序遍歷 void Insert(const T &data,Node * &b); /插入結(jié)點(diǎn)，參數(shù)為引用！ void Destory(Node * Current); /刪除樹7.4.2 二叉樹的遍歷（選讀） public: BinaryTree()root=NULL;/空樹構(gòu)造函數(shù) BinaryTree()Destory(root);/析構(gòu)函數(shù) void Creat(T* data,int n); /建立（排序）二叉樹 void InOrder()InO

49、rder(root); /中序遍歷，公有函數(shù)為接口 void PreOrder()PreOrder(root);/前序遍歷，公有函數(shù)為接口 void PostOrder()PostOrder(root); /后序遍歷，公有函數(shù)為接口;檢驗(yàn)主函數(shù)7.4.2 二叉樹的遍歷（選讀） 【例7.14】某二叉樹先序遍歷為ABCEFDGHIJK，中序遍歷為ECFBDGAIHJK繪出該二叉樹。 ABCDEFGHIJK圖7.24 例7.14二叉樹 按同樣方法推出A的右子樹。結(jié)果如圖7.23?？梢宰C明已知先序和中序訪問次序可以唯一確定一棵二叉樹。 解：由先序知A為根結(jié)點(diǎn)，而由中序知E C F B D G為左子樹，

50、I H J K為右子樹。由先序中的B C E F D G知B為左子樹根結(jié)點(diǎn)，由中序中的E C F B D G知E C F為其左子樹，而DG為右子樹。再由先序C E F知C為左子樹根結(jié)點(diǎn)，由中序E C F知E為C左子樹，F(xiàn)為的右子樹。再由先序D G知，D為B的右子樹根結(jié)點(diǎn)，由中序D G知G為D的右子樹。7.4.3 排序二叉樹 （選讀） 二叉排序樹（Binary Sorting Tree）又稱二叉搜索樹（Binary Search Tree），是一種特殊結(jié)構(gòu)的二叉數(shù)，作為一種排序和查找的手段，對(duì)應(yīng)有序表的對(duì)半查找，通常亦被稱為數(shù)表。其定義也是遞歸的。二叉排序樹的定義： 二叉排序樹或者是空樹或者是具

51、有下述性質(zhì)的二叉數(shù)，其左子樹上所有結(jié)點(diǎn)的數(shù)據(jù)值均小于根結(jié)點(diǎn)的數(shù)據(jù)值；右子樹上所有結(jié)點(diǎn)的數(shù)據(jù)值均大于等于根結(jié)點(diǎn)的數(shù)據(jù)值，左子樹和右子樹又各是一棵二叉排序樹。7.4.3 排序二叉樹（選讀） 二叉排序樹用中序遍歷就可以得到由小到大的有序序列，如圖7.24可得有序序列8，10，11，12，15，16，18，22，24，26，29。 101826812222911241615圖7.24 二叉排序樹例 二叉排序樹的遍歷：二叉排序樹生成算法：對(duì)任意一組數(shù)據(jù)元素序列a0，a1，a2，an-1。要生成二叉排序樹的過程為：1. 令a0為二叉樹的根結(jié)點(diǎn)。2.若a1a0，令a1為a0左子樹的根結(jié)點(diǎn)，否則a1為a0右子

52、樹的根結(jié)點(diǎn)。3. 如ai小于根結(jié)點(diǎn)，則去左子樹，否則去右子樹，按此法查找，直到成為空樹，則安放此位置。這步就是插入算法。 7.4.3 排序二叉樹（選讀） 7.4.3 排序二叉樹（選讀） templateNode* BinaryTree:Find(const T &data,Node *b) if(b!=NULL)Node *temp=b;while(temp!=NULL)if(temp-info=data)return temp;if(temp-inforchild;else temp=temp-lchild; return NULL;【例7.15】排序二叉樹查找函數(shù)。算法：用中序遍歷即可，但

53、遞歸慢，下面為迭代查找算法。第七章 動(dòng)態(tài)內(nèi)存分配與數(shù)據(jù)結(jié)構(gòu)完謝謝！7.1.1自由存儲(chǔ)區(qū)內(nèi)存的分配與釋放【例7.1】【例7.1】動(dòng)態(tài)數(shù)組的建立與撤銷#include #include using namespace std；int main()int n;char *pc;cout請(qǐng)輸入動(dòng)態(tài)數(shù)組的元素個(gè)數(shù)n; /在運(yùn)行時(shí)確定，可輸入25pc=new charn;strcpy(pc, 自由存儲(chǔ)區(qū)內(nèi)存的動(dòng)態(tài)分配);coutpcendl;delete pc;/釋放pc所指向的n個(gè)字符的內(nèi)存空間return 0;7.1.1自由存儲(chǔ)區(qū)內(nèi)存的分配與釋放【例7.2】 【例7.2】 動(dòng)態(tài)創(chuàng)建和刪除一個(gè)m*n個(gè)元

54、素的數(shù)組。采用指針數(shù)組方式來(lái)完成二維數(shù)組的動(dòng)態(tài)創(chuàng)建。(選讀)int m=4,n=6; /行數(shù)與列數(shù)二維數(shù)組的動(dòng)態(tài)創(chuàng)建：int main() double *data; int i,j; data = new double*m; /建立指向組成二維數(shù)組各行的指針數(shù)組 if (data ) = 0) cout Could not allocate. Bye .; return -1; for(j=0;jm;j+) dataj = new doublen; /建立各行 if (dataj = 0) cout Could not allocate. Bye .; return -1; 7.1.1自由存

55、儲(chǔ)區(qū)內(nèi)存的分配與釋放【例7.2】 for (i=0;im;i+) for (j=0;jn;j+) dataij=i*n+j; /數(shù)組元素賦值 display(data);/略 de_allocate(data); return 0; 二維數(shù)組的撤銷與內(nèi)存釋放：void de_allocate(double *data) int i; for (i=0;im;i+) delete datai; /注意撤銷次序，與設(shè)置相反 delete data; 7.1.2自由存儲(chǔ)區(qū)對(duì)象與構(gòu)造函數(shù)【例7.3】類說(shuō)明：class CGoods string Name; int Amount; float Pric

56、e; float Total_value;public: CGoods()cout調(diào)用默認(rèn)構(gòu)造函數(shù)endl; CGoods(string name,int amount ,float price)cout調(diào)用三參數(shù)構(gòu)造函數(shù)endl;Name=name; Amount=amount;Price=price; Total_value=price*amount; CGoods() cout調(diào)用析構(gòu)函數(shù)endl;【例7.3】演示自由存儲(chǔ)區(qū)對(duì)象分配和釋放。7.1.2自由存儲(chǔ)區(qū)對(duì)象與構(gòu)造函數(shù)【例7.3】使用：int main() int n; CGoods *pc,*pc1,*pc2; pc=new CG

57、oods(“夏利2000”，10，118000); /調(diào)用三參數(shù)構(gòu)造函數(shù) pc1=new CGoods(); /調(diào)用默認(rèn)構(gòu)造函數(shù) cout輸入商品類數(shù)組元素?cái)?shù)n; pc2=new CGoodsn; /動(dòng)態(tài)建立數(shù)組，不能初始化，調(diào)用n次默認(rèn)構(gòu)造函數(shù) delete pc; delete pc1; delete pc2; return 0;例7.4 實(shí)現(xiàn)深復(fù)制默認(rèn)構(gòu)造函數(shù)：student:student() coutConstructor; pName=NULL; cout默認(rèn)“endl;帶參數(shù)構(gòu)造函數(shù)：student:student(char *pname) coutConstructor; if

58、(pName=new charstrlen(pname)+1) strcpy(pName,pname); coutpNameendl;例7.4 實(shí)現(xiàn)深復(fù)制復(fù)制構(gòu)造函數(shù)：student:student(student &s) coutCopy Constructor; if(s.pName) if(pName=new charstrlen(s.pName)+1) strcpy(pName,s.pName); else pName=NULL; coutpNameendl;析構(gòu)函數(shù)：student:student() coutDestructorpNameendl; if(pName) pName0

59、=0; delete pName; /釋放字符串例7.4 實(shí)現(xiàn)深復(fù)制復(fù)制賦值操作符：student & student:operator=(student &s) coutCopy Assign operator; delete pName;/如原來(lái)已分配，應(yīng)先撤銷，再重分配 if(s.pName) /否則會(huì)發(fā)生內(nèi)存泄漏 if(pName=new charstrlen(s.pName)+1) strcpy(pName,s.pName); else pName=NULL; coutpNameendl; return *this;int main(void)student s1(范英明),s2(沈

60、俊),s3;student s4=s1;s3=s2;return 0;例7.4 實(shí)現(xiàn)深復(fù)制例7.5_h 單鏈表類型模板template Node:Node()link=NULL;template Node:Node(const T & data)info=data;link=NULL; templatevoid Node:InsertAfter(Node* p)p-link=link;link=p; templateNode* Node:RemoveAfter()Node* tempP=link;if(link=NULL) tempP=NULL; /已在鏈尾,后面無(wú)結(jié)點(diǎn)else link=te