動(dòng)態(tài)內(nèi)存分配第一頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.1堆內(nèi)存分配

7.5MFC對(duì)象和Windows對(duì)象的關(guān)系

7.4二叉樹

7.3棧與隊(duì)列的基本操作及其應(yīng)用

7.2鏈表與鏈表的基本操作

第七章動(dòng)態(tài)內(nèi)存分配

7.6圖書流通管理系統(tǒng)設(shè)計(jì)——鏈表類應(yīng)用

第二頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.1

堆內(nèi)存分配

堆內(nèi)存的分配與釋放

7.1.2堆對(duì)象與構(gòu)造函數(shù)

7.1.3淺拷貝與深拷貝

通常定義變量（或?qū)ο螅?，編譯器在編譯時(shí)都可以根據(jù)該變量（或?qū)ο螅┑念愋椭浪鑳?nèi)存空間的大小，從而系統(tǒng)在適當(dāng)?shù)臅r(shí)候?yàn)樗麄兎峙浯_定的存儲(chǔ)空間。這種內(nèi)存分配稱為靜態(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)行。第三頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.1.1堆內(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類型名(初始化式)；delete指針名;

new運(yùn)算符返回的是一個(gè)指向所分配類型變量（對(duì)象）的指針。對(duì)所創(chuàng)建的變量或?qū)ο螅际峭ㄟ^(guò)該指針來(lái)間接操作的，而動(dòng)態(tài)創(chuàng)建的對(duì)象本身沒(méi)有名字。

第四頁(yè)，共一百二十二頁(yè)，2022年，8月28日

7.1.1堆內(nèi)存的分配與釋放一般定義變量和對(duì)象時(shí)要用標(biāo)識(shí)符命名，稱命名對(duì)象，而動(dòng)態(tài)的稱無(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=newint(0);它與下列代碼序列大體等價(jià)：intival=0;int*pi=&ival;只是pi現(xiàn)在所指向的變量是由庫(kù)操作符new()分配的，位于程序的堆區(qū)中，并且該對(duì)象未命名。

第五頁(yè)，共一百二十二頁(yè)，2022年，8月28日

7.1.1堆內(nèi)存的分配與釋放堆０Ｐi下面看演示：１．用初始化式(initializer)來(lái)顯式初始化int*pi=newint(0);２．當(dāng)pi生命周期結(jié)束時(shí)，必須釋放pi所指向的目標(biāo)：

deletepi;注意這時(shí)釋放了pi所指的目標(biāo)的內(nèi)存空間，也就是撤銷了該目標(biāo)，稱動(dòng)態(tài)內(nèi)存釋放（dynamicmemorydeallocation），但指針pi本身并沒(méi)有撤銷，該指針?biāo)純?nèi)存空間并未釋放。第六頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.1.1堆內(nèi)存的分配與釋放

對(duì)于數(shù)組進(jìn)行動(dòng)態(tài)分配的格式為：指針變量名=new類型名[下標(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)自知。即使寫了，編譯器也忽略。請(qǐng)注意“下標(biāo)表達(dá)式”不是常量表達(dá)式，即它的值不必在編譯時(shí)確定，可以在運(yùn)行時(shí)確定。第七頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.1.1堆內(nèi)存的分配與釋放【例7.1】動(dòng)態(tài)數(shù)組的建立與撤銷#include<iostream.h>#include<string.h>voidmain(){ intn; char*pc; cout<<"請(qǐng)輸入動(dòng)態(tài)數(shù)組的元素個(gè)數(shù)"<<endl; cin>>n;

//在運(yùn)行時(shí)確定，可輸入17

pc=newchar[n]; strcpy(pc,"堆內(nèi)存的動(dòng)態(tài)分配"); cout<<pc<<endl; delete[]pc;//釋放pc所指向的n個(gè)字符的內(nèi)存空間

return;

}第八頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.1.1堆內(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è)字符的空間釋放，而用deletepc則只釋放了一個(gè)字符的空間；2.如果有一個(gè)char*pc1，令pc1=p，同樣可用delete[]pc1來(lái)釋放該空間。盡管C++不對(duì)數(shù)組作邊界檢查，但在堆空間分配時(shí)，對(duì)數(shù)組分配空間大小是紀(jì)錄在案的。3.沒(méi)有初始化式（initializer），不可對(duì)數(shù)組初始化。

第九頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.1.1堆內(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=newfloat[15][30][20];

//建立由15個(gè)30*20數(shù)組組成的數(shù)組；注意cp等效于三維數(shù)組名，但沒(méi)有指出其邊界，即最高維的元素?cái)?shù)量，就像指向字符的指針即等效一個(gè)字符串,不要把指向字符的指針，說(shuō)成指向字符串的指針。這與數(shù)組的嵌套定義相一致。第十頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.1.1堆內(nèi)存的分配與釋放比較：float(*cp)[30][20];

//三級(jí)指針float(*bp)[20];//二級(jí)指針cp=newfloat[1][20][30];bp=newfloat[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ù)組第十一頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.1.1堆內(nèi)存的分配與釋放【例7.2】動(dòng)態(tài)創(chuàng)建和刪除一個(gè)m*n個(gè)元素的數(shù)組。采用指針數(shù)組方式來(lái)完成二維數(shù)組的動(dòng)態(tài)創(chuàng)建。constintm=4;

//行數(shù)constintn=6;

//列數(shù)先看二維數(shù)組的動(dòng)態(tài)創(chuàng)建：voidmain(){double**data;

data=newdouble*[m];

//設(shè)置行

if((data)==0){cout<<"Couldnotallocate.Bye...";exit(-1);}for(intj=0;j<m;j++){

data[j]=newdouble[n];

//設(shè)置列

if(data[j]==0){cout<<"Couldnotallocate.Bye...";exit(-1);}}第十二頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.1.1堆內(nèi)存的分配與釋放

for(inti=0;i<m;i++)for(intj=0;j<n;j++)data[i][j]=i*n+j;

//初始化數(shù)組元素

display(data);de_allocate(data);return;}再看二維數(shù)組的撤銷與內(nèi)存釋放：voidde_allocate(double**data){for(inti=0;i<m;i++)delete[]data[i];//注意撤銷次序，先列后行，與設(shè)置相反

delete[]data;}

第十三頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.1.1堆內(nèi)存的分配與釋放指針使用的幾個(gè)問(wèn)題：1.

動(dòng)態(tài)分配失敗。返回一個(gè)空指針（NULL），表示發(fā)生了異常，堆資源不足，分配失敗。2.指針刪除與堆空間釋放。刪除一個(gè)指針p（deletep;）實(shí)際意思是刪除了p所指的目標(biāo)（變量或?qū)ο蟮龋尫帕怂嫉亩芽臻g，而不是刪除ｐ本身，釋放堆空間后，ｐ成了空懸指針。第十四頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.1.1堆內(nèi)存的分配與釋放３．內(nèi)存泄漏（memoryleak）和重復(fù)釋放。new與delete是配對(duì)使用的，delete只能釋放堆空間。如果new返回的指針值丟失，則所分配的堆空間無(wú)法回收，稱內(nèi)存泄漏，同一空間重復(fù)釋放也是危險(xiǎn)的，因?yàn)樵摽臻g可能已另分配，所以必須妥善保存new返回的指針，以保證不發(fā)生內(nèi)存泄漏，也必須保證不會(huì)重復(fù)釋放堆內(nèi)存空間。４．動(dòng)態(tài)分配的變量或?qū)ο蟮纳?。無(wú)名對(duì)象的生命期并不依賴于建立它的作用域，比如在函數(shù)中建立的動(dòng)態(tài)對(duì)象在函數(shù)返回后仍可使用。我們也稱堆空間為自由空間（freestore）就是這個(gè)原因。但必須記住釋放該對(duì)象所占堆空間，并只能釋放一次，在函數(shù)內(nèi)建立，而在函數(shù)外釋放是一件很容易失控的事，往往會(huì)出錯(cuò)。

第十五頁(yè)，共一百二十二頁(yè)，2022年，8月28日

堆對(duì)象與構(gòu)造函數(shù)

通過(guò)new建立的對(duì)象要調(diào)用構(gòu)造函數(shù)，通過(guò)delete刪除對(duì)象也要調(diào)用析構(gòu)函數(shù)。CGoods*pc;pc=newCGoods;

//分配堆空間，并構(gòu)造一個(gè)無(wú)名的CGoods對(duì)象；…….deletepc;

//先析構(gòu)，然后將內(nèi)存空間返回給堆；堆對(duì)象的生命期并不依賴于建立它的作用域，所以除非程序結(jié)束，堆對(duì)象（無(wú)名對(duì)象）的生命期不會(huì)到期，并且需要顯式地用delete語(yǔ)句析構(gòu)堆對(duì)象，上面的堆對(duì)象在執(zhí)行delete語(yǔ)句時(shí)，C++自動(dòng)調(diào)用其析構(gòu)函數(shù)。第十六頁(yè)，共一百二十二頁(yè)，2022年，8月28日

堆對(duì)象與構(gòu)造函數(shù)classCGoods{charName[21];intAmount;floatPrice;floatTotalvalue;public:CGoods(){};//缺省構(gòu)造函數(shù)。

CGoods(char*name,intamount,floatprice){strcpy(Name,name);Amount=amount;Price=price;Total_value=price*amount;

}

……}正因?yàn)闃?gòu)造函數(shù)可以有參數(shù)，所以new后面類（class）類型也可以有參數(shù)。這些參數(shù)即構(gòu)造函數(shù)的參數(shù)。但對(duì)創(chuàng)建數(shù)組，則無(wú)參數(shù)，并只調(diào)用缺省的構(gòu)造函數(shù)。見(jiàn)下例類說(shuō)明：第十七頁(yè)，共一百二十二頁(yè)，2022年，8月28日

堆對(duì)象與構(gòu)造函數(shù)下面注意如何使用：voidmain(){intn;CGoods*pc,*pc1,*pc2;pc=newCGoods(“夏利2000”，10，118000);

//調(diào)用三參數(shù)構(gòu)造函數(shù)

pc1=newCGoods();//調(diào)用缺省構(gòu)造函數(shù)

cout<<’輸入商品類數(shù)組元素?cái)?shù)’<<endl;cin>>n;pc2=newCGoods[n];

//動(dòng)態(tài)建立數(shù)組，不能初始化，調(diào)用n次缺省構(gòu)造函數(shù)

……

deletepc;deletepc1;delete[]pc2;}第十八頁(yè)，共一百二十二頁(yè)，2022年，8月28日

堆對(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ù)組。第十九頁(yè)，共一百二十二頁(yè)，2022年，8月28日

淺拷貝與深拷貝

缺省拷貝構(gòu)造函數(shù)，可用一個(gè)類對(duì)象初始化另一個(gè)類對(duì)象，稱為缺省的按成員拷貝，而不是對(duì)整個(gè)類對(duì)象的按位拷貝。這稱為淺拷貝。

P堆對(duì)象堆對(duì)象PP

圖7.1淺拷貝

拷貝前拷貝后

第二十頁(yè)，共一百二十二頁(yè)，2022年，8月28日

淺拷貝與深拷貝

如果類中有一個(gè)數(shù)據(jù)成員為指針，該類的一個(gè)對(duì)象obj1中的這個(gè)指針p，指向了動(dòng)態(tài)分配的一個(gè)堆對(duì)象，（參見(jiàn)圖7.1拷貝前），如果用obj1按成員拷貝了一個(gè)對(duì)象obj2，這時(shí)obj2.p也指向同一個(gè)堆對(duì)象。當(dāng)析構(gòu)時(shí)，如用缺省的析構(gòu)函數(shù)，則動(dòng)態(tài)分配的堆對(duì)象不能回收。如果在析構(gòu)函數(shù)中有“deletep;”語(yǔ)句，則如果先析構(gòu)函數(shù)obj1時(shí)，堆對(duì)象已經(jīng)釋放，以后再析構(gòu)obj2時(shí)出現(xiàn)了二次釋放的問(wèn)題。這時(shí)就要重新定義拷貝的構(gòu)造函數(shù)，給每個(gè)對(duì)象獨(dú)立分配一個(gè)堆對(duì)象，稱深拷貝。這時(shí)先拷貝對(duì)象主體，再為obj2分配一個(gè)堆對(duì)象，最后用obj1的堆對(duì)象拷貝obj2的堆對(duì)象。

堆對(duì)象PP堆對(duì)象

圖7.2深拷貝

第二十一頁(yè)，共一百二十二頁(yè)，2022年，8月28日

淺拷貝與深拷貝【例7.2】定義拷貝（copystructor）和拷貝賦值操作符（copyAssignmentOperator）實(shí)現(xiàn)深拷貝。

學(xué)生類定義：classstudent{char*pName;

//指針成員public:student();

//缺省構(gòu)造函數(shù)

student(char*pname);

//帶參數(shù)構(gòu)造函數(shù)

student(student&s);

//拷貝構(gòu)造函數(shù)

~student();

//析構(gòu)函數(shù)

student&operator=(student&s);};

//拷貝賦值操作符檢驗(yàn)主函數(shù)和運(yùn)行結(jié)果第二十二頁(yè)，共一百二十二頁(yè)，2022年，8月28日

淺拷貝與深拷貝

堆內(nèi)存是最常用的需要拷貝構(gòu)造函數(shù)自定義的資源，但不是唯一的，如打開(kāi)文件等。如果類需要析構(gòu)函數(shù)來(lái)析構(gòu)資源，則類也需要一個(gè)自定義的拷貝析構(gòu)函數(shù)。對(duì)象的拷貝就是深拷貝了。第二十三頁(yè)，共一百二十二頁(yè)，2022年，8月28日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單鏈表類型模板第二十四頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.2.1單鏈表基本算法

單鏈表（SinglyLinkedlist）也稱線性鏈表。每個(gè)數(shù)據(jù)元素占用一個(gè)節(jié)點(diǎn)（Node）。一個(gè)節(jié)點(diǎn)包含兩個(gè)域，一個(gè)域存放數(shù)據(jù)元素info，其數(shù)據(jù)類型由應(yīng)用問(wèn)題決定，另一個(gè)存放指向該鏈表中下一個(gè)節(jié)點(diǎn)的指針link。節(jié)點(diǎn)定義如下：typedefintDatatype;//數(shù)據(jù)為整型structnode{Datatypeinfo;node*link;}在C/C++中允許結(jié)構(gòu)（或?qū)ο螅┏蓡T是結(jié)構(gòu)自身的指針類型，通過(guò)指針引用自身這種類型的結(jié)構(gòu)。但結(jié)構(gòu)成員決不能是結(jié)構(gòu)自身類型，即結(jié)構(gòu)不能自己定義自己，這會(huì)導(dǎo)致一個(gè)無(wú)窮遞歸的定義。

第二十五頁(yè)，共一百二十二頁(yè)，2022年，8月28日

7.2.1單鏈表基本算法單鏈表的第一個(gè)結(jié)點(diǎn)的地址可通過(guò)鏈表的表頭指針head找到，

head在使用中必須妥善保存，千萬(wàn)不可丟失，否則鏈表整個(gè)丟失，內(nèi)存也發(fā)生泄漏。infon-1^info2

info1

info0

……h(huán)aed圖7.3單向鏈表結(jié)構(gòu)

單鏈表的插入與刪除：只要改變鏈中結(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)之后。

第二十六頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.2.1單鏈表基本算法newnodeinfoxinfo0info1·············headhead插在鏈?zhǔn)?/p>

首先新結(jié)點(diǎn)的link指針指向info0所在結(jié)點(diǎn)，然后，head指向新結(jié)點(diǎn)。即：newnode→link=head；//注意：鏈表操作次序非常重要head=newnode；第二十七頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.2.1單鏈表基本算法infoxinfoi-1infoipｑnewnode插在中間

首先用工作指針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)。即：newnode→link=p；//或newnode→link=q→link；可用于插入某結(jié)點(diǎn)之后q→link=newnode；第二十八頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.2.1單鏈表基本算法infox

newnode············p^infon-1^插在隊(duì)尾只要工作指針p找到隊(duì)尾，即可鏈在其后：p→link=newnode；newnode.link=NULL;第二十九頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.2.1單鏈表基本算法headtailpinfo1tailpinfo0tail^1.向后生成鏈表算法：node*createdown(){Datatypedata;Node*head,*tail,*p;head=newnode;//建立鏈表頭結(jié)點(diǎn)

tail=head;while(cin>>data){ //回車結(jié)束

p=new(node);//每輸入一個(gè)數(shù)申請(qǐng)一個(gè)結(jié)點(diǎn)p->info=data;//添入數(shù)據(jù)tail->link=p1;//新結(jié)點(diǎn)接到鏈尾

tail=p1;}//尾指針到鏈尾

tail->link=NULL;//鏈尾加空指針，表示鏈結(jié)束

returnhead;//返回頭指針}第三十頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.2.1單鏈表基本算法head^info0

P^Pinfo12.向前生成鏈表算法node*createup(){node*head,*p;Datatypedata;head=newnode;//建立頭結(jié)點(diǎn)

head->link=NULL;while(cin>>data){

//建立的總是第一個(gè)結(jié)點(diǎn)

p=newnode;p->info=data;p->link=head->link;//新結(jié)點(diǎn)放在原鏈表前方

head->link=p;

//頭結(jié)點(diǎn)放新結(jié)點(diǎn)之前}returnhead;}第三十一頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.2.1單鏈表基本算法3.鏈表查找算法（Traversal），按數(shù)據(jù)（關(guān)鍵字）查找：node*traversal(node*head,Datatypedata){node*p=head->link;while(p!=NULL||p->info!=data)p=p->link;returnp;//p為NULL則未找到}返回值為指針p，指向鏈表中找到的結(jié)點(diǎn)。4.在單鏈表的p節(jié)點(diǎn)后插入一個(gè)信息域?yàn)閤的新節(jié)點(diǎn)（注意只有一種情況了）。voidinsert(nodep,Datatypex){node*q=newnode;q->info=x;q->link=p->link;p->link=q;}第三十二頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.2.1單鏈表基本算法5.刪除單鏈表節(jié)點(diǎn)*p后面節(jié)點(diǎn)voiddel(node*p){node*q;q=p->link;p->link=q->link;deleteq;

//如果要把該節(jié)點(diǎn)移入另一個(gè)鏈中，則可將q返回。}第三十三頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.2.2單鏈表類型模板【例7.4_h】單鏈表類模板。

首先看結(jié)點(diǎn)類template<typenameT>classList;template<typenameT>classNode{Tinfo;//數(shù)據(jù)域

Node<T>*link;//指針域public:Node();//生成頭結(jié)點(diǎn)的構(gòu)造函數(shù)

Node(constT&data);//生成一般結(jié)點(diǎn)的構(gòu)造函數(shù)

voidInsertAfter(Node<T>*p);//在當(dāng)前結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)

Node<T>*RemoveAfter();//刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)

friendclassList<T>;

//以List為友元類，List可直接訪問(wèn)Node的私有函數(shù)};第三十四頁(yè)，共一百二十二頁(yè)，2022年，8月28日再定義鏈表類:template<typenameT>classList{Node<T>*head,*tail;//鏈表頭指針和尾指針public:List();//構(gòu)造函數(shù)，生成頭結(jié)點(diǎn)(空鏈表)~List();//析構(gòu)函數(shù)

voidMakeEmpty();//清空鏈表，只余表頭結(jié)點(diǎn)

Node<T>*Find(Tdata);

//搜索數(shù)據(jù)域與data相同的結(jié)點(diǎn)，返回該結(jié)點(diǎn)的地址

intLength();//計(jì)算單鏈表長(zhǎng)度

voidPrintList();//打印鏈表的數(shù)據(jù)域

voidInsertFront(Node<T>*p);//可用來(lái)向前生成鏈表

voidInsertRear(Node<T>*p);//可用來(lái)向后生成鏈表

voidInsertOrder(Node<T>*p);//按升序生成鏈表

Node<T>*CreatNode(Tdata);//創(chuàng)建結(jié)點(diǎn)(孤立結(jié)點(diǎn))Node<T>*DeleteNode(Node<T>*p);};//刪除指定結(jié)點(diǎn)7.2.2單鏈表類型模板第三十五頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.2.2單鏈表類型模板【例7.4】由鍵盤輸入16個(gè)整數(shù)，以這些整數(shù)作為結(jié)點(diǎn)數(shù)據(jù)，生成兩個(gè)鏈表，一個(gè)向前生成，一個(gè)向后生成，輸出兩個(gè)表。然后給出一個(gè)整數(shù)在一個(gè)鏈表中查找，找到后刪除它，再輸出該表。清空該表，再按升序生成鏈表并輸出。在本例中程序只需調(diào)用類模板中的成員函數(shù)就可以完成所有鏈表操作。第三十六頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.2.3雙向鏈表

考慮順序表中總是可以很方便地找到表元素的前驅(qū)和后繼，但單鏈表只能找后繼。如要找前驅(qū)，必須從表頭開(kāi)始搜索。為了克服這一缺點(diǎn)，可采用雙向鏈表（DoubleLinkedList)。雙向鏈表的結(jié)點(diǎn)有三個(gè)域：左鏈接指針（llink)，數(shù)據(jù)域（info)，右鏈接指針域(rlink)。雙向鏈表經(jīng)常采用帶頭結(jié)點(diǎn)的循環(huán)鏈表方式。

info0infon-1.’.’.’.’.’.’info1head(a)非空表head(b)空表第三十七頁(yè)，共一百二十二頁(yè)，2022年，8月28日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)，間接訪問(wèn)符->可以連續(xù)使用。pllinkrlinkrlinkllinkrlink前驅(qū)結(jié)點(diǎn)llink本結(jié)點(diǎn)后繼結(jié)點(diǎn)

間接訪問(wèn)符的使用【例7.5】雙向鏈表類模板和結(jié)點(diǎn)類模板。第三十八頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.3棧與隊(duì)列的基本操作及其應(yīng)用

棧和隊(duì)都是特殊的線性表，限制存取位置的線性結(jié)構(gòu)，可以由順序表實(shí)現(xiàn)，也可以由鏈表實(shí)現(xiàn)。

7.

3.

1棧與應(yīng)用

7.

3.

2

隊(duì)列

第三十九頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.3.1棧與應(yīng)用

棧定義為只允許在表的一端進(jìn)行插入和刪除的線性表。允許進(jìn)行插入和刪除的一端叫做棧頂(top)，而另一端叫棧底(bottom)。棧中沒(méi)有任何元素時(shí)，稱為空棧。進(jìn)棧時(shí)最先進(jìn)棧的在最下面，最后的在最上面，后來(lái)居上。而出棧時(shí)順序相反，最后進(jìn)棧的最先出棧，而最先進(jìn)棧的a0最后出棧。所以棧又稱作后進(jìn)先出（LIFO：LastInFirstOut）的線性表。?？梢杂庙樞虮韺?shí)現(xiàn)，稱順序棧；也可以用鏈表實(shí)現(xiàn)，稱鏈棧。第四十頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.3.1棧與應(yīng)用

參見(jiàn)下圖，設(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-2……a1an-1bottom進(jìn)棧toptoptoptoptop出棧圖示為順序棧。其中棧底bottom是指向棧數(shù)據(jù)區(qū)的下一單元，這樣判斷是否為空棧會(huì)更方便，只需top與bottom相同就是空棧。通常只有棧頂與操作有關(guān)。第四十一頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.3.1棧與應(yīng)用【例7.6】順序棧的類模板定義：template<typenameT>classStack{inttop;//棧頂指針（下標(biāo)）

T*elements;//動(dòng)態(tài)建立的元素

intmaxSize;//棧最大容納的元素個(gè)數(shù)public:Stack(int=20);//構(gòu)造函數(shù)，棧如不指定大小，設(shè)為20元素

~Stack(){delete[]elements;}voidPush(constT&data);//壓棧

TPop();//彈出，top--TGetElem(inti);//取數(shù)據(jù)，top不變

voidMakeEmpty(){top=-1;}//清空棧

boolIsEmpty()const{returntop==-1;}//判?？?/p>

boolIsFull()const{returntop==maxSize-1;}//判棧滿

voidPrintStack();};//輸出棧內(nèi)所有數(shù)據(jù)第四十二頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.3.1棧與應(yīng)用voidmain(){ inti,a[10]={0,1,2,3,4,5,6,7,8,9},b[10]; Stack<int>istack(10); for(i=0;i<10;i++)istack.Push(a[i]); if(istack.IsFull())cout<<"棧滿"<<endl; istack.PrintStack(); for(i=0;i<10;i++)b[i]=istack.Pop(); if(istack.IsEmpty())cout<<"?？?<<endl; for(i=0;i<10;i++)cout<<b[i]<<'\t';//注意先進(jìn)后出

cout<<endl; istack.Pop();//下溢出}第四十三頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.3.1棧與應(yīng)用【例7.7_h】鏈棧的結(jié)點(diǎn)類模板:

template<typenameT>classNode{//鏈棧結(jié)點(diǎn)類模板

Tinfo; Node<T>*link;public: Node(Tdata=0,Node<T>*next=NULL){ info=data; link=next; } friendclassStack<T>;};top

……^

……

鏈棧第四十四頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.3.1棧與應(yīng)用鏈棧類模板，無(wú)頭結(jié)點(diǎn)鏈表template<typenameT>classStack{//鏈棧類模板

Node<T>*top;//棧頂指針public: Stack(){top=NULL;} ~Stack(); voidPush(constT&data);//壓棧

TPop();//彈出

TGetTop();//取棧頂元素

voidMakeEmpty();//清空棧

boolIsEmpty(){returntop==NULL;}};第四十五頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.3.1棧與應(yīng)用

順序棧和鏈棧邏輯功能是一樣，盡管這里兩個(gè)棧模板的成員函數(shù)功能選擇稍有出入，因?yàn)轫樞驐？梢噪S機(jī)訪問(wèn)其中的元素，而鏈棧只能順序訪問(wèn)，但邏輯上完全可以做到一樣（物理結(jié)構(gòu)不同）。順序棧必須先開(kāi)一定大小內(nèi)存空間，執(zhí)行起來(lái)簡(jiǎn)單，速度快，可能溢出。鏈棧內(nèi)存空間隨用隨開(kāi)，不會(huì)溢出，但執(zhí)行復(fù)雜（不斷地動(dòng)態(tài)分配），速度慢。?？捎糜诒磉_(dá)式的計(jì)算?，F(xiàn)考慮最簡(jiǎn)單的+、-、*、/四個(gè)運(yùn)算符和結(jié)束符＝組成的算術(shù)表達(dá)式，只有兩個(gè)優(yōu)先級(jí)，先*/，后+-。第四十六頁(yè)，共一百二十二頁(yè)，2022年，8月28日Ncba＊＋O＊＋at1deNat1de＋＋／－O／－－＋O－＋Nt1at2t1at2t3aNt3aN＋O＋Ob*c->t1d/e->t2t1-t2->t3a+t3->t4N：數(shù)棧O：運(yùn)算符

(a)

(b)

(c)

(d)

(e)

表達(dá)式運(yùn)算

設(shè)有：a+b*c-d/e=；為實(shí)現(xiàn)運(yùn)算符的優(yōu)先級(jí)，采用兩個(gè)棧：一個(gè)數(shù)棧，一個(gè)運(yùn)算符棧。數(shù)棧暫存操作數(shù)，運(yùn)算符棧暫存運(yùn)算符。從左向右掃描算術(shù)表達(dá)式，遇到操作數(shù)，壓入數(shù)棧；遇到運(yùn)算符，則與運(yùn)算符棧棧頂?shù)倪\(yùn)算符比較優(yōu)先級(jí)，若新的運(yùn)算符優(yōu)先級(jí)高，或運(yùn)算符棧空，則壓棧。否則將棧頂運(yùn)算符出棧，與數(shù)字棧出棧的兩個(gè)數(shù)據(jù)進(jìn)行運(yùn)算，結(jié)果壓入數(shù)棧，再將新運(yùn)算符壓棧。繼續(xù)掃描，直到遇到＝號(hào)，掃描結(jié)束。棧中數(shù)據(jù)繼續(xù)按前面規(guī)則出棧。第四十七頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.3.1棧與應(yīng)用【例7.7】模擬簡(jiǎn)單計(jì)算器，該計(jì)算器只認(rèn)+-*/四個(gè)運(yùn)算符，輸入為整數(shù)。表達(dá)式結(jié)束符使用＝號(hào)，清空棧用‘c’字符。使用‘z’字符表示結(jié)束。簡(jiǎn)易計(jì)算器類定義：classCalculator{Stack<int>Nstack;//使用鏈棧

Stack<char>Ostack;public:Calculator(void){};voidCal(void);//計(jì)算器運(yùn)算程序

voidGetTwoNum(int&Num1,int&Num2);//取數(shù)

voidCompute(charOpr);//讀算式

voidClear(void);};//清除在VC++平臺(tái)上演示例7.7第四十八頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.3.2隊(duì)列

隊(duì)列(Queue)也是一種限定存取位置的線性表。它只允許在表的一端插入，而在另一端刪除。允許插入的一端稱為隊(duì)尾(rear)，允許刪除的一端叫做隊(duì)頭(front)。每次在隊(duì)尾加入新元素，加入稱為進(jìn)隊(duì)，刪除稱為出隊(duì)。隊(duì)列的這種特性正好與棧相反，叫做先進(jìn)先出FIFO(FirstInFirstOut)。

a0a1a2…an-1…front元素移動(dòng)方向rear圖7.15隊(duì)列

圖7.15所示隊(duì)列隨隊(duì)尾加入元素，隊(duì)尾(rear)不斷向后移；而隨隊(duì)頭元素的出隊(duì)，則隊(duì)頭(front)也不斷后移，即位置在變（如要位置不變，移動(dòng)元素工作量也太大）。

第四十九頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.3.2隊(duì)列rearfrontADCABDECFHGBCD進(jìn)隊(duì)A進(jìn)隊(duì)空隊(duì)DCAB出隊(duì)EFGH進(jìn)隊(duì)rearfrontrearrearrearfrontfrontfront圖7.16順序隊(duì)列的插入和刪除

由圖可見(jiàn)：空隊(duì)時(shí)指針（下標(biāo)）front和rear在一起都指向隊(duì)前方，當(dāng)有元素進(jìn)隊(duì)，則rear后移；有元素出隊(duì)，則front后移，最后分配給隊(duì)的前端不再被利用。第五十頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.3.2隊(duì)列隊(duì)列總是做成一個(gè)邏輯上的循環(huán)隊(duì)列注意，空隊(duì)時(shí)rear=front，滿隊(duì)時(shí)必須空一個(gè)位置第五十一頁(yè)，共一百二十二頁(yè)，2022年，8月28日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ú)此問(wèn)題

【例7.8】順序存儲(chǔ)方式的循環(huán)隊(duì)列類模板?！纠?.9】鏈隊(duì)類模板。鏈?zhǔn)壮鲫?duì)，鏈尾入隊(duì)。無(wú)鏈?zhǔn)捉Y(jié)點(diǎn)方式。第五十二頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.4

二叉樹

樹形結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)，樹和二叉樹是常用的樹形結(jié)構(gòu)。

7.4.2

二叉樹的遍歷

二叉樹的概念

7.4.3

排序二叉樹

第五十三頁(yè)，共一百二十二頁(yè)，2022年，8月28日

二叉樹的概念

樹（Tree）是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。如n=0，稱為空樹。非空樹有一個(gè)特定的結(jié)點(diǎn)，它只有直接后繼，沒(méi)有直接前驅(qū)，稱之為根（root）。除根以外的其它結(jié)點(diǎn)劃分為m（m≥0）個(gè)互不相交的有限集合T0，T1，……，Tm-1，每個(gè)集合又是一棵樹，稱為根的子樹（subtree）。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。這是一個(gè)遞歸方法定義的數(shù)據(jù)結(jié)構(gòu)。

第五十四頁(yè)，共一百二十二頁(yè)，2022年，8月28日

二叉樹的概念A(yù)BCDEFGIHJLKONM…………0層……1層2層3層深度圖7.17樹的示意圖

結(jié)點(diǎn)，包括數(shù)據(jù)項(xiàng)和多個(gè)指針項(xiàng)，指針項(xiàng)數(shù)目并不固定，且無(wú)次序。結(jié)點(diǎn)的度，結(jié)點(diǎn)所擁有的子樹數(shù)量。葉結(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)。第五十五頁(yè)，共一百二十二頁(yè)，2022年，8月28日

二叉樹的概念A(yù)BCDEFGIHJLKONM…………0層……1層2層3層深度圖7.17樹的示意圖

雙親結(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)度的最大值。

第五十六頁(yè)，共一百二十二頁(yè)，2022年，8月28日

二叉樹的概念

二叉樹（BinaryTree）是另一種獨(dú)立的樹形結(jié)構(gòu)。二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或?yàn)榭?，或是由一個(gè)根結(jié)點(diǎn)及兩棵樹分別稱為左子樹和右子樹的（注意有左右之分）互不相交的二叉樹組成，其中左右子樹分別可以為空子樹或均為空樹。這也是一個(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葉子結(jié)點(diǎn)，有n2個(gè)度為2的結(jié)點(diǎn)，則有n0=n2+1。第五十七頁(yè)，共一百二十二頁(yè)，2022年，8月28日

二叉樹的概念【例7.9】畫出有三個(gè)結(jié)點(diǎn)的所有二叉樹。解：結(jié)果見(jiàn)圖7.18，共5種。圖7.18

5種不同的三結(jié)點(diǎn)二叉樹

第五十八頁(yè)，共一百二十二頁(yè)，2022年，8月28日

二叉樹的概念二叉樹有滿二叉樹和完全二叉樹，分別如圖7.19和圖7.20，完全二叉樹已有的結(jié)點(diǎn)排序與滿二叉樹相同。

123456798101114131215圖7.19滿二叉樹

12345679810圖7.20完全二叉樹

第五十九頁(yè)，共一百二十二頁(yè)，2022年，8月28日

二叉樹的概念下面給出鏈?zhǔn)絻?chǔ)存方式的二叉樹。每個(gè)結(jié)點(diǎn)有三個(gè)域：數(shù)據(jù)域、左孩子指針和右孩子指針，見(jiàn)圖7.21。

lchildrchildinfo圖7.21二叉樹結(jié)點(diǎn)

第六十頁(yè)，共一百二十二頁(yè)，2022年，8月28日

二叉樹的概念二叉樹類結(jié)點(diǎn)類模板定義如下：template<typenameT>classBinaryTree;template<typenameT>classNode{Node<T>*lchild,*rchild; Tinfo;public:Node(){lchild=NULL;rchild=NULL;}Node(Tdata,Node<T>*left=NULL,Node<T>*right=NULL){info=data;lchild=left;rchild=right;}

第六十一頁(yè)，共一百二十二頁(yè)，2022年，8月28日

二叉樹的概念

TGetinfo(){returninfo;}//取得結(jié)點(diǎn)數(shù)據(jù)

voidsetinfo(constT&data){info=data;}

//修改結(jié)點(diǎn)數(shù)據(jù)

Node<T>*Getleft(){returnlchild;}//取得左子樹

Node<T>*Getright(){returnrchild;}//取得右子樹

voidsetleft(Node<T>*left){lchild=left;}

//設(shè)置左指針

voidsetright<Node<T>*right){rchild=right;}

//設(shè)置右指針

friendclassBinaryTree<T>;//二叉樹類說(shuō)明為友元類第六十二頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.4.2二叉樹的遍歷

所謂二叉樹的遍歷（binarytreetraversal），就是遵從某種次序，查巡二叉樹的所有結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)都被訪問(wèn)一次，而且僅訪問(wèn)一次。所謂“訪問(wèn)”指對(duì)結(jié)點(diǎn)施行某些操作，但不破壞它原來(lái)的數(shù)據(jù)結(jié)構(gòu)。遍歷二叉樹有不同次序，規(guī)定先左后右，令L，R，V分別代表遍歷一個(gè)結(jié)點(diǎn)的左右子樹和訪問(wèn)該結(jié)點(diǎn)的操作，有三種方式：前序遍歷（VLR）中序遍歷（LVR）后序遍歷（LRV）

第六十三頁(yè)，共一百二十二頁(yè)，2022年，8月28日

7.4.2二叉樹的遍歷例如：前序遍歷訪問(wèn)次序?yàn)锳BDEGCFH。

圖7.22二叉樹遍歷

中序遍歷結(jié)果為DBGEAFHC。后序遍歷結(jié)果為DGEBHFCA。

第六十四頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.4.2二叉樹的遍歷【例7.10】二叉樹類模板（其中二叉樹生成借用二叉排序樹，見(jiàn)下節(jié)）。特別注意插入結(jié)點(diǎn)時(shí)，第二參數(shù)為指針的引用！否則不能建立樹。為什么？請(qǐng)讀者自己思考。本例采用簡(jiǎn)單的接口函數(shù)，而把較復(fù)雜的算法作為私有函數(shù)。

template<typenameT>classBinaryTree{Node<T>*root;//二叉樹的根指針

voidInOrder(Node<T>*Current);//中序遍歷

voidPreOrder(Node<T>*Current);//前序遍歷

voidPostOrder(Node<T>*Current);//后序遍歷

voidInsert(constT&data,Node<T>*&b);

//插入結(jié)點(diǎn)，參數(shù)為引用！

voidDestory(Node<T>*Current);//刪除樹第六十五頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.4.2二叉樹的遍歷public:BinaryTree(){root=NULL;} //空樹構(gòu)造函數(shù)

~BinaryTree(){Destory(root);} //析構(gòu)函數(shù)

voidCreat(T*data,intn);//建立（排序）二叉樹

voidInOrder(){InOrder(root);}

//中序遍歷，公有函數(shù)為接口

voidPreOrder(){PreOrder(root);}

//前序遍歷，公有函數(shù)為接口

voidPostOrder(){PostOrder(root);}

//后序遍歷，公有函數(shù)為接口};檢驗(yàn)主函數(shù)第六十六頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.4.2二叉樹的遍歷【例7.13】某二叉樹先序遍歷為ABCEFDGHIJK，中序遍歷為ECFBDGAIHJK繪出該二叉樹。

ABCDEFGHIJK圖7.23例7.11二叉樹

按同樣方法推出A的右子樹。結(jié)果如圖7.23。可以證明已知先序和中序訪問(wèn)次序可以唯一確定一棵二叉樹。

解：由先序知A為根結(jié)點(diǎn)，而EFBDG為左子樹，IHJK為右子樹。由先序中的BCEFDG知B為左子樹根結(jié)點(diǎn)，由中序中的ECFBDG知ECF為其左子樹，而DG為右子樹。再由先序CEF知C為左子樹根結(jié)點(diǎn)，由中序ECF知E為C左子樹，F(xiàn)為的右子樹。再由先序DG知，D為B的右子樹根結(jié)點(diǎn)，由中序DG知G為D的右子樹。第六十七頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.4.3排序二叉樹

二叉排序樹（BinarySortingTree）又稱二叉搜索樹（BinarySearchTree），是一種特殊結(jié)構(gòu)的二叉數(shù)，作為一種排序和查找的手段，對(duì)應(yīng)有序表的對(duì)半查找，通常亦被稱為數(shù)表。其定義也是遞歸的。二叉排序樹的定義：二叉排序樹或者是空樹或者是具有下述性質(zhì)的二叉數(shù)，其左子樹上所有結(jié)點(diǎn)的數(shù)據(jù)值均小于根結(jié)點(diǎn)的數(shù)據(jù)值；右子樹上所有結(jié)點(diǎn)的數(shù)據(jù)值均大于等于根結(jié)點(diǎn)的數(shù)據(jù)值，左子樹和右子樹又各是一棵二叉排序樹。第六十八頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.4.3排序二叉樹

二叉排序樹用中序遍歷就可以得到由小到大的有序序列，如圖7.24可得有序序列｛8，10，11，12，15，16，18，22，24，26，29｝。

101826812222911241615圖7.24二叉排序樹例

第六十九頁(yè)，共一百二十二頁(yè)，2022年，8月28日二叉排序樹的結(jié)點(diǎn)插入（可生成排序二叉樹）生成算法：對(duì)任意一組數(shù)據(jù)元素序列{a0，a1，a2，…，an-1}。要生成二叉排序樹的過(guò)程為：1.

令a0為二叉樹的根結(jié)點(diǎn)。2.

若a1<a0，令a1為a0左子樹的根結(jié)點(diǎn)，否則a1為a0右子樹的根結(jié)點(diǎn)。3.如ai小于根結(jié)點(diǎn)，則去左子樹，否則去右子樹，按此法查找，直到成為空樹，則安放此位置。這步就是插入算法。

7.4.3排序二叉樹第七十頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.4.3排序二叉樹template<typenameT>Node<T>*BinaryTree<T>::Find(constT&data,Node<T>*b){if(b!=NULL){ Node<T>*temp=b; while(temp!=NULL){ if(temp->info==data)returntemp; if(temp->info<data)temp=temp->rchild; elsetemp=temp->lchild; }}returnNULL;}再次在VC++平臺(tái)上演示例7.13【例7.13】排序二叉樹查找函數(shù)。算法：用中序遍歷即可，但遞歸慢，下面為迭代查找算法。第七十一頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.5MFC對(duì)象和Windows對(duì)象的關(guān)系

MFC對(duì)象是C++對(duì)象，而且是特指封裝了Window對(duì)象的C++對(duì)象，不是任意的C++對(duì)象。本節(jié)討論MFC對(duì)象與Window對(duì)象的聯(lián)系，以最典型的的窗口類（CWnd）為例，討論CWnd類對(duì)象與Windows窗口對(duì)象的關(guān)系。參見(jiàn)下圖。

....其它成員m_hWndhwndCWnd類對(duì)象HWND句柄類型wndwindows對(duì)象句柄Windows操作系統(tǒng)窗口對(duì)象MFC窗口對(duì)象與Windows窗口對(duì)象的關(guān)系第七十二頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.5MFC對(duì)象和Windows對(duì)象的關(guān)系

MFC的窗口對(duì)象wnd是C++類的實(shí)例，即CWnd類或其派生類的實(shí)例，是由CWnd類或其派生類的構(gòu)造函數(shù)創(chuàng)建的，而最終由CWnd類或其派生類的析構(gòu)函數(shù)撤消。hwnd是HWND句柄類型的實(shí)例，為它建立了一個(gè)Windows操作系統(tǒng)的對(duì)象。然后把這個(gè)句柄放入CWnd類對(duì)象wnd的成員數(shù)據(jù)m_hwnd中。這樣wnd就包含了一個(gè)Windows操作系統(tǒng)的窗口對(duì)象。程序段如下：CWndwnd;//定義窗口類（CWnd）的對(duì)象wndHWNDhwnd;//定義窗口句柄hwndhwnd=CreateWindows(......);//調(diào)用API函數(shù)CreateWindows(...)建立一個(gè)Windows窗口類實(shí)例wnd.Attach(hwd);//把Windows窗口實(shí)例的句柄鏈到CWnd對(duì)象hwnd上......DestroryWindow(hwnd);//調(diào)用API函數(shù)撤消Windows窗口

第七十三頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.5MFC對(duì)象和Windows對(duì)象的關(guān)系MFC封裝了幾乎所有Windows的API函數(shù)，所以上面的API函數(shù)，可以用CWnd的成員函數(shù)代替。成員函數(shù)Create()可以代替API函數(shù)CreateWindows()并加上另一個(gè)成員函數(shù)Attach()的全部功能，建立一個(gè)Windows操作系統(tǒng)的窗口對(duì)象，并把句柄自動(dòng)保存在MFC窗口對(duì)象wnd的m_hwnd成員數(shù)據(jù)中。通常MFC程序員直接使用CWnd的成員函數(shù)就可以了。

其它的MFC對(duì)象和對(duì)應(yīng)Windows對(duì)象也有類似的關(guān)系。見(jiàn)下頁(yè)表7.1Windows窗口句柄通常是全局量，動(dòng)態(tài)建立的Windows窗口對(duì)象也是全局性的。所以一個(gè)進(jìn)程或線程可以取得另一個(gè)進(jìn)程或線程的窗口句柄，并給它發(fā)送消息。但一個(gè)線程只能使用本線程創(chuàng)建的MFC窗口對(duì)象，不能使用其它線程創(chuàng)建的MFC窗口對(duì)象。第七十四頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.5MFC對(duì)象和Windows對(duì)象的關(guān)系項(xiàng)目MFC類對(duì)象句柄應(yīng)用程序CWinAppHINSTANCEm_hInstance窗口CWndHWNDm_hWnd菜單CMenuHMENUm_hMenu設(shè)備環(huán)境CDCHDCm_hDC矩形區(qū)域CRgnHRGNm_hRgn畫刷CBrushHBRUSHm_hBrush畫筆CPenHPENm_hPen字體CFontHFONTm_hFont位圖CBitmapHBITMAPm_hBitmap調(diào)色板CPalatteHPALATTEm_hPalatte表7.1常用MFC類與Windows對(duì)象句柄對(duì)應(yīng)關(guān)系第七十五頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.5MFC對(duì)象和Windows對(duì)象的關(guān)系Windows對(duì)象是Windows操作系統(tǒng)的一個(gè)內(nèi)部數(shù)據(jù)結(jié)構(gòu)的實(shí)例，由一個(gè)Windows系統(tǒng)全局的窗口句柄來(lái)唯一標(biāo)志，由API函數(shù)CreatWindow()創(chuàng)建，而由DestroyWindow()撤消。在MFC編程中，Windows對(duì)象通常在MFC對(duì)象建立以后，調(diào)用Create()成員函數(shù)建立Windows對(duì)象，并鏈接在MFC對(duì)象上。下面的程序段用來(lái)建立應(yīng)用程序的主框架窗口。CFrameWnd*pFrame=newCFrameWnd;

//動(dòng)態(tài)建立框架窗口對(duì)象pFrame->Create(NULL,”Ex7_xx”,ws_OVERLAPPENDWINDOW,rect,NULL,MAKEINTRESOURCE(IDR_MENUI),0,NULL);//建立與pFrame指向動(dòng)態(tài)框架窗口對(duì)象相連的Windows//框架窗口第七十六頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.6圖書流通管理系統(tǒng)設(shè)計(jì)——鏈表類應(yīng)用在圖書館類中，存儲(chǔ)在館圖書、讀者、管理員及借閱信息的數(shù)組的大小都是固定的。當(dāng)這些對(duì)象的數(shù)目超過(guò)數(shù)組大小時(shí)，就必然發(fā)生溢出，通?？偸恰按箝_(kāi)小用”。通過(guò)本章學(xué)習(xí)后應(yīng)考慮采用動(dòng)態(tài)數(shù)組或鏈表結(jié)構(gòu)來(lái)存儲(chǔ)對(duì)象。

首先，定義雙向環(huán)形鏈表類模板，對(duì)節(jié)模板稍作改動(dòng)。template<typenameT>classDblList; //鏈表類模板聲明template<typenameT>classDblNode{

//結(jié)點(diǎn)類模板聲明TInfo; //數(shù)據(jù)域DblNode<T>*llink,*rlink;//前驅(qū)（左鏈）、后繼（右鏈）指針public:DblNode(Tdata); //一般結(jié)點(diǎn)

DblNode(); //頭結(jié)點(diǎn)

TGetInfo(){returnInfo;};friendclassDblList<T>; //將鏈表類聲明為友元

friendclassLibrary; //將圖書館類聲明為友元};第七十七頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.6圖書流通管理系統(tǒng)設(shè)計(jì)——鏈表類應(yīng)用template<typenameT>classDblList{ //鏈表類模板定義

DblNode<T>*head,*current;public: DblList(); ~DblList(); voidInsert(constT&data); DblNode<T>*Remove(DblNode<T>*p); voidPrint(); intLength(); //計(jì)算鏈表長(zhǎng)度

DblNode<T>*Find(Tdata);//搜索數(shù)據(jù)與定值相同的結(jié)點(diǎn)

DblNode<T>*Find(intdata);//按某個(gè)關(guān)鍵字搜索

voidMakeEmpty(); //清空鏈表

voidShowList(); //顯示鏈表所有元素};第七十八頁(yè)，共一百二十二頁(yè)，2022年，8月28日新增加按照關(guān)鍵字搜索的函數(shù)：template<typenameT>DblNode<T>*DblList<T>::Find(intdata){ current=head->rlink; inttemp=current->Info.GetCode(); while(current!=head&&temp!=data){ current=current->rlink; temp=current->Info.GetCode(); } if(current==head)current=NULL; returncurrent;}7.6圖書流通管理系統(tǒng)設(shè)計(jì)——鏈表類應(yīng)用第七十九頁(yè)，共一百二十二頁(yè)，2022年，8月28日?qǐng)D書館類中記錄在館圖書、讀者、管理員及借閱信息的數(shù)組改為鏈表類，參見(jiàn)圖7.27。classLibrary{ //封裝圖書館流通

DblList<Item>item;//記錄書目的鏈表

DblList<Reader>reader;//記錄讀者的鏈表

DblList<Loan>loan;//記錄借閱信息的鏈表

DblList<Manager>manager;//記錄管理員的鏈表7.6圖書流通管理系統(tǒng)設(shè)計(jì)——鏈表類應(yīng)用第八十頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.6圖書流通管理系統(tǒng)設(shè)計(jì)——鏈表類應(yīng)用圖7.27圖書館類

intitemNum;//記錄在館圖書數(shù)目

intreaderNum;//記錄讀者數(shù)目

intloanNum; //記錄借閱信息數(shù)目

intmanagerNum;//記錄管理員數(shù)目public:Library();//構(gòu)造函數(shù)

voidRun();//運(yùn)行圖書館業(yè)務(wù)函數(shù)

voidCreateBibliotheca();//創(chuàng)建書目

voidCreateReader();//創(chuàng)建讀者

voidCreateManager();//創(chuàng)建管理員

intShowMainMenu();//顯示主菜單

voidBorrow();//借書操作

voidReturn();//還書操作

voidRequire();//查詢操作};第八十一頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.6圖書流通管理系統(tǒng)設(shè)計(jì)——鏈表類應(yīng)用

修改讀者、在館圖書、管理員及借閱信息類。首先，讀者類Reader原來(lái)用數(shù)組記錄所借的書，在此用一個(gè)Item類的指針代替，用單鏈表記錄所借的書，該指針是單鏈表頭指針。對(duì)讀者進(jìn)行借書或還書操作是通過(guò)對(duì)單鏈表插入或刪除結(jié)點(diǎn)實(shí)現(xiàn)。這個(gè)單鏈表只是附在讀者類中，不是一個(gè)規(guī)范的單鏈表類。

圖書類Item的條碼是識(shí)別圖書的關(guān)鍵字，原來(lái)取名BarCode，現(xiàn)在為了與鏈表模板統(tǒng)一，將其改為Code，并增加GetCode函數(shù)以訪問(wèn)其條碼。為了在Reader類所借書單鏈表中操作，為Item類增加指向Item類的指針Next。

管理員類ManagerGetCode函數(shù)訪問(wèn)其編號(hào)，增加Show函數(shù)顯示其基本信息。

借閱信息類Loan除了增加GetCode和Show函數(shù)，還增加一個(gè)long類型的數(shù)據(jù)成員Code，定義為所借書的條碼。修改后的各類可表示為圖7.28，圖中斜體字表示與圖5.18的不同之處。

第八十二頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.6圖書流通管理系統(tǒng)設(shè)計(jì)——鏈表類應(yīng)用圖7.28圖書流通管理系統(tǒng)中的類第八十三頁(yè)，共一百二十二頁(yè)，2022年，8月28日借書操作：voidLibrary::Borrow(){intcode,barcode;Loanln; DblNode<Item>*ti=NULL;

//定義數(shù)據(jù)為Item類型的結(jié)點(diǎn)指針

DblNode<Manager>*tm=NULL;

//定義數(shù)據(jù)為Manager類型的結(jié)點(diǎn)指針

DblNode<Reader>*tr=NULL;

//定義數(shù)據(jù)為Reader類型的結(jié)點(diǎn)指針

cout<<"借書，請(qǐng)輸入借書證號(hào)：\n";cin>>code;tr=reader.Find(code);//查找讀者7.6圖書流通管理系統(tǒng)設(shè)計(jì)——鏈表類應(yīng)用第八十四頁(yè)，共一百二十二頁(yè)，2022年，8月28日if(tr){cout<<"借書，請(qǐng)選擇書的條碼\n";cout<<"書名\t作者\(yùn)t分類號(hào)\t條碼\n";item.ShowList();//顯示可借閱書

cin>>barcode;ti=item.Find(barcode);//查找管理員

if(ti){cout<<"請(qǐng)輸入管理員工號(hào)：\n";cout<<"姓名\t年齡\t工號(hào)\n";manager.ShowList();//顯示所有管理員信息

cin>>code;tm=manager.Find(code);//查找書

if(tm){tr->Info.AddBook(ti->GetInfo());//添加到讀者所借書

item.Remove(ti);//從可借書中刪除

itemNum--;7.6圖書流通管理系統(tǒng)設(shè)計(jì)——鏈表類應(yīng)用第八十五頁(yè)，共一百二十二頁(yè)，2022年，8月28日7.6圖書流通管理系統(tǒng)設(shè)計(jì)——鏈表類應(yīng)用

ln.reader=tr->GetInfo();//添加借閱信息