1、動態內存分配第1頁，共125頁，2022年，5月20日，15點8分，星期一7.1 堆內存分配 7.5 MFC對象和Windows對象的關系 7.4二叉樹 7.3 棧與隊列的基本操作及其應用 7.2 鏈表與鏈表的基本操作 第七章 動態內存分配 7.6 圖書流通管理系統設計鏈表類應用 第2頁，共125頁，2022年，5月20日，15點8分，星期一7.1 堆內存分配 堆內存的分配與釋放 7.1.2 堆對象與構造函數 7.1.3 淺拷貝與深拷貝 通常定義變量（或對象），編譯器在編譯時都可以根據該變量（或對象）的類型知道所需內存空間的大小，從而系統在適當的時候為他們分配確定的存儲空間。這種內存分配稱為靜

2、態存儲分配有些操作對象只有在程序運行時才能確定，這樣編譯器在編譯時就無法為他們預定存儲空間，只能在程序運行時，系統根據運行時的要求進行內存分配，這種方法稱為動態存儲分配。所有動態存儲分配都在堆區中進行。第3頁，共125頁，2022年，5月20日，15點8分，星期一7.1.1 堆內存的分配與釋放當程序運行到需要一個動態分配的變量或對象時，必須向系統申請取得堆中的一塊所需大小的存貯空間，用于存貯該變量或對象。當不再使用該變量或對象時，也就是它的生命結束時，要顯式釋放它所占用的存貯空間，這樣系統就能對該堆空間進行再次分配，做到重復使用有限的資源。在C+中，申請和釋放堆中分配的存貯空間，分別使用new

3、和delete的兩個運算符來完成，其使用的格式如下：指針變量名=new 類型名(初始化式)；delete 指針名;new運算符返回的是一個指向所分配類型變量（對象）的指針。對所創建的變量或對象，都是通過該指針來間接操作的，而動態創建的對象本身沒有名字。 第4頁，共125頁，2022年，5月20日，15點8分，星期一 7.1.1 堆內存的分配與釋放一般定義變量和對象時要用標識符命名，稱命名對象，而動態的稱無名對象(請注意與棧區中的臨時對象的區別，兩者完全不同：生命期不同，操作方法不同，臨時變量對程序員是透明的)。堆區是不會自動在分配時做初始化的（包括清零），所以必須用初始化式(initializ

4、er)來顯式初始化。new表達式的操作序列如下：從堆區分配對象，然后用括號中的值初始化該對象。從堆區分配對象時，new表達式調用庫操作符new()。例如： int *pi=new int(0);它與下列代碼序列大體等價：int ival=0;int *pi=&ival;只是pi現在所指向的變量是由庫操作符new()分配的，位于程序的堆區中，并且該對象未命名。 第5頁，共125頁，2022年，5月20日，15點8分，星期一 7.1.1 堆內存的分配與釋放堆i下面看演示：用初始化式(initializer)來顯式初始化 int *pi=new int(0);當pi生命周期結束時，必須釋放pi所指向

5、的目標： delete pi;注意這時釋放了pi所指的目標的內存空間，也就是撤銷了該目標，稱動態內存釋放（dynamic memory deallocation），但指針pi本身并沒有撤銷，該指針所占內存空間并未釋放。 第6頁，共125頁，2022年，5月20日，15點8分，星期一7.1.1 堆內存的分配與釋放對于數組進行動態分配的格式為：指針變量名=new 類型名下標表達式;Delete 指向該數組的指針變量名;兩式中的方括號是非常重要的，兩者必須配對使用。如果delete語句中少了方括號，因編譯器認為該指針是指向數組第一個元素的指針，會產生回收不徹底的問題（只回收了第一個元素所占空間），加

6、了方括號后就轉化為指向數組的指針，回收整個數組。 delete 的方括號中不需要填數組元素數，系統自知。即使寫了，編譯器也忽略。 請注意“下標表達式”不是常量表達式，即它的值不必在編譯時確定，可以在運行時確定。第7頁，共125頁，2022年，5月20日，15點8分，星期一7.1.1 堆內存的分配與釋放【例7.1】動態數組的建立與撤銷#include #include void main()int n;char *pc;cout請輸入動態數組的元素個數n; /在運行時確定，可輸入17pc=new charn;strcpy(pc,堆內存的動態分配);coutpcendl;delete pc;/釋放

7、pc所指向的n個字符的內存空間return ;第8頁，共125頁，2022年，5月20日，15點8分，星期一7.1.1 堆內存的分配與釋放動態分配數組有三個特點：1. 變量n在編譯時沒有確定的值，而是在運行中輸入，按運行時所需分配堆空間，這一點是動態分配的優點，可克服數組“大開小用”的弊端，在表、排序與查找中的算法，若用動態數組，通用性更佳。delete pc是將n個字符的空間釋放，而用delete pc則只釋放了一個字符的空間；2. 如果有一個char *pc1，令pc1=p，同樣可用delete pc1來釋放該空間。盡管C+不對數組作邊界檢查，但在堆空間分配時，對數組分配空間大小是紀錄在案

8、的。3. 沒有初始化式（initializer），不可對數組初始化。 第9頁，共125頁，2022年，5月20日，15點8分，星期一7.1.1 堆內存的分配與釋放多維數組動態分配：new 類型名下標表達式1 下標表達式2;建立一個動態三維數組float (*cp)3020 ; /指向一個30行20列數組的指針cp=new float 15 30 20; /建立由15個30*20數組組成的數組；注意cp等效于三維數組名，但沒有指出其邊界，即最高維的元素數量，就像指向字符的指針即等效一個字符串,不要把指向字符的指針，說成指向字符串的指針。這與數組的嵌套定義相一致。第10頁，共125頁，2022年，

9、5月20日，15點8分，星期一7.1.1 堆內存的分配與釋放比較：float(*cp) 30 20; /三級指針float (*bp) 20; /二級指針cp=new float 1 20 30;bp=new float 30 20;兩個數組都是由600個浮點數組成，前者是只有一個元素的三維數組，每個元素為30行20列的二維數組，而另一個是有30個元素的二維數組，每個元素為20個元素的一維數組。刪除這兩個動態數組可用下式：delete cp; /刪除（釋放）三維數組delete bp; /刪除（釋放）二維數組第11頁，共125頁，2022年，5月20日，15點8分，星期一7.1.1 堆內存的分

10、配與釋放【例7.2】 動態創建和刪除一個m*n個元素的數組。采用指針數組方式來完成二維數組的動態創建。const int m=4; /行數const int n=6; /列數先看二維數組的動態創建：void main() double *data; data = new double*m; /設置行 if (data ) = 0) cout Could not allocate. Bye .;exit(-1); for(int j=0;jm;j+) dataj = new doublen; /設置列 if (dataj = 0) cout Could not allocate. Bye .;e

11、xit(-1); 第12頁，共125頁，2022年，5月20日，15點8分，星期一7.1.1 堆內存的分配與釋放 for (int i=0;im;i+) for (int j=0;jn;j+) dataij=i*n+j; /初始化數組元素 display(data); de_allocate(data); return; 再看二維數組的撤銷與內存釋放：void de_allocate(double *data) for (int i=0;im;i+) delete datai; /注意撤銷次序，先列后行，與設置相反 delete data; 第13頁，共125頁，2022年，5月20日，15點

12、8分，星期一7.1.1 堆內存的分配與釋放指針使用的幾個問題：1. 動態分配失敗。返回一個空指針（NULL），表示發生了異常，堆資源不足，分配失敗。2. 指針刪除與堆空間釋放。刪除一個指針p（delete p;）實際意思是刪除了p所指的目標（變量或對象等），釋放了它所占的堆空間，而不是刪除本身，釋放堆空間后，成了空懸指針。第14頁，共125頁，2022年，5月20日，15點8分，星期一7.1.1 堆內存的分配與釋放內存泄漏（memory leak）和重復釋放。new與delete 是配對使用的， delete只能釋放堆空間。如果new返回的指針值丟失，則所分配的堆空間無法回收，稱內存泄漏，同一

13、空間重復釋放也是危險的，因為該空間可能已另分配，所以必須妥善保存new返回的指針，以保證不發生內存泄漏，也必須保證不會重復釋放堆內存空間。動態分配的變量或對象的生命期。無名對象的生命期并不依賴于建立它的作用域，比如在函數中建立的動態對象在函數返回后仍可使用。我們也稱堆空間為自由空間（free store）就是這個原因。但必須記住釋放該對象所占堆空間，并只能釋放一次，在函數內建立，而在函數外釋放是一件很容易失控的事，往往會出錯。 第15頁，共125頁，2022年，5月20日，15點8分，星期一堆對象與構造函數 通過new建立的對象要調用構造函數，通過deletee刪除對象也要調用析構函數。CGo

14、ods *pc;pc=new CGoods; /分配堆空間，并構造一個無名的CGoods對象；.delete pc; /先析構，然后將內存空間返回給堆；堆對象的生命期并不依賴于建立它的作用域，所以除非程序結束，堆對象（無名對象）的生命期不會到期，并且需要顯式地用delete語句析構堆對象，上面的堆對象在執行delete語句時，C+自動調用其析構函數。第16頁，共125頁，2022年，5月20日，15點8分，星期一堆對象與構造函數class CGoods char Name21; int Amount; float Price; float Total value;public: CGoods(

15、); /缺省構造函數。 CGoods(char* name,int amount ,float price) strcpy(Name,name); Amount=amount; Price=price; Total_value=price*amount; 正因為構造函數可以有參數，所以new后面類（class）類型也可以有參數。這些參數即構造函數的參數。但對創建數組，則無參數，并只調用缺省的構造函數。見下例類說明：第17頁，共125頁，2022年，5月20日，15點8分，星期一堆對象與構造函數下面注意如何使用：void main() int n; CGoods *pc,*pc1,*pc2; p

16、c=new CGoods(“夏利2000”，10，118000); /調用三參數構造函數 pc1=new CGoods(); /調用缺省構造函數 cout輸入商品類數組元素數n; pc2=new CGoodsn; /動態建立數組，不能初始化，調用n次缺省構造函數 delete pc; delete pc1; delete pc2;第18頁，共125頁，2022年，5月20日，15點8分，星期一堆對象與構造函數這里再次強調：由堆區創建對象數組，只能調用缺省的構造函數，不能調用其他任何構造函數。如果沒有缺省的構造函數，則不能創建對象數組。第19頁，共125頁，2022年，5月20日，15點8分，星

17、期一淺拷貝與深拷貝 缺省拷貝構造函數，可用一個類對象初始化另一個類對象，稱為缺省的按成員拷貝，而不是對整個類對象的按位拷貝。這稱為淺拷貝。 P堆對象堆對象PP 圖7.1 淺拷貝 拷貝前拷貝后 第20頁，共125頁，2022年，5月20日，15點8分，星期一淺拷貝與深拷貝如果類中有一個數據成員為指針，該類的一個對象obj1中的這個指針p，指向了動態分配的一個堆對象，（參見圖7.1拷貝前），如果用obj1按成員拷貝了一個對象obj2，這時obj2.p也指向同一個堆對象。當析構時，如用缺省的析構函數，則動態分配的堆對象不能回收。如果在析構函數中有“delete p;”語句，則如果先析構函數obj1時

18、，堆對象已經釋放，以后再析構obj2時出現了二次釋放的問題。這時就要重新定義拷貝的構造函數，給每個對象獨立分配一個堆對象，稱深拷貝。這時先拷貝對象主體，再為obj2分配一個堆對象，最后用obj1的堆對象拷貝obj2的堆對象。 堆對象PP堆對象 圖7.2 深拷貝 第21頁，共125頁，2022年，5月20日，15點8分，星期一淺拷貝與深拷貝【例7.2】定義拷貝（copy structor）和拷貝賦值操作符（copy Assignment Operator）實現深拷貝。 學生類定義：class student char *pName; /指針成員public: student(); /缺省構造函數

19、 student(char *pname); /帶參數構造函數 student(student &s); /拷貝構造函數 student(); /析構函數 student & operator=(student &s); ; /拷貝賦值操作符檢驗主函數和運行結果第22頁，共125頁，2022年，5月20日，15點8分，星期一淺拷貝與深拷貝 堆內存是最常用的需要拷貝構造函數自定義的資源，但不是唯一的，如打開文件等。如果類需要析構函數來析構資源，則類也需要一個自定義的拷貝構造函數。對象的拷貝就是深拷貝了。第23頁，共125頁，2022年，5月20日，15點8分，星期一7.2 鏈表與鏈表的基本操作

20、線性表是最簡單，最常用的一種數據結構。線性表的邏輯結構是n個數據元素的有限序列（a1,a2,an）。而線性表的物理結構，除順序表，還有鏈表 7.2.1 單鏈表基本算法 7.2.3 雙向鏈表 7.2.2單鏈表類型模板 第24頁，共125頁，2022年，5月20日，15點8分，星期一7.2.1 單鏈表基本算法單鏈表（Singly Linked list）也稱線性鏈表。每個數據元素占用一個節點（Node）。一個節點包含兩個域，一個域存放數據元素info，其數據類型由應用問題決定，另一個存放指向該鏈表中下一個節點的指針link。節點定義如下：typedef int Datatype; /數據為整型st

21、ruct node Datatype info; node *link;在C/C+中允許結構（或對象）成員是結構自身的指針類型，通過指針引用自身這種類型的結構。但結構成員決不能是結構自身類型，即結構不能自己定義自己，這會導致一個無窮遞歸的定義。 第25頁，共125頁，2022年，5月20日，15點8分，星期一 7.2.1 單鏈表基本算法單鏈表的第一個結點的地址可通過鏈表的表頭指針head找到， head在使用中必須妥善保存，千萬不可丟失，否則鏈表整個丟失，內存也發生泄漏。infon-1 info2 info1 info0 haed圖7.3 單向鏈表結構 單鏈表的插入與刪除：只要改變鏈中結點指針

22、的值，無需移動表中的元素，就能實現插入和刪除操作。插入算法有三種情況，我們希望在單鏈表中包含數據infoi的結點之前插入一個新元素，則infoi可在第一個結點，或在中間結點，如未找到，則把新結點插在鏈尾結點之后。 第26頁，共125頁，2022年，5月20日，15點8分，星期一7.2.1 單鏈表基本算法newnodeinfoxinfo0info1headhead插在鏈首 首先新結點的link指針指向info0所在結點，然后，head指向新結點。即：newnodelink=head；/注意：鏈表操作次序非常重要head=newnode；第27頁，共125頁，2022年，5月20日，15點8分，星

23、期一7.2.1 單鏈表基本算法infoxinfoi-1infoipnewnode插在中間 首先用工作指針p找到指定結點，而讓指針q指向緊跟其后的結點，令infoi-1所在結點的link指針指向新結點，而后讓新結點的link指向infoi所在結點。即：newnodelink=p；/或newnodelink=qlink；可用于插入某結點之后qlink=newnode；第28頁，共125頁，2022年，5月20日，15點8分，星期一7.2.1 單鏈表基本算法infox newnodepinfon-1 插在隊尾只要工作指針p找到隊尾，即可鏈在其后：plink=newnode；newnode.link=

24、NULL;第29頁，共125頁，2022年，5月20日，15點8分，星期一7.2.1 單鏈表基本算法headtailpinfo1tailpinfo0tail1. 向后生成鏈表算法：node *createdown() Datatype data;Node*head,*tail,*p; head=new node; /建立鏈表頭結點 tail=head;while(cindata) /回車結束 p=new(node);/每輸入一個數申請一個結點p-info=data; /添入數據tail-link= p1; /新結點接到鏈尾 tail=p1; /尾指針到鏈尾 tail-link=NULL;/鏈尾

25、加空指針，表示鏈結束 return head; /返回頭指針 第30頁，共125頁，2022年，5月20日，15點8分，星期一7.2.1 單鏈表基本算法headinfo0 PPinfo12. 向前生成鏈表算法node *createup() node *head,*p; Datatype data; head=new node; /建立頭結點 head-link=NULL; while(cindata) /建立的總是第一個結點 p=new node; p-info=data; p-link= head-link ;/新結點放在原鏈表前方 head-link=p; /頭結點放新結點之前 retu

26、rn head;第31頁，共125頁，2022年，5月20日，15點8分，星期一7.2.1 單鏈表基本算法3.鏈表查找算法（Traversal），按數據（關鍵字）查找：node *traversal(node *head,Datatype data) node *p=head-link; while(p!=NULL|p-info!=data) p=p-link; return p; /p為NULL則未找到返回值為指針p，指向鏈表中找到的結點。4. 在單鏈表的p節點后插入一個信息域為x的新節點（注意只有一種情況了）。void insert(node p,Datatype x) node *q=n

27、ew node; q-info=x; q-link=p-link; p-link=q;第32頁，共125頁，2022年，5月20日，15點8分，星期一7.2.1 單鏈表基本算法5. 刪除單鏈表節點*p后面節點void del (node *p) node *q; q=p-link; p-link=q-link; delete q; /如果要把該節點移入另一個鏈中，則可將q返回。第33頁，共125頁，2022年，5月20日，15點8分，星期一7.2.2 單鏈表類型模板【例7.4_h】單鏈表類模板。 首先看結點類templateclass List;templateclass Node T inf

28、o; /數據域 Node *link; /指針域public: Node(); /生成頭結點的構造函數 Node(const T & data); /生成一般結點的構造函數 void InsertAfter(Node* p); /在當前結點后插入一個結點 Node* RemoveAfter(); /刪除當前結點的后繼結點 friend class List; /以List為友元類，List可直接訪問Node的私有函數;第34頁，共125頁，2022年，5月20日，15點8分，星期一再定義鏈表類: templateclass List Node *head,*tail; /鏈表頭指針和尾指針pu

29、blic: List(); /構造函數，生成頭結點(空鏈表) List(); /析構函數 void MakeEmpty(); /清空鏈表，只余表頭結點 Node* Find(T data); /搜索數據域與data相同的結點，返回該結點的地址 int Length(); /計算單鏈表長度 void PrintList(); /打印鏈表的數據域 void InsertFront(Node* p); /可用來向前生成鏈表 void InsertRear(Node* p); /可用來向后生成鏈表 void InsertOrder(Node *p); /按升序生成鏈表 Node*CreatNode(T

30、 data); /創建結點(孤立結點) Node*DeleteNode(Node* p); ; /刪除指定結點7.2.2 單鏈表類型模板第35頁，共125頁，2022年，5月20日，15點8分，星期一7.2.2 單鏈表類型模板【例7.4】由鍵盤輸入16個整數，以這些整數作為結點數據，生成兩個鏈表，一個向前生成，一個向后生成，輸出兩個表。然后給出一個整數在一個鏈表中查找，找到后刪除它，再輸出該表。清空該表，再按升序生成鏈表并輸出。在本例中程序只需調用類模板中的成員函數就可以完成所有鏈表操作。第36頁，共125頁，2022年，5月20日，15點8分，星期一7.2.3 雙向鏈表 考慮順序表中總是可以

31、很方便地找到表元素的前驅和后繼，但單鏈表只能找后繼。如要找前驅，必須從表頭開始搜索。為了克服這一缺點，可采用雙向鏈表（Double Linked List)。雙向鏈表的結點有三個域：左鏈接指針（llink)，數據域（info)，右鏈接指針域(rlink)。雙向鏈表經常采用帶頭結點的循環鏈表方式。 info0 infon-1. info1head(a) 非空表head(b)空表第37頁，共125頁，2022年，5月20日，15點8分，星期一7.2.3 雙向鏈表假設指針p指向雙向循環鏈表的某一個結點，那么，p-llink指示P所指結點的前驅結點，p-rlink指示后繼結點。p-llink-rlin

32、k指示本結點的前驅結點的后繼結點，即本結點，間接訪問符-可以連續使用。pllink rlinkrlinkllink rlink前驅結點 llink 本結點 后繼結點 間接訪問符的使用【例7.5】雙向鏈表類模板和結點類模板。第38頁，共125頁，2022年，5月20日，15點8分，星期一7.3 棧與隊列的基本操作及其應用 棧和隊都是特殊的線性表，限制存取位置的線性結構，可以由順序表實現，也可以由鏈表實現。 7.3.1 棧與應用 7.3.2隊列 第39頁，共125頁，2022年，5月20日，15點8分，星期一7.3.1 棧與應用棧定義為只允許在表的一端進行插入和刪除的線性表。允許進行插入和刪除的一

33、端叫做棧頂(top)，而另一端叫棧底(bottom)。棧中沒有任何元素時，稱為空棧。進棧時最先進棧的在最下面，最后的在最上面，后來居上。而出棧時順序相反，最后進棧的最先出棧，而最先進棧的a0最后出棧。所以棧又稱作后進先出（LIFO：Last In First Out）的線性表。 ?？梢杂庙樞虮韺崿F，稱順序棧；也可以用鏈表實現，稱鏈棧。第40頁，共125頁，2022年，5月20日，15點8分，星期一7.3.1 棧與應用參見下圖，設給定棧s=(a0，a1，an-1)，稱a0為棧底，an-1為棧頂。進棧時最先進棧的a0在最下面，an-1在最上面。而出棧時順序相反，最后進棧的an-1最先出棧，而最先進

34、棧的a0最后出棧。a0an-2a1an-1bottom進棧toptoptoptoptop出棧圖示為順序棧。其中棧底bottom是指向棧數據區的下一單元，這樣判斷是否為空棧會更方便，只需top與bottom相同就是空棧。通常只有棧頂與操作有關。第41頁，共125頁，2022年，5月20日，15點8分，星期一7.3.1 棧與應用【例7.6】順序棧的類模板定義：templateclass Stack int top; /棧頂指針（下標） T *elements; /動態建立的元素 int maxSize; /棧最大容納的元素個數public: Stack(int=20); /構造函數，棧如不指定大小

35、，設為20元素 Stack()delete elements; void Push(const T &data); /壓棧 T Pop(); /彈出，top- T GetElem(int i); /取數據，top不變 void MakeEmpty()top= -1; /清空棧 bool IsEmpty() constreturn top= -1; /判?？?bool IsFull() constreturn top=maxSize-1; /判棧滿 void PrintStack(); ; /輸出棧內所有數據第42頁，共125頁，2022年，5月20日，15點8分，星期一7.3.1 棧與應用vo

36、id 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();if(istack.IsEmpty() cout?？誩ndl;for(i=0;i10;i+) coutbit; /注意先進后出coutendl;istack.Pop(); /下溢出第43頁，共125頁，2022年，5月20日，15點8分，星期一7.3.

37、1 棧與應用【例7.7_h】鏈棧的結點類模板: templateclass Node /鏈棧結點類模板T info;Node *link;public:Node(T data=0,Node *next=NULL)info=data;link=next;friend class Stack;top 鏈棧第44頁，共125頁，2022年，5月20日，15點8分，星期一7.3.1 棧與應用鏈棧類模板，無頭結點鏈表templateclass Stack /鏈棧類模板Node *top; /棧頂指針public:Stack()top=NULL;Stack();void Push(const T &dat

38、a); /壓棧T Pop(); /彈出T GetTop(); /取棧頂元素void MakeEmpty(); /清空棧bool IsEmpty()return top=NULL;第45頁，共125頁，2022年，5月20日，15點8分，星期一7.3.1 棧與應用順序棧和鏈棧邏輯功能是一樣，盡管這里兩個棧模板的成員函數功能選擇稍有出入，因為順序?？梢噪S機訪問其中的元素，而鏈棧只能順序訪問，但邏輯上完全可以做到一樣（物理結構不同）。順序棧必須先開一定大小內存空間，執行起來簡單，速度快，可能溢出。鏈棧內存空間隨用隨開，不會溢出，但執行復雜（不斷地動態分配），速度慢。 棧可用于表達式的計算?，F考慮最簡

39、單的+、-、*、/四個運算符和結束符組成的算術表達式，只有兩個優先級，先*/，后+-。第46頁，共125頁，2022年，5月20日，15點8分，星期一NcbaOat1deNat1deOONt1at2t1at2t3aNt3aNOOb*c-t1d/e-t2t1-t2-t3a+t3-t4N：數棧 O：運算符 (a) (b) (c) (d) (e) 表達式運算 設有：a+b*c-d/e=；為實現運算符的優先級，采用兩個棧：一個數棧，一個運算符棧。數棧暫存操作數，運算符棧暫存運算符。從左向右掃描算術表達式，遇到操作數，壓入數棧；遇到運算符，則與運算符棧棧頂的運算符比較優先級，若新的運算符優先級高，或運算

40、符?？?，則壓棧。否則將棧頂運算符出棧，與數字棧出棧的兩個數據進行運算，結果壓入數棧，再將新運算符壓棧。繼續掃描，直到遇到號，掃描結束。棧中數據繼續按前面規則出棧。 第47頁，共125頁，2022年，5月20日，15點8分，星期一7.3.1 棧與應用【例7.7】模擬簡單計算器，該計算器只認+ - * / 四個運算符，輸入為整數。表達式結束符使用號，清空棧用c字符。使用z字符表示結束。簡易計算器類定義：class Calculator Stack Nstack; /使用鏈棧 Stack Ostack;public: Calculator(void); void Cal(void); /計算器運算程

41、序 void GetTwoNum(int &Num1,int &Num2); /取數 void Compute(char Opr); /讀算式 void Clear(void); ; /清除在VC+平臺上演示例7.7第48頁，共125頁，2022年，5月20日，15點8分，星期一7.3.2 隊列 隊列(Queue)也是一種限定存取位置的線性表。它只允許在表的一端插入，而在另一端刪除。允許插入的一端稱為隊尾(rear)，允許刪除的一端叫做隊頭(front)。每次在隊尾加入新元素，加入稱為進隊，刪除稱為出隊。隊列的這種特性正好與棧相反，叫做先進先出FIFO(First In First Out)。

42、 a0a1a2an-1front元素移動方向rear圖7.15隊列 圖7.15所示隊列隨隊尾加入元素，隊尾(rear)不斷向后移；而隨隊頭元素的出隊，則隊頭(front)也不斷后移，即位置在變（如要位置不變，移動元素工作量也太大）。 第49頁，共125頁，2022年，5月20日，15點8分，星期一7.3.2 隊列rearfrontADCABDECFHGBCD進隊A進隊空隊DCAB出隊EFGH進隊rearfrontrearrearrearfrontfrontfront圖7.16 順序隊列的插入和刪除 由圖可見：空隊時指針（下標）front和rear在一起都指向隊前方，當有元素進隊，則rear后移

43、；有元素出隊，則front后移，最后分配給隊的前端不再被利用。 第50頁，共125頁，2022年，5月20日，15點8分，星期一7.3.2 隊列隊列總是做成一個邏輯上的循環隊列 注意，空隊時rear=front，滿隊時必須空一個位置 第51頁，共125頁，2022年，5月20日，15點8分，星期一7.3.2 隊列 循環隊列浪費一個位置好像太可惜，特別在該位置中存放一個很大的對象時。實際上只能有所不為才能有所為，而且對象很大時，總是由索引（指針）來排隊。若想利用這個空間，必然加一個標志來表示隊空/隊滿，進隊出隊都要判斷，使用上更不方便。 用鏈表實現隊列無此問題 【例7.8】順序存儲方式的循環隊列

44、類模板?！纠?.9】鏈隊類模板。鏈首出隊，鏈尾入隊。無鏈首結點方式。第52頁，共125頁，2022年，5月20日，15點8分，星期一7.4二叉樹 樹形結構是一類重要的非線性數據，樹和二叉樹是常用的樹形結構。 7.4.2 二叉樹的遍歷 二叉樹的概念 7.4.3 排序二叉樹 第53頁，共125頁，2022年，5月20日，15點8分，星期一二叉樹的概念 樹（Tree）是由n（n0）個結點組成的有限集合。如n=0，稱為空樹。非空樹有一個特定的結點，它只有直接后繼，沒有直接前驅，稱之為根（root）。除根以外的其它結點劃分為m（m0）個互不相交的有限集合T0，T1，Tm-1，每個集合又是一棵樹，稱為根的

45、子樹（subtree）。每棵子樹的根結點有且僅有一個直接前驅，但可以有0個或多個直接后繼。這是一個遞歸方法定義的數據結構。 第54頁，共125頁，2022年，5月20日，15點8分，星期一二叉樹的概念ABCDEFGIHJLKONM0層1層2層3層深度圖7.17 樹的示意圖 結點，包括數據項和多個指針項，指針項數目并不固定，且無次序。結點的度，結點所擁有的子樹數量。葉結點，度為0的結點，如G，I，J，K，L，M，N，O結點。分支結點，度1的結點。孩子結點，若結點x有子樹，則子樹根結點即為x的孩子結點。第55頁，共125頁，2022年，5月20日，15點8分，星期一二叉樹的概念ABCDEFGIHJ

46、LKONM0層1層2層3層深度圖7.17 樹的示意圖 雙親結點，若結點x有孩子，它即為孩子的雙親。兄弟結點，同一雙親的結點互稱為兄弟。結點的層次，從根到該結點所經路徑上的分支條數。樹的深度,樹中結點的層次數。樹的度，樹中結點度的最大值。 第56頁，共125頁，2022年，5月20日，15點8分，星期一二叉樹的概念二叉樹（Binary Tree）是另一種獨立的樹形結構。二叉樹是結點的一個有限集合，該集合或為空，或是由一個根結點及兩棵樹分別稱為左子樹和右子樹的（注意有左右之分）互不相交的二叉樹組成，其中左右子樹分別可以為空子樹或均為空樹。這也是一個遞歸的定義。二叉樹的特點是：每個結點最多兩個孩子，

47、并且子樹有左右之分。二叉樹的基本性質：1二叉樹的第i層上最多有2i-1(i=1)個結點；2深度為h的二叉樹中最多有2h-1個結點；3在任一棵二叉樹中，有n0葉子結點，有n2個度為2的 結點，則有n0=n2+1。第57頁，共125頁，2022年，5月20日，15點8分，星期一二叉樹的概念【例7.9】畫出有三個結點的所有二叉樹。解：結果見圖7.18，共5種。圖7.18 5種不同的三結點二叉樹 第58頁，共125頁，2022年，5月20日，15點8分，星期一二叉樹的概念二叉樹有滿二叉樹和完全二叉樹，分別如圖7.19和圖7.20，完全二叉樹已有的結點排序與滿二叉樹相同。 123456798101114

48、131215圖7.19 滿二叉樹 12345679810圖7.20 完全二叉樹 第59頁，共125頁，2022年，5月20日，15點8分，星期一二叉樹的概念下面給出鏈式儲存方式的二叉樹。每個結點有三個域：數據域、左孩子指針和右孩子指針，見圖7.21。 lchildrchildinfo圖7.21 二叉樹結點 第60頁，共125頁，2022年，5月20日，15點8分，星期一二叉樹的概念二叉樹類結點類模板定義如下：templateclass BinaryTree;templateclass Node Node *lchild,*rchild; T info;public: Node() lchild

49、=NULL; rchild=NULL; Node(T data,Node *left=NULL , Node *right=NULL) info=data; lchild=left; rchild=right; 第61頁，共125頁，2022年，5月20日，15點8分，星期一二叉樹的概念 T Getinfo()return info; /取得結點數據 void setinfo(const T &data)info=data; /修改結點數據 Node *Getleft()return lchild; /取得左子樹 Node *Getright()return rchild; /取得右子樹 vo

50、id setleft(Node *left)lchild=left; /設置左指針 void setrightNode *right)rchild=right; /設置右指針 friend class BinaryTree; /二叉樹類說明為友元類第62頁，共125頁，2022年，5月20日，15點8分，星期一7.4.2 二叉樹的遍歷所謂二叉樹的遍歷（binary tree traversal），就是遵從某種次序，查巡二叉樹的所有結點，每個結點都被訪問一次，而且僅訪問一次。所謂“訪問”指對結點施行某些操作，但不破壞它原來的數據結構。遍歷二叉樹有不同次序，規定先左后右，令L，R，V分別代表遍歷一

51、個結點的左右子樹和訪問該結點的操作，有三種方式：前序遍歷（VLR）中序遍歷（LVR）后序遍歷（LRV） 第63頁，共125頁，2022年，5月20日，15點8分，星期一 7.4.2 二叉樹的遍歷例如：前序遍歷訪問次序為ABDEGCFH。 圖7.22 二叉樹遍歷 中序遍歷結果為D B G E A F H C。后序遍歷結果為D G E B H F C A。 第64頁，共125頁，2022年，5月20日，15點8分，星期一7.4.2 二叉樹的遍歷【例7.10】二叉樹類模板（其中二叉樹生成借用二叉排序樹，見下節）。特別注意插入結點時，第二參數為指針的引用！否則不能建立樹。為什么？請讀者自己思考。本例采

52、用簡單的接口函數，而把較復雜的算法作為私有函數。 templateclass BinaryTree Node *root; /二叉樹的根指針 void InOrder(Node *Current); /中序遍歷 void PreOrder(Node *Current); /前序遍歷 void PostOrder(Node *Current); /后序遍歷 void Insert(const T &data,Node * &b); /插入結點，參數為引用！ void Destory(Node * Current); /刪除樹第65頁，共125頁，2022年，5月20日，15點8分，星期一7.4.

53、2 二叉樹的遍歷public: BinaryTree()root=NULL;/空樹構造函數 BinaryTree()Destory(root);/析構函數 void Creat(T* data,int n); /建立（排序）二叉樹 void InOrder()InOrder(root); /中序遍歷，公有函數為接口 void PreOrder()PreOrder(root);/前序遍歷，公有函數為接口 void PostOrder()PostOrder(root); /后序遍歷，公有函數為接口;檢驗主函數第66頁，共125頁，2022年，5月20日，15點8分，星期一7.4.2 二叉樹的遍歷【

54、例7.13】某二叉樹先序遍歷為ABCEFDGHIJK，中序遍歷為ECFBDGAIHJK繪出該二叉樹。 ABCDEFGHIJK圖7.23 例7.11二叉樹 按同樣方法推出A的右子樹。結果如圖7.23?？梢宰C明已知先序和中序訪問次序可以唯一確定一棵二叉樹。 解：由先序知A為根結點，而E F B D G為左子樹，I H J K為右子樹。由先序中的B C E F D G知B為左子樹根結點，由中序中的E C F B D G知E C F為其左子樹，而DG為右子樹。再由先序C E F知C為左子樹根結點，由中序E C F知E為C左子樹，F為的右子樹。再由先序D G知，D為B的右子樹根結點，由中序D G知G為D

55、的右子樹。第67頁，共125頁，2022年，5月20日，15點8分，星期一7.4.3 排序二叉樹 二叉排序樹（Binary Sorting Tree）又稱二叉搜索樹（Binary Search Tree），是一種特殊結構的二叉數，作為一種排序和查找的手段，對應有序表的對半查找，通常亦被稱為數表。其定義也是遞歸的。二叉排序樹的定義：二叉排序樹或者是空樹或者是具有下述性質的二叉數，其左子樹上所有結點的數據值均小于根結點的數據值；右子樹上所有結點的數據值均大于等于根結點的數據值，左子樹和右子樹又各是一棵二叉排序樹。第68頁，共125頁，2022年，5月20日，15點8分，星期一7.4.3 排序二叉樹

56、二叉排序樹用中序遍歷就可以得到由小到大的有序序列，如圖7.24可得有序序列8，10，11，12，15，16，18，22，24，26，29。 101826812222911241615圖7.24 二叉排序樹例 第69頁，共125頁，2022年，5月20日，15點8分，星期一二叉排序樹的結點插入（可生成排序二叉樹）生成算法：對任意一組數據元素序列a0，a1，a2，an-1。要生成二叉排序樹的過程為：1. 令a0為二叉樹的根結點。2.若a1a0，令a1為a0左子樹的根結點，否則a1為a0右子樹的根結點。3. 如ai小于根結點，則去左子樹，否則去右子樹，按此法查找，直到成為空樹，則安放此位置。這步就是

57、插入算法。 7.4.3 排序二叉樹第70頁，共125頁，2022年，5月20日，15點8分，星期一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;再次在VC+平臺上演示例7.13【例7.13】排序二叉樹查找函數。算法：用中序遍歷即可，但遞歸慢，下面為迭代查找算法。第71

58、頁，共125頁，2022年，5月20日，15點8分，星期一7.5 MFC對象和Windows對象的關系MFC對象是C+對象，而且是特指封裝了Window對象的C+對象，不是任意的C+對象。本節討論MFC對象與Window對象的聯系，以最典型的的窗口類（CWnd）為例，討論CWnd類對象與Windows窗口對象的關系。參見下圖。 .其它成員m_hWndhwndCWnd類對象HWND句柄類型wndwindows對象句柄Windows操作系統窗口對象MFC窗口對象與Windows窗口對象的關系第72頁，共125頁，2022年，5月20日，15點8分，星期一7.5 MFC對象和Windows對象的關系

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

60、tach(hwd);/把Windows窗口實例的句柄鏈到CWnd對象hwnd上.Destrory Window(hwnd);/調用API函數撤消Windows窗口 第73頁，共125頁，2022年，5月20日，15點8分，星期一7.5 MFC對象和Windows對象的關系 MFC封裝了幾乎所有Windows的API函數，所以上面的API函數，可以用CWnd的成員函數代替。成員函數Create()可以代替API函數CreateWindows()并加上另一個成員函數Attach()的全部功能，建立一個Windows操作系統的窗口對象，并把句柄自動保存在MFC窗口對象wnd的m_hwnd成員數據中。