第七章+動(dòng)態(tài)內(nèi)存分配與數(shù)據(jù)結(jié)構(gòu)

1、C+程序設(shè)計(jì) 第七章 動(dòng)態(tài)內(nèi)存分配第七章 動(dòng)態(tài)內(nèi)存分配本章首先介紹程序運(yùn)行時(shí)動(dòng)態(tài)內(nèi)存分配（Dynamic Memory Allocation）的概念與方法。到目前為止，教材中介紹的程序設(shè)計(jì)方法，變量和對(duì)象在內(nèi)存中的分配都是編譯器在編譯程序時(shí)安排好了的，這帶來(lái)了極大的不便，如數(shù)組必須大開(kāi)小用，指針必須指向一個(gè)已經(jīng)存在的變量或?qū)ο?。?dòng)態(tài)內(nèi)存分配解決了這個(gè)問(wèn)題。 本章將進(jìn)一步討論復(fù)制構(gòu)造函數(shù)；還要學(xué)習(xí)更多有關(guān)數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)，包括棧，隊(duì)，二叉樹(shù)等的基本算法和應(yīng)用。模板是標(biāo)準(zhǔn)C+實(shí)現(xiàn)代碼復(fù)用的有力工具，特別是對(duì)有關(guān)數(shù)據(jù)結(jié)構(gòu)的算法。本章繼續(xù)使用模板介紹算法。7.1 自由存儲(chǔ)區(qū)內(nèi)存管理C/C+定義了4個(gè)

2、內(nèi)存區(qū)間：代碼區(qū)，存放程序代碼；全局變量與靜態(tài)變量區(qū)，存放全局的和靜態(tài)的變量與對(duì)象；局部變量區(qū)即棧（Stack）區(qū)，存放局部變量；自由存儲(chǔ)（Free Store）區(qū)，亦稱堆（Heap），將在本章介紹。通常定義變量（或?qū)ο螅?，無(wú)論是局部變量（對(duì)象）或全局變量（對(duì)象），也無(wú)論它是什么類型，編譯器在編譯時(shí)都可以根據(jù)該變量（或?qū)ο螅┑念愋椭浪鑳?nèi)存空間的大小，從而系統(tǒng)在適當(dāng)?shù)臅r(shí)候?yàn)樗麄兎峙浯_定的內(nèi)存空間。全局變量在程序開(kāi)始運(yùn)行前在全局區(qū)分配。局部變量在程序運(yùn)行到該局部域時(shí)在棧區(qū)分配，但怎樣分配是在編譯時(shí)就已經(jīng)確定。尤其是數(shù)組，在第六章中介紹的表的基本操作和查找與排序算法，都為數(shù)組開(kāi)了100個(gè)元素。如

3、果使用50個(gè)，則浪費(fèi)50個(gè)；如果使用150個(gè)，則后50個(gè)元素就占用了分配給其他變量的內(nèi)存，造成嚴(yán)重的錯(cuò)誤，系統(tǒng)還不知道，編譯器也不會(huì)報(bào)錯(cuò)（不對(duì)數(shù)組邊界做檢查），只可能在運(yùn)行時(shí)報(bào)“執(zhí)行非法操作，程序?qū)㈥P(guān)閉”。這種內(nèi)存分配稱為靜態(tài)存儲(chǔ)分配（Static Memory Allocation）。有些操作對(duì)象只有在程序運(yùn)行時(shí)才能確定，編譯器在編譯時(shí)就無(wú)法為他們預(yù)定內(nèi)存空間，只能在程序運(yùn)行時(shí)，系統(tǒng)根據(jù)運(yùn)行時(shí)的要求進(jìn)行內(nèi)存分配，這種方法稱為動(dòng)態(tài)存儲(chǔ)分配。系統(tǒng)在內(nèi)存安排了一個(gè)自由存儲(chǔ)區(qū)（Free Store）即堆（Heap），所有動(dòng)態(tài)存儲(chǔ)分配都在這個(gè)自由存儲(chǔ)區(qū)中進(jìn)行。7.1.1 自由存儲(chǔ)區(qū)內(nèi)存的分配與釋放當(dāng)程

4、序運(yùn)行時(shí)遇到一個(gè)需要?jiǎng)討B(tài)分配的變量或?qū)ο髸r(shí)，必須向系統(tǒng)申請(qǐng)取得自由存儲(chǔ)區(qū)中一塊所需大小的內(nèi)存空間，用于存儲(chǔ)該變量或?qū)ο?。?dāng)不再使用該變量或?qū)ο髸r(shí)，也就是它的生命結(jié)束時(shí)，要顯式釋放它所占用的內(nèi)存空間，這樣系統(tǒng)就能對(duì)該自由存儲(chǔ)區(qū)空間再次進(jìn)行分配，做到重復(fù)使用有限的資源。在C+中，申請(qǐng)和釋放自由存儲(chǔ)區(qū)中分配的內(nèi)存空間，分別使用new和delete的兩個(gè)運(yùn)算符來(lái)完成，其使用的格式如下：指針變量名=new 類型名(初始化式);delete 指針名;new運(yùn)算符返回的是一個(gè)指向所分配類型變量（對(duì)象）的指針。對(duì)所創(chuàng)建的變量或?qū)ο?，都是通過(guò)該指針來(lái)間接操作的，而動(dòng)態(tài)創(chuàng)建的對(duì)象本身沒(méi)有名字。靜態(tài)定義變量和對(duì)象時(shí)

5、要用標(biāo)識(shí)符命名，稱命名對(duì)象，而動(dòng)態(tài)的稱無(wú)名對(duì)象(請(qǐng)注意與棧區(qū)中的臨時(shí)對(duì)象的區(qū)別，兩者完全不同：生命期不同、操作方法不同，臨時(shí)變量對(duì)程序員是透明的)。自由存儲(chǔ)區(qū)是不會(huì)自動(dòng)在分配時(shí)做初始化的（包括清零），所以必須用初始化式(Initializer)來(lái)顯式初始化。new表達(dá)式的操作序列如下：在自由存儲(chǔ)區(qū)中為對(duì)象或變量分配內(nèi)存，然后用括號(hào)中的值初始化該對(duì)象或變量。new表達(dá)式是調(diào)用庫(kù)操作符new()完成該操作序列的。例如： int *pi=new int(0);pi現(xiàn)在所指向的變量的內(nèi)存空間是由庫(kù)操作符new()分配的，位于程序的自由存儲(chǔ)區(qū)中，并且該對(duì)象未命名。該式給出了怎樣為一個(gè)指針創(chuàng)建一個(gè)對(duì)象或變

6、量的過(guò)程。當(dāng)pi所指向的對(duì)象或變量的生命周期結(jié)束時(shí)，必須釋放pi所指向的目標(biāo)占用的內(nèi)存空間：delete pi;注意這時(shí)釋放了pi所指的目標(biāo)的內(nèi)存空間，也就是撤銷了該目標(biāo)，稱動(dòng)態(tài)內(nèi)存釋放（Dynamic Memory Deallocation），但指針pi本身并沒(méi)有撤銷，它自己仍然存在，該指針本身所占內(nèi)存空間并未釋放。對(duì)于數(shù)組進(jìn)行動(dòng)態(tài)分配和撤銷的格式為：指針變量名=new 類型名下標(biāo)表達(dá)式;delete 指向該數(shù)組的指針變量名;兩式中的方括號(hào)是非常重要的，兩者必須配對(duì)使用，如果delete語(yǔ)句中少了方括號(hào)，因編譯器認(rèn)為該指針是指向數(shù)組第一個(gè)元素的指針，會(huì)產(chǎn)生回收不徹底的問(wèn)題（只回收了第一個(gè)元素

7、所占空間），加了方括號(hào)后就轉(zhuǎn)化為指向數(shù)組整體的指針，回收整個(gè)數(shù)組所占全部?jī)?nèi)存空間。delete 的方括號(hào)中不需要填數(shù)組元素?cái)?shù)，系統(tǒng)自知。即使寫(xiě)了，編譯器也忽略。請(qǐng)注意“下標(biāo)表達(dá)式”不是常量表達(dá)式，即它的值不必在編譯時(shí)確定，可以在運(yùn)行時(shí)確定，參見(jiàn)下例?！纠?.1】動(dòng)態(tài)數(shù)組的建立與撤銷。#include <iostream>#include <cstring>using namespace std;int main()int n;char *pc;cout<<"請(qǐng)輸入動(dòng)態(tài)數(shù)組的元素個(gè)數(shù)"<<endl;cin>>n;pc

8、=new charn; /申請(qǐng)包含25個(gè)字符（可裝12個(gè)漢字和一個(gè)結(jié)束符）元素的內(nèi)存空間strcpy(pc,"自由存儲(chǔ)區(qū)內(nèi)存的動(dòng)態(tài)分配");cout<<pc<<endl;delete pc; / 撤銷并釋放pc所指向的n個(gè)字符的內(nèi)存空間return 0 ;標(biāo)準(zhǔn)字符串類string就是采用動(dòng)態(tài)建立數(shù)組的方式解決數(shù)組溢出的問(wèn)題的，本例所做的動(dòng)態(tài)內(nèi)存分配與釋放，在string類對(duì)象中都是自動(dòng)完成的，在程序中不需要也不允許再顯式地為string進(jìn)行動(dòng)態(tài)內(nèi)存的分配與釋放。在本例中應(yīng)注意3個(gè)問(wèn)題：首先，變量n在編譯時(shí)沒(méi)有確定的值，而是在運(yùn)行中輸入，按運(yùn)行時(shí)所需大

9、小分配自由存儲(chǔ)區(qū)空間，這一點(diǎn)是動(dòng)態(tài)分配的優(yōu)點(diǎn)，可克服數(shù)組“大開(kāi)小用”的弊端。在第六章中有關(guān)表、排序與查找中的算法，若用動(dòng)態(tài)數(shù)組，則通用性更佳。delete pc是將n個(gè)字符的空間釋放，而用delete pc則只釋放了一個(gè)字符的空間。其次如果有一個(gè)char *pc1，令pc1=pc，同樣可用delete pc1來(lái)釋放該空間。由此可知，空間的大小是保存在分配空間的首地址相關(guān)的地方，盡管C+不對(duì)數(shù)組作邊界檢查，但在自由存儲(chǔ)區(qū)空間分配時(shí)，為數(shù)組分配的內(nèi)存空間的大小是紀(jì)錄在案的。第三，沒(méi)有對(duì)應(yīng)的初始化式（Initializer），不可對(duì)數(shù)組初始化。這與靜態(tài)數(shù)組不同。下面探討如何對(duì)多維數(shù)組進(jìn)行動(dòng)態(tài)分配。（

10、選讀）格式如下：new 類型名下標(biāo)表達(dá)式1 下標(biāo)表達(dá)式2;例如下面建立一個(gè)動(dòng)態(tài)三維數(shù)組float (*cp)3020 ; /指向一個(gè)30行20列數(shù)組整體的指針cp=new float 15 30 20; /建立一個(gè)由15個(gè)30*20數(shù)組組成的數(shù)組注意cp等效于一個(gè)三維的數(shù)組名，但它沒(méi)有指出其邊界，即最高維的元素?cái)?shù)量，就像指向字符的指針即等效一個(gè)字符串一樣。這與數(shù)組的嵌套定義相一致。不要把指向字符的指針，說(shuō)成指向字符串的指針。請(qǐng)?jiān)俦容^：float (*cp) 30 20; /三級(jí)指針float (*bp) 20; /二級(jí)指針cp=new float 1 30 20;bp=new float 30

11、 20;兩個(gè)數(shù)組都是由600個(gè)浮點(diǎn)數(shù)組成，但一個(gè)是只有一個(gè)元素的三維數(shù)組，每個(gè)元素為30行20列的二維數(shù)組，而另一個(gè)是有30個(gè)元素的二維數(shù)組，每個(gè)元素為20個(gè)元素的一維數(shù)組。如果畫(huà)出內(nèi)存安排示意圖，兩者是一樣，但它們的概念卻完全不同。刪除這兩個(gè)動(dòng)態(tài)數(shù)組可用下式：delete cp; /刪除（釋放）三維數(shù)組delete bp; /刪除（釋放）二維數(shù)組多維數(shù)組也可以用指針數(shù)組方式等效建立。（選讀）【例7.2】 動(dòng)態(tài)創(chuàng)建和刪除一個(gè)m*n個(gè)元素的數(shù)組。采用指針數(shù)組方式來(lái)完成二維數(shù)組的動(dòng)態(tài)創(chuàng)建，該方法同樣可用于建立三維數(shù)組。#include <iostream>#include<cst

12、dlib>using namespace std;void display(double *);void de_allocate(double *);int m=4; /行數(shù)int n=6; /列數(shù)int main()int i,j;double *data;data = new double*m; /建立指向組成二維數(shù)組各行的指針數(shù)組if (data)=0)cout<<"Could not allocate. Bye ."return -1;for(j=0;j<m;j+)dataj = new doublen; /建立二維數(shù)組各行if (dataj

13、 = 0)cout << "Could not allocate. Bye ."return -1;for (i=0;i<m;i+)for (j=0;j<n;j+)dataij=i*n+j;/數(shù)組元素賦值display(data);de_allocate(data);return 0;void display(double *data)int i,j;for (i=0;i<m;i+)for (j=0;j<n;j+) cout<<dataij<<"t"cout << endl;void

14、 de_allocate(double *data)int i;for (i=0;i<m;i+) delete datai; /注意撤銷次序，與設(shè)置相反delete data;注意，建立數(shù)組時(shí)先建立行后建立列，而撤銷時(shí)，先撤銷列后撤銷行。正如第5章所述，指針可以直接對(duì)內(nèi)存尋址，所以指針的操作非常靈活和高效，但是使用不當(dāng)，又會(huì)造成難以診斷的錯(cuò)誤，甚至導(dǎo)致死機(jī)。下面繼續(xù)討論指針使用的新問(wèn)題：(1) 動(dòng)態(tài)分配失敗。動(dòng)態(tài)創(chuàng)建是在自由存儲(chǔ)區(qū)中進(jìn)行，但是自由存儲(chǔ)區(qū)資源有限，動(dòng)態(tài)分配可能失敗，尤其在動(dòng)態(tài)創(chuàng)建一個(gè)大的數(shù)組時(shí)。這時(shí)new操作符返回一個(gè)空指針（NULL），表示發(fā)生了異常，自由存儲(chǔ)區(qū)資源不足，

15、分配失敗。在例7.1中沒(méi)有去檢測(cè)是否創(chuàng)建成功，這可能會(huì)在使用中出問(wèn)題。(2) 指針刪除與自由存儲(chǔ)區(qū)空間釋放。刪除一個(gè)指針p（delete p;）實(shí)際意思是刪除了p所指的目標(biāo)（變量或?qū)ο蟮龋尫帕四繕?biāo)所占的自由存儲(chǔ)區(qū)空間，而不是刪除本身，釋放自由存儲(chǔ)區(qū)空間后，成了空懸指針（指針未指向一個(gè)有效地址，稱為空懸指針（Dangling Pointer）。空懸指針是程序錯(cuò)誤的一個(gè)根源）。建議這時(shí)將置空（NULL）。注意，空間釋放后，并不清空，只要未被重新利用，原來(lái)數(shù)據(jù)并沒(méi)有消失。delete表達(dá)式只能應(yīng)用于指向自由存儲(chǔ)區(qū)中由new表達(dá)式分配的內(nèi)存空間的指針。如果delete表達(dá)式作用于未指向自由存儲(chǔ)區(qū)有

16、效內(nèi)存的指針，會(huì)使程序運(yùn)行時(shí)出現(xiàn)未定義的行為，這是不允許的。 (3) 內(nèi)存泄漏（Memory Leak）和重復(fù)釋放。new與delete 是配對(duì)使用的， 只能由delete釋放自由存儲(chǔ)區(qū)空間。如果new返回的指針值丟失，則所分配的自由存儲(chǔ)區(qū)空間無(wú)法回收，稱內(nèi)存泄漏。程序執(zhí)行結(jié)束后，這部分內(nèi)存空間將從系統(tǒng)中丟失，必須重新啟動(dòng)計(jì)算機(jī)才能找回。所以必須妥善保存new返回的指針，以保證不發(fā)生內(nèi)存泄漏。如果對(duì)同一空間重復(fù)釋放也是危險(xiǎn)的，除了可能使程序運(yùn)行時(shí)出現(xiàn)未定義的行為外，第一次釋放后，該空間可能已分配給新的對(duì)象，再次釋放，會(huì)使新的對(duì)象丟失。所以必須保證不會(huì)重復(fù)釋放自由存儲(chǔ)區(qū)內(nèi)存空間。釋放了指針目標(biāo)所

17、占的自由存儲(chǔ)區(qū)空間后，應(yīng)及時(shí)把該指針清空。delete表達(dá)式作用于空指針時(shí)C+保證不會(huì)調(diào)用庫(kù)操作符delete()。 (4) 動(dòng)態(tài)分配的變量或?qū)ο蟮纳?。命名?duì)象的生命期由它的作用域決定，但動(dòng)態(tài)分配的無(wú)名對(duì)象，其生命期并不依賴于建立它的作用域，比如在函數(shù)中建立的動(dòng)態(tài)對(duì)象在函數(shù)返回后仍可使用。但必須記住釋放該對(duì)象所占自由存儲(chǔ)區(qū)空間，并只能釋放一次，在函數(shù)內(nèi)建立，而在函數(shù)外釋放是一件很容易失控的事，往往會(huì)出錯(cuò)。(5) new()和delete()是可以重載的，它們都是類的靜態(tài)成員函數(shù)。程序員無(wú)需顯式聲明它為靜態(tài)的，系統(tǒng)自動(dòng)定義為靜態(tài)的。本教材不討論new()和delete()的重載。未重載時(shí)，調(diào)

18、用全局庫(kù)操作符new()。7.1.2自由存儲(chǔ)區(qū)對(duì)象與構(gòu)造函數(shù)前一小節(jié)介紹了C+的關(guān)鍵字new和delete怎樣分配和釋放自由存儲(chǔ)區(qū)空間，實(shí)際上通過(guò)new建立的對(duì)象要調(diào)用構(gòu)造函數(shù)，通過(guò)delete刪除對(duì)象也要調(diào)用析構(gòu)函數(shù)。請(qǐng)看下面的程序段，其中CGoods類（Class）已在第5章中定義：CGoods *pc;pc=new CGoods; /分配自由存儲(chǔ)區(qū)空間，并構(gòu)造一個(gè)無(wú)名的CGoods對(duì)象.delete pc; /先析構(gòu)，然后將內(nèi)存空間返回給自由存儲(chǔ)區(qū)正如上節(jié)指出自由存儲(chǔ)區(qū)對(duì)象的生命期并不依賴于建立它的作用域，所以除非程序結(jié)束，自由存儲(chǔ)區(qū)對(duì)象（無(wú)名對(duì)象）的生命期不會(huì)結(jié)束，并且需要顯式地用de

19、lete語(yǔ)句析構(gòu)自由存儲(chǔ)區(qū)對(duì)象和釋放所占用的內(nèi)存。上例在執(zhí)行delete語(yǔ)句時(shí)，C+自動(dòng)調(diào)用商品類的析構(gòu)函數(shù)。正因?yàn)闃?gòu)造函數(shù)可以有參數(shù)，所以new后面類類型也可以有參數(shù)。這些參數(shù)即構(gòu)造函數(shù)的參數(shù)。但對(duì)創(chuàng)建數(shù)組，則沒(méi)有參數(shù)，只能調(diào)用默認(rèn)的構(gòu)造函數(shù)。【例7.3】演示自由存儲(chǔ)區(qū)對(duì)象分配和釋放。#include<iostream>#include <string>using namespace std;class CGoodsstring Name;int Amount;float Price;float Total_value;public:CGoods()cout<&

20、lt;"調(diào)用默認(rèn)構(gòu)造函數(shù)"<<endl;CGoods(string name,int amount ,float price)cout<<"調(diào)用三參數(shù)構(gòu)造函數(shù)"<<endl;Name=name; Amount=amount;Price=price; Total_value=price*amount;CGoods() cout<<"調(diào)用析構(gòu)函數(shù)"<<endl;int main()int n;CGoods *pc,*pc1,*pc2;pc=new CGoods("夏利2

21、000",10,118000); /調(diào)用三參數(shù)構(gòu)造函數(shù)pc1=new CGoods(); /調(diào)用默認(rèn)構(gòu)造函數(shù)cout<<"輸入商品類數(shù)組元素?cái)?shù)"<<endl;cin>>n;pc2=new CGoodsn; /動(dòng)態(tài)建立數(shù)組，調(diào)用默認(rèn)構(gòu)造函數(shù)，共調(diào)n次delete pc;delete pc1;delete pc2;return 0;最后再次強(qiáng)調(diào)：由自由存儲(chǔ)區(qū)創(chuàng)建對(duì)象數(shù)組，只能調(diào)用默認(rèn)的構(gòu)造函數(shù)，不能調(diào)用其他任何構(gòu)造函數(shù)。如果沒(méi)有默認(rèn)的構(gòu)造函數(shù)，則不能創(chuàng)建對(duì)象數(shù)組。7.1.3淺復(fù)制與深復(fù)制在第四章中介紹的按成員語(yǔ)義支持的默認(rèn)復(fù)制構(gòu)造函

22、數(shù)，可以用一個(gè)類對(duì)象初始化另一個(gè)類對(duì)象，稱為默認(rèn)的按成員復(fù)制，而不是對(duì)整個(gè)類對(duì)象的按位復(fù)制。一般情況下這是沒(méi)有問(wèn)題的。但是如果類中有一個(gè)數(shù)據(jù)成員為指針，該類的一個(gè)對(duì)象obj1中的這個(gè)指針p，指向了動(dòng)態(tài)分配的一個(gè)自由存儲(chǔ)區(qū)對(duì)象，（如圖7.1(a)所示），如果用obj1按成員復(fù)制了一個(gè)對(duì)象obj2，這時(shí)obj2.p也指向同一個(gè)自由存儲(chǔ)區(qū)對(duì)象（如圖7.1(b)所示）。這稱為淺復(fù)制。這帶來(lái)了兩個(gè)問(wèn)題：首先，正常工作時(shí)修改obj1的自由存儲(chǔ)區(qū)對(duì)象，obj2也變了，這是絕大多數(shù)情況下，不可接受的。第二，當(dāng)析構(gòu)時(shí)，如用默認(rèn)的析構(gòu)函數(shù)，則動(dòng)態(tài)分配的自由存儲(chǔ)區(qū)對(duì)象不能回收，必須使用自定義析構(gòu)函數(shù)釋放內(nèi)存，該析構(gòu)

23、函數(shù)中包含釋放自由存儲(chǔ)區(qū)對(duì)象的delete語(yǔ)句。進(jìn)一步分析析構(gòu)過(guò)程，如果先析構(gòu)obj1，自由存儲(chǔ)區(qū)已經(jīng)釋放，結(jié)果obj2缺了一個(gè)自由存儲(chǔ)區(qū)對(duì)象，不能正常使用。在析構(gòu)obj2時(shí)又出現(xiàn)二次釋放的問(wèn)題，再次造成錯(cuò)誤。解決辦法是重新定義復(fù)制的構(gòu)造函數(shù)，給每個(gè)對(duì)象各自分配一個(gè)獨(dú)立的自由存儲(chǔ)區(qū)對(duì)象，如圖7.2所示，稱深復(fù)制。這時(shí)先復(fù)制對(duì)象主體，再為obj2分配一個(gè)自由存儲(chǔ)區(qū)對(duì)象，最后用obj1的自由存儲(chǔ)區(qū)對(duì)象復(fù)制obj2的自由存儲(chǔ)區(qū)對(duì)象。共分三步完成。 obj1 obj1P自由存儲(chǔ)區(qū)對(duì)象自由存儲(chǔ)區(qū)對(duì)象PP obj2 (a)復(fù)制前 (b)復(fù)制后 圖7.1 淺復(fù)制自由存儲(chǔ)區(qū)對(duì)象PP自由存儲(chǔ)區(qū)對(duì)象 Obj1 O

24、bj2 圖7.2 深復(fù)制【例7.4】類含有動(dòng)態(tài)生成的數(shù)據(jù)成員，必須自定義析構(gòu)函數(shù)以釋放動(dòng)態(tài)分配的內(nèi)存，自定義復(fù)制構(gòu)造函數(shù)（Copy Structor）和復(fù)制賦值操作符（Copy Assignment Operator）實(shí)現(xiàn)深復(fù)制。#include <iostream>#include <cstring>using namespace std;class studentchar *pName; /為了演示深復(fù)制，不用string類public:student();student(char *pname);student(student &s);student();

25、student & operator=(student &s);student:student()cout<<"Constructor"pName=NULL;cout<<"默認(rèn)"<<endl;student:student(char *pname)cout<<"Constructor"if(pName=new charstrlen(pname)+1) strcpy(pName,pname);/加一不可少，否則串結(jié)束符沖了其他信息，析構(gòu)會(huì)出錯(cuò)！cout<<pNa

26、me<<endl;student:student(student &s)cout<<"Copy Constructor"if(s.pName)if(pName=new charstrlen(s.pName)+1) strcpy(pName,s.pName);cout<<pName<<endl;else pName=NULL;student:student() /因有動(dòng)態(tài)生成的類成員，析構(gòu)函數(shù)不可用默認(rèn)的析構(gòu)函數(shù)cout<<"Destructor"if(pName) cout<<

27、;pName<<endl;delete pName;student & student:operator=(student &s)cout<<"Copy Assign operator"delete pName; if(s.pName)if(pName=new charstrlen(s.pName)+1) strcpy(pName,s.pName);cout<<pName<<endl;else pName=NULL;return *this;int main(void)student s1("范英明&

28、quot;),s2("沈俊"),s3;student s4=s1;s3=s2;return 0;運(yùn)行結(jié)果為：Constuctor 范英明 /建立S1Constuctor 沈俊 /建立S2Constuctor 默認(rèn) /建立S3Copy Constuctor 范英明 /建立S4Copy Assign Operator 沈俊 /用S2賦值S3Destructor 范英明 /析構(gòu)S4Destructor 沈俊 /析構(gòu)S3Destructor 沈俊 /析構(gòu)S2Destructor 范英明 /析構(gòu)S1自由存儲(chǔ)區(qū)內(nèi)存是最常見(jiàn)的需要自定義復(fù)制構(gòu)造函數(shù)的資源，但不是唯一的，還有打開(kāi)文件等也需

29、要自定義復(fù)制構(gòu)造函數(shù)。如果類對(duì)象需要?jiǎng)討B(tài)分配資源應(yīng)該由構(gòu)造函數(shù)完成，而釋放資源由析構(gòu)函數(shù)完成，這時(shí)類也需要一個(gè)自定義的復(fù)制構(gòu)造函數(shù)，實(shí)現(xiàn)對(duì)象的深復(fù)制。由此可見(jiàn)，構(gòu)造函數(shù)并非僅做初始化工作。標(biāo)準(zhǔn)模板庫(kù)中的sting標(biāo)準(zhǔn)字符串類中存放字符串的容器就是動(dòng)態(tài)數(shù)組，與【例7.4】中動(dòng)態(tài)建立的C風(fēng)格字符串的處理過(guò)程有些類似，但完備得多。再深入地考慮【例7.4】，如果數(shù)據(jù)域還有很多其他數(shù)據(jù)，甚至有好幾個(gè)是動(dòng)態(tài)建立的C字符串，深復(fù)制是不是太復(fù)雜了？如果使用C+標(biāo)準(zhǔn)字符串string作為成員對(duì)象（聚合）是否就不需要考慮深復(fù)制了？的確是這樣的。準(zhǔn)確地說(shuō)，string類的內(nèi)部包含動(dòng)態(tài)建立字符數(shù)組的操作，其復(fù)制構(gòu)造函

30、數(shù)是深復(fù)制。如果在student類中使用string類而不是C字符串，就不要再考慮深復(fù)制問(wèn)題了，student類的構(gòu)造函數(shù)自動(dòng)調(diào)用string類的構(gòu)造函數(shù)實(shí)現(xiàn)深復(fù)制。也就是說(shuō)，動(dòng)態(tài)內(nèi)存分配和深復(fù)制應(yīng)該放在一個(gè)適當(dāng)?shù)膶用嫔?，即一個(gè)更單純的類定義中，如string類。在使用時(shí)，把它作為一個(gè)成員對(duì)象，就像使用string類對(duì)象那樣。最后進(jìn)一步討論類的封裝。封裝的更高境界是在該類對(duì)象中一切都是完備的、自給自足的，不僅有數(shù)據(jù)和對(duì)數(shù)據(jù)的操作，還包括資源的動(dòng)態(tài)安排和釋放。在需要時(shí)可以無(wú)條件地安全使用。標(biāo)準(zhǔn)string類模板就是典型的例子。這樣的類對(duì)象，作為另一個(gè)類的成員對(duì)象使用時(shí)，就不會(huì)出任何問(wèn)題。這表明聚

31、合實(shí)現(xiàn)了完善的封裝。7.2 鏈表與鏈表的基本操作線性表是最簡(jiǎn)單，最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)是n個(gè)數(shù)據(jù)元素的有限序列（a1,a2,an）。實(shí)現(xiàn)線性表的物理結(jié)構(gòu)，前面已經(jīng)學(xué)習(xí)過(guò)順序表，也就是數(shù)組，或者講以數(shù)組為容器，把線性表放入該容器。順序表容器可以靜態(tài)建立，也可以動(dòng)態(tài)建立，動(dòng)態(tài)建立的可以在運(yùn)行時(shí)決定大小，但是它們都做不到用多少空間，就開(kāi)多少空間。其次在順序表中如果要插入一個(gè)元素，就需要把該元素所要插入位置上的元素及其后面所有元素順序后移一個(gè)元素位置；而刪除一個(gè)元素，就要把要?jiǎng)h除的元素其后的所有元素前移一個(gè)元素位置，這也是很不方便的。另一種線性表的物理結(jié)構(gòu)鏈表可以解決這兩個(gè)問(wèn)題。7.2

32、.1 單鏈表基本算法單鏈表（Singly Linked list）也稱線性鏈表。每個(gè)數(shù)據(jù)元素占用一個(gè)結(jié)點(diǎn)（Node）。一個(gè)結(jié)點(diǎn)包含兩個(gè)域，一個(gè)域存放數(shù)據(jù)元素info，其數(shù)據(jù)類型由應(yīng)用問(wèn)題決定，另一個(gè)域存放指向該鏈表中下一個(gè)結(jié)點(diǎn)的指針link。結(jié)點(diǎn)類型可以采用類或結(jié)構(gòu)。采用結(jié)構(gòu)類型，并以整型數(shù)為數(shù)據(jù)域的結(jié)點(diǎn)定義如下：typedef int Datatype; /數(shù)據(jù)為整型struct nodeDatatype info;node *link;這里node和node*的定義出現(xiàn)了嵌套。嚴(yán)格地講，這不符合“先說(shuō)明后引用”的原則。但在C/C+中允許這個(gè)例外，允許結(jié)構(gòu)成員是結(jié)構(gòu)自身的指針類型，并可通過(guò)指

33、針訪問(wèn)與自身同類型的結(jié)構(gòu)變量。但結(jié)構(gòu)成員絕不能是結(jié)構(gòu)自身類型的變量，即結(jié)構(gòu)不能自己定義自己，這會(huì)導(dǎo)致一個(gè)無(wú)窮遞歸的定義。單鏈表的構(gòu)造如圖7.3所示。鏈表最后一個(gè)結(jié)點(diǎn)（鏈尾）的指針域?yàn)榭罩羔槪∟ULL，圖中用表示），表示鏈表結(jié)束。借助結(jié)點(diǎn)的指針域，可以從第一個(gè)結(jié)點(diǎn)開(kāi)始順序遍歷鏈表所有結(jié)點(diǎn)。info0info1info2infon-1 head···········圖7.3 單鏈表結(jié)構(gòu)單鏈表的第1結(jié)點(diǎn)的地址可通過(guò)鏈表的表頭指針head找到，鏈表建立在自由存儲(chǔ)區(qū)中，head在使用中必須妥善保

34、存，千萬(wàn)不可丟失，否則鏈表整個(gè)丟失，內(nèi)存也會(huì)發(fā)生泄漏。實(shí)現(xiàn)單鏈表的插入與刪除不再需要移動(dòng)表中的各元素，只要改變鏈表中結(jié)點(diǎn)指針的值，重新鏈接相關(guān)結(jié)點(diǎn)就完成了。當(dāng)希望在單鏈表中包含數(shù)據(jù)infoi的結(jié)點(diǎn)之前插入一個(gè)包含數(shù)據(jù)infox的新結(jié)點(diǎn)，則插入算法應(yīng)考慮3情況：infoi在第一個(gè)結(jié)點(diǎn)中；或在其它結(jié)點(diǎn)中；第三未找到包含數(shù)據(jù)infoi的結(jié)點(diǎn)，這時(shí)如何處理新結(jié)點(diǎn)則可有不同規(guī)定，如可以放棄插入，但本例指定插在鏈尾結(jié)點(diǎn)之后。對(duì)于第1情況，infoi在第1結(jié)點(diǎn)中，則新結(jié)點(diǎn)將插在鏈?zhǔn)?，如圖7.4所示。newnodeinfoxinfo0info1head·····

35、;········ 圖7.4 插入鏈?zhǔn)资紫刃陆Y(jié)點(diǎn)的link指針指向info0所在結(jié)點(diǎn)，然后，head指向新結(jié)點(diǎn)。插入過(guò)程完成。即：newnode->link=head； /注意：鏈表操作次序非常重要head=newnode；infoi在其它結(jié)點(diǎn)中的情況如圖7.5所示。首先用工作指針p找到指定結(jié)點(diǎn)，而讓指針q跟蹤p指向其前一個(gè)結(jié)點(diǎn)，這樣問(wèn)題轉(zhuǎn)化為新結(jié)點(diǎn)插在q所指結(jié)點(diǎn)之后。插入的第一步是，令新結(jié)點(diǎn)的link指向infoi所在結(jié)點(diǎn)，然后讓infoi-1所在結(jié)點(diǎn)的link指針指向新結(jié)點(diǎn)。即：newnode->l

36、ink=q->link;/該算法實(shí)際為插入infoi-1所在結(jié)點(diǎn)之后的算法q->link=newnode;xinfoxinfoi-1infoipinfoi-1infoinewnodeqpnewnode q 插入前 插入后 圖7.5 插入鏈中插在鏈尾的情況如圖7.6所示。只要工作指針p找到鏈尾，即可鏈在其后：p->link=newnode；newnode->link=NULL;Infon-1infox newnode············p 圖7.6

37、接在鏈尾研究以上算法，插在鏈表第一個(gè)結(jié)點(diǎn)之前與其他結(jié)點(diǎn)之前的算法有所不同。要使算法中沒(méi)有特殊者，可以給每一個(gè)鏈表加上一個(gè)表頭結(jié)點(diǎn)，如圖7.7所示。實(shí)際上，新結(jié)點(diǎn)插在鏈尾仍然有特殊性，但這是指定的處理方法引起的。如算法改為新節(jié)點(diǎn)插在在某一結(jié)點(diǎn)之后則無(wú)任何形式的特殊。headinfo0info1··············infon-1 (a) 非空表 head (b)空表圖7.7 帶表頭結(jié)構(gòu)的鏈表下面分別介紹帶表頭結(jié)構(gòu)的鏈表的鏈表生成算法、鏈表查找算法、插入

38、一個(gè)結(jié)點(diǎn)的算法和刪除一個(gè)結(jié)點(diǎn)的算法。結(jié)點(diǎn)定義不變：typedef int Datatype;info0info1info0info1 tailtailtailp pheadheadhead（a）建立頭結(jié)點(diǎn)（b）新結(jié)點(diǎn)鏈入前（c）鏈入新結(jié)點(diǎn)struct nodeDatatype info;node * link;1. 向后生成鏈表算法：node *createdown()Datatype data;node *head,*tail,*p;head=new node; /建立鏈表頭結(jié)點(diǎn)tail=head; while(cin>>data)/輸入Z(Ctrl_Z)結(jié)束/這時(shí)流關(guān)閉，循環(huán)結(jié)

39、束，參見(jiàn)9.3節(jié)p=new node;/每輸入一個(gè)數(shù)申請(qǐng)一個(gè)結(jié)點(diǎn)p->info=data; /添入數(shù)據(jù)tail->link =p; /新結(jié)點(diǎn)接到鏈尾tail=p; /尾指針到鏈尾 tail->link=NULL;/鏈尾加空指針，表示鏈結(jié)束 return head; /返回頭指針 這里首先建立頭結(jié)點(diǎn)，這時(shí)鏈表的頭指針和尾指針都指向頭結(jié)點(diǎn)（如圖7.8a所示）。 圖7.8 向后生成鏈表以后每輸入一個(gè)數(shù)申請(qǐng)一個(gè)結(jié)點(diǎn)（如圖7.8b所示），并將該結(jié)點(diǎn)鏈到鏈尾（如info0 info1圖7.8c所示）。2. 向前生成鏈表算法（如圖7.9所示）： headnode *createup()no

40、de *head,*p; pDatatype data;head=new node; /建立頭結(jié)點(diǎn) head->link=NULL; （a）新結(jié)點(diǎn)鏈入前while(cin>>data) /建立的總是第一個(gè)結(jié)點(diǎn)info0 info1p=new node; p->info=data; headp->link= head->link ;/新結(jié)點(diǎn)放在原鏈表前面（緊跟頭結(jié)點(diǎn)）head->link=p; /頭結(jié)點(diǎn)放新結(jié)點(diǎn)之前 preturn head; (b）新結(jié)點(diǎn)鏈入后3.鏈表查找算法，按數(shù)據(jù)（關(guān)鍵字）查找：node *traversal(node *head,

41、Datatype data) 圖7.9 向前生成鏈表node *p=head->link; while(p!=NULL&&p->info!=data) p=p->link; return p; /p為NULL則未找到/借助工作指針順序訪問(wèn)鏈表各結(jié)點(diǎn)是鏈表最基礎(chǔ)的算法返回值為指針p，指向鏈表中找到的結(jié)點(diǎn)。4. 在單鏈表的p結(jié)點(diǎn)后插入一個(gè)信息域?yàn)閤的新結(jié)點(diǎn)（注意僅有一種情況）。void insert(node *p,Datatype x)node *q=new node;q->info=x;q->link=p->link;p->link=q

42、;5. 刪除單鏈表結(jié)點(diǎn)*p后面的結(jié)點(diǎn)：void del (node *p)node *q;q=p->link;p->link=q->link; delete q; /如果要把該結(jié)點(diǎn)移入另一個(gè)鏈中，則可將q返回7.2.2單鏈表類型模板怎樣建立一個(gè)單鏈表的類是本小節(jié)的主題。對(duì)常用數(shù)據(jù)結(jié)構(gòu)而言，設(shè)計(jì)一個(gè)類應(yīng)該是比較簡(jiǎn)單的，它不同于實(shí)際問(wèn)題需要抽象建模，因?yàn)樗旧硪呀?jīng)是抽象的模型，只需要決定結(jié)點(diǎn)的組織和基本算法的選擇即可。與順序表一樣，單鏈表類模板的操作也應(yīng)該盡可能完備?！纠?.5_h】單鏈表類模板，本例作為一個(gè)頭文件。單鏈表的結(jié)點(diǎn)采用類，與結(jié)點(diǎn)有關(guān)的基本操作都作為結(jié)點(diǎn)類的成員函數(shù)。

43、對(duì)鏈表整體的操作則作為鏈表類的成員函數(shù)，包括清空鏈表、查找數(shù)據(jù)、計(jì)算單鏈表長(zhǎng)度、打印鏈表數(shù)據(jù)、向前生成鏈表、向后生成鏈表、按升序生成鏈表等等。#include<iostream>using namespace std;/首先看結(jié)點(diǎn)組織，采用結(jié)點(diǎn)類，凡與結(jié)點(diǎn)數(shù)據(jù)和指針操作有關(guān)函數(shù)作為成員函數(shù)template<typename T>class List; /前向引用聲明template<typename T>class NodeT info; /數(shù)據(jù)域Node<T> *link; /指針域，注意結(jié)點(diǎn)類格式，尖括號(hào)中是參數(shù)名表，類模板實(shí)例化為類publ

44、ic:Node(); /生成頭結(jié)點(diǎn)的構(gòu)造函數(shù)Node(const T & data); /生成一般結(jié)點(diǎn)的構(gòu)造函數(shù)void InsertAfter(Node<T>* P); /在當(dāng)前結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)Node<T>* RemoveAfter(); /刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)，返回該結(jié)點(diǎn)備用friend class List<T>/以List為友元類，List可直接訪問(wèn)Node的私有成員，與結(jié)構(gòu)一樣方便，但更安全;template <typename T> Node<T>:Node()link=NULL;template <t

45、ypename T> Node<T>:Node(const T & data)info=data;link=NULL;template<typename T>void Node<T>:InsertAfter(Node<T>* p)p->link=link;link=p;template<typename T>Node<T>* Node<T>:RemoveAfter()Node<T>* tempP=link;if(link=NULL) tempP=NULL; /已在鏈尾,后面無(wú)結(jié)點(diǎn)

46、else link=tempP->link;return tempP;/再定義鏈表類，選擇常用操作：包括建立有序鏈表、搜索遍歷、插入、刪除、取數(shù)據(jù)等template<typename T>class ListNode<T> *head,*tail; /鏈表頭指針和尾指針public:List(); /構(gòu)造函數(shù)，生成頭結(jié)點(diǎn)(空鏈表)List(); /析構(gòu)函數(shù)void MakeEmpty(); /清空一個(gè)鏈表，只余表頭結(jié)點(diǎn)Node<T>* Find(T data); /搜索數(shù)據(jù)域與data相同的結(jié)點(diǎn)，返回該結(jié)點(diǎn)的地址int Length(); /計(jì)算單鏈表

47、長(zhǎng)度void PrintList(); /打印鏈表的數(shù)據(jù)域 void InsertFront(Node<T>* p); /可用來(lái)向前生成鏈表，在表頭插入一個(gè)結(jié)點(diǎn)void InsertRear(Node<T>* p); /可用來(lái)向后生成鏈表，在表尾添加一個(gè)結(jié)點(diǎn)void InsertOrder(Node<T> *p); /按升序生成鏈表Node<T>*CreatNode(T data); /創(chuàng)建一個(gè)結(jié)點(diǎn)(孤立結(jié)點(diǎn))Node<T>*DeleteNode(Node<T>* p); /刪除指定結(jié)點(diǎn);template<typen

48、ame T>List<T>:List()head=tail=new Node<T>();template<typename T>List<T>:List()MakeEmpty();delete head;template<typename T>void List<T>:MakeEmpty()Node<T> *tempP;while(head->link!=NULL)tempP=head->link;head->link=tempP->link; /把頭結(jié)點(diǎn)后的第一個(gè)節(jié)點(diǎn)從鏈中脫離d

49、elete tempP; /刪除(釋放)脫離下來(lái)的結(jié)點(diǎn)tail=head; /表頭指針與表尾指針均指向表頭結(jié)點(diǎn)，表示空鏈template<typename T> Node<T>* List<T>:Find(T data)Node<T> *tempP=head->link;while(tempP!=NULL&&tempP->info!=data) tempP=tempP->link;return tempP; /搜索成功返回該結(jié)點(diǎn)地址，不成功返回NULLtemplate<typename T>int L

50、ist<T>:Length()Node<T>* tempP=head->link;int count=0;while(tempP!=NULL)tempP=tempP->link;count+;return count;template<typename T>void List<T>:PrintList()Node<T>* tempP=head->link;while(tempP!=NULL)cout<<tempP->info<<'t'tempP=tempP->lin

51、k;cout<<endl;template<typename T>void List<T>:InsertFront(Node<T> *p) /鏈頭插入p->link=head->link;head->link=p;if(tail=head) tail=p;template<typename T>void List<T>:InsertRear(Node<T> *p) /鏈尾插入p->link=tail->link;tail->link=p;tail=p;template<

52、typename T>void List<T>:InsertOrder(Node<T> *p) /升序插入Node<T> *tempP=head->link,*tempQ=head; /tempQ指向tempP前面的一個(gè)節(jié)點(diǎn)while(tempP!=NULL)if(p->info<tempP->info)break; /找第一個(gè)比插入結(jié)點(diǎn)大的結(jié)點(diǎn)，由tempP指向tempQ=tempP;tempP=tempP->link;tempQ->InsertAfter(p); /插在tempP指向結(jié)點(diǎn)之前，tempQ之后if(

53、tail=tempQ) tail=tempQ->link;template<typename T>Node<T>* List<T>:CreatNode(T data)/建立新節(jié)點(diǎn)Node<T>*tempP=new Node<T>(data);return tempP;template<typename T>Node<T>* List<T>:DeleteNode(Node<T>* p)Node<T>* tempP=head;while(tempP->link!=NULL&&tempP->link!=p) tempP=tempP->link;if(tempP->link=tail) tail=tempP;return tempP->RemoveAfter(); /本函數(shù)所用方法可省一個(gè)工作指針，與InsertOrder比較在本例中使用了友元類，這使得List類中的函數(shù)全部可以直接訪問(wèn)Node類中的私有數(shù)據(jù)，而不必使用公有函數(shù)NextNode()和Getinfo()。下面用整型數(shù)代替模板中的類型T，來(lái)完成一些鏈表的基本操作。【例7.5】由鍵盤(pán)輸入16個(gè)整數(shù)，以這些整數(shù)作為結(jié)點(diǎn)數(shù)據(jù)，生成兩個(gè)鏈表，一個(gè)向前生