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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、/二級(jí)指針二級(jí)指針cp=new float 1 30 20;bp=new float 30 20;兩個(gè)數(shù)組都是由兩個(gè)數(shù)組都是由600個(gè)浮點(diǎn)數(shù)組成，前者是個(gè)浮點(diǎn)數(shù)組成，前者是只需一個(gè)元素的三維數(shù)組，每個(gè)元素為只需一個(gè)元素的三維數(shù)組，每個(gè)元素為30行行20列的二維數(shù)組，而另一個(gè)是有列的二維數(shù)組，而另一個(gè)是有30個(gè)元個(gè)元素的二維數(shù)組，每個(gè)元素為素的二維數(shù)組，每個(gè)元素為20個(gè)元素的一個(gè)元素的一維數(shù)組。維數(shù)組。刪除這兩個(gè)動(dòng)態(tài)數(shù)組可用下式：刪除這兩個(gè)動(dòng)態(tài)數(shù)組可用下式：delete cp; /刪除釋放三維數(shù)組刪除釋放三維數(shù)組delete bp; /刪除釋放二維數(shù)組刪除釋放二維數(shù)組【例【例7.2】 動(dòng)態(tài)創(chuàng)建和

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

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

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

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

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

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

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

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

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

25、分配一個(gè)自在存儲(chǔ)區(qū)對(duì)分配一個(gè)自在存儲(chǔ)區(qū)對(duì)象，最后用象，最后用obj1的自在存儲(chǔ)區(qū)對(duì)象復(fù)的自在存儲(chǔ)區(qū)對(duì)象復(fù)制制obj2的自在存儲(chǔ)區(qū)對(duì)象。的自在存儲(chǔ)區(qū)對(duì)象。 obj1obj27.1.3淺復(fù)制與深復(fù)制淺復(fù)制與深復(fù)制【例【例7.4】定義復(fù)制構(gòu)造函數(shù)】定義復(fù)制構(gòu)造函數(shù) copy structor和復(fù)制賦值操和復(fù)制賦值操作符作符copy Assignment Operator實(shí)現(xiàn)深復(fù)制。實(shí)現(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ù)制賦值操作符操作符檢驗(yàn)主函數(shù)和運(yùn)轉(zhuǎn)結(jié)果檢驗(yàn)主函數(shù)和運(yùn)轉(zhuǎn)結(jié)果7.1.3淺復(fù)制與深復(fù)制淺復(fù)制與深復(fù)制 提示：提示： 自在存儲(chǔ)區(qū)內(nèi)存是最常見的需求自定義復(fù)制構(gòu)自在存儲(chǔ)區(qū)內(nèi)存是最常見的需求自定義復(fù)制構(gòu)造函數(shù)的資源，但不是獨(dú)一的，還有翻開文件等也造函數(shù)的資源，但不是獨(dú)一的，還有翻開文件等也需求自定義復(fù)制構(gòu)造函數(shù)。需求自定

27、義復(fù)制構(gòu)造函數(shù)。 假設(shè)類對(duì)象需求動(dòng)態(tài)分配資源應(yīng)該由構(gòu)造函假設(shè)類對(duì)象需求動(dòng)態(tài)分配資源應(yīng)該由構(gòu)造函數(shù)完成，而釋放資源由析構(gòu)函數(shù)完成，這時(shí)類也需數(shù)完成，而釋放資源由析構(gòu)函數(shù)完成，這時(shí)類也需求一個(gè)自定義的復(fù)制構(gòu)造函數(shù)，實(shí)現(xiàn)對(duì)象的深復(fù)制。求一個(gè)自定義的復(fù)制構(gòu)造函數(shù)，實(shí)現(xiàn)對(duì)象的深復(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ù)，甚至有好幾個(gè)是動(dòng)態(tài)建立有很多其他數(shù)據(jù)，甚至有好幾個(gè)是動(dòng)態(tài)建立的的C C字符串，深復(fù)制是不是太復(fù)雜了？假設(shè)字符串

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

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

30、類模板就是典型的例子。這樣的類對(duì)象，作為另一個(gè)類的型的例子。這樣的類對(duì)象，作為另一個(gè)類的成員對(duì)象運(yùn)用時(shí)，就不會(huì)出任何問(wèn)題。這闡成員對(duì)象運(yùn)用時(shí)，就不會(huì)出任何問(wèn)題。這闡明聚合實(shí)現(xiàn)了完善的封裝。明聚合實(shí)現(xiàn)了完善的封裝。 7.2 鏈表與鏈表的根本操作鏈表與鏈表的根本操作 線性表是最簡(jiǎn)單，最常用的一種數(shù)據(jù)構(gòu)線性表是最簡(jiǎn)單，最常用的一種數(shù)據(jù)構(gòu)造。線性表的邏輯構(gòu)造是造。線性表的邏輯構(gòu)造是n n個(gè)數(shù)據(jù)元素的有個(gè)數(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： 每個(gè)數(shù)據(jù)元素占用一個(gè)節(jié)點(diǎn)每個(gè)數(shù)據(jù)元素占用一個(gè)節(jié)點(diǎn)Node。一個(gè)節(jié)點(diǎn)包含兩個(gè)域，一個(gè)域存放數(shù)據(jù)元素一個(gè)節(jié)點(diǎn)包含兩個(gè)域，一個(gè)域存放數(shù)據(jù)元素info，其數(shù)據(jù)類型由運(yùn)用問(wèn)題決議；另一個(gè)存，其數(shù)據(jù)類型由運(yùn)用問(wèn)題決議；另一個(gè)存放指向該鏈表中下一個(gè)節(jié)點(diǎn)的指針?lè)胖赶蛟撴湵碇邢乱粋€(gè)節(jié)點(diǎn)的指針link。節(jié)點(diǎn)定義如下：節(jié)點(diǎn)定義如下： 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)過(guò)指針援用本身這種類型的構(gòu)造。但構(gòu)呵斥員決不能是構(gòu)經(jīng)過(guò)指針援用本身這種類型的構(gòu)造。但構(gòu)呵斥員決不能是構(gòu)造本身類型，即構(gòu)造不能本人定義本人，這會(huì)導(dǎo)致一個(gè)無(wú)窮造本身類型，即構(gòu)造不能本人定義本人，這會(huì)導(dǎo)致一個(gè)無(wú)窮遞歸的定義。遞歸的定義。 7.2.1 單鏈表根本算法單鏈表根本算法單鏈表的第一個(gè)結(jié)點(diǎn)的地址可經(jīng)過(guò)鏈表的表頭指針單鏈表的第一個(gè)結(jié)點(diǎn)的地址可經(jīng)過(guò)鏈表的表頭指針head找找到，

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

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

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

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

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é)點(diǎn)結(jié)點(diǎn) tail=head;tail=head;while(cindata)while(cindata) / /回車終了回車終了 p=new(no

38、de);p=new(node);/每輸入一個(gè)數(shù)懇求一個(gè)結(jié)點(diǎn)每輸入一個(gè)數(shù)懇求一個(gè)結(jié)點(diǎn)p-info=data; /p-info=data; /添入數(shù)據(jù)添入數(shù)據(jù)tail-link= p; /tail-link= p; /新結(jié)點(diǎn)接新結(jié)點(diǎn)接到鏈尾到鏈尾 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é)點(diǎn)頭結(jié)點(diǎn) head-link=NULL; head-link=NULL; while(cindata) while(cindata) / /建立的總是第一個(gè)結(jié)點(diǎn)建立的總是第一個(gè)結(jié)點(diǎn) p=new node; p=new node; p-info=data; p-info=data; p-link= head-l

40、ink ; p-link= head-link ;/新結(jié)點(diǎn)放在原鏈表前方新結(jié)點(diǎn)放在原鏈表前方 head-link=p;head-link=p; / /頭結(jié)點(diǎn)放新結(jié)點(diǎn)之前頭結(jié)點(diǎn)放新結(jié)點(diǎn)之前 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é)點(diǎn)。，指向鏈表中找到的結(jié)點(diǎn)。4. 4. 在單鏈表的在單鏈表的p p節(jié)點(diǎn)后插入：節(jié)點(diǎn)后插入：留意只需一種情況。留意只需一種情況。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é)點(diǎn)刪除單鏈表節(jié)點(diǎn)* *p p后面節(jié)點(diǎn)：后面節(jié)點(diǎn)：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é)點(diǎn)移入另一個(gè)鏈中，那么可將假設(shè)要把該節(jié)點(diǎn)移入另

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

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

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

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

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

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ù)： 在本例中沒(méi)有給出在本例中沒(méi)有給出Node類的復(fù)制構(gòu)造函數(shù)，并非類的復(fù)制構(gòu)造函數(shù)，并非可以運(yùn)用默許的復(fù)制構(gòu)造函數(shù)，而是避開了一切運(yùn)用可以運(yùn)用默許的復(fù)制構(gòu)造函數(shù)，而是避開了一切運(yùn)用它的情況，本例中函數(shù)的參數(shù)和前往值僅運(yùn)用指向它的情況，

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

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

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

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

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

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

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

56、 *elements; /動(dòng)態(tài)建立的元素動(dòng)態(tài)建立的元素 int maxSize; /棧最大包容的元素個(gè)數(shù)棧最大包容的元素個(gè)數(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; /留意先進(jìn)后出留意先進(jìn)后出coutendl;istack.Pop(); /下溢出下溢出7.3.1 棧?！纠纠?.9_h】鏈棧的結(jié)點(diǎn)類模板：鏈棧的結(jié)點(diǎn)類模板： templateclass Node /鏈棧結(jié)點(diǎn)類鏈棧結(jié)點(diǎn)類模板模板T info;Node *link;public:Node(T data=0,Node *next=NULL)info=data;link=next;friend class Stack;top 鏈棧7.3.1 棧棧鏈棧類模板鏈

59、棧類模板(無(wú)頭結(jié)點(diǎn)鏈表無(wú)頭結(jié)點(diǎn)鏈表)：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 棧的運(yùn)用選讀棧的運(yùn)用選讀順序棧和鏈棧邏輯功能是一樣，雖然這里兩個(gè)棧順序棧和鏈棧邏輯功能是一樣，雖然這里兩個(gè)棧模板

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