unit07動態(tài)分配內(nèi)存空間ppt課件

1、第七章第七章 動態(tài)內(nèi)存分配與數(shù)據(jù)構(gòu)造動態(tài)內(nèi)存分配與數(shù)據(jù)構(gòu)造本章首先引見程序運轉(zhuǎn)時動態(tài)內(nèi)存分配本章首先引見程序運轉(zhuǎn)時動態(tài)內(nèi)存分配dynamic dynamic memory allocationmemory allocation的概念與方法。進一步討論復(fù)制的概念與方法。進一步討論復(fù)制構(gòu)造函數(shù)構(gòu)造函數(shù). .然后學(xué)習(xí)更多有關(guān)數(shù)據(jù)構(gòu)造的根本知識，包括鏈表，然后學(xué)習(xí)更多有關(guān)數(shù)據(jù)構(gòu)造的根本知識，包括鏈表，棧，隊，二叉樹等的根本算法和運用。模板是規(guī)范棧，隊，二叉樹等的根本算法和運用。模板是規(guī)范C+實現(xiàn)代碼復(fù)用的有力工具，特別是有關(guān)數(shù)據(jù)構(gòu)造實現(xiàn)代碼復(fù)用的有力工具，特別是有關(guān)數(shù)據(jù)構(gòu)造的算法，本章繼續(xù)運用。的算法

2、，本章繼續(xù)運用。7.1自在存儲區(qū)內(nèi)存分配自在存儲區(qū)內(nèi)存分配 7.4二叉樹二叉樹 選讀選讀 7.3 棧與隊列的根本操作及其運用棧與隊列的根本操作及其運用 7.2 鏈表與鏈表的根本操作鏈表與鏈表的根本操作 第七章第七章 動態(tài)內(nèi)存分配與數(shù)據(jù)構(gòu)造動態(tài)內(nèi)存分配與數(shù)據(jù)構(gòu)造7.17.1自在存儲區(qū)內(nèi)存分配自在存儲區(qū)內(nèi)存分配 7.1.1自在存儲區(qū)內(nèi)存自在存儲區(qū)內(nèi)存的分配與釋放的分配與釋放 7.1.2自在存儲區(qū)對象自在存儲區(qū)對象與構(gòu)造函數(shù)與構(gòu)造函數(shù) 7.1.3 淺復(fù)制與深復(fù)制淺復(fù)制與深復(fù)制 靜態(tài)存儲分配：靜態(tài)存儲分配：通常定義變量通常定義變量( (或?qū)ο蠡驅(qū)ο? )，編，編譯器在編譯時都可以根據(jù)該譯器在編譯時都可

3、以根據(jù)該變量變量( (或?qū)ο蠡驅(qū)ο? )的類型知道所的類型知道所需內(nèi)存空間的大小，從而系需內(nèi)存空間的大小，從而系統(tǒng)在適當(dāng)?shù)臅r候為它們分配統(tǒng)在適當(dāng)?shù)臅r候為它們分配確定的存儲空間。確定的存儲空間。動態(tài)存儲分配：動態(tài)存儲分配：有些操作對象只需在程序運有些操作對象只需在程序運轉(zhuǎn)時才干確定，這樣編譯器轉(zhuǎn)時才干確定，這樣編譯器在編譯時就無法為他們預(yù)定在編譯時就無法為他們預(yù)定存儲空間，只能在程序運轉(zhuǎn)存儲空間，只能在程序運轉(zhuǎn)時，系統(tǒng)根據(jù)運轉(zhuǎn)時的要求時，系統(tǒng)根據(jù)運轉(zhuǎn)時的要求進展內(nèi)存分配，稱為動態(tài)存進展內(nèi)存分配，稱為動態(tài)存儲分配。動態(tài)分配都在自在儲分配。動態(tài)分配都在自在存儲區(qū)中進展。存儲區(qū)中進展。7.1.17.1

4、.1自在存儲區(qū)內(nèi)存的分配與釋放自在存儲區(qū)內(nèi)存的分配與釋放當(dāng)程序運轉(zhuǎn)到需求一個動態(tài)分配的變量或?qū)ο髸r，必需向系統(tǒng)懇求獲得當(dāng)程序運轉(zhuǎn)到需求一個動態(tài)分配的變量或?qū)ο髸r，必需向系統(tǒng)懇求獲得自在存儲區(qū)中的一塊所需大小的存貯空間，用于存貯該變量或?qū)ο?。?dāng)不自在存儲區(qū)中的一塊所需大小的存貯空間，用于存貯該變量或?qū)ο?。?dāng)不再運用該變量或?qū)ο髸r，也就是它的生命終了時，要顯式釋放它所占用的再運用該變量或?qū)ο髸r，也就是它的生命終了時，要顯式釋放它所占用的存貯空間，這樣系統(tǒng)就能進展再次分配，做到反復(fù)運用有限的資源。存貯空間，這樣系統(tǒng)就能進展再次分配，做到反復(fù)運用有限的資源。 懇求和釋放自在存儲區(qū)中分配的存貯空間，分別

5、運用懇求和釋放自在存儲區(qū)中分配的存貯空間，分別運用newnew和和deletedelete的兩個運算符來完成，其運用的格式如下：的兩個運算符來完成，其運用的格式如下：指針變量名指針變量名=new =new 類型名類型名( (初始化式初始化式) )；delete delete 指針名指針名; ;newnew運算符前往的是一個指向所分配類型變量對象的運算符前往的是一個指向所分配類型變量對象的指針。對所創(chuàng)建的變量或?qū)ο?，都是?jīng)過該指針來間接操作的，指針。對所創(chuàng)建的變量或?qū)ο?，都是?jīng)過該指針來間接操作的，而動態(tài)創(chuàng)建的對象本身沒有名字。而動態(tài)創(chuàng)建的對象本身沒有名字。 動態(tài)分配與釋放：動態(tài)分配與釋放： 7

6、.1.1自在存儲區(qū)內(nèi)存的分配與釋放普通定義變量和對象時要用標(biāo)識符命名，稱命名對象，而動普通定義變量和對象時要用標(biāo)識符命名，稱命名對象，而動態(tài)的稱無名對象態(tài)的稱無名對象( (請留意與棧區(qū)中的暫時對象的區(qū)別，兩者完請留意與棧區(qū)中的暫時對象的區(qū)別，兩者完全不同：生命期不同，操作方法不同，暫時變量對程序員是全不同：生命期不同，操作方法不同，暫時變量對程序員是透明的透明的) )。自在存儲區(qū)是不會自動在分配時做初始化的包括。自在存儲區(qū)是不會自動在分配時做初始化的包括清零，所以必需用初始化式清零，所以必需用初始化式(initializer)(initializer)來顯式初始化。來顯式初始化。newnew表

7、達式的操作：表達式的操作：從自在存儲區(qū)分配對象，然后用括號中的值從自在存儲區(qū)分配對象，然后用括號中的值初始化該對象。初始化該對象。分配對象時，分配對象時，newnew表達式調(diào)用庫操作符表達式調(diào)用庫操作符new()new()： int int * *pi=new int(0);pi=new int(0);pipi如今所指向的變量的存儲空間是由庫操作如今所指向的變量的存儲空間是由庫操作符符new()new()分配的，位于程序的自在存儲區(qū)中，分配的，位于程序的自在存儲區(qū)中，并且該對象未命名。并且該對象未命名。 無名對象：無名對象： 7.1.1自在存儲區(qū)內(nèi)存的分配與釋放自在存儲區(qū)自在存儲區(qū)i演示：演示

8、：用初始化式用初始化式(initializer)(initializer)來顯式初始來顯式初始化化 int int * *pi=new int(0);pi=new int(0);當(dāng)當(dāng)pipi生命周期終了時，生命周期終了時，必需釋放必需釋放pipi所指向的目的：所指向的目的： delete pi;delete pi;留意這時釋放了留意這時釋放了pipi所指的目的的內(nèi)存空間，所指的目的的內(nèi)存空間，也就是撤銷了該目的，稱動態(tài)內(nèi)存釋放也就是撤銷了該目的，稱動態(tài)內(nèi)存釋放dynamic memory deallocationdynamic memory deallocation，但指，但指針針pipi本身

9、并沒有撤銷，該指針?biāo)純?nèi)存空間本身并沒有撤銷，該指針?biāo)純?nèi)存空間并未釋放。并未釋放。 7.1.17.1.1自在存儲區(qū)內(nèi)存的分配與釋放自在存儲區(qū)內(nèi)存的分配與釋放數(shù)組動態(tài)分配格式：數(shù)組動態(tài)分配格式：指針變量名指針變量名=new =new 類型名類型名 下標(biāo)表達式下標(biāo)表達式;Delete Delete 指向該數(shù)組的指針變量名指向該數(shù)組的指針變量名; ;闡明：闡明：兩式中的方括號必需配對運用。兩式中的方括號必需配對運用。假設(shè)假設(shè)deletedelete語句中少了方括號，因編譯器語句中少了方括號，因編譯器以為該指針是指向數(shù)組第一個元素的指針，以為該指針是指向數(shù)組第一個元素的指針，會產(chǎn)生回收不徹底的問題只

10、回收了第一會產(chǎn)生回收不徹底的問題只回收了第一個元素所占空間，加了方括號后就轉(zhuǎn)化個元素所占空間，加了方括號后就轉(zhuǎn)化為指向數(shù)組的指針，回收整個數(shù)組。為指向數(shù)組的指針，回收整個數(shù)組。 delete delete 的方括號中不需求填數(shù)組的方括號中不需求填數(shù)組元素數(shù)，系統(tǒng)自知。即使寫了，編譯器也元素數(shù)，系統(tǒng)自知。即使寫了，編譯器也忽略。忽略。 請留意請留意“下標(biāo)表達式不是常量表達式，下標(biāo)表達式不是常量表達式，即它的值不用在編譯時確定，可以在運轉(zhuǎn)即它的值不用在編譯時確定，可以在運轉(zhuǎn)時確定。時確定。7.1.17.1.1自在存儲區(qū)內(nèi)存的分配與釋放自在存儲區(qū)內(nèi)存的分配與釋放動態(tài)分配數(shù)組與規(guī)范字符串類：動態(tài)分配數(shù)

11、組與規(guī)范字符串類： 規(guī)范字符串類規(guī)范字符串類string就是采用動態(tài)建立數(shù)組的方式處理就是采用動態(tài)建立數(shù)組的方式處理數(shù)組溢出的問題的，例數(shù)組溢出的問題的，例7.1所做的動態(tài)內(nèi)存分配與釋放，所做的動態(tài)內(nèi)存分配與釋放，在在string類對象中都是自動完成的，在程序中不需求也不類對象中都是自動完成的，在程序中不需求也不允許再顯式地為允許再顯式地為string進展動態(tài)內(nèi)存的分配與釋放。進展動態(tài)內(nèi)存的分配與釋放?！纠纠?.1】動態(tài)數(shù)組的建立與撤銷】動態(tài)數(shù)組的建立與撤銷7.1.17.1.1自在存儲區(qū)內(nèi)存的分配與釋放自在存儲區(qū)內(nèi)存的分配與釋放動態(tài)分配數(shù)組的特點：動態(tài)分配數(shù)組的特點：1. 變量變量n在編譯時

12、沒有確定的值，而是在運轉(zhuǎn)中輸入，按運轉(zhuǎn)在編譯時沒有確定的值，而是在運轉(zhuǎn)中輸入，按運轉(zhuǎn)時所需分配空間，這一點是動態(tài)分配的優(yōu)點，可抑制數(shù)組時所需分配空間，這一點是動態(tài)分配的優(yōu)點，可抑制數(shù)組“大開小用的弊端，在表、排序與查找中的算法，假設(shè)用大開小用的弊端，在表、排序與查找中的算法，假設(shè)用動態(tài)數(shù)組，通用性更佳。動態(tài)數(shù)組，通用性更佳。delete pc是將是將n個字符的空間個字符的空間釋放，而用釋放，而用delete pc那么只釋放了一個字符的空間；那么只釋放了一個字符的空間；2. 假設(shè)有假設(shè)有char *pc1，令，令pc1=pc，同樣可用，同樣可用delete pc1 來釋放該空間。雖然來釋放該空間

13、。雖然C+不對數(shù)組作邊境檢查，但在自在不對數(shù)組作邊境檢查，但在自在 存儲區(qū)存儲區(qū) 空間分配時，對數(shù)組分配空間大小是紀(jì)錄在案的?？臻g分配時，對數(shù)組分配空間大小是紀(jì)錄在案的。3. 沒有初始化式?jīng)]有初始化式initializer，不可對數(shù)組初始化。，不可對數(shù)組初始化。 7.1.17.1.1自在存儲區(qū)內(nèi)存的分配與釋放選讀自在存儲區(qū)內(nèi)存的分配與釋放選讀多維數(shù)組動態(tài)分配：多維數(shù)組動態(tài)分配：new 類型名類型名下標(biāo)表達式下標(biāo)表達式1 下標(biāo)表達式下標(biāo)表達式2;建立一個動態(tài)三維數(shù)組建立一個動態(tài)三維數(shù)組float (*cp)3020 ; /指向一個指向一個30行行20列數(shù)組的指針列數(shù)組的指針cp=new floa

14、t 15 30 20; /建立由建立由15個個30*20數(shù)組組成的數(shù)組；數(shù)組組成的數(shù)組；留意留意cp等效于三維數(shù)組名，但沒有指出其邊等效于三維數(shù)組名，但沒有指出其邊境，即最高維的元素數(shù)量，就像指向字符的指境，即最高維的元素數(shù)量，就像指向字符的指針即等效一個字符串針即等效一個字符串,不要把指向字符的指針，不要把指向字符的指針，說成指向字符串的指針。這與數(shù)組的嵌套定義說成指向字符串的指針。這與數(shù)組的嵌套定義相一致。相一致。7.1.17.1.1自在存儲區(qū)內(nèi)存的分配與釋放選讀自在存儲區(qū)內(nèi)存的分配與釋放選讀比較：比較：float(*cp) 30 20; /三級指針三級指針float (*bp) 20;

15、/二級指針二級指針cp=new float 1 30 20;bp=new float 30 20;兩個數(shù)組都是由兩個數(shù)組都是由600個浮點數(shù)組成，前者是個浮點數(shù)組成，前者是只需一個元素的三維數(shù)組，每個元素為只需一個元素的三維數(shù)組，每個元素為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)建和

16、刪除一個動態(tài)創(chuàng)建和刪除一個m*n個元素的數(shù)組個元素的數(shù)組7.1.17.1.1自在存儲區(qū)的分配與釋放自在存儲區(qū)的分配與釋放指針運用的要點：指針運用的要點：1. 動態(tài)分配失敗。前往一個空指針動態(tài)分配失敗。前往一個空指針NULL，表示發(fā)生了異常，堆資源缺乏，分配失敗。表示發(fā)生了異常，堆資源缺乏，分配失敗。 指針刪除與自在存儲區(qū)空間釋放。刪除一個指針指針刪除與自在存儲區(qū)空間釋放。刪除一個指針pdelete p;實踐意思是刪除了實踐意思是刪除了p所指的目的變量或?qū)λ傅哪康淖兞炕驅(qū)ο蟮龋尫帕怂嫉淖栽诖鎯^(qū)空間，而不是刪除象等，釋放了它所占的自在存儲區(qū)空間，而不是刪除本身，釋放自在存儲區(qū)空間后，成了

17、空懸指針?？諔抑副旧?，釋放自在存儲區(qū)空間后，成了空懸指針?？諔抑羔樖浅绦蝈e誤的一個根源。建議這時將置空針是程序錯誤的一個根源。建議這時將置空NULL。3. new()和和delete()是可以重載的，它們都是類的靜態(tài)是可以重載的，它們都是類的靜態(tài)成員函數(shù)。程序員無需顯式聲明它為靜態(tài)的，系統(tǒng)自動成員函數(shù)。程序員無需顯式聲明它為靜態(tài)的，系統(tǒng)自動定義為靜態(tài)的。本教材不討論定義為靜態(tài)的。本教材不討論new()和和delete()的重載。的重載。未重載時，調(diào)用全局庫操作符未重載時，調(diào)用全局庫操作符new()。7.1.17.1.1自在存儲區(qū)內(nèi)存的分配與釋放自在存儲區(qū)內(nèi)存的分配與釋放4內(nèi)存走漏內(nèi)存走漏mem

18、ory leak和反復(fù)釋放。和反復(fù)釋放。new與與delete 是配對運用的，是配對運用的， delete只能釋放自在存儲區(qū)空間。只能釋放自在存儲區(qū)空間。假設(shè)假設(shè)new前往的指針值喪失，那么所分配的自在存儲區(qū)空前往的指針值喪失，那么所分配的自在存儲區(qū)空間無法回收，稱內(nèi)存走漏，同一空間反復(fù)釋放也是危險的，間無法回收，稱內(nèi)存走漏，同一空間反復(fù)釋放也是危險的，由于該空間能夠已另分配，所以必需妥善保管由于該空間能夠已另分配，所以必需妥善保管new前往的前往的指針，以保證不發(fā)生內(nèi)存走漏，也必需保證不會反復(fù)釋放指針，以保證不發(fā)生內(nèi)存走漏，也必需保證不會反復(fù)釋放自在存儲區(qū)內(nèi)存空間。自在存儲區(qū)內(nèi)存空間。5動態(tài)

19、分配的變量或?qū)ο蟮纳?。無名對象的生命期動態(tài)分配的變量或?qū)ο蟮纳?。無名對象的生命期并不依賴于建立它的作用域，比如在函數(shù)中建立的動態(tài)對并不依賴于建立它的作用域，比如在函數(shù)中建立的動態(tài)對象在函數(shù)前往后仍可運用。但必需記住釋放該對象所占自象在函數(shù)前往后仍可運用。但必需記住釋放該對象所占自在存儲區(qū)空間，并只能釋放一次，在函數(shù)內(nèi)建立，而在函在存儲區(qū)空間，并只能釋放一次，在函數(shù)內(nèi)建立，而在函數(shù)外釋放是一件很容易失控的事，往往會出錯。數(shù)外釋放是一件很容易失控的事，往往會出錯。 7.1.27.1.2自在存儲區(qū)對象與構(gòu)造函數(shù)自在存儲區(qū)對象與構(gòu)造函數(shù) 類對象動態(tài)建立與刪除過程：類對象動態(tài)建立與刪除過程：經(jīng)過

20、經(jīng)過new建立的對象要調(diào)用構(gòu)造函數(shù)，經(jīng)過建立的對象要調(diào)用構(gòu)造函數(shù)，經(jīng)過delete刪除對象也要調(diào)用析構(gòu)函數(shù)。刪除對象也要調(diào)用析構(gòu)函數(shù)。CGoods *pc;pc=new CGoods; /分配自在存儲區(qū)空間，并構(gòu)造一個無名的分配自在存儲區(qū)空間，并構(gòu)造一個無名的CGoods對象；對象；.delete pc; /先析構(gòu)，然后將內(nèi)存空間前往給自先析構(gòu)，然后將內(nèi)存空間前往給自在存儲區(qū)；在存儲區(qū)；自在存儲區(qū)對象的生命期并不依賴于建立它的作用域，所以除非自在存儲區(qū)對象的生命期并不依賴于建立它的作用域，所以除非程序終了，自在存儲區(qū)對象無名對象的生命期不會到期，并程序終了，自在存儲區(qū)對象無名對象的生命期不會到

21、期，并且需求顯式地用且需求顯式地用delete語句析構(gòu)該類對象，上例執(zhí)行語句析構(gòu)該類對象，上例執(zhí)行delete語句語句時，時，C+自動調(diào)用商品類的析構(gòu)函數(shù)。自動調(diào)用商品類的析構(gòu)函數(shù)。7.1.27.1.2自在存儲區(qū)對象與構(gòu)造函數(shù)自在存儲區(qū)對象與構(gòu)造函數(shù)由自在存儲區(qū)創(chuàng)建對象數(shù)組，只能調(diào)用由自在存儲區(qū)創(chuàng)建對象數(shù)組，只能調(diào)用默許的構(gòu)造函數(shù)，不能調(diào)用其他任何構(gòu)造默許的構(gòu)造函數(shù)，不能調(diào)用其他任何構(gòu)造函數(shù)。假設(shè)沒有默許的構(gòu)造函數(shù)，那么不函數(shù)。假設(shè)沒有默許的構(gòu)造函數(shù)，那么不能創(chuàng)建對象數(shù)組。能創(chuàng)建對象數(shù)組。類對象初始化：類對象初始化：new后面類后面類class類型可以有參數(shù)。這些參數(shù)即構(gòu)類型可以有參數(shù)。這些參

22、數(shù)即構(gòu)造函數(shù)的參數(shù)。但對創(chuàng)建數(shù)組，那么無參數(shù)，只能調(diào)造函數(shù)的參數(shù)。但對創(chuàng)建數(shù)組，那么無參數(shù)，只能調(diào)用默許的構(gòu)造函數(shù)。用默許的構(gòu)造函數(shù)?！纠纠?.37.3】演示自在存儲區(qū)對象分配和釋放?！垦菔咀栽诖鎯^(qū)對象分配和釋放。7.1.3淺復(fù)制與深復(fù)制淺復(fù)制與深復(fù)制 淺復(fù)制：默許復(fù)制構(gòu)造函數(shù)，可用一淺復(fù)制：默許復(fù)制構(gòu)造函數(shù)，可用一個類對象初始化另一個類對象，稱為默許個類對象初始化另一個類對象，稱為默許的按成員復(fù)制，而不是對整個類對象的按的按成員復(fù)制，而不是對整個類對象的按位復(fù)制。這稱為淺復(fù)制。位復(fù)制。這稱為淺復(fù)制。 圖圖7.1 淺復(fù)制淺復(fù)制 P自 在 存自 在 存儲 區(qū) 對儲 區(qū) 對象象自 在 存自 在

23、 存儲 區(qū) 對儲 區(qū) 對象象PP 復(fù)制前復(fù)制后復(fù)制后 假設(shè)類中有一個數(shù)據(jù)成員為指針，該類的一個對象假設(shè)類中有一個數(shù)據(jù)成員為指針，該類的一個對象obj1中中的這個指針的這個指針p，指向了動態(tài)分配的一個自在存儲區(qū)對象，參見，指向了動態(tài)分配的一個自在存儲區(qū)對象，參見圖圖7.1復(fù)制前，假設(shè)用復(fù)制前，假設(shè)用obj1按成員復(fù)制了一個對象按成員復(fù)制了一個對象obj2，這時，這時obj2.p也指向同一個自在存儲區(qū)對象。也指向同一個自在存儲區(qū)對象。obj1obj1obj27.1.3淺復(fù)制與深復(fù)制復(fù)制淺復(fù)制與深復(fù)制復(fù)制當(dāng)淺復(fù)制析構(gòu)時，如用默許的析當(dāng)淺復(fù)制析構(gòu)時，如用默許的析構(gòu)函數(shù)，那么動態(tài)分配的自在存儲區(qū)構(gòu)函數(shù)，

24、那么動態(tài)分配的自在存儲區(qū)對象不能回收。假設(shè)在析構(gòu)函數(shù)中有對象不能回收。假設(shè)在析構(gòu)函數(shù)中有“delete p;語句，那么假設(shè)先析構(gòu)語句，那么假設(shè)先析構(gòu)函數(shù)函數(shù)obj1時，自在存儲區(qū)對象曾經(jīng)釋時，自在存儲區(qū)對象曾經(jīng)釋放，以后再析構(gòu)放，以后再析構(gòu)obj2時出現(xiàn)了二次釋時出現(xiàn)了二次釋放的問題。放的問題。自在自在存儲存儲區(qū)對區(qū)對象象PP自在自在存儲存儲區(qū)對區(qū)對象象 圖圖7.2 深復(fù)制深復(fù)制 深復(fù)制：重新定義復(fù)制的構(gòu)造函數(shù)，深復(fù)制：重新定義復(fù)制的構(gòu)造函數(shù)，給每個對象獨立分配一個自在存儲區(qū)給每個對象獨立分配一個自在存儲區(qū)對象，稱深復(fù)制。這時先復(fù)制對象主對象，稱深復(fù)制。這時先復(fù)制對象主體，再為體，再為obj2

25、分配一個自在存儲區(qū)對分配一個自在存儲區(qū)對象，最后用象，最后用obj1的自在存儲區(qū)對象復(fù)的自在存儲區(qū)對象復(fù)制制obj2的自在存儲區(qū)對象。的自在存儲區(qū)對象。 obj1obj27.1.3淺復(fù)制與深復(fù)制淺復(fù)制與深復(fù)制【例【例7.4】定義復(fù)制構(gòu)造函數(shù)】定義復(fù)制構(gòu)造函數(shù) copy structor和復(fù)制賦值操和復(fù)制賦值操作符作符copy Assignment Operator實現(xiàn)深復(fù)制。實現(xiàn)深復(fù)制。 學(xué)生類定義：學(xué)生類定義：class student char *pName; /為了演示深復(fù)制，不用為了演示深復(fù)制，不用string類類public: student(); /默許構(gòu)造函數(shù)默許構(gòu)造函數(shù) stu

26、dent(char *pname); /帶參數(shù)構(gòu)造函數(shù)帶參數(shù)構(gòu)造函數(shù) student(student &s); /復(fù)制構(gòu)造函數(shù)復(fù)制構(gòu)造函數(shù) student(); /析構(gòu)函數(shù)析構(gòu)函數(shù) student & operator=(student &s); ; /復(fù)制賦值復(fù)制賦值操作符操作符檢驗主函數(shù)和運轉(zhuǎn)結(jié)果檢驗主函數(shù)和運轉(zhuǎn)結(jié)果7.1.3淺復(fù)制與深復(fù)制淺復(fù)制與深復(fù)制 提示：提示： 自在存儲區(qū)內(nèi)存是最常見的需求自定義復(fù)制構(gòu)自在存儲區(qū)內(nèi)存是最常見的需求自定義復(fù)制構(gòu)造函數(shù)的資源，但不是獨一的，還有翻開文件等也造函數(shù)的資源，但不是獨一的，還有翻開文件等也需求自定義復(fù)制構(gòu)造函數(shù)。需求自定

27、義復(fù)制構(gòu)造函數(shù)。 假設(shè)類對象需求動態(tài)分配資源應(yīng)該由構(gòu)造函假設(shè)類對象需求動態(tài)分配資源應(yīng)該由構(gòu)造函數(shù)完成，而釋放資源由析構(gòu)函數(shù)完成，這時類也需數(shù)完成，而釋放資源由析構(gòu)函數(shù)完成，這時類也需求一個自定義的復(fù)制構(gòu)造函數(shù)，實現(xiàn)對象的深復(fù)制。求一個自定義的復(fù)制構(gòu)造函數(shù)，實現(xiàn)對象的深復(fù)制。由此可見，構(gòu)造函數(shù)并非僅做初始化任務(wù)。由此可見，構(gòu)造函數(shù)并非僅做初始化任務(wù)。7.1.3淺復(fù)制與深復(fù)制淺復(fù)制與深復(fù)制思索：思索： 深化地思索【例深化地思索【例7.47.4】，假設(shè)數(shù)據(jù)域還】，假設(shè)數(shù)據(jù)域還有很多其他數(shù)據(jù)，甚至有好幾個是動態(tài)建立有很多其他數(shù)據(jù)，甚至有好幾個是動態(tài)建立的的C C字符串，深復(fù)制是不是太復(fù)雜了？假設(shè)字符串

28、，深復(fù)制是不是太復(fù)雜了？假設(shè)運用運用C+C+規(guī)范字符串規(guī)范字符串stringstring作為成員對象作為成員對象聚合能否就不需求思索深復(fù)制了？聚合能否就不需求思索深復(fù)制了？確實是這樣的，準(zhǔn)確地說，確實是這樣的，準(zhǔn)確地說，string類的內(nèi)部包含動態(tài)建立字類的內(nèi)部包含動態(tài)建立字符數(shù)組的操作，其復(fù)制構(gòu)造函數(shù)是深復(fù)制。假設(shè)在符數(shù)組的操作，其復(fù)制構(gòu)造函數(shù)是深復(fù)制。假設(shè)在student類中運用類中運用string類而不是類而不是C字符串，就不要再思索深復(fù)制問字符串，就不要再思索深復(fù)制問題了。也就是說，動態(tài)內(nèi)存分配和深復(fù)制應(yīng)該放在一個適當(dāng)題了。也就是說，動態(tài)內(nèi)存分配和深復(fù)制應(yīng)該放在一個適當(dāng)?shù)膶用嫔?，一個更

29、單純的類定義中，如的層面上，一個更單純的類定義中，如string類。在運用中，類。在運用中，把它作為一個成員對象，就像運用把它作為一個成員對象，就像運用string類對象那樣。類對象那樣。7.1.3淺復(fù)制與深復(fù)制淺復(fù)制與深復(fù)制討論：討論： 最后進一步討論類的封裝。封裝的更高最后進一步討論類的封裝。封裝的更高境界是在該類對象中一切都是完備的、自給境界是在該類對象中一切都是完備的、自給自足的，不僅有數(shù)據(jù)和對數(shù)據(jù)的操作，還包自足的，不僅有數(shù)據(jù)和對數(shù)據(jù)的操作，還包括資源的動態(tài)安排和釋放。在需求時可以無括資源的動態(tài)安排和釋放。在需求時可以無條件地平安運用。規(guī)范條件地平安運用。規(guī)范string類模板就是典

30、類模板就是典型的例子。這樣的類對象，作為另一個類的型的例子。這樣的類對象，作為另一個類的成員對象運用時，就不會出任何問題。這闡成員對象運用時，就不會出任何問題。這闡明聚合實現(xiàn)了完善的封裝。明聚合實現(xiàn)了完善的封裝。 7.2 鏈表與鏈表的根本操作鏈表與鏈表的根本操作 線性表是最簡單，最常用的一種數(shù)據(jù)構(gòu)線性表是最簡單，最常用的一種數(shù)據(jù)構(gòu)造。線性表的邏輯構(gòu)造是造。線性表的邏輯構(gòu)造是n n個數(shù)據(jù)元素的有個數(shù)據(jù)元素的有限序列限序列a1,a2,ana1,a2,an。而線性表的物理。而線性表的物理構(gòu)造包括：順序表，鏈表構(gòu)造包括：順序表，鏈表 。7.2.1 單鏈表根本算法單鏈表根本算法 7.2.3 雙向鏈表雙向

31、鏈表(選讀選讀)7.2.2單鏈表類型模板單鏈表類型模板 7.2.1 單鏈表根本算法單鏈表根本算法單鏈表單鏈表Singly Linked list： 每個數(shù)據(jù)元素占用一個節(jié)點每個數(shù)據(jù)元素占用一個節(jié)點Node。一個節(jié)點包含兩個域，一個域存放數(shù)據(jù)元素一個節(jié)點包含兩個域，一個域存放數(shù)據(jù)元素info，其數(shù)據(jù)類型由運用問題決議；另一個存，其數(shù)據(jù)類型由運用問題決議；另一個存放指向該鏈表中下一個節(jié)點的指針放指向該鏈表中下一個節(jié)點的指針link。節(jié)點定義如下：節(jié)點定義如下： typedef int Datatype; /typedef int Datatype; /數(shù)據(jù)為整型數(shù)據(jù)為整型struct nodest

32、ruct node Datatype info; Datatype info; node node * *link;link;在在C/C+中允許構(gòu)造或?qū)ο蟪蓡T是構(gòu)造本身的指針類型，中允許構(gòu)造或?qū)ο蟪蓡T是構(gòu)造本身的指針類型，經(jīng)過指針援用本身這種類型的構(gòu)造。但構(gòu)呵斥員決不能是構(gòu)經(jīng)過指針援用本身這種類型的構(gòu)造。但構(gòu)呵斥員決不能是構(gòu)造本身類型，即構(gòu)造不能本人定義本人，這會導(dǎo)致一個無窮造本身類型，即構(gòu)造不能本人定義本人，這會導(dǎo)致一個無窮遞歸的定義。遞歸的定義。 7.2.1 單鏈表根本算法單鏈表根本算法單鏈表的第一個結(jié)點的地址可經(jīng)過鏈表的表頭指針單鏈表的第一個結(jié)點的地址可經(jīng)過鏈表的表頭指針head找找到，

33、到， head在運用中千萬不可喪失，否那么鏈表整個喪失，內(nèi)在運用中千萬不可喪失，否那么鏈表整個喪失，內(nèi)存也發(fā)生走漏。存也發(fā)生走漏。infon-1 info2 info1 info0 head圖圖7.3 單鏈表構(gòu)造單鏈表構(gòu)造 單鏈表的插入與刪除：單鏈表的插入與刪除： 只需改動鏈中結(jié)點指針的值，無需挪動表中的只需改動鏈中結(jié)點指針的值，無需挪動表中的元素，就能實現(xiàn)插入和刪除操作。元素，就能實現(xiàn)插入和刪除操作。插入算法有三種情況，我們希望在單鏈表中包插入算法有三種情況，我們希望在單鏈表中包含數(shù)據(jù)含數(shù)據(jù)infoi的結(jié)點之前插入一個新元素，那么的結(jié)點之前插入一個新元素，那么infoi可在第一個結(jié)點，或在中

34、間結(jié)點，如未找到，那么可在第一個結(jié)點，或在中間結(jié)點，如未找到，那么把新結(jié)點插在鏈尾結(jié)點之后。把新結(jié)點插在鏈尾結(jié)點之后。 7.2.1 單鏈表根本算法單鏈表根本算法newnodeinfoxinfo0info1headhead插在鏈?zhǔn)祝翰逶阪準(zhǔn)祝?首先新結(jié)點的首先新結(jié)點的link指針指向指針指向info0所在結(jié)點，然后，所在結(jié)點，然后，head指向新結(jié)點。即：指向新結(jié)點。即：newnodelink=head；/留意：鏈表操作次序非常重留意：鏈表操作次序非常重要要head=newnode；7.2.1 單鏈表根本算法單鏈表根本算法infoxinfoi-1infoipnewnode插在中間：插在中間： 首

35、先用任務(wù)指針首先用任務(wù)指針p找到指定結(jié)點，而讓指針找到指定結(jié)點，而讓指針q指向緊跟指向緊跟其后的結(jié)點，令其后的結(jié)點，令infoi-1所在結(jié)點的所在結(jié)點的link指針指向新結(jié)點，指針指向新結(jié)點，而后讓新結(jié)點的而后讓新結(jié)點的link指向指向infoi所在結(jié)點。即：所在結(jié)點。即：newnodelink=p；/或或newnodelink=qlink；可用于插入某結(jié)點之后；可用于插入某結(jié)點之后qlink=newnode；7.2.1 單鏈表根本算法單鏈表根本算法infox infox newnodepinfon-1 infon-1 插在隊尾：插在隊尾：只需任務(wù)指針只需任務(wù)指針p找到隊尾，即可鏈在其后：找到

36、隊尾，即可鏈在其后：plink=newnode；newnode.link=NULL;7.2.1 單鏈表根本算法單鏈表根本算法帶表頭構(gòu)造的鏈表：帶表頭構(gòu)造的鏈表：研討以上算法，插在鏈表第一個結(jié)點之前與其研討以上算法，插在鏈表第一個結(jié)點之前與其他結(jié)點之前的算法有所不同。要使算法中沒有他結(jié)點之前的算法有所不同。要使算法中沒有特殊者，可以給每一個鏈表加上一個表頭結(jié)點，特殊者，可以給每一個鏈表加上一個表頭結(jié)點，如以下圖所示。如以下圖所示?？毡砣缦拢嚎毡砣缦拢篽eadinfo0Infon-1info1head 下面分別引見帶表頭構(gòu)造的鏈表的生成鏈表算法、鏈表查找算法、插入一個結(jié)點的算法和刪除一個結(jié)點的算法

37、。 7.2.1 單鏈表根本算法單鏈表根本算法headtailpinfo1tailpinfo0tail1. 1. 向后生成鏈表算法：向后生成鏈表算法：node node * *createdown() createdown() Datatype data;Datatype data;NodeNode* *head,head,* *tail,tail,* *p; p; head=new node; /head=new node; /建立鏈表頭建立鏈表頭結(jié)點結(jié)點 tail=head;tail=head;while(cindata)while(cindata) / /回車終了回車終了 p=new(no

38、de);p=new(node);/每輸入一個數(shù)懇求一個結(jié)點每輸入一個數(shù)懇求一個結(jié)點p-info=data; /p-info=data; /添入數(shù)據(jù)添入數(shù)據(jù)tail-link= p; /tail-link= p; /新結(jié)點接新結(jié)點接到鏈尾到鏈尾 tail=p; /tail=p; /尾指針到鏈尾尾指針到鏈尾 tail-link=NULL;tail-link=NULL;/鏈尾加空指針，表示鏈終了鏈尾加空指針，表示鏈終了 return head; /return head; /前往頭前往頭指針指針 7.2.1 單鏈表根本算法單鏈表根本算法headinfo0 PPinfo12. 2. 向前生成鏈表算法：

39、向前生成鏈表算法：node node * *createup() createup() node node * *head,head,* *p; p; Datatype data; Datatype data; head=new node; / head=new node; /建立建立頭結(jié)點頭結(jié)點 head-link=NULL; head-link=NULL; while(cindata) while(cindata) / /建立的總是第一個結(jié)點建立的總是第一個結(jié)點 p=new node; p=new node; p-info=data; p-info=data; p-link= head-l

40、ink ; p-link= head-link ;/新結(jié)點放在原鏈表前方新結(jié)點放在原鏈表前方 head-link=p;head-link=p; / /頭結(jié)點放新結(jié)點之前頭結(jié)點放新結(jié)點之前 return head; return head;7.2.1 單鏈表根本算法單鏈表根本算法3.3.鏈表查找算法鏈表查找算法( (按關(guān)鍵字按關(guān)鍵字) )查找：查找：node node * *traversal(node traversal(node * *head,Datatype head,Datatype data)data) node node * *p=head-link;p=head-link; wh

41、ile(p!=NULL&p-info!=data) p=p- while(p!=NULL&p-info!=data) p=p-link;link; return p; /p return p; /p為為NULLNULL那么未找到那么未找到 前往值為指針前往值為指針p p，指向鏈表中找到的結(jié)點。，指向鏈表中找到的結(jié)點。4. 4. 在單鏈表的在單鏈表的p p節(jié)點后插入：節(jié)點后插入：留意只需一種情況。留意只需一種情況。void insert(node void insert(node * *p,Datatype x)p,Datatype x) node node * *q=new n

42、ode;q=new node; q-info=x; q-info=x; q-link=p-link; q-link=p-link; p-link=q; p-link=q; 7.2.1 單鏈表根本算法單鏈表根本算法5. 5. 刪除單鏈表節(jié)點刪除單鏈表節(jié)點* *p p后面節(jié)點：后面節(jié)點：void del (node void del (node * *p)p) node node * *q;q; q=p-link; q=p-link; p-link=q-link; p-link=q-link; delete q; delete q; / /假設(shè)要把該節(jié)點移入另一個鏈中，那么可將假設(shè)要把該節(jié)點移入另

43、一個鏈中，那么可將q q前往。前往。 7.2.2 單鏈表類型模板單鏈表類型模板【例【例7.5_h】單鏈表類模板?！繂捂湵眍惸０?。定義結(jié)點類：定義結(jié)點類：templateclass List;templateclass Node T info; /數(shù)據(jù)域數(shù)據(jù)域 Node *link; /指針域，留意結(jié)點類格式，尖括號中是參數(shù)名表，類模板實例指針域，留意結(jié)點類格式，尖括號中是參數(shù)名表，類模板實例化為類化為類public: Node(); /生成頭結(jié)點的構(gòu)造函數(shù)生成頭結(jié)點的構(gòu)造函數(shù) Node(const T & data); /生成普通結(jié)點的構(gòu)造函數(shù)生成普通結(jié)點的構(gòu)造函數(shù) void Inse

44、rtAfter(Node* p); /在當(dāng)前結(jié)點后插入一個結(jié)點在當(dāng)前結(jié)點后插入一個結(jié)點 Node* RemoveAfter(); /刪除當(dāng)前結(jié)點的后繼結(jié)點刪除當(dāng)前結(jié)點的后繼結(jié)點 friend class List; /以以List為友元類，為友元類，List可直接訪問可直接訪問Node的私有函數(shù)的私有函數(shù);定義鏈表類定義鏈表類: : templateclass Listtemplateclass List Node Node * *head,head,* *tail; /tail; /鏈表頭指針和尾指針鏈表頭指針和尾指針public:public: List(); / List(); /構(gòu)造函

45、數(shù)，生成頭結(jié)點構(gòu)造函數(shù)，生成頭結(jié)點( (空鏈表空鏈表) ) List(); / List(); /析構(gòu)函數(shù)析構(gòu)函數(shù) void MakeEmpty(); /void MakeEmpty(); /清空鏈表，只余表頭結(jié)點清空鏈表，只余表頭結(jié)點 NodeNode* * Find(T data); Find(T data); / /搜索數(shù)據(jù)域與搜索數(shù)據(jù)域與datadata一樣的結(jié)點，前往該結(jié)點的一樣的結(jié)點，前往該結(jié)點的地址地址 int Length(); /int Length(); /計算單鏈表長度計算單鏈表長度 void PrintList(); /void PrintList(); /打印鏈表的數(shù)

46、據(jù)域打印鏈表的數(shù)據(jù)域 void InsertFront(Nodevoid InsertFront(Node* * p); / p); /可用來可用來向前生成鏈表向前生成鏈表 void InsertRear(Nodevoid InsertRear(Node* * p); / p); /可用來向后可用來向后生成鏈表生成鏈表 void InsertOrder(Node void InsertOrder(Node * *p); /p); /按升序生成按升序生成鏈表鏈表 NodeNode* *CreatNode(T data); /CreatNode(T data); /創(chuàng)建結(jié)點創(chuàng)建結(jié)點( (孤孤立結(jié)點

47、立結(jié)點) ) Node Node* *DeleteNode(NodeDeleteNode(Node* * p); ; / p); ; /刪除指刪除指定結(jié)點定結(jié)點7.2.2 單鏈表類型模板單鏈表類型模板7.2.2 單鏈表類型模板單鏈表類型模板【例【例7.57.5】由鍵盤輸入】由鍵盤輸入1616個整數(shù)，以這些整數(shù)作為結(jié)點數(shù)據(jù)，個整數(shù)，以這些整數(shù)作為結(jié)點數(shù)據(jù)，生成兩個鏈表，一個向前生成，一個向后生成，輸出兩個生成兩個鏈表，一個向前生成，一個向后生成，輸出兩個表。然后給出一個整數(shù)在一個鏈表中查找，找到后刪除它，表。然后給出一個整數(shù)在一個鏈表中查找，找到后刪除它，再輸出該表。清空該表，再按升序生成鏈表并

48、輸出。再輸出該表。清空該表，再按升序生成鏈表并輸出。在本例中程序只需調(diào)用類模板中的成員函數(shù)就可以完成一在本例中程序只需調(diào)用類模板中的成員函數(shù)就可以完成一切鏈表操作。切鏈表操作。【例【例7.67.6】以學(xué)生類作為鏈表的數(shù)據(jù)類，完成學(xué)生檔案的管】以學(xué)生類作為鏈表的數(shù)據(jù)類，完成學(xué)生檔案的管理。理。7.2.2 單鏈表類型模板單鏈表類型模板討論復(fù)制構(gòu)造函數(shù)：討論復(fù)制構(gòu)造函數(shù)： 在本例中沒有給出在本例中沒有給出Node類的復(fù)制構(gòu)造函數(shù)，并非類的復(fù)制構(gòu)造函數(shù)，并非可以運用默許的復(fù)制構(gòu)造函數(shù)，而是避開了一切運用可以運用默許的復(fù)制構(gòu)造函數(shù)，而是避開了一切運用它的情況，本例中函數(shù)的參數(shù)和前往值僅運用指向它的情況，

49、本例中函數(shù)的參數(shù)和前往值僅運用指向Node的指針，類定義中也沒有用復(fù)制方式初始化。定的指針，類定義中也沒有用復(fù)制方式初始化。定義復(fù)制構(gòu)造函數(shù)與類的實踐意義和運用方式有關(guān)，并義復(fù)制構(gòu)造函數(shù)與類的實踐意義和運用方式有關(guān)，并非只是深復(fù)制和淺復(fù)制的問題。非只是深復(fù)制和淺復(fù)制的問題。 通常對通常對Node類復(fù)制的結(jié)果應(yīng)是一個孤立結(jié)點：類復(fù)制的結(jié)果應(yīng)是一個孤立結(jié)點：template Node:Node(Node & node)info=node.data;link=NULL;link域值為域值為NULL。該函數(shù)與。該函數(shù)與Node的有參構(gòu)造函數(shù)功的有參構(gòu)造函數(shù)功能根本一樣。思索到函數(shù)的參數(shù)和前往值

50、僅運用指向能根本一樣。思索到函數(shù)的參數(shù)和前往值僅運用指向Node的指針，定義復(fù)制構(gòu)造函數(shù)曾經(jīng)沒有實踐意義的指針，定義復(fù)制構(gòu)造函數(shù)曾經(jīng)沒有實踐意義 單鏈表的復(fù)制構(gòu)造函數(shù)和復(fù)制運算符是一個復(fù)雜單鏈表的復(fù)制構(gòu)造函數(shù)和復(fù)制運算符是一個復(fù)雜的算法，與前文所編的復(fù)制構(gòu)造函數(shù)和復(fù)制運算符構(gòu)的算法，與前文所編的復(fù)制構(gòu)造函數(shù)和復(fù)制運算符構(gòu)造相去甚遠了。造相去甚遠了。7.2.3 雙向鏈表選讀雙向鏈表選讀 雙向鏈表引入：雙向鏈表引入：思索單鏈表只能找后繼。如要找前驅(qū)，必需從表思索單鏈表只能找后繼。如要找前驅(qū)，必需從表頭開場搜索。為了抑制這一缺陷，可采用雙向鏈頭開場搜索。為了抑制這一缺陷，可采用雙向鏈表表Double

51、 Linked List)Double Linked List)。雙向鏈表的結(jié)點有三。雙向鏈表的結(jié)點有三個域：左鏈接指針個域：左鏈接指針llink)llink)，數(shù)據(jù)域，數(shù)據(jù)域info)info)，右，右鏈接指針域鏈接指針域(rlink)(rlink)。雙向鏈表經(jīng)常采用帶頭結(jié)點。雙向鏈表經(jīng)常采用帶頭結(jié)點的循環(huán)鏈表方式。的循環(huán)鏈表方式。 info0 infon-1. info1head(a) 非空表非空表head(b)空表空表7.2.3 雙向鏈表選讀雙向鏈表選讀雙向鏈表的訪問：雙向鏈表的訪問：假設(shè)指針假設(shè)指針p指向雙向循環(huán)鏈表的某一個結(jié)點，那么，指向雙向循環(huán)鏈表的某一個結(jié)點，那么，p-llink

52、指示指示P所指結(jié)點的前驅(qū)結(jié)點，所指結(jié)點的前驅(qū)結(jié)點，p-rlink指示后指示后繼結(jié)點。繼結(jié)點。p-llink-rlink指示本結(jié)點的前驅(qū)結(jié)點的后指示本結(jié)點的前驅(qū)結(jié)點的后繼結(jié)點，即本結(jié)點，間接訪問符繼結(jié)點，即本結(jié)點，間接訪問符-可以延續(xù)運用?？梢匝永m(xù)運用。pllink rlinkrlinkllink rlink前驅(qū)結(jié)點前驅(qū)結(jié)點 llink 本結(jié)點本結(jié)點 后繼結(jié)點后繼結(jié)點 間接訪問符的運用間接訪問符的運用【例【例7.77.7】雙向鏈表類模板和結(jié)點類模板?！侩p向鏈表類模板和結(jié)點類模板。7.3 棧與隊列的根本操作及其運用棧與隊列的根本操作及其運用 棧和隊都是特殊的線性表，限棧和隊都是特殊的線性表，限制存

53、取位置的線性構(gòu)造，可以由順制存取位置的線性構(gòu)造，可以由順序表實現(xiàn)，也可以由鏈表實現(xiàn)。序表實現(xiàn)，也可以由鏈表實現(xiàn)。 7.3.1 棧棧 7.3.3隊列隊列 7.3.2 棧的運用選讀棧的運用選讀 7.3.1 棧棧棧的根本概念：棧的根本概念： 棧定義為只允許在表的一端進展插入和刪除的棧定義為只允許在表的一端進展插入和刪除的線性表。允許進展插入和刪除的一端叫做棧頂線性表。允許進展插入和刪除的一端叫做棧頂(top)，而另一端叫棧底而另一端叫棧底(bottom)。 棧中沒有任何元素時，稱為空棧。棧中沒有任何元素時，稱為空棧。 進棧時最先進棧的在最下面，最后的在最上面，進棧時最先進棧的在最下面，最后的在最上面

54、，后來居上。而出棧時順序相反，最后進棧的最先出后來居上。而出棧時順序相反，最后進棧的最先出棧，而最先進棧的棧，而最先進棧的a0最后出棧。所以棧又稱作后進最后出棧。所以棧又稱作后進先出先出LIFO：Last In First Out的線性表。的線性表。 ?？梢杂庙樞虮韺崿F(xiàn)，稱順序棧；也可以用鏈?？梢杂庙樞虮韺崿F(xiàn)，稱順序棧；也可以用鏈表實現(xiàn)，稱鏈棧。表實現(xiàn)，稱鏈棧。7.3.1 棧棧棧的根本操作：棧的根本操作： 參見以下圖，設(shè)給定棧參見以下圖，設(shè)給定棧s=(a0，a1，an-1)，稱稱a0為棧底，為棧底，an-1為棧頂。進棧時最先進棧的為棧頂。進棧時最先進棧的a0在在最下面，最下面，an-1在最上面

55、。而出棧時順序相反，最后在最上面。而出棧時順序相反，最后進棧的進棧的an-1最先出棧，而最先進棧的最先出棧，而最先進棧的a0最后出棧。最后出棧。a0an-2a1an-1bottom進棧進棧toptoptoptoptop出棧出棧圖示為順序棧。其中棧圖示為順序棧。其中棧底底bottom是指向棧數(shù)據(jù)是指向棧數(shù)據(jù)區(qū)的下一單元，這樣判區(qū)的下一單元，這樣判別能否為空棧會更方便，別能否為空棧會更方便，只需只需top與與bottom一樣一樣就是空棧。通常只需棧就是空棧。通常只需棧頂與操作有關(guān)。頂與操作有關(guān)。7.3.1 棧棧templateclass Stack int top; /棧頂指針下標(biāo)棧頂指針下標(biāo) T

56、 *elements; /動態(tài)建立的元素動態(tài)建立的元素 int maxSize; /棧最大包容的元素個數(shù)棧最大包容的元素個數(shù)public: Stack(int=20); /構(gòu)造函數(shù)，棧如不指定大小，設(shè)為構(gòu)造函數(shù)，棧如不指定大小，設(shè)為20元素元素 Stack()delete elements; void Push(const T &data); /壓棧壓棧 T Pop(); /彈出，彈出，top- T GetElem(int i); /取數(shù)據(jù)，取數(shù)據(jù)，top不變不變 void MakeEmpty()top= -1; /清空棧清空棧 bool IsEmpty() constreturn t

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

58、=istack.Pop();if(istack.IsEmpty() cout棧空?？誩ndl;for(i=0;i10;i+) coutbit; /留意先進后出留意先進后出coutendl;istack.Pop(); /下溢出下溢出7.3.1 棧?！纠纠?.9_h】鏈棧的結(jié)點類模板：鏈棧的結(jié)點類模板： templateclass Node /鏈棧結(jié)點類鏈棧結(jié)點類模板模板T info;Node *link;public:Node(T data=0,Node *next=NULL)info=data;link=next;friend class Stack;top 鏈棧7.3.1 棧棧鏈棧類模板鏈

59、棧類模板(無頭結(jié)點鏈表無頭結(jié)點鏈表)：templateclass Stack /鏈棧類模板鏈棧類模板Node *top; /棧頂指針棧頂指針public:Stack()top=NULL;Stack(); /析構(gòu)函數(shù)析構(gòu)函數(shù)void Push(const T &data); /壓棧壓棧T Pop(); /彈出彈出T GetTop(); /取棧頂元素取棧頂元素void MakeEmpty(); /清空棧清空棧bool IsEmpty()return top=NULL;7.3.2 棧的運用選讀棧的運用選讀順序棧和鏈棧邏輯功能是一樣，雖然這里兩個棧順序棧和鏈棧邏輯功能是一樣，雖然這里兩個棧模板

60、的成員函數(shù)功能選擇稍有出入，由于順序?？梢阅０宓某蓡T函數(shù)功能選擇稍有出入，由于順序?？梢噪S機訪問其中的元素，而鏈棧只能順序訪問，但邏輯隨機訪問其中的元素，而鏈棧只能順序訪問，但邏輯上完全可以做到一樣物理構(gòu)造不同。順序棧必需上完全可以做到一樣物理構(gòu)造不同。順序棧必需先開一定大小內(nèi)存空間，執(zhí)行起來簡單，速度快，能先開一定大小內(nèi)存空間，執(zhí)行起來簡單，速度快，能夠溢出。鏈棧內(nèi)存空間隨用隨開，不會溢出，但執(zhí)行夠溢出。鏈棧內(nèi)存空間隨用隨開，不會溢出，但執(zhí)行復(fù)雜不斷地動態(tài)分配，速度慢。復(fù)雜不斷地動態(tài)分配，速度慢。 順序棧和鏈棧比較：順序棧和鏈棧比較：7.3.2 棧的運用選讀棧的運用選讀 ?？捎糜诒磉_式的計算?，F(xiàn)思索最簡單的棧可用于表達式的計算?，F(xiàn)思索最簡單的+、-、*、/四個運算符和終