cunit動態(tài)內(nèi)存分配與數(shù)據(jù)結(jié)構(gòu)PPT課件

1、第七章第七章 動態(tài)內(nèi)存分配與數(shù)據(jù)結(jié)構(gòu)動態(tài)內(nèi)存分配與數(shù)據(jù)結(jié)構(gòu)本章首先介紹程序運行時本章首先介紹程序運行時動態(tài)內(nèi)存分配動態(tài)內(nèi)存分配（dynamic dynamic memory allocationmemory allocation）的概念與方法。進一步討論復制構(gòu)造）的概念與方法。進一步討論復制構(gòu)造函數(shù)函數(shù). .然后學習更多有關(guān)數(shù)據(jù)結(jié)構(gòu)的基本知識，包括鏈表，棧，隊，二叉樹等的基本算法和應用。模板是標準C+實現(xiàn)代碼復用的有力工具，特別是有關(guān)數(shù)據(jù)結(jié)構(gòu)的算法，本章繼續(xù)使用。第1頁/共119頁自由存儲區(qū)內(nèi)存分配 二叉樹 （選讀） 7.3 棧與隊列的基本操作及其應用 7.2 鏈表與鏈表的基本操作 第七章第七

2、章 動態(tài)內(nèi)存分配與數(shù)據(jù)結(jié)構(gòu)動態(tài)內(nèi)存分配與數(shù)據(jù)結(jié)構(gòu)第2頁/共119頁自由存儲區(qū)內(nèi)存分配自由存儲區(qū)內(nèi)存分配 自由存儲區(qū)內(nèi)存的分配與釋放 自由存儲區(qū)對象與構(gòu)造函數(shù) 7.1.3 淺復制與深復制 靜態(tài)存儲分配：靜態(tài)存儲分配：通常定義變量通常定義變量( (或?qū)ο蠡驅(qū)ο? )，編譯器在，編譯器在編譯時都可以根據(jù)該變量編譯時都可以根據(jù)該變量( (或?qū)ο蠡驅(qū)ο? )的類型知道所需內(nèi)存空間的大小，的類型知道所需內(nèi)存空間的大小，從而系統(tǒng)在適當?shù)臅r候為它們分配從而系統(tǒng)在適當?shù)臅r候為它們分配確定的存儲空間。確定的存儲空間。動態(tài)存儲分配：動態(tài)存儲分配：有些操作對象只有在程序運行時才能有些操作對象只有在程序運行時才能確定，

3、這樣編譯器在編譯時就無法為確定，這樣編譯器在編譯時就無法為他們預定存儲空間，只能在程序運行他們預定存儲空間，只能在程序運行時，系統(tǒng)根據(jù)運行時的要求進行內(nèi)存時，系統(tǒng)根據(jù)運行時的要求進行內(nèi)存分配，稱為動態(tài)存儲分配。動態(tài)分配分配，稱為動態(tài)存儲分配。動態(tài)分配都在都在自由存儲區(qū)中進行。中進行。第3頁/共119頁自由存儲區(qū)自由存儲區(qū)內(nèi)存的分配與釋放內(nèi)存的分配與釋放當程序運行到需要一個動態(tài)分配的變量或?qū)ο髸r，必須向系統(tǒng)當程序運行到需要一個動態(tài)分配的變量或?qū)ο髸r，必須向系統(tǒng)申請申請取得自由存儲區(qū)取得自由存儲區(qū)中的一塊所需大小的存貯空間，用于存貯該變中的一塊所需大小的存貯空間，用于存貯該變量或?qū)ο蟆．敳辉偈褂迷?/p>

4、變量或?qū)ο髸r，也就是它的生命結(jié)束量或?qū)ο?。當不再使用該變量或?qū)ο髸r，也就是它的生命結(jié)束時，要時，要顯式釋放顯式釋放它所占用的存貯空間，這樣系統(tǒng)就能進行再次分配，它所占用的存貯空間，這樣系統(tǒng)就能進行再次分配，做到重復使用有限的資源。做到重復使用有限的資源。 申請和釋放申請和釋放自由存儲區(qū)中分配的存貯空間，分別使用中分配的存貯空間，分別使用newnew和和deletedelete的兩個運算符來完成，其使用的格式如下：的兩個運算符來完成，其使用的格式如下：指針變量名指針變量名=new =new 類型名類型名( (初始化式初始化式) )；delete delete 指針名指針名; ;newnew運算符

5、運算符返回返回的是一個指向所分配類型變量（對象）的的是一個指向所分配類型變量（對象）的指針指針。對所創(chuàng)建的變量或?qū)ο?，都是通過該指針來間接操作的，而對所創(chuàng)建的變量或?qū)ο?，都是通過該指針來間接操作的，而動動態(tài)創(chuàng)建的對象本身沒有名字。態(tài)創(chuàng)建的對象本身沒有名字。 動態(tài)分配與釋放：動態(tài)分配與釋放：第4頁/共119頁 自由存儲區(qū)自由存儲區(qū)內(nèi)存的分配與釋放內(nèi)存的分配與釋放一般定義變量和對象時要用標識符命名，稱一般定義變量和對象時要用標識符命名，稱命名對象命名對象，而動態(tài)的稱，而動態(tài)的稱無名對象無名對象( (請注意與棧區(qū)中的臨時對象的區(qū)別，兩者完全不同：生命請注意與棧區(qū)中的臨時對象的區(qū)別，兩者完全不同：生命

6、期不同，操作方法不同，臨時變量對程序員是透明的期不同，操作方法不同，臨時變量對程序員是透明的) )。自由存儲區(qū)是不會自動在分配時做初始化的（包括清零），所以必須用初始化是不會自動在分配時做初始化的（包括清零），所以必須用初始化式式(initializer)(initializer)來顯式初始化。來顯式初始化。newnew表達式的操作：表達式的操作：從自由存儲區(qū)分配對象，然后用括號中的值初始化該對象。分配對象時，new表達式調(diào)用庫操作符new()： int *pi=new int(0);pi現(xiàn)在所指向的變量的存儲空間是由庫操作符new()分配的，位于程序的自由存儲區(qū)中，并且該對象未命名。 無名對

7、象：無名對象：第5頁/共119頁 自由存儲區(qū)自由存儲區(qū)內(nèi)存的分配與釋放內(nèi)存的分配與釋放自由存儲區(qū)i演示：演示：用初始化式用初始化式(initializer)(initializer)來顯式初始化來顯式初始化 int int * *pi=new int(0);pi=new int(0);當當pipi生命周期結(jié)束時，生命周期結(jié)束時，必須釋放必須釋放pipi所指向的目標：所指向的目標： delete pi;delete pi;注意這時釋放了注意這時釋放了pipi所指的目標的內(nèi)存空間，也就是撤銷了該所指的目標的內(nèi)存空間，也就是撤銷了該目標，稱動態(tài)內(nèi)存釋放（目標，稱動態(tài)內(nèi)存釋放（dynamic memo

8、ry deallocationdynamic memory deallocation），但），但指針指針pipi本身并沒有撤銷本身并沒有撤銷，該指針所占內(nèi)存空間并未釋放。，該指針所占內(nèi)存空間并未釋放。 第6頁/共119頁自由存儲區(qū)自由存儲區(qū)內(nèi)存的分配與釋放內(nèi)存的分配與釋放數(shù)組動態(tài)分配格式：數(shù)組動態(tài)分配格式：指針變量名指針變量名=new =new 類型名類型名 下標表達式下標表達式;Delete Delete 指向該數(shù)組的指針變量名指向該數(shù)組的指針變量名; ;說明：說明：兩式中的方括號必須配對使用。如果delete語句中少了方括號，因編譯器認為該指針是指向數(shù)組第一個元素的指針，會產(chǎn)生回收不徹底的

9、問題（只回收了第一個元素所占空間），加了方括號后就轉(zhuǎn)化為指向數(shù)組的指針，回收整個數(shù)組。 delete 的方括號中不需要填數(shù)組元素數(shù)，系統(tǒng)自知。即使寫了，編譯器也忽略。 請注意“下標表達式”不是常量表達式，即它的值不必在編譯時確定，可以在運行時確定。第7頁/共119頁自由存儲區(qū)自由存儲區(qū)內(nèi)存的分配與釋放內(nèi)存的分配與釋放動態(tài)分配數(shù)組與動態(tài)分配數(shù)組與標準字符串類標準字符串類： 標準字符串類string就是采用動態(tài)建立數(shù)組的方式解決數(shù)組溢出的問題的，例所做的動態(tài)內(nèi)存分配與釋放，在string類對象中都是自動完成的，在程序中不需要也不允許再顯式地為string進行動態(tài)內(nèi)存的分配與釋放?！纠?.1】動態(tài)數(shù)

10、組的建立與撤銷第8頁/共119頁自由存儲區(qū)自由存儲區(qū)內(nèi)存的分配與釋放內(nèi)存的分配與釋放動態(tài)分配數(shù)組的特點：動態(tài)分配數(shù)組的特點：1. 變量n在編譯時沒有確定的值，而是在運行中輸入，按運行時所需分配空間，這一點是動態(tài)分配的優(yōu)點，可克服數(shù)組“大開小用”的弊端，在表、排序與查找中的算法，若用動態(tài)數(shù)組，通用性更佳。delete pc是將n個字符的空間釋放，而用delete pc則只釋放了一個字符的空間；2. 如果有char *pc1，令pc1=pc，同樣可用delete pc1 來釋放該空間。盡管C+不對數(shù)組作邊界檢查，但在自由 存儲區(qū) 空間分配時，對數(shù)組分配空間大小是紀錄在案的。3. 沒有初始化式（in

11、itializer），不可對數(shù)組初始化。 第9頁/共119頁自由存儲區(qū)自由存儲區(qū)內(nèi)存的分配與釋放內(nèi)存的分配與釋放（選讀）多維數(shù)組動態(tài)分配：多維數(shù)組動態(tài)分配：new 類型名類型名下標表達式下標表達式1 下標表達式下標表達式2;建立一個動態(tài)三維數(shù)組建立一個動態(tài)三維數(shù)組float (*cp)3020 ; /指向一個指向一個30行行20列數(shù)組的指針列數(shù)組的指針cp=new float 15 30 20; /建立由建立由15個個30*20數(shù)組組成的數(shù)組；數(shù)組組成的數(shù)組；注意注意cp等效于三維數(shù)組名，但沒有指出其邊界，即最等效于三維數(shù)組名，但沒有指出其邊界，即最高維的元素數(shù)量，就像指向字符的指針即等效一個

12、字高維的元素數(shù)量，就像指向字符的指針即等效一個字符串符串,不要把指向字符的指針，說成指向字符串的指針不要把指向字符的指針，說成指向字符串的指針。這與數(shù)組的嵌套定義相一致。這與數(shù)組的嵌套定義相一致。第10頁/共119頁自由存儲區(qū)自由存儲區(qū)內(nèi)存的分配與釋放內(nèi)存的分配與釋放（選讀）比較：比較：float(*cp) 30 20; /三級指針三級指針float (*bp) 20; /二級指針二級指針cp=new float 1 30 20;bp=new float 30 20;兩個數(shù)組都是由兩個數(shù)組都是由600個浮點數(shù)組成，前者是只有個浮點數(shù)組成，前者是只有一個元素的三一個元素的三維數(shù)組維數(shù)組，每個元素

13、為，每個元素為30行行20列的二維數(shù)組，而另一個是有列的二維數(shù)組，而另一個是有30個元素的二維數(shù)組個元素的二維數(shù)組，每個元素為，每個元素為20個元素的一維數(shù)組。個元素的一維數(shù)組。刪除這兩個動態(tài)數(shù)組可用下式：刪除這兩個動態(tài)數(shù)組可用下式：delete cp; /刪除（釋放）三維數(shù)組刪除（釋放）三維數(shù)組delete bp; /刪除（釋放）二維數(shù)組刪除（釋放）二維數(shù)組【例7.2】 動態(tài)創(chuàng)建和刪除一個m*n個元素的數(shù)組第11頁/共119頁自由存儲區(qū)自由存儲區(qū)的分配與釋放的分配與釋放指針使用的要點：指針使用的要點：1. 動態(tài)分配失敗動態(tài)分配失敗。返回一個空指針（。返回一個空指針（NULL），表示發(fā)生了異常

14、，），表示發(fā)生了異常，堆資源不足，分配失敗。堆資源不足，分配失敗。2. 指針刪除與自由存儲區(qū)空間釋放。刪除一個指針p（delete p;）實際意思是刪除了p所指的目標（變量或?qū)ο蟮龋?，釋放了它所占的自由存儲區(qū)空間，而不是刪除本身，釋放自由存儲區(qū)空間后，成了空懸指針?？諔抑羔樖浅绦蝈e誤的一個根源）。建議這時將置空（NULL）。3. new()和delete()是可以重載的，它們都是類的靜態(tài)成員函數(shù)。程序員無需顯式聲明它為靜態(tài)的，系統(tǒng)自動定義為靜態(tài)的。本教材不討論new()和delete()的重載。未重載時，調(diào)用全局庫操作符new()。第12頁/共119頁自由存儲區(qū)自由存儲區(qū)內(nèi)存的分配與釋放內(nèi)存的

15、分配與釋放4內(nèi)存泄漏（內(nèi)存泄漏（memory leak）和重復釋放）和重復釋放。new與與delete 是配對使用的，是配對使用的， delete只能釋放只能釋放自由存儲區(qū)空間。如果空間。如果new返回的指針值丟失，則所分配的返回的指針值丟失，則所分配的自由存儲區(qū)空間無法回收，空間無法回收，稱內(nèi)存泄漏，同一空間重復釋放也是危險的，因為稱內(nèi)存泄漏，同一空間重復釋放也是危險的，因為該空間可該空間可能已另分配能已另分配，所以必須妥善保存，所以必須妥善保存new返回的指針，以保證不發(fā)返回的指針，以保證不發(fā)生內(nèi)存泄漏，也必須保證不會重復釋放生內(nèi)存泄漏，也必須保證不會重復釋放自由存儲區(qū)內(nèi)存空間。內(nèi)存空間。

16、5動態(tài)分配的變量或?qū)ο蟮纳?。無名對象的生命期并不依賴于建立它的作用域，比如在函數(shù)中建立的動態(tài)對象在函數(shù)返回后仍可使用。但必須記住釋放該對象所占自由存儲區(qū)空間，并只能釋放一次，在函數(shù)內(nèi)建立，而在函數(shù)外釋放是一件很容易失控的事，往往會出錯。 第13頁/共119頁自由存儲區(qū)自由存儲區(qū)對象與構(gòu)造函數(shù)對象與構(gòu)造函數(shù) 類對象動態(tài)建立與刪除過程：類對象動態(tài)建立與刪除過程：通過通過newnew建立的對象要調(diào)用構(gòu)造函數(shù)，通過建立的對象要調(diào)用構(gòu)造函數(shù)，通過deletedelete刪除對象也刪除對象也要調(diào)用析構(gòu)函數(shù)。要調(diào)用析構(gòu)函數(shù)。CGoods *pc;pc=new CGoods; /分配自由存儲區(qū)空間，并構(gòu)造

17、一個無名的CGoods對象；.delete pc; /先析構(gòu)，然后將內(nèi)存空間返回給自由存儲區(qū)；自由存儲區(qū)對象的生命期并不依賴于建立它的作用域，所以除非程序結(jié)束，自由存儲區(qū)對象（無名對象）的生命期不會到期，并且需要顯式地用delete語句析構(gòu)該類對象，上例執(zhí)行delete語句時，C+自動調(diào)用商品類的析構(gòu)函數(shù)。第14頁/共119頁自由存儲區(qū)自由存儲區(qū)對象與構(gòu)造函數(shù)對象與構(gòu)造函數(shù)由自由存儲區(qū)創(chuàng)建對象數(shù)組，只能調(diào)用默認的由自由存儲區(qū)創(chuàng)建對象數(shù)組，只能調(diào)用默認的構(gòu)造函數(shù)，不能調(diào)用其他任何構(gòu)造函數(shù)。如果沒構(gòu)造函數(shù)，不能調(diào)用其他任何構(gòu)造函數(shù)。如果沒有默認的構(gòu)造函數(shù)，則不能創(chuàng)建對象數(shù)組。有默認的構(gòu)造函數(shù)，則不

18、能創(chuàng)建對象數(shù)組。類對象初始化：類對象初始化：new后面類（class）類型可以有參數(shù)。這些參數(shù)即構(gòu)造函數(shù)的參數(shù)。但對創(chuàng)建數(shù)組，則無參數(shù)，只能調(diào)用默認的構(gòu)造函數(shù)。【例例7.37.3】演示自由存儲區(qū)對象分配和釋放。演示自由存儲區(qū)對象分配和釋放。第15頁/共119頁淺復制與深復制淺復制與深復制 淺復制：淺復制：默認復制構(gòu)造函數(shù)，可用一個類對象初始化另一個類對象，稱為默認的按成員復制，而不是對整個類對象的按位復制。這稱為淺復制。 圖7.1 淺復制 P自 由 存儲 區(qū) 對象自 由 存儲 區(qū) 對象PP 復制前復制后 如果類中有一個數(shù)據(jù)成員為指針，該類的一個對象obj1中的這個指針p，指向了動態(tài)分配的一個自

19、由存儲區(qū)對象，（參見圖復制前），如果用obj1按成員復制了一個對象obj2，這時也指向同一個自由存儲區(qū)對象。obj1obj1obj2第16頁/共119頁淺復制與深復制復制淺復制與深復制復制當淺復制析構(gòu)時，如用默認的析構(gòu)函數(shù)，則動態(tài)分配的自由存儲區(qū)對象不能回收。如果在析構(gòu)函數(shù)中有“delete p;”語句，則如果先析構(gòu)函數(shù)obj1時，自由存儲區(qū)對象已經(jīng)釋放，以后再析構(gòu)obj2時出現(xiàn)了二次釋放的問題。自 由 存儲區(qū)對象PP自由存儲區(qū)對象 圖7.2 深復制 深復制：重新定義復制的構(gòu)造函數(shù)，給每個對象獨立分配一個自由存儲區(qū)對象，稱深復制。這時先復制對象主體，再為obj2分配一個自由存儲區(qū)對象，最后用o

20、bj1的自由存儲區(qū)對象復制obj2的自由存儲區(qū)對象。 obj1obj2第17頁/共119頁淺復制與深復制淺復制與深復制【例7.4】定義復制構(gòu)造函數(shù) （copy structor）和復制賦值操作符（copy Assignment Operator）實現(xiàn)深復制。 學生類定義：class student char *pName; /為了演示深復制，不用string類public: student(); /默認構(gòu)造函數(shù) student(char *pname); /帶參數(shù)構(gòu)造函數(shù) student(student &s); /復制構(gòu)造函數(shù) student(); /析構(gòu)函數(shù) student &am

21、p; operator=(student &s); ; /復制賦值操作符檢驗主函數(shù)和運行結(jié)果第18頁/共119頁淺復制與深復制淺復制與深復制 提示：提示： 自由存儲區(qū)內(nèi)存是最常見的需要自定義復制構(gòu)造函數(shù)的資源，但不是唯一的，還有打開文件等也需要自定義復制構(gòu)造函數(shù)。 如果類對象需要動態(tài)分配資源應該由構(gòu)造函數(shù)完成，而釋放資源由析構(gòu)函數(shù)完成，這時類也需要一個自定義的復制構(gòu)造函數(shù)，實現(xiàn)對象的深復制。由此可見，構(gòu)造函數(shù)并非僅做初始化工作。第19頁/共119頁淺復制與深復制淺復制與深復制思考：思考： 深入地考慮深入地考慮【例例7.47.4】，如果數(shù)據(jù)域還有很多其他數(shù)據(jù)，如果數(shù)據(jù)域還有很多其他數(shù)據(jù)，

22、甚至有好幾個是動態(tài)建立的甚至有好幾個是動態(tài)建立的C C字符串，深復制是不是太復雜了？字符串，深復制是不是太復雜了？如果使用如果使用C+C+標準字符串標準字符串stringstring作為成員對象（聚合）作為成員對象（聚合）是否就是否就不需要考慮深復制了？不需要考慮深復制了？的確是這樣的，準確地說，string類的內(nèi)部包含動態(tài)建立字符數(shù)組的操作，其復制構(gòu)造函數(shù)是深復制。如果在student類中使用string類而不是C字符串，就不要再考慮深復制問題了。也就是說，動態(tài)內(nèi)存分配和深復制應該放在一個適當?shù)膶用嫔希粋€更單純的類定義中，如string類。在使用中，把它作為一個成員對象，就像使用strin

23、g類對象那樣。第20頁/共119頁淺復制與深復制淺復制與深復制探討：探討： 最后進一步討論類的封裝。封裝的更高境界是在該類對象中一切都是完備的、自給自足的，不僅有數(shù)據(jù)和對數(shù)據(jù)的操作，還包括資源的動態(tài)安排和釋放。在需要時可以無條件地安全使用。標準string類模板就是典型的例子。這樣的類對象，作為另一個類的成員對象使用時，就不會出任何問題。這表明聚合實現(xiàn)了完善的封裝。 第21頁/共119頁7.2 鏈表與鏈表的基本操作鏈表與鏈表的基本操作 線性表線性表是最簡單，最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的邏輯是最簡單，最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)是結(jié)構(gòu)是n個數(shù)據(jù)元素的有限序列（個數(shù)據(jù)元素的有限序列（a

24、1,a2,an）。而線性表的）。而線性表的物理結(jié)構(gòu)物理結(jié)構(gòu)包括：順序表，包括：順序表，鏈表鏈表 。7.2.1 單鏈表基本算法 7.2.3 雙向鏈表(選讀)單鏈表類型模板 第22頁/共119頁7.2.1 單鏈表基本算法單鏈表基本算法單鏈表單鏈表（Singly Linked list）： 每個數(shù)據(jù)元素占用一個節(jié)點（Node）。一個節(jié)點包含兩個域，一個域存放數(shù)據(jù)元素info，其數(shù)據(jù)類型由應用問題決定；另一個存放指向該鏈表中下一個節(jié)點的指針link。節(jié)點定義如下：節(jié)點定義如下： typedef int Datatype; /數(shù)據(jù)為整型struct node Datatype info; node *l

25、ink;在C/C+中允許結(jié)構(gòu)（或?qū)ο螅┏蓡T是結(jié)構(gòu)自身的指針類型，通過指針引用自身這種類型的結(jié)構(gòu)。但結(jié)構(gòu)成員決不能是結(jié)構(gòu)自身類型，即結(jié)構(gòu)不能自己定義自己，這會導致一個無窮遞歸的定義。 第23頁/共119頁 7.2.1 單鏈表基本算法單鏈表基本算法單鏈表的第一個結(jié)點的地址可通過鏈表的表頭指針head找到， head在使用中千萬不可丟失，否則鏈表整個丟失，內(nèi)存也發(fā)生泄漏。infon-1 info2 info1 info0 head圖7.3 單鏈表結(jié)構(gòu) 單鏈表的插入與刪除：單鏈表的插入與刪除： 只要改變鏈中結(jié)點指針的值，無需移動表中的元素，就能實現(xiàn)插入和刪除操作。插入算法有三種情況，我們希望在單鏈表中

26、包含數(shù)據(jù)infoi的結(jié)點之前插入一個新元素，則infoi可在第一個結(jié)點，或在中間結(jié)點，如未找到，則把新結(jié)點插在鏈尾結(jié)點之后。 第24頁/共119頁7.2.1 單鏈表基本算法單鏈表基本算法newnodeinfoxinfo0info1headhead插在鏈首：插在鏈首： 首先新結(jié)點的link指針指向info0所在結(jié)點，然后，head指向新結(jié)點。即：newnodelink=head；/注意：鏈表操作次序非常重要head=newnode；第25頁/共119頁7.2.1 單鏈表基本算法單鏈表基本算法infoxinfoi-1infoipnewnode插在中間：插在中間： 首先用工作指針p找到指定結(jié)點，而讓

27、指針q指向緊跟其后的結(jié)點，令infoi-1所在結(jié)點的link指針指向新結(jié)點，而后讓新結(jié)點的link指向infoi所在結(jié)點。即：newnodelink=p；/或newnodelink=qlink；可用于插入某結(jié)點之后qlink=newnode；第26頁/共119頁7.2.1 單鏈表基本算法單鏈表基本算法infoinfox x newnodepinfoinfon-1n-1 插在隊尾：插在隊尾：只要工作指針p找到隊尾，即可鏈在其后：plink=newnode；newnode.link=NULL;第27頁/共119頁7.2.1 單鏈表基本算法單鏈表基本算法帶表頭結(jié)構(gòu)的鏈表：帶表頭結(jié)構(gòu)的鏈表：研究以上算

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

29、點 tail=head;while(cindata) /回車結(jié)束 p=new(node);/每輸入一個數(shù)申請一個結(jié)點p-info=data; /添入數(shù)據(jù)tail-link= p; /新結(jié)點接到鏈尾 tail=p; /尾指針到鏈尾 tail-link=NULL;/鏈尾加空指針，表示鏈結(jié)束 return head; /返回頭指針 第29頁/共119頁7.2.1 單鏈表基本算法單鏈表基本算法headinfo0 PPinfo12. 2. 向前生成鏈表算法：向前生成鏈表算法：node *createup() node *head,*p; Datatype data; head=new node; /建立

30、頭結(jié)點 head-link=NULL; while(cindata) /建立的總是第一個結(jié)點 p=new node; p-info=data; p-link= head-link ;/新結(jié)點放在原鏈表前方 head-link=p; /頭結(jié)點放新結(jié)點之前 return head;第30頁/共119頁7.2.1 單鏈表基本算法單鏈表基本算法3.3.鏈表查找算法鏈表查找算法( (按關(guān)鍵字按關(guān)鍵字) )查找：查找：node *traversal(node *head,Datatype data) node *p=head-link; while(p!=NULL&p-info!=data) p=

31、p-link; return p; /p為NULL則未找到返回值為指針p，指向鏈表中找到的結(jié)點。4. 4. 在單鏈表的在單鏈表的p p節(jié)點后插入節(jié)點后插入：注意只有一種情況。void insert(node *p,Datatype x) node *q=new node; q-info=x; q-link=p-link; p-link=q;第31頁/共119頁7.2.1 單鏈表基本算法單鏈表基本算法5. 5. 刪除單鏈表節(jié)點刪除單鏈表節(jié)點* *p p后面節(jié)點：后面節(jié)點：void del (node *p) node *q; q=p-link; p-link=q-link; delete q;

32、/如果要把該節(jié)點移入另一個鏈中，則可將q返回。第32頁/共119頁7.2.2 單鏈表類型模板單鏈表類型模板【例】單鏈表類模板單鏈表類模板。定義結(jié)點類：定義結(jié)點類：templateclass List;templateclass Node T info; /數(shù)據(jù)域 Node *link; /指針域，注意結(jié)點類格式，尖括號中是參數(shù)名表，類模板實例化為類public: Node(); /生成頭結(jié)點的構(gòu)造函數(shù) Node(const T & data); /生成一般結(jié)點的構(gòu)造函數(shù) void InsertAfter(Node* p); /在當前結(jié)點后插入一個結(jié)點 Node* RemoveAfter

33、(); /刪除當前結(jié)點的后繼結(jié)點 friend class List; /以List為友元類，List可直接訪問Node的私有函數(shù);第33頁/共119頁定義鏈表類定義鏈表類: : templateclass List Node *head,*tail; /鏈表頭指針和尾指針public: List(); /構(gòu)造函數(shù)，生成頭結(jié)點(空鏈表) List(); /析構(gòu)函數(shù) void MakeEmpty(); /清空鏈表，只余表頭結(jié)點 Node* Find(T data); /搜索數(shù)據(jù)域與data相同的結(jié)點，返回該結(jié)點的地址 int Length(); /計算單鏈表長度 void PrintList()

34、; /打印鏈表的數(shù)據(jù)域 void InsertFront(Node* p); /可用來向前生成鏈表 void InsertRear(Node* p); /可用來向后生成鏈表 void InsertOrder(Node *p); /按升序生成鏈表 Node*CreatNode(T data); /創(chuàng)建結(jié)點(孤立結(jié)點) Node*DeleteNode(Node* p); ; /刪除指定結(jié)點7.2.2 單鏈表類型模板單鏈表類型模板第34頁/共119頁7.2.2 單鏈表類型模板單鏈表類型模板【例例7.57.5】由鍵盤輸入由鍵盤輸入1616個整數(shù)，以這些整數(shù)作為結(jié)點數(shù)據(jù)，生成個整數(shù)，以這些整數(shù)作為結(jié)點數(shù)

35、據(jù)，生成兩個鏈表，一個向前生成，一個向后生成，輸出兩個表。然后給兩個鏈表，一個向前生成，一個向后生成，輸出兩個表。然后給出一個整數(shù)在一個鏈表中查找，找到后刪除它，再輸出該表。清出一個整數(shù)在一個鏈表中查找，找到后刪除它，再輸出該表。清空該表，再按升序生成鏈表并輸出?？赵摫恚侔瓷蛏涉湵聿⑤敵?。在本例中程序只需調(diào)用類模板中的成員函數(shù)就可以完成所有在本例中程序只需調(diào)用類模板中的成員函數(shù)就可以完成所有鏈表操作。鏈表操作?！纠?.67.6】以學生類作為鏈表的數(shù)據(jù)類，完成學生檔案的管以學生類作為鏈表的數(shù)據(jù)類，完成學生檔案的管理。理。第35頁/共119頁7.2.2 單鏈表類型模板單鏈表類型模板討論復制

36、構(gòu)造函數(shù)：討論復制構(gòu)造函數(shù)： 在本例中沒有給出Node類的復制構(gòu)造函數(shù)，并非可以使用默認的復制構(gòu)造函數(shù)，而是避開了所有使用它的情況，本例中函數(shù)的參數(shù)和返回值僅使用指向Node的指針，類定義中也沒有用復制方式初始化。定義復制構(gòu)造函數(shù)與類的實際意義和使用方式有關(guān)，并非只是深復制和淺復制的問題。 通常對Node類復制的結(jié)果應是一個孤立結(jié)點：template Node:Node(Node & node)info=node.data;link=NULL;link域值為NULL。該函數(shù)與Node的有參構(gòu)造函數(shù)功能基本相同?？紤]到函數(shù)的參數(shù)和返回值僅使用指向Node的指針，定義復制構(gòu)造函數(shù)已經(jīng)沒有實

37、際意義 單鏈表的復制構(gòu)造函數(shù)和復制運算符是一個復雜的算法，與前文所編的復制構(gòu)造函數(shù)和復制運算符構(gòu)造相去甚遠了。第36頁/共119頁7.2.3 雙向鏈表（選讀）雙向鏈表（選讀） 雙向鏈表引入：雙向鏈表引入：考慮單鏈表只能找后繼。如要找前驅(qū)，必須從表頭開始搜索?？紤]單鏈表只能找后繼。如要找前驅(qū)，必須從表頭開始搜索。為了克服這一缺點，可采用為了克服這一缺點，可采用雙向鏈表雙向鏈表（Double Linked List)Double Linked List)。雙向鏈表的雙向鏈表的結(jié)點有三個域結(jié)點有三個域：左鏈接指針左鏈接指針（llink)llink)，數(shù)據(jù)域數(shù)據(jù)域（info)info)，右鏈接指針域右

38、鏈接指針域(rlink)(rlink)。雙向鏈表經(jīng)常采用。雙向鏈表經(jīng)常采用帶頭結(jié)點帶頭結(jié)點的循環(huán)鏈表方式的循環(huán)鏈表方式。 info0 infon-1. info1head(a) 非空表head(b)空表第37頁/共119頁7.2.3 雙向鏈表（選讀）雙向鏈表（選讀）雙向鏈表的訪問：雙向鏈表的訪問：假設指針假設指針p p指向雙向循環(huán)鏈表的某一個結(jié)點，那么，指向雙向循環(huán)鏈表的某一個結(jié)點，那么，p-llinkp-llink指示指示P P所指結(jié)點的所指結(jié)點的前驅(qū)結(jié)點前驅(qū)結(jié)點，p-rlinkp-rlink指示指示后繼結(jié)點。后繼結(jié)點。p-llink-p-llink-rlinkrlink指示本結(jié)點的前驅(qū)結(jié)點

39、的后繼結(jié)點，即本結(jié)點，指示本結(jié)點的前驅(qū)結(jié)點的后繼結(jié)點，即本結(jié)點，間接訪問符間接訪問符-可以連續(xù)使用可以連續(xù)使用。pllink rlinkrlinkllink rlink前驅(qū)結(jié)點 llink 本結(jié)點 后繼結(jié)點 間接訪問符的使用【例例7.77.7】雙向鏈表類模板和結(jié)點類模板。雙向鏈表類模板和結(jié)點類模板。第38頁/共119頁7.3 棧與隊列的基本操作及其應用棧與隊列的基本操作及其應用 棧和隊都是特殊的線性表，限制存取位置的線性結(jié)構(gòu)，可以由順序表實現(xiàn)，也可以由鏈表實現(xiàn)。 7.3.1 棧 7.3.3隊列 7.3.2 棧的應用（選讀） 第39頁/共119頁7.3.1 棧棧棧的基本概念：棧的基本概念： 棧定

40、義為只允許在表的一端進行插入和刪除的線性表。允許進行插入和刪除的一端叫做棧頂(top)，而另一端叫棧底(bottom)。 棧中沒有任何元素時，稱為空棧。 進棧時最先進棧的在最下面，最后的在最上面，后來居上。而出棧時順序相反，最后進棧的最先出棧，而最先進棧的a0最后出棧。所以棧又稱作后進先出（LIFO：Last In First Out）的線性表。 棧可以用順序表實現(xiàn)，稱順序棧；也可以用鏈表實現(xiàn)，稱鏈棧。第40頁/共119頁7.3.1 棧棧棧的基本操作：棧的基本操作： 參見下圖，設給定棧s=(a0，a1，an-1)，稱a0為棧底，an-1為棧頂。進棧時最先進棧的a0在最下面，an-1在最上面。而

41、出棧時順序相反，最后進棧的an-1最先出棧，而最先進棧的a0最后出棧。a0an-2a1an-1bottom進棧toptoptoptoptop出棧圖示為順序棧。其中棧底bottom是指向棧數(shù)據(jù)區(qū)的下一單元，這樣判斷是否為空棧會更方便，只需top與bottom相同就是空棧。通常只有棧頂與操作有關(guān)。第41頁/共119頁7.3.1 棧棧templateclass Stack int top; /棧頂指針（下標） T *elements; /動態(tài)建立的元素 int maxSize; /棧最大容納的元素個數(shù)public: Stack(int=20); /構(gòu)造函數(shù)，棧如不指定大小，設為20元素 Stack(

42、)delete elements; void Push(const T &data); /壓棧 T Pop(); /彈出，top- T GetElem(int i); /取數(shù)據(jù)，top不變 void MakeEmpty()top= -1; /清空棧 bool IsEmpty() constreturn top= -1; /判棧空 bool IsFull() constreturn top=maxSize-1; /判棧滿 void PrintStack(); ; /輸出棧內(nèi)所有數(shù)據(jù)【例7.8】順序棧的類模板：順序棧的類模板：第42頁/共119頁7.3.1 棧棧void main()int

43、 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頁/共119頁7.3.1 棧棧【例7.9_h】鏈棧的鏈棧的結(jié)點結(jié)點類模板：類模板： tem

44、plateclass Node /鏈棧結(jié)點類模板T info;Node *link;public:Node(T data=0,Node *next=NULL)info=data;link=next;friend class Stack;top 鏈棧鏈棧第44頁/共119頁7.3.1 棧棧鏈棧類模板鏈棧類模板(無頭結(jié)點鏈表無頭結(jié)點鏈表)：templateclass Stack /鏈棧類模板Node *top; /棧頂指針public:Stack()top=NULL;Stack(); /析構(gòu)函數(shù)void Push(const T &data); /壓棧T Pop(); /彈出T GetTo

45、p(); /取棧頂元素void MakeEmpty(); /清空棧bool IsEmpty()return top=NULL;第45頁/共119頁7.3.2 棧的應用（選讀）棧的應用（選讀）順序棧和鏈棧邏輯功能是一樣，盡管這里兩個棧順序棧和鏈棧邏輯功能是一樣，盡管這里兩個棧模板的成員函數(shù)功能選擇稍有出入，因為模板的成員函數(shù)功能選擇稍有出入，因為順序?？梢噪S順序?？梢噪S機訪問其中的元素機訪問其中的元素，而鏈棧只能順序訪問，而鏈棧只能順序訪問，但邏輯上完全但邏輯上完全可以做到一樣（物理結(jié)構(gòu)不同）可以做到一樣（物理結(jié)構(gòu)不同）。順序棧必須先開一定大小。順序棧必須先開一定大小內(nèi)存空間，執(zhí)行起來簡單，速度

46、快，可能溢出。內(nèi)存空間，執(zhí)行起來簡單，速度快，可能溢出。鏈棧內(nèi)存鏈棧內(nèi)存空間隨用隨開，不會溢出，但執(zhí)行復雜（不斷地動態(tài)分空間隨用隨開，不會溢出，但執(zhí)行復雜（不斷地動態(tài)分配），速度慢。配），速度慢。 順序棧和鏈棧比較：順序棧和鏈棧比較：第46頁/共119頁7.3.2 棧的應用（選讀）棧的應用（選讀） 棧可用于表達式的計算?，F(xiàn)考慮最簡單的+、-、*、/四個運算符和結(jié)束符組成的算術(shù)表達式，只有兩個優(yōu)先級，先*/，后+-。 為實現(xiàn)運算符的優(yōu)先級，采用兩個棧：一個數(shù)棧，一個運算符棧。數(shù)棧暫存操作數(shù)，運算符棧暫存運算符。棧的使用棧的使用(表達式運算表達式運算) ： 第47頁/共119頁NcbaOat1de

47、Nat1deOONt1at2t1at2t3aNt3aNOOb*c-t1d/e-t2t1-t2-t3a+t3-t4N：數(shù)棧：數(shù)棧 O：運算符：運算符 (a) (b) (c) (d) (e)設有：設有：a+b*c-d/e=；參見上圖。；參見上圖。從左向右掃描算術(shù)表達式從左向右掃描算術(shù)表達式，遇到，遇到操作數(shù)操作數(shù)，壓入數(shù)棧壓入數(shù)棧；遇到；遇到運算運算符符，則，則與運算符棧棧頂?shù)倪\算符比較優(yōu)先級與運算符棧棧頂?shù)倪\算符比較優(yōu)先級，若新的運算符優(yōu)先級高，或運算符?？?，則壓棧。，若新的運算符優(yōu)先級高，或運算符?？眨瑒t壓棧。否則將棧頂運算符出棧，與數(shù)字棧出棧的兩個數(shù)據(jù)進行運算，結(jié)果壓入數(shù)棧，再將新運算符壓否

48、則將棧頂運算符出棧，與數(shù)字棧出棧的兩個數(shù)據(jù)進行運算，結(jié)果壓入數(shù)棧，再將新運算符壓棧。繼續(xù)掃描，直到遇到號，掃描結(jié)束。棧中數(shù)據(jù)繼續(xù)按前面規(guī)則出棧。棧。繼續(xù)掃描，直到遇到號，掃描結(jié)束。棧中數(shù)據(jù)繼續(xù)按前面規(guī)則出棧。 第48頁/共119頁7.3.2 棧的應用（選讀）棧的應用（選讀）【例】模擬簡單計算器，該計算器只認+ - * / 四個運算符，輸入為整數(shù)。表達式結(jié)束符使用號，清空棧用c字符。使用z字符表示結(jié)束。簡易計算器類定義：簡易計算器類定義：class Calculator Stack Nstack; /使用鏈棧 Stack Ostack;public: Calculator(void); void

49、 Cal(void); /計算器運算程序 void GetTwoNum(int &Num1,int &Num2); /取數(shù) void Compute(char Opr); /讀算式 void Clear(void); ; /清除第49頁/共119頁7.3.3 隊列隊列 隊列的基本概念：隊列的基本概念：隊列隊列(Queue)(Queue)也是一種限定存取位置的線性表。它也是一種限定存取位置的線性表。它只允許在表只允許在表的一端插入，而在另一端刪除的一端插入，而在另一端刪除。允許插入的一端稱為。允許插入的一端稱為隊尾隊尾(rear)(rear)，允許刪除的一端叫做允許刪除的一端叫做

50、隊頭隊頭(front)(front)。每次在隊尾加入新元素，加入稱為。每次在隊尾加入新元素，加入稱為進隊進隊，刪除稱為，刪除稱為出隊出隊。隊列的這種特性正好與棧相反，叫做。隊列的這種特性正好與棧相反，叫做先進先先進先出出FIFO(First In First Out)FIFO(First In First Out)。 a0a1a2an-1front元素移動方向rear圖隊列 圖所示隊列隨隊尾加入元素，隊尾(rear)不斷向后移；而隨隊頭元素的出隊，則隊頭(front)也不斷后移，即位置在變（如要位置不變，移動元素工作量也太大）。 第50頁/共119頁7.3.2 隊列隊列rearfrontADC

51、ABDECFHGBCD進隊A進隊空隊DCAB出隊EFGH進隊rearfrontrearrearrearfrontfrontfront圖7.16 順序隊列的插入和刪除 由圖可見：空隊時指由圖可見：空隊時指針（下標）針（下標）front和和rear在一起都指向隊前在一起都指向隊前方，當有元素進隊，則方，當有元素進隊，則rear后移；有元素出后移；有元素出隊，則隊，則front后移，最后移，最后分配給隊的前端不后分配給隊的前端不再被利用。再被利用。 順序表隊列的缺點：第51頁/共119頁7.3.2 隊列隊列順序表隊列的改進：順序表隊列的改進：邏輯上的循環(huán)隊列邏輯上的循環(huán)隊列 注意，空隊時注意，空隊時

52、rear=frontrear=front，滿隊時必須空一個位置，滿隊時必須空一個位置 第52頁/共119頁7.3.2 隊列隊列 循環(huán)隊列循環(huán)隊列浪費一個位置好像太可惜，特別在該浪費一個位置好像太可惜，特別在該位置中存放一個很大的對象時。實際上位置中存放一個很大的對象時。實際上對象很大時，對象很大時，總是由索引（指針）來排隊總是由索引（指針）來排隊。若想利用這個空間，。若想利用這個空間，必然加一個標志來表示隊空必然加一個標志來表示隊空/ /隊滿，進隊出隊都要判隊滿，進隊出隊都要判斷，使用上更不方便。斷，使用上更不方便。 用鏈表實現(xiàn)隊列無此問題用鏈表實現(xiàn)隊列無此問題 【例7.10】順序存儲方式的循

53、環(huán)隊列類模板?！纠?.11】鏈隊類模板。鏈首出隊，鏈尾入隊。無鏈表頭結(jié)點方式。第53頁/共119頁二叉樹（選讀）二叉樹（選讀） 樹形結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)，樹和二叉樹形結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)，樹和二叉樹是常用的樹形結(jié)構(gòu)。樹是常用的樹形結(jié)構(gòu)。 7.4.2 二叉樹的遍歷 二叉樹的概念 7.4.3 排序二叉樹 第54頁/共119頁二叉樹的概念二叉樹的概念 （選讀）（選讀） 樹（Tree）是由n（n0）個結(jié)點組成的有限集合。如n=0，稱為空樹。非空樹有一個特定的結(jié)點，它只有直接后繼，沒有直接前驅(qū)，稱之為根（root）。除根以外的其它結(jié)點劃分為m（m0）個互不相交的有限集合T0，T1，Tm-1，

54、每個集合又是一棵樹，稱為根的子樹（subtree）。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個直接后繼。這是一個遞歸方法定義的數(shù)據(jù)結(jié)構(gòu)。 樹的概念：第55頁/共119頁二叉樹的概念（選讀）二叉樹的概念（選讀） ABCDEFGIHJLKONM0層1層2層3層深度圖7.18 樹的示意圖 結(jié)點，包括數(shù)據(jù)項和多個指針項，指針項數(shù)目并不固定，且無次序。結(jié)點的度，結(jié)點所擁有的子樹數(shù)量。葉結(jié)點，度為0的結(jié)點，如G，I，J，K，L，M，N，O結(jié)點。分支結(jié)點，度1的結(jié)點。孩子結(jié)點，若結(jié)點x有子樹，則子樹根結(jié)點即為x的孩子結(jié)點。樹的術(shù)語：第56頁/共119頁二叉樹的概念（選讀）二叉樹的概念（選讀）

55、ABCDEFGIHJLKONM0層1層2層3層深度圖7.18 樹的示意圖 雙親結(jié)點，若結(jié)點x有孩子，它即為孩子的雙親。兄弟結(jié)點，同一雙親的結(jié)點互稱為兄弟。結(jié)點的層次，從根到該結(jié)點所經(jīng)路徑上的分支條數(shù)。樹的深度,樹中結(jié)點的層次數(shù)。樹的度，樹中結(jié)點度的最大值。 樹的術(shù)語：第57頁/共119頁二叉樹的概念（選讀）二叉樹的概念（選讀） 二叉樹（Binary Tree）是另一種獨立的樹形結(jié)構(gòu)。二叉樹是結(jié)點的一個有限集合，該集合或為空，或是由一個根結(jié)點及兩棵樹分別稱為左子樹和右子樹的（注意有左右之分）互不相交的二叉樹組成，其中左右子樹分別可以為空子樹或均為空樹。這也是一個遞歸的定義。二叉樹的特點是：每個結(jié)

56、點最多兩個孩子，并且子樹有左右之分。二叉樹的基本性質(zhì)：二叉樹的基本性質(zhì)：1二叉樹的第i層上最多有2i-1(i=1)個結(jié)點；2深度為h的二叉樹中最多有2h-1個結(jié)點；3在任一棵二叉樹中，有n0個葉子結(jié)點，有n2個度為2的 結(jié)點，則有n0=n2+1。樹的概念：第58頁/共119頁二叉樹的概念（選讀）二叉樹的概念（選讀） 【例】畫出有三個結(jié)點的所有二叉樹。解：結(jié)果見圖，共5種。圖7.19 5種不同的三結(jié)點二叉樹 第59頁/共119頁二叉樹的概念（選讀）二叉樹的概念（選讀） 滿二叉樹和完全二叉樹：滿二叉樹和完全二叉樹：分別如圖和圖，完全二叉樹已有的結(jié)點排序與滿二叉樹相同。 12345679810111

57、4131215圖7.20 滿二叉樹 12345679810圖7.21 完全二叉樹 第60頁/共119頁二叉樹的概念（選讀）二叉樹的概念（選讀） 下面給出鏈式儲存方式的二叉樹。每個結(jié)點有三個域：數(shù)據(jù)域、左孩子指針和右孩子指針，見圖。 lchildrchildinfo圖7.22 二叉樹結(jié)點 第61頁/共119頁二叉樹的概念（選讀）二叉樹的概念（選讀） 二叉樹類結(jié)點類模板定義：二叉樹類結(jié)點類模板定義：templateclass BinaryTree;templateclass Node Node *lchild,*rchild; T info;public: Node() lchild=NULL;

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

59、Node *left)lchild=left; /設置左指針 void setrightNode *right)rchild=right; /設置右指針 friend class BinaryTree; /二叉樹類說明為友元類第63頁/共119頁7.4.2 二叉樹的遍歷（選讀）二叉樹的遍歷（選讀） 二叉樹的遍歷二叉樹的遍歷( (binary tree traversal) )： 遵從某種次序，查巡二叉樹的所有結(jié)點，每個結(jié)點都遵從某種次序，查巡二叉樹的所有結(jié)點，每個結(jié)點都被訪問一次，而且僅訪問一次。所謂被訪問一次，而且僅訪問一次。所謂“訪問訪問”指對結(jié)點施行指對結(jié)點施行某些操作，但不破壞它原來的

60、數(shù)據(jù)結(jié)構(gòu)。某些操作，但不破壞它原來的數(shù)據(jù)結(jié)構(gòu)。遍歷二叉樹有不同次序，規(guī)定先左后右，令遍歷二叉樹有不同次序，規(guī)定先左后右，令L L，R R，V V分別分別代表遍歷一個結(jié)點的左右子樹和訪問該結(jié)點的操作，有三種代表遍歷一個結(jié)點的左右子樹和訪問該結(jié)點的操作，有三種方式：方式：前序遍歷（前序遍歷（VLRVLR）中序遍歷（中序遍歷（LVRLVR）后序遍歷（后序遍歷（LRVLRV） 第64頁/共119頁 7.4.2 二叉樹的遍歷（選讀）二叉樹的遍歷（選讀） 遍歷實遍歷實例：例：前序遍歷訪問次序為ABDEGCFH。 圖7.23 二叉樹遍歷 中序遍歷結(jié)果為D B G E A F H C。后序遍歷結(jié)果為D G E B H F C A。 第65頁/共119頁7.4.2 二叉樹的遍歷（選讀）二叉樹的遍歷（選讀） 【例