【正文】 了？如果使用 C++標(biāo)準(zhǔn)字符串 string作為成員對(duì)象（聚合） 是否就不需要考慮深復(fù)制了？ 的確是這樣的，準(zhǔn)確地說(shuō)， string類的內(nèi)部包含動(dòng)態(tài)建立字符數(shù)組的操作，其復(fù)制構(gòu)造函數(shù)是深復(fù)制。 }。 //復(fù)制構(gòu)造函數(shù) ~student()。 //為了演示深復(fù)制，不用 string類 public: student()。 自由存儲(chǔ)區(qū) 對(duì)象 P P 自由存儲(chǔ)區(qū) 對(duì)象 圖 深復(fù)制 深復(fù)制： 重新定義復(fù)制的構(gòu)造函數(shù)，給每個(gè)對(duì)象獨(dú)立分配一個(gè) 自由存儲(chǔ)區(qū)對(duì)象，稱 深復(fù)制 。 圖 淺復(fù)制 P 自 由存儲(chǔ) 區(qū)對(duì)象 自 由 存儲(chǔ)區(qū) 對(duì)象 P P 復(fù)制前 復(fù)制后 如果類中有一個(gè)數(shù)據(jù)成員為指針，該類的一個(gè)對(duì)象 obj1中的這個(gè)指針 p，指向了動(dòng)態(tài)分配的一個(gè) 自由存儲(chǔ)區(qū) 對(duì)象，（參見(jiàn)圖 ），如果用 obj1按成員復(fù)制了一個(gè)對(duì)象 obj2，這時(shí) 自由存儲(chǔ)區(qū) 對(duì)象。但對(duì) 創(chuàng)建數(shù)組 ，則無(wú)參數(shù)， 只能調(diào)用默認(rèn)的構(gòu)造函數(shù) 。 對(duì)象與構(gòu)造函數(shù) 由自由存儲(chǔ)區(qū)創(chuàng)建對(duì)象數(shù)組 ， 只能調(diào)用默認(rèn)的構(gòu)造函數(shù) ， 不能調(diào)用其他任何構(gòu)造函數(shù) 。 CGoods *pc。 5． 動(dòng)態(tài)分配的變量或?qū)ο蟮纳?。未重載時(shí)，調(diào)用全局庫(kù)操作符 new()。建議這時(shí)將ｐ置空（ NULL）。 2. 指針刪除與 自由存儲(chǔ)區(qū) 空間釋放 。 刪除這兩個(gè)動(dòng)態(tài)數(shù)組可用下式： delete [] cp。 //三級(jí)指針 float (*bp) [20]。 //指向一個(gè) 30行 20列數(shù)組的指針 cp=new float [15] [30] [20]。盡管 C++不對(duì)數(shù)組作邊界檢查，但 在 自由 存儲(chǔ)區(qū) 空間分配時(shí)，對(duì)數(shù)組分配空間大小是紀(jì)錄在案的 。 請(qǐng)注意 “下標(biāo)表達(dá)式”不是常量表達(dá)式 ，即它的值不必在編譯時(shí)確定， 可以在運(yùn)行時(shí)確定 。 說(shuō)明： 兩式中的 方括號(hào) 必須配對(duì)使用 。 ２ ． 當(dāng) pi生命周期結(jié)束時(shí) ， 必須釋放 pi所指向的目標(biāo)： delete pi。 new表達(dá)式的操作： 從自由存儲(chǔ)區(qū)分配對(duì)象，然后用括號(hào)中的值初始化該對(duì)象 。 new運(yùn)算符 返回 的是一個(gè)指向所分配類型變量（對(duì)象）的指針 。動(dòng)態(tài)分配都在 自由存儲(chǔ)區(qū) 中進(jìn)行。進(jìn)一步討論復(fù)制構(gòu)造函數(shù) . 然后學(xué)習(xí)更多有關(guān) 數(shù)據(jù)結(jié)構(gòu) 的基本知識(shí)，包括 鏈表 ，棧 ， 隊(duì) ， 二叉樹 等的基本算法和應(yīng)用。 模板 是標(biāo)準(zhǔn)C++實(shí)現(xiàn)代碼復(fù)用的有力工具，特別是有關(guān)數(shù)據(jù)結(jié)構(gòu)的算法，本章繼續(xù)使用。 內(nèi)存的分配與釋放 當(dāng)程序運(yùn)行到需要一個(gè)動(dòng)態(tài)分配的變量或?qū)ο髸r(shí) ， 必須向系統(tǒng) 申請(qǐng)取得自由存儲(chǔ)區(qū) 中的一塊所需大小的存貯空間 ， 用于存貯該變量或?qū)ο?。對(duì)所創(chuàng)建的變量或?qū)ο?，都是通過(guò)該指針來(lái)間接操作的，而 動(dòng)態(tài)創(chuàng)建的對(duì)象本身沒(méi)有名字。 分配對(duì)象時(shí)， new表達(dá)式調(diào)用庫(kù)操作符 new()： int *pi=new int(0)。 注意這時(shí)釋放了 pi所指的目標(biāo)的內(nèi)存空間，也就是撤銷了該目標(biāo)，稱動(dòng)態(tài)內(nèi)存釋放（ dynamic memory deallocation），但 指針 pi本身并沒(méi)有撤銷 ，該指針?biāo)純?nèi)存空間并未釋放。 如果 delete語(yǔ)句中少了方括號(hào) ， 因編譯器認(rèn)為該指針是指向數(shù)組第一個(gè)元素的指針 ， 會(huì)產(chǎn)生 回收不徹底 的問(wèn)題 （ 只回收了第一個(gè)元素所占空間 ） ， 加了方括號(hào)后就轉(zhuǎn)化為指向數(shù)組的指針 ， 回收整個(gè)數(shù)組 。 內(nèi)存的分配與釋放 動(dòng)態(tài)分配數(shù)組與 標(biāo)準(zhǔn)字符串類 ： 標(biāo)準(zhǔn)字符串類 string就是采用動(dòng)態(tài)建立數(shù)組的方式解決數(shù)組溢出的問(wèn)題的，例 ，在 string類對(duì)象中都是自動(dòng)完成的，在程序中不需要也不允許再顯式地為 string進(jìn)行動(dòng)態(tài)內(nèi)存的分配與釋放。 3. 沒(méi)有初始化式（ initializer）， 不可對(duì)數(shù)組初始化 。 //建立由 15個(gè) 30*20數(shù)組組成的數(shù)組； 注意 cp等效于三維數(shù)組名，但沒(méi)有指出其邊界，即最高維的元素?cái)?shù)量，就像指向字符的指針即等效一個(gè)字符串 ,不要把指向字符的指針，說(shuō)成指向字符串的指針 。 //二級(jí)指針 cp=new float [1] [30] [20]。 //刪除（釋放）三維數(shù)組 delete [] bp。刪除一個(gè)指針 p（ delete p。 3. new()和 delete()是可以重載的 ，它們都是類的靜態(tài)成員函數(shù)。 內(nèi)存的分配與釋放 4． 內(nèi)存泄漏（ memory leak）和重復(fù)釋放 。 無(wú)名對(duì)象的生命期并不依賴于建立它的作用域，比如在函數(shù)中建立的動(dòng)態(tài)對(duì)象在函數(shù)返回后仍可使用 。 pc=new CGoods。 如果沒(méi)有默認(rèn)的構(gòu)造函數(shù) ， 則不能創(chuàng)建對(duì)象數(shù)組 。 【 例 】 演示自由存儲(chǔ)區(qū)對(duì)象分配和釋放。 obj1 obj1 obj2 淺復(fù)制與深復(fù)制復(fù)制 當(dāng) 淺復(fù)制 析構(gòu)時(shí)，如用默認(rèn)的析構(gòu)函數(shù)，則動(dòng)態(tài)分配的 自由存儲(chǔ)區(qū) 對(duì)象不能回收。 這時(shí)先復(fù)制對(duì)象主體，再為 obj2分配一個(gè) 自由存儲(chǔ)區(qū) 對(duì)象，最后用 obj1的 自由存儲(chǔ)區(qū) 對(duì)象復(fù)制 obj2的 自由存儲(chǔ)區(qū) 對(duì)象。 //默認(rèn)構(gòu)造函數(shù) student(char *pname)。 //析構(gòu)函數(shù) student amp。 //復(fù)制賦值操作符 檢驗(yàn) 主函數(shù) 和 運(yùn)行結(jié)果 淺復(fù)制與深復(fù)制 提示： 自由存儲(chǔ)區(qū)內(nèi)存是最常見(jiàn)的需要自定義復(fù)制構(gòu)造函數(shù)的資源，但不是唯一的，還有打開文件等也需要自定義復(fù)制構(gòu)造函數(shù)。如果在 student類中使用 string類而不是 C字符串，就不要再考慮深復(fù)制問(wèn)題了。封裝的更高境界是在該類對(duì)象中一切都是完備的、自給自足的，不僅有數(shù)據(jù)和對(duì)數(shù)據(jù)的操作，還包括資源的動(dòng)態(tài)安排和釋放。這表明 聚合實(shí)現(xiàn)了完善的封裝 。 單鏈表基本算法 雙向鏈表 (選讀 ) 單鏈表基本算法 單鏈表 （ Singly Linked list） ： 每個(gè)數(shù)據(jù)元素占用一個(gè)節(jié)點(diǎn) （ Node） 。 node *link。 單鏈表基本算法 單鏈表的第一個(gè)結(jié)點(diǎn)的地址可通過(guò)鏈表的表頭指針 head找到， head在使用中千萬(wàn)不可丟失，否則鏈表整個(gè)丟失，內(nèi)存也發(fā)生泄漏。 head head 插在鏈?zhǔn)祝? 首先新結(jié)點(diǎn)的 link指針指向 info0所在結(jié)點(diǎn) ， 然后 ， head指向新結(jié)點(diǎn) 。 要使算法中沒(méi)有特殊者 ， 可以給每一個(gè)鏈表加上一個(gè) 表頭結(jié)點(diǎn) ， 如下圖所示 。 head=new node。 //添入數(shù)據(jù) taillink= p。 //返回頭指針 } 單鏈表基本算法 head ^ info0 P ^ P info1 2. 向前生成鏈表算法： node *createup(){ node *head,*p。 while(cindata){ //建立的總是第一個(gè)結(jié)點(diǎn) p=new node。 //頭結(jié)點(diǎn)放新結(jié)點(diǎn)之前 } return head。pinfo!=data) p=plink。 void insert(node *p,Datatype x){ node *q=new node。 } 單鏈表基本算法 5. 刪除單鏈表節(jié)點(diǎn) *p后面節(jié)點(diǎn)： void del (node *p){ node *q。 //如果要把該節(jié)點(diǎn)移入另一個(gè)鏈中 ， 則可將 q返回 。 //數(shù)據(jù)域 NodeT *link。 //生成 一般結(jié)點(diǎn)的構(gòu)造函數(shù) void InsertAfter(NodeT* p)。 定義鏈表類 : templatetypename Tclass List{ NodeT *head,*tail。 //清空鏈表 ，只余表頭結(jié)點(diǎn) NodeT* Find(T data)。 //可用來(lái) 向前生成鏈表 void InsertRear(NodeT* p)。 }。 在本例中程序只需調(diào)用類模板中的成員函數(shù)就可以完成所有鏈表操作。 通常對(duì) Node類復(fù)制的結(jié)果應(yīng)是一個(gè)孤立結(jié)點(diǎn)： template typename T NodeT::Node(Node amp。該函數(shù)與 Node的有參構(gòu)造函數(shù)功能基本相同。為了克服這一缺點(diǎn)，可采用 雙向鏈表 （ Double Linked List)。 pllinkrlink指示本結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的后繼結(jié)點(diǎn)，即本結(jié)點(diǎn)，間接訪問(wèn)符 可以連續(xù)使用 。允許進(jìn)行插入和刪除的一端叫做 棧頂 (top)，而另一端叫 棧底 (bottom)。所以棧又稱作 后進(jìn)先出（ LIFO： Last In First Out）的線性表 。而出棧時(shí)順序相反，最后進(jìn)棧的 an1最先出棧，而最先進(jìn)棧的 a0最后出棧。 棧 templatetypename Tclass Stack{ int top。 //構(gòu)造函數(shù) ，棧如不指定大小，設(shè)為 20元素 ~Stack(){delete[ ] elements。 //彈出 ， top T GetElem(int i)。} //判棧滿 void PrintStack()。 for(i=0。 ()。 if(()) cout棧空 endl。\t39。 NodeT *link。 }。 //析構(gòu)函數(shù) void Push(const T amp。 //取棧頂元素 void MakeEmpty()。順序棧必須先開一定大小內(nèi)存空間，執(zhí)行起來(lái)簡(jiǎn)單，速度快，可能溢出。 為實(shí)現(xiàn)運(yùn)算符的優(yōu)先級(jí)，采用兩個(gè)棧：一個(gè) 數(shù)棧 ，一個(gè) 運(yùn)算符棧 。否則將棧頂運(yùn)算符出棧，與數(shù)字棧出棧的兩個(gè)數(shù)據(jù)進(jìn)行運(yùn)算，結(jié)果壓入數(shù)棧，再將新運(yùn)算符壓棧。 表達(dá)式結(jié)束符使用＝號(hào) ， 清空棧用 ‘ c’字符 。 public: Calculator(void){}。Num2)。 //清除 隊(duì)列 隊(duì)列的基本概念： 隊(duì)列 (Queue)也是一種限定存取位置的線性表。隊(duì)列的這種特性正好與棧相反，叫做 先進(jìn)先出 FIFO(First In First Out)。實(shí)際上 對(duì)象很大時(shí)，總是由索引（指針）來(lái)排隊(duì) 。鏈?zhǔn)壮鲫?duì)，鏈尾入隊(duì)。如 n=0，稱為空樹。這是一個(gè)遞歸方法定義的數(shù)據(jù)結(jié)構(gòu)。 分支結(jié)點(diǎn) ， 度 ≥1的結(jié)點(diǎn) 。 結(jié)點(diǎn)的層次 ， 從根到該結(jié)點(diǎn)所經(jīng)路徑上的分支條數(shù) 。二叉樹是結(jié)點(diǎn)的一個(gè)有限集合 ， 該集合或?yàn)榭?， 或是由一個(gè)根結(jié)點(diǎn)及兩棵樹分別稱為左子樹和右子樹的 （ 注意有左右之分 ） 互不相交的二叉樹組成 ， 其中左右子樹分別可以為空子樹或均為空樹 。 樹的概念： 二叉樹的概念（選讀） 【 例 】 畫出有三個(gè)結(jié)點(diǎn)的所有二叉樹 。每個(gè)結(jié)點(diǎn)有三個(gè)域：數(shù)據(jù)域、左孩子指針和右孩子指針，見(jiàn)圖 。 public: Node(){ lchild=NULL。 rchild=right。} //修改結(jié)點(diǎn)數(shù)據(jù) NodeT *Getleft(){return lchild。} //設(shè)置右指針 friend class BinaryTreeT。 圖 二叉樹遍歷 中序遍歷結(jié)果為 D B G E A F H C。 為什么 ？ 請(qǐng)讀者自己思考 。 //中序遍歷 void PreOrder(NodeT *Current)。b)。} //析構(gòu)函數(shù) void Creat(T* data,int n)。} //后序遍歷，公有函數(shù)為接口 }?？梢宰C明已知先序和中序訪問(wèn)次序可以唯一確定一棵二叉樹。再由先序 D G知，D為 B的右子樹根結(jié)點(diǎn)，由中序 D G知 G為 D的右子樹。 排序二叉樹 （選讀） 二叉排序樹用中序遍歷就可以得到由小到大的有序序列，如圖 ｛ 8， 10， 11， 12，15， 16， 18， 22， 24， 26， 29｝。 3. 如 ai小于根結(jié)點(diǎn)，則去左子樹，否則去右子樹，按此法查找，直到成為空樹，則安放此位置。 while(temp!=NULL){ if(tempinfo==data)return temp。} 【 例 】 排序二叉樹查找函數(shù)。 cout請(qǐng)輸入動(dòng)態(tài)數(shù)組的元素個(gè)數(shù) endl。 coutpcendl。采用 指針數(shù)組方式 來(lái)完成二維數(shù)組的動(dòng)態(tài)創(chuàng)建。 int i,j。 } for(j=0。 r