動態(tài)內存分配

動態(tài)內存分配第1頁，課件共125頁，創(chuàng)作于2023年2月7.1堆內存分配

7.5MFC對象和Windows對象的關系

7.4二叉樹

7.3棧與隊列的基本操作及其應用

7.2鏈表與鏈表的基本操作

第七章動態(tài)內存分配

7.6圖書流通管理系統(tǒng)設計——鏈表類應用

第2頁，課件共125頁，創(chuàng)作于2023年2月7.1

堆內存分配

7.1.1堆內存的分配與釋放

7.1.2堆對象與構造函數

7.1.3淺拷貝與深拷貝

通常定義變量（或對象），編譯器在編譯時都可以根據該變量（或對象）的類型知道所需內存空間的大小，從而系統(tǒng)在適當的時候為他們分配確定的存儲空間。這種內存分配稱為靜態(tài)存儲分配有些操作對象只有在程序運行時才能確定，這樣編譯器在編譯時就無法為他們預定存儲空間，只能在程序運行時，系統(tǒng)根據運行時的要求進行內存分配，這種方法稱為動態(tài)存儲分配。所有動態(tài)存儲分配都在堆區(qū)中進行。第3頁，課件共125頁，創(chuàng)作于2023年2月7.1.1堆內存的分配與釋放

當程序運行到需要一個動態(tài)分配的變量或對象時，必須向系統(tǒng)申請取得堆中的一塊所需大小的存貯空間，用于存貯該變量或對象。當不再使用該變量或對象時，也就是它的生命結束時，要顯式釋放它所占用的存貯空間，這樣系統(tǒng)就能對該堆空間進行再次分配，做到重復使用有限的資源。在C++中，申請和釋放堆中分配的存貯空間，分別使用new和delete的兩個運算符來完成，其使用的格式如下：指針變量名=new類型名(初始化式)；delete指針名;

new運算符返回的是一個指向所分配類型變量（對象）的指針。對所創(chuàng)建的變量或對象，都是通過該指針來間接操作的，而動態(tài)創(chuàng)建的對象本身沒有名字。

第4頁，課件共125頁，創(chuàng)作于2023年2月

7.1.1堆內存的分配與釋放一般定義變量和對象時要用標識符命名，稱命名對象，而動態(tài)的稱無名對象(請注意與棧區(qū)中的臨時對象的區(qū)別，兩者完全不同：生命期不同，操作方法不同，臨時變量對程序員是透明的)。堆區(qū)是不會自動在分配時做初始化的（包括清零），所以必須用初始化式(initializer)來顯式初始化。new表達式的操作序列如下：從堆區(qū)分配對象，然后用括號中的值初始化該對象。從堆區(qū)分配對象時，new表達式調用庫操作符new()。例如：int*pi=newint(0);它與下列代碼序列大體等價：intival=0;int*pi=&ival;只是pi現在所指向的變量是由庫操作符new()分配的，位于程序的堆區(qū)中，并且該對象未命名。

第5頁，課件共125頁，創(chuàng)作于2023年2月

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

deletepi;注意這時釋放了pi所指的目標的內存空間，也就是撤銷了該目標，稱動態(tài)內存釋放（dynamicmemorydeallocation），但指針pi本身并沒有撤銷，該指針所占內存空間并未釋放。第6頁，課件共125頁，創(chuàng)作于2023年2月7.1.1堆內存的分配與釋放

對于數組進行動態(tài)分配的格式為：指針變量名=new類型名[下標表達式];Delete[]指向該數組的指針變量名;兩式中的方括號是非常重要的，兩者必須配對使用。如果delete語句中少了方括號，因編譯器認為該指針是指向數組第一個元素的指針，會產生回收不徹底的問題（只回收了第一個元素所占空間），加了方括號后就轉化為指向數組的指針，回收整個數組。

delete[]的方括號中不需要填數組元素數，系統(tǒng)自知。即使寫了，編譯器也忽略。請注意“下標表達式”不是常量表達式，即它的值不必在編譯時確定，可以在運行時確定。第7頁，課件共125頁，創(chuàng)作于2023年2月7.1.1堆內存的分配與釋放【例7.1】動態(tài)數組的建立與撤銷#include<iostream.h>#include<string.h>voidmain(){ intn; char*pc; cout<<"請輸入動態(tài)數組的元素個數"<<endl; cin>>n;

//在運行時確定，可輸入17

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

return;

}第8頁，課件共125頁，創(chuàng)作于2023年2月7.1.1堆內存的分配與釋放動態(tài)分配數組有三個特點：1.變量n在編譯時沒有確定的值，而是在運行中輸入，按運行時所需分配堆空間，這一點是動態(tài)分配的優(yōu)點，可克服數組“大開小用”的弊端，在表、排序與查找中的算法，若用動態(tài)數組，通用性更佳。delete[]pc是將n個字符的空間釋放，而用deletepc則只釋放了一個字符的空間；2.如果有一個char*pc1，令pc1=p，同樣可用delete[]pc1來釋放該空間。盡管C++不對數組作邊界檢查，但在堆空間分配時，對數組分配空間大小是紀錄在案的。3.沒有初始化式（initializer），不可對數組初始化。

第9頁，課件共125頁，創(chuàng)作于2023年2月7.1.1堆內存的分配與釋放多維數組動態(tài)分配：new類型名[下標表達式1][下標表達式2]……;建立一個動態(tài)三維數組float(*cp)[30][20];

//指向一個30行20列數組的指針cp=newfloat[15][30][20];

//建立由15個30*20數組組成的數組；注意cp等效于三維數組名，但沒有指出其邊界，即最高維的元素數量，就像指向字符的指針即等效一個字符串,不要把指向字符的指針，說成指向字符串的指針。這與數組的嵌套定義相一致。第10頁，課件共125頁，創(chuàng)作于2023年2月7.1.1堆內存的分配與釋放比較：float(*cp)[30][20];

//三級指針float(*bp)[20];//二級指針cp=newfloat[1][20][30];bp=newfloat[30][20];兩個數組都是由600個浮點數組成，前者是只有一個元素的三維數組，每個元素為30行20列的二維數組，而另一個是有30個元素的二維數組，每個元素為20個元素的一維數組。刪除這兩個動態(tài)數組可用下式：delete[]cp;

//刪除（釋放）三維數組delete[]bp;//刪除（釋放）二維數組第11頁，課件共125頁，創(chuàng)作于2023年2月7.1.1堆內存的分配與釋放【例7.2】動態(tài)創(chuàng)建和刪除一個m*n個元素的數組。采用指針數組方式來完成二維數組的動態(tài)創(chuàng)建。constintm=4;

//行數constintn=6;

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

data=newdouble*[m];

//設置行

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

data[j]=newdouble[n];

//設置列

if(data[j]==0){cout<<"Couldnotallocate.Bye...";exit(-1);}}第12頁，課件共125頁，創(chuàng)作于2023年2月7.1.1堆內存的分配與釋放

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

//初始化數組元素

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

delete[]data;}

第13頁，課件共125頁，創(chuàng)作于2023年2月7.1.1堆內存的分配與釋放指針使用的幾個問題：1.

動態(tài)分配失敗。返回一個空指針（NULL），表示發(fā)生了異常，堆資源不足，分配失敗。2.指針刪除與堆空間釋放。刪除一個指針p（deletep;）實際意思是刪除了p所指的目標（變量或對象等），釋放了它所占的堆空間，而不是刪除ｐ本身，釋放堆空間后，ｐ成了空懸指針。第14頁，課件共125頁，創(chuàng)作于2023年2月7.1.1堆內存的分配與釋放３．內存泄漏（memoryleak）和重復釋放。new與delete是配對使用的，delete只能釋放堆空間。如果new返回的指針值丟失，則所分配的堆空間無法回收，稱內存泄漏，同一空間重復釋放也是危險的，因為該空間可能已另分配，所以必須妥善保存new返回的指針，以保證不發(fā)生內存泄漏，也必須保證不會重復釋放堆內存空間。４．動態(tài)分配的變量或對象的生命期。無名對象的生命期并不依賴于建立它的作用域，比如在函數中建立的動態(tài)對象在函數返回后仍可使用。我們也稱堆空間為自由空間（freestore）就是這個原因。但必須記住釋放該對象所占堆空間，并只能釋放一次，在函數內建立，而在函數外釋放是一件很容易失控的事，往往會出錯。

第15頁，課件共125頁，創(chuàng)作于2023年2月7.1.2

堆對象與構造函數

通過new建立的對象要調用構造函數，通過deletee刪除對象也要調用析構函數。CGoods*pc;pc=newCGoods;

//分配堆空間，并構造一個無名的CGoods對象；…….deletepc;

//先析構，然后將內存空間返回給堆；堆對象的生命期并不依賴于建立它的作用域，所以除非程序結束，堆對象（無名對象）的生命期不會到期，并且需要顯式地用delete語句析構堆對象，上面的堆對象在執(zhí)行delete語句時，C++自動調用其析構函數。第16頁，課件共125頁，創(chuàng)作于2023年2月7.1.2

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

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

}

……}正因為構造函數可以有參數，所以new后面類（class）類型也可以有參數。這些參數即構造函數的參數。但對創(chuàng)建數組，則無參數，并只調用缺省的構造函數。見下例類說明：第17頁，課件共125頁，創(chuàng)作于2023年2月7.1.2

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

//調用三參數構造函數

pc1=newCGoods();//調用缺省構造函數

cout<<’輸入商品類數組元素數’<<endl;cin>>n;pc2=newCGoods[n];

//動態(tài)建立數組，不能初始化，調用n次缺省構造函數

……

deletepc;deletepc1;delete[]pc2;}第18頁，課件共125頁，創(chuàng)作于2023年2月7.1.2

堆對象與構造函數這里再次強調：由堆區(qū)創(chuàng)建對象數組，只能調用缺省的構造函數，不能調用其他任何構造函數。如果沒有缺省的構造函數，則不能創(chuàng)建對象數組。第19頁，課件共125頁，創(chuàng)作于2023年2月7.1.3

淺拷貝與深拷貝

缺省拷貝構造函數，可用一個類對象初始化另一個類對象，稱為缺省的按成員拷貝，而不是對整個類對象的按位拷貝。這稱為淺拷貝。

P堆對象堆對象PP

圖7.1淺拷貝

拷貝前拷貝后

第20頁，課件共125頁，創(chuàng)作于2023年2月7.1.3

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

堆對象PP堆對象

圖7.2深拷貝

第21頁，課件共125頁，創(chuàng)作于2023年2月7.1.3

淺拷貝與深拷貝【例7.2】定義拷貝（copystructor）和拷貝賦值操作符（copyAssignmentOperator）實現深拷貝。

學生類定義：classstudent{char*pName;

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

//缺省構造函數

student(char*pname);

//帶參數構造函數

student(student&s);

//拷貝構造函數

~student();

//析構函數

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

//拷貝賦值操作符檢驗主函數和運行結果第22頁，課件共125頁，創(chuàng)作于2023年2月7.1.3

淺拷貝與深拷貝堆內存是最常用的需要拷貝構造函數自定義的資源，但不是唯一的，如打開文件等。如果類需要析構函數來析構資源，則類也需要一個自定義的拷貝構造函數。對象的拷貝就是深拷貝了。第23頁，課件共125頁，創(chuàng)作于2023年2月7.2鏈表與鏈表的基本操作

線性表是最簡單，最常用的一種數據結構。線性表的邏輯結構是n個數據元素的有限序列（a1,a2,…,an）。而線性表的物理結構，除順序表，還有鏈表

7.

2.

1單鏈表基本算法

7.

2.

3雙向鏈表7.

2.

2單鏈表類型模板第24頁，課件共125頁，創(chuàng)作于2023年2月7.2.1單鏈表基本算法

單鏈表（SinglyLinkedlist）也稱線性鏈表。每個數據元素占用一個節(jié)點（Node）。一個節(jié)點包含兩個域，一個域存放數據元素info，其數據類型由應用問題決定，另一個存放指向該鏈表中下一個節(jié)點的指針link。節(jié)點定義如下：typedefintDatatype;//數據為整型structnode{Datatypeinfo;node*link;}在C/C++中允許結構（或對象）成員是結構自身的指針類型，通過指針引用自身這種類型的結構。但結構成員決不能是結構自身類型，即結構不能自己定義自己，這會導致一個無窮遞歸的定義。

第25頁，課件共125頁，創(chuàng)作于2023年2月

7.2.1單鏈表基本算法單鏈表的第一個結點的地址可通過鏈表的表頭指針head找到，

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

info1

info0

……h(huán)aed圖7.3單向鏈表結構

單鏈表的插入與刪除：只要改變鏈中結點指針的值，無需移動表中的元素，就能實現插入和刪除操作。插入算法有三種情況，我們希望在單鏈表中包含數據infoi的結點之前插入一個新元素，則infoi可在第一個結點，或在中間結點，如未找到，則把新結點插在鏈尾結點之后。

第26頁，課件共125頁，創(chuàng)作于2023年2月7.2.1單鏈表基本算法newnodeinfoxinfo0info1·············headhead插在鏈首

首先新結點的link指針指向info0所在結點，然后，head指向新結點。即：newnode→link=head；//注意：鏈表操作次序非常重要head=newnode；第27頁，課件共125頁，創(chuàng)作于2023年2月7.2.1單鏈表基本算法infoxinfoi-1infoipｑnewnode插在中間

首先用工作指針p找到指定結點，而讓指針q指向緊跟其后的結點，令infoi-1所在結點的link指針指向新結點，而后讓新結點的link指向infoi所在結點。即：newnode→link=p；//或newnode→link=q→link；可用于插入某結點之后q→link=newnode；第28頁，課件共125頁，創(chuàng)作于2023年2月7.2.1單鏈表基本算法infox

newnode············p^infon-1^插在隊尾只要工作指針p找到隊尾，即可鏈在其后：p→link=newnode；newnode.link=NULL;第29頁，課件共125頁，創(chuàng)作于2023年2月7.2.1單鏈表基本算法headtailpinfo1tailpinfo0tail^1.向后生成鏈表算法：node*createdown(){Datatypedata;Node*head,*tail,*p;head=newnode;//建立鏈表頭結點

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

p=new(node);//每輸入一個數申請一個結點p->info=data;//添入數據tail->link=p1;//新結點接到鏈尾

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

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

returnhead;//返回頭指針}第30頁，課件共125頁，創(chuàng)作于2023年2月7.2.1單鏈表基本算法head^info0

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

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

//建立的總是第一個結點

p=newnode;p->info=data;p->link=head->link;//新結點放在原鏈表前方

head->link=p;

//頭結點放新結點之前}returnhead;}第31頁，課件共125頁，創(chuàng)作于2023年2月7.2.1單鏈表基本算法3.鏈表查找算法（Traversal），按數據（關鍵字）查找：node*traversal(node*head,Datatypedata){node*p=head->link;while(p!=NULL||p->info!=data)p=p->link;returnp;//p為NULL則未找到}返回值為指針p，指向鏈表中找到的結點。4.在單鏈表的p節(jié)點后插入一個信息域為x的新節(jié)點（注意只有一種情況了）。voidinsert(nodep,Datatypex){node*q=newnode;q->info=x;q->link=p->link;p->link=q;}第32頁，課件共125頁，創(chuàng)作于2023年2月7.2.1單鏈表基本算法5.刪除單鏈表節(jié)點*p后面節(jié)點voiddel(node*p){node*q;q=p->link;p->link=q->link;deleteq;

//如果要把該節(jié)點移入另一個鏈中，則可將q返回。}第33頁，課件共125頁，創(chuàng)作于2023年2月7.2.2單鏈表類型模板【例7.4_h】單鏈表類模板。

首先看結點類template<typenameT>classList;template<typenameT>classNode{Tinfo;//數據域

Node<T>*link;//指針域public:Node();//生成頭結點的構造函數

Node(constT&data);//生成一般結點的構造函數

voidInsertAfter(Node<T>*p);//在當前結點后插入一個結點

Node<T>*RemoveAfter();//刪除當前結點的后繼結點

friendclassList<T>;

//以List為友元類，List可直接訪問Node的私有函數};第34頁，課件共125頁，創(chuàng)作于2023年2月再定義鏈表類:template<typenameT>classList{Node<T>*head,*tail;//鏈表頭指針和尾指針public:List();//構造函數，生成頭結點(空鏈表)~List();//析構函數

voidMakeEmpty();//清空鏈表，只余表頭結點

Node<T>*Find(Tdata);

//搜索數據域與data相同的結點，返回該結點的地址

intLength();//計算單鏈表長度

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

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

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

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

Node<T>*CreatNode(Tdata);//創(chuàng)建結點(孤立結點)Node<T>*DeleteNode(Node<T>*p);};//刪除指定結點7.2.2單鏈表類型模板第35頁，課件共125頁，創(chuàng)作于2023年2月7.2.2單鏈表類型模板【例7.4】由鍵盤輸入16個整數，以這些整數作為結點數據，生成兩個鏈表，一個向前生成，一個向后生成，輸出兩個表。然后給出一個整數在一個鏈表中查找，找到后刪除它，再輸出該表。清空該表，再按升序生成鏈表并輸出。在本例中程序只需調用類模板中的成員函數就可以完成所有鏈表操作。第36頁，課件共125頁，創(chuàng)作于2023年2月7.2.3雙向鏈表

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

info0

infon-1.’.’.’.’.’.’

info1head(a)非空表head(b)空表第37頁，課件共125頁，創(chuàng)作于2023年2月7.2.3雙向鏈表假設指針p指向雙向循環(huán)鏈表的某一個結點，那么，p->llink指示P所指結點的前驅結點，p->rlink指示后繼結點。p->llink->rlink指示本結點的前驅結點的后繼結點，即本結點，間接訪問符->可以連續(xù)使用。pllinkrlinkrlinkllinkrlink前驅結點llink本結點后繼結點間接訪問符的使用【例7.5】雙向鏈表類模板和結點類模板。第38頁，課件共125頁，創(chuàng)作于2023年2月7.3棧與隊列的基本操作及其應用

棧和隊都是特殊的線性表，限制存取位置的線性結構，可以由順序表實現，也可以由鏈表實現。

7.

3.

1棧與應用

7.

3.

2

隊列

第39頁，課件共125頁，創(chuàng)作于2023年2月7.3.1棧與應用

棧定義為只允許在表的一端進行插入和刪除的線性表。允許進行插入和刪除的一端叫做棧頂(top)，而另一端叫棧底(bottom)。棧中沒有任何元素時，稱為空棧。進棧時最先進棧的在最下面，最后的在最上面，后來居上。而出棧時順序相反，最后進棧的最先出棧，而最先進棧的a0最后出棧。所以棧又稱作后進先出（LIFO：LastInFirstOut）的線性表。?？梢杂庙樞虮韺崿F，稱順序棧；也可以用鏈表實現，稱鏈棧。第40頁，課件共125頁，創(chuàng)作于2023年2月7.3.1棧與應用

參見下圖，設給定棧s=(a0，a1，……，an-1)，稱a0為棧底，an-1為棧頂。進棧時最先進棧的a0在最下面，an-1在最上面。而出棧時順序相反，最后進棧的an-1最先出棧，而最先進棧的a0最后出棧。a0an-2……a1an-1bottom進棧toptoptoptoptop出棧圖示為順序棧。其中棧底bottom是指向棧數據區(qū)的下一單元，這樣判斷是否為空棧會更方便，只需top與bottom相同就是空棧。通常只有棧頂與操作有關。第41頁，課件共125頁，創(chuàng)作于2023年2月7.3.1棧與應用【例7.6】順序棧的類模板定義：template<typenameT>classStack{inttop;//棧頂指針（下標）

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

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

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

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

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

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

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

voidPrintStack();};//輸出棧內所有數據第42頁，課件共125頁，創(chuàng)作于2023年2月7.3.1棧與應用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';//注意先進后出

cout<<endl; istack.Pop();//下溢出}第43頁，課件共125頁，創(chuàng)作于2023年2月7.3.1棧與應用【例7.7_h】鏈棧的結點類模板:

template<typenameT>classNode{//鏈棧結點類模板

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

……^

……

鏈棧第44頁，課件共125頁，創(chuàng)作于2023年2月7.3.1棧與應用鏈棧類模板，無頭結點鏈表template<typenameT>classStack{//鏈棧類模板

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

TPop();//彈出

TGetTop();//取棧頂元素

voidMakeEmpty();//清空棧

boolIsEmpty(){returntop==NULL;}};第45頁，課件共125頁，創(chuàng)作于2023年2月7.3.1棧與應用

順序棧和鏈棧邏輯功能是一樣，盡管這里兩個棧模板的成員函數功能選擇稍有出入，因為順序?？梢噪S機訪問其中的元素，而鏈棧只能順序訪問，但邏輯上完全可以做到一樣（物理結構不同）。順序棧必須先開一定大小內存空間，執(zhí)行起來簡單，速度快，可能溢出。鏈棧內存空間隨用隨開，不會溢出，但執(zhí)行復雜（不斷地動態(tài)分配），速度慢。?？捎糜诒磉_式的計算。現考慮最簡單的+、-、*、/四個運算符和結束符＝組成的算術表達式，只有兩個優(yōu)先級，先*/，后+-。第46頁，課件共125頁，創(chuàng)作于2023年2月Ncba＊＋O＊＋at1deNat1de＋＋／－O／－－＋O－＋Nt1at2t1at2t3aNt3aN＋O＋Ob*c->t1d/e->t2t1-t2->t3a+t3->t4N：數棧O：運算符

(a)

(b)

(c)

(d)

(e)

表達式運算

設有：a+b*c-d/e=；為實現運算符的優(yōu)先級，采用兩個棧：一個數棧，一個運算符棧。數棧暫存操作數，運算符棧暫存運算符。從左向右掃描算術表達式，遇到操作數，壓入數棧；遇到運算符，則與運算符棧棧頂的運算符比較優(yōu)先級，若新的運算符優(yōu)先級高，或運算符?？?，則壓棧。否則將棧頂運算符出棧，與數字棧出棧的兩個數據進行運算，結果壓入數棧，再將新運算符壓棧。繼續(xù)掃描，直到遇到＝號，掃描結束。棧中數據繼續(xù)按前面規(guī)則出棧。第47頁，課件共125頁，創(chuàng)作于2023年2月7.3.1棧與應用【例7.7】模擬簡單計算器，該計算器只認+-*/四個運算符，輸入為整數。表達式結束符使用＝號，清空棧用‘c’字符。使用‘z’字符表示結束。簡易計算器類定義：classCalculator{Stack<int>Nstack;//使用鏈棧

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

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

voidCompute(charOpr);//讀算式

voidClear(void);};//清除在VC++平臺上演示例7.7第48頁，課件共125頁，創(chuàng)作于2023年2月7.3.2隊列

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

a0a1a2…an-1…front元素移動方向rear圖7.15隊列

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

第49頁，課件共125頁，創(chuàng)作于2023年2月7.3.2隊列rearfrontADCABDECFHGBCD進隊A進隊空隊DCAB出隊EFGH進隊rearfrontrearrearrearfrontfrontfront圖7.16順序隊列的插入和刪除

由圖可見：空隊時指針（下標）front和rear在一起都指向隊前方，當有元素進隊，則rear后移；有元素出隊，則front后移，最后分配給隊的前端不再被利用。第50頁，課件共125頁，創(chuàng)作于2023年2月7.3.2隊列隊列總是做成一個邏輯上的循環(huán)隊列注意，空隊時rear=front，滿隊時必須空一個位置第51頁，課件共125頁，創(chuàng)作于2023年2月7.3.2隊列循環(huán)隊列浪費一個位置好像太可惜，特別在該位置中存放一個很大的對象時。實際上只能有所不為才能有所為，而且對象很大時，總是由索引（指針）來排隊。若想利用這個空間，必然加一個標志來表示隊空/隊滿，進隊出隊都要判斷，使用上更不方便。

用鏈表實現隊列無此問題

【例7.8】順序存儲方式的循環(huán)隊列類模板?！纠?.9】鏈隊類模板。鏈首出隊，鏈尾入隊。無鏈首結點方式。第52頁，課件共125頁，創(chuàng)作于2023年2月7.4

二叉樹

樹形結構是一類重要的非線性數據，樹和二叉樹是常用的樹形結構。

7.4.2

二叉樹的遍歷

7.4.1

二叉樹的概念

7.4.3

排序二叉樹

第53頁，課件共125頁，創(chuàng)作于2023年2月7.4.1

二叉樹的概念

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

第54頁，課件共125頁，創(chuàng)作于2023年2月7.4.1

二叉樹的概念ABCDEFGIHJLKONM…………0層……1層2層3層深度圖7.17樹的示意圖

結點，包括數據項和多個指針項，指針項數目并不固定，且無次序。結點的度，結點所擁有的子樹數量。葉結點，度為0的結點，如G，I，J，K，L，M，N，O結點。分支結點，度≥1的結點。孩子結點，若結點x有子樹，則子樹根結點即為x的孩子結點。第55頁，課件共125頁，創(chuàng)作于2023年2月7.4.1

二叉樹的概念ABCDEFGIHJLKONM…………0層……1層2層3層深度圖7.17樹的示意圖

雙親結點，若結點x有孩子，它即為孩子的雙親。兄弟結點，同一雙親的結點互稱為兄弟。結點的層次，從根到該結點所經路徑上的分支條數。樹的深度,樹中結點的層次數。樹的度，樹中結點度的最大值。

第56頁，課件共125頁，創(chuàng)作于2023年2月7.4.1

二叉樹的概念

二叉樹（BinaryTree）是另一種獨立的樹形結構。二叉樹是結點的一個有限集合，該集合或為空，或是由一個根結點及兩棵樹分別稱為左子樹和右子樹的（注意有左右之分）互不相交的二叉樹組成，其中左右子樹分別可以為空子樹或均為空樹。這也是一個遞歸的定義。二叉樹的特點是：每個結點最多兩個孩子，并且子樹有左右之分。二叉樹的基本性質：

1．二叉樹的第i層上最多有2i-1(i>=1)個結點；

2．深度為h的二叉樹中最多有2h-1個結點；

3．在任一棵二叉樹中，有n0葉子結點，有n2個度為2的結點，則有n0=n2+1。第57頁，課件共125頁，創(chuàng)作于2023年2月7.4.1

二叉樹的概念【例7.9】畫出有三個結點的所有二叉樹。解：結果見圖7.18，共5種。圖7.18

5種不同的三結點二叉樹

第58頁，課件共125頁，創(chuàng)作于2023年2月7.4.1

二叉樹的概念二叉樹有滿二叉樹和完全二叉樹，分別如圖7.19和圖7.20，完全二叉樹已有的結點排序與滿二叉樹相同。

123456798101114131215圖7.19滿二叉樹

12345679810圖7.20完全二叉樹

第59頁，課件共125頁，創(chuàng)作于2023年2月7.4.1

二叉樹的概念下面給出鏈式儲存方式的二叉樹。每個結點有三個域：數據域、左孩子指針和右孩子指針，見圖7.21。

lchildrchildinfo圖7.21二叉樹結點

第60頁，課件共125頁，創(chuàng)作于2023年2月7.4.1

二叉樹的概念二叉樹類結點類模板定義如下：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;}第61頁，課件共125頁，創(chuàng)作于2023年2月7.4.1

二叉樹的概念

TGetinfo(){returninfo;}//取得結點數據

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

//修改結點數據

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

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

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

//設置左指針

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

//設置右指針

friendclassBinaryTree<T>;//二叉樹類說明為友元類第62頁，課件共125頁，創(chuàng)作于2023年2月7.4.2二叉樹的遍歷

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

第63頁，課件共125頁，創(chuàng)作于2023年2月

7.4.2二叉樹的遍歷例如：前序遍歷訪問次序為ABDEGCFH。

圖7.22二叉樹遍歷

中序遍歷結果為DBGEAFHC。后序遍歷結果為DGEBHFCA。

第64頁，課件共125頁，創(chuàng)作于2023年2月7.4.2二叉樹的遍歷【例7.10】二叉樹類模板（其中二叉樹生成借用二叉排序樹，見下節(jié)）。特別注意插入結點時，第二參數為指針的引用！否則不能建立樹。為什么？請讀者自己思考。本例采用簡單的接口函數，而把較復雜的算法作為私有函數。

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

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

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

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

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

//插入結點，參數為引用！

voidDestory(Node<T>*Current);//刪除樹第65頁，課件共125頁，創(chuàng)作于2023年2月7.4.2二叉樹的遍歷public:BinaryTree(){root=NULL;} //空樹構造函數

~BinaryTree(){Destory(root);} //析構函數

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

voidInOrder(){InOrder(root);}

//中序遍歷，公有函數為接口

voidPreOrder(){PreOrder(root);}

//前序遍歷，公有函數為接口

voidPostOrder(){PostOrder(root);}

//后序遍歷，公有函數為接口};檢驗主函數第66頁，課件共125頁，創(chuàng)作于2023年2月7.4.2二叉樹的遍歷【例7.13】某二叉樹先序遍歷為ABCEFDGHIJK，中序遍歷為ECFBDGAIHJK繪出該二叉樹。

ABCDEFGHIJK圖7.23例7.11二叉樹

按同樣方法推出A的右子樹。結果如圖7.23?？梢宰C明已知先序和中序訪問次序可以唯一確定一棵二叉樹。

解：由先序知A為根結點，而EFBDG為左子樹，IHJK為右子樹。由先序中的BCEFDG知B為左子樹根結點，由中序中的ECFBDG知ECF為其左子樹，而DG為右子樹。再由先序CEF知C為左子樹根結點，由中序ECF知E為C左子樹，F為的右子樹。再由先序DG知，D為B的右子樹根結點，由中序DG知G為D的右子樹。第67頁，課件共125頁，創(chuàng)作于2023年2月7.4.3排序二叉樹

二叉排序樹（BinarySortingTree）又稱二叉搜索樹（BinarySearchTree），是一種特殊結構的二叉數，作為一種排序和查找的手段，對應有序表的對半查找，通常亦被稱為數表。其定義也是遞歸的。二叉排序樹的定義：二叉排序樹或者是空樹或者是具有下述性質的二叉數，其左子樹上所有結點的數據值均小于根結點的數據值；右子樹上所有結點的數據值均大于等于根結點的數據值，左子樹和右子樹又各是一棵二叉排序樹。第68頁，課件共125頁，創(chuàng)作于2023年2月7.4.3排序二叉樹

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

101826812222911241615圖7.24二叉排序樹例

第69頁，課件共125頁，創(chuàng)作于2023年2月二叉排序樹的結點插入（可生成排序二叉樹）生成算法：對任意一組數據元素序列{a0，a1，a2，…，an-1}。要生成二叉排序樹的過程為：1.

令a0為二叉樹的根結點。2.

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

7.4.3排序二叉樹第70頁，課件共125頁，創(chuàng)作于2023年2月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++平臺上演示例7.13【例7.13】排序二叉樹查找函數。算法：用中序遍歷即可，但遞歸慢，下面為迭代查找算法。第71頁，課件共125頁，創(chuàng)作于2023年2月7.5MFC對象和Windows對象的關系

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

....其它成員m_hWndhwndCWnd類對象HWND句柄類型wndwindows對象句柄Windows操作系統(tǒng)窗口對象MFC窗口對象與Windows窗口對象的關系第72頁，課件共125頁，創(chuàng)作于2023年2月7.5MFC對象和Windows對象的關系

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

第73頁，課件共125頁，創(chuàng)作于2023年2月7.5MFC對象和Windows對象的關系

MFC封裝了幾乎所有Windows的API函數，所以上面的API函數，可以用CWnd的成員函數代替。成員函數Create()可以代替API函數CreateWindows()并加上另一個成員函數Attach()的全部功能，建立一個Windows操作系統(tǒng)的窗口對象，并把句柄自動保存在MFC窗口對象wnd的m_hwnd成員數據中。通常MFC程序員直接使用CWnd的成員函數就可以了。

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

//動態(tài)建立框架窗口對象pFrame->Create(NULL,”Ex7_xx”,ws_OVERLAPPENDWINDOW,rect,NULL,MAKEINTRESOURCE(IDR_MENUI),0,NULL);//建立與pFrame指向動態(tài)框架窗口對象相連的Windows//框架窗口第76頁，課件共125頁，創(chuàng)作于2023年2月7.6圖書流通管理系統(tǒng)設計——鏈表類應用在圖書館類中，存儲在館圖書、讀者、管理員及借閱信息的數組的大小都是固定的。當這些對象的數目超過數組大小時，就必然發(fā)生溢出，通?？偸恰按箝_小用”。通過本章學習后應考慮采用動態(tài)數組或鏈表結構來存儲對象。

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

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

DblNode(); //頭結點

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

friendclassLibrary; //將圖書館類聲明為友元};第77頁，課件共125頁，創(chuàng)作于2023年2月7.6圖書流通管理系統(tǒng)設計——鏈表類應用template<typenameT>classDblList{ //鏈表類模板定義

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

DblNode<T>*Find(Tdata);//搜索數據與定值相同的結點

DblNode<T>*Find(intdata);//按某個關鍵字搜索

voidMakeEmpty(); //清空鏈表

voidShowList(); //顯示鏈表所有元素};第78頁，課件共125頁，創(chuàng)作于2023年2月新增加按照關鍵字搜索的函數：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)設計——鏈表類應用第79頁，課件共125頁，創(chuàng)作于2023年2月圖書館類中記錄在館圖書、讀者、管理員及借閱信息的數組改為鏈表類，參見圖7.27。classLibrary{ //封裝圖書館流通

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

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

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

DblList<Manager>manager;//記錄管理員的鏈表7.6圖書流通管理系統(tǒng)設計——鏈表類應用第80頁，課件共125頁，創(chuàng)作于2023年2月7.6圖書流通管理系統(tǒng)設計——鏈表類應用圖7.27圖書館類

intitemNum;//記錄在館圖書數目

intreaderNum;//記錄讀者數目

intloanNum; //記錄借閱信息數目

intmanagerNum;//記錄管理員數目public:Library();//構造函數

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

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

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

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

intShowMainMenu();//顯示主菜單

voidBorrow();//借書操作

voidReturn();//還書操作

voidRequire();//查詢操作};第81頁，課件共125頁，創(chuàng)作于2023年2月7.6圖書流通管理系統(tǒng)設計——鏈表類應用修改讀者、在館圖書、管理員及借閱信息類。首先，讀者類Reader原來用數組記錄所借的書，在此用一個Item類的指針代替，用單鏈表記錄所借的書，該指針是單鏈表頭指針。對讀者進行借書或還書操作是通過對單鏈表插入或刪除結點實現。這個單鏈表只是附在讀者類中，不是一個規(guī)范的單鏈表類。

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

管理員類ManagerGetCode函數訪問其編號，增加Show函數顯示其基本信息。

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

第82頁，課件共125頁，創(chuàng)作于2023年2月7.6圖書流通管理系統(tǒng)設計——鏈表類應用圖7.28圖書流通管理系統(tǒng)中的類第83頁，課件共125頁，創(chuàng)作于2023年2月借書操作：voidLibrary::Borrow(){intcode,barcode;Loanln; DblNode<Item>*ti=NULL;

//定義數據為Item類型的結點指針

DblNode<Manager>*tm=NULL;

//定義數據為Manager類型的結點指針

DblNode<Reader>*tr=NULL;

//定義數據為Reader類型的結點指針

cout<<"借書，請輸入借書證號：\n";cin>>code;tr=reader.Find(code);//查找讀者7.6圖書流通管理系統(tǒng)設計——鏈表類應用第84頁，課件共125頁，創(chuàng)作于2023年2月if(tr){cout<<"借書，請選擇書的條碼\n";cout<<"書名\t作者\t分類號\t條碼\n";item.ShowList();//顯示可借閱書

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

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

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

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

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

itemNum--;7.6圖書流通管理系統(tǒng)設計——鏈表類應用第85頁，課件共125頁，創(chuàng)作于2023年2月7.6圖書流通管理系統(tǒng)設計——鏈表類應用

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

ln.item=ti-