【正文】 ，而是避開了所有使用它的情況，本例中函數(shù)的參數(shù)和返回值僅使用指向 Node的指針，類定義中也沒有用復(fù)制方式初始化。 //按 升序生成鏈表 NodeT*CreatNode(T data)。 //構(gòu)造函數(shù) ，生成頭結(jié)點(diǎn) (空鏈表 ) ~List()。 //生成 頭結(jié)點(diǎn)的構(gòu)造函數(shù) Node(const T amp。 plink=qlink。 //p為 NULL則未找到 } 返回值為指針 p， 指向鏈表中找到的結(jié)點(diǎn) 。 plink= headlink 。 } //尾指針到鏈尾 taillink=NULL。 單鏈表基本算法 head tail p info1 tail p info0 tail ^ 1. 向后生成鏈表算法： node *createdown(){ Datatype data。 即： newnode→ link=p； //或 newnode→ link=q→ link；可用于插入某結(jié)點(diǎn)之后 q→ link=newnode； 單鏈表基本算法 infox newnode 插入算法有 三種 情況，我們希望在單鏈表中包含數(shù)據(jù) infoi的結(jié)點(diǎn)之前插入一個(gè)新元素，則 infoi可在第一個(gè)結(jié)點(diǎn)，或在中間結(jié)點(diǎn)，如未找到，則把新結(jié)點(diǎn)插在鏈尾結(jié)點(diǎn)之后。 head不可丟失，否則鏈表整個(gè)丟失，內(nèi)存發(fā)生泄漏。這表明 聚合實(shí)現(xiàn)了完善的封裝 。如果在 student類中使用 string類而不是 C字符串，就不要再考慮深復(fù)制問題了。 //析構(gòu)函數(shù) student amp。 這時(shí)先復(fù)制對(duì)象主體，再為 obj2分配一個(gè) 自由存儲(chǔ)區(qū) 對(duì)象，最后用 obj1的 自由存儲(chǔ)區(qū) 對(duì)象復(fù)制 obj2的 自由存儲(chǔ)區(qū) 對(duì)象。 【 例 】 演示自由存儲(chǔ)區(qū)對(duì)象分配和釋放。 pc=new CGoods。 內(nèi)存的分配與釋放 4． 內(nèi)存泄漏（ memory leak）和重復(fù)釋放 。刪除一個(gè)指針 p（ delete p。 //二級(jí)指針 cp=new float [1] [30] [20]。 3. 沒有初始化式（ initializer）， 不可對(duì)數(shù)組初始化 。 如果 delete語句中少了方括號(hào) ， 因編譯器認(rèn)為該指針是指向數(shù)組第一個(gè)元素的指針 ， 會(huì)產(chǎn)生 回收不徹底 的問題 （ 只回收了第一個(gè)元素所占空間 ） ， 加了方括號(hào)后就轉(zhuǎn)化為指向數(shù)組的指針 ， 回收整個(gè)數(shù)組 。 分配對(duì)象時(shí)， new表達(dá)式調(diào)用庫操作符 new()： int *pi=new int(0)。 內(nèi)存的分配與釋放 當(dāng)程序運(yùn)行到需要?jiǎng)討B(tài)分配變量或?qū)ο髸r(shí) ， 必須向系統(tǒng) 申請(qǐng)取得自由存儲(chǔ)區(qū) 中的一塊所需大小的存貯空間 ， 用于存貯該變量或?qū)ο?。第七章 動(dòng)態(tài)內(nèi)存分配與數(shù)據(jù)結(jié)構(gòu) 本章首先介紹程序運(yùn)行時(shí) 動(dòng)態(tài)內(nèi)存分配 （ dynamic memory allocation）的概念與方法。 當(dāng)不再使用該變量或?qū)ο髸r(shí) ， 也就是它的生命結(jié)束時(shí) ， 要 顯式釋放 它所占用的存貯空間 ， 這樣系統(tǒng)就能進(jìn)行再次分配 ， 做到重復(fù)使用有限的資源 。 pi現(xiàn)在所指向的變量的存儲(chǔ)空間是由庫操作符 new()分配的，位于程序的自由存儲(chǔ)區(qū)中，并且該對(duì)象未命名。 delete [ ]的方括號(hào)中 不需要 填 數(shù)組元素?cái)?shù) ，系統(tǒng)自知。 內(nèi)存的分配與釋放 （選讀） 多維數(shù)組動(dòng)態(tài)分配： new 類型名 [下標(biāo)表達(dá)式 1] [下標(biāo)表達(dá)式 2]……。 bp=new float [30] [20]。）實(shí)際意思是刪除了 p所指的目標(biāo)（變量或?qū)ο蟮龋?，釋放了它所占的自由存?chǔ)區(qū)空間，而不是刪除ｐ本身，釋放自由存儲(chǔ)區(qū)空間后，ｐ成了空懸指針。 new與 delete 是配對(duì)使用的， delete只能釋放 自由存儲(chǔ)區(qū) 空間。 //分配自由存儲(chǔ)區(qū)空間，并構(gòu)造一個(gè)無名的 CGoods對(duì)象； ……. delete pc。 淺復(fù)制與深復(fù)制 淺復(fù)制： 默認(rèn)復(fù)制構(gòu)造函數(shù) ，可用一個(gè)類對(duì)象初始化另一個(gè)類對(duì)象，稱為默認(rèn)的 按成員復(fù)制， 而不是對(duì)整個(gè)類對(duì)象的 按位復(fù)制。 obj1 obj2 淺復(fù)制與深復(fù)制 【 例 】 定義復(fù)制構(gòu)造函數(shù) （ copy structor）和復(fù)制賦值操作符（ copy Assignment Operator）實(shí)現(xiàn)深復(fù)制。 operator=(student amp。也就是說， 動(dòng)態(tài)內(nèi)存分配和深復(fù)制應(yīng)該放在一個(gè)適當(dāng)?shù)膶用嫔?，一個(gè)更單純的類定義中，如 string類。 鏈表與鏈表的基本操作 線性表 是最簡單，最常用的一種數(shù)據(jù)結(jié)構(gòu)。 單鏈表基本算法 結(jié)點(diǎn)定義如下： typedef int Datatype。 單鏈表基本算法 newnode infox info0 info1 Node*head,*tail,*p。 //鏈尾加空指針 ， 表示鏈結(jié)束 return head。 //新結(jié)點(diǎn)放在原鏈表前方 headlink=p。 4. 在單鏈表的 p結(jié)點(diǎn)后插入 ： 注意只有一種情況。 delete q。 data)。 //析構(gòu)函數(shù) void MakeEmpty()。 //創(chuàng)建結(jié)點(diǎn) (孤立結(jié)點(diǎn) ) NodeT*DeleteNode(NodeT* p)。 定義復(fù)制構(gòu)造函數(shù)與類的實(shí)際意義和使用方式有關(guān)，并非只是深復(fù)制和淺復(fù)制的問題 。如要找前驅(qū)，必須從表頭開始搜索。 7. 3. 1 棧 7. 3. 3 隊(duì) 列 7. 3. 2 棧的應(yīng)用（選讀） 棧 棧的基本概念： 棧定義為只允許在表的一端進(jìn)行插入和刪除的線性表 。進(jìn)棧時(shí)最先進(jìn)棧的 a0在最下面， an1在最上面。 //棧最大容納的元素個(gè)數(shù) public: Stack(int=20)。} //判棧空 bool IsFull() const{return top==maxSize1。 if(()) cout棧滿 endl。i++) coutb[i]39。 } friend class StackT。 //彈出 T GetTop()。現(xiàn)考慮最簡單的 +、 、 *、 /四個(gè)運(yùn)算符和結(jié)束符＝組成的算術(shù)表達(dá)式，只有 兩個(gè)優(yōu)先級(jí) ，先 */，后 +。 棧的應(yīng)用（選讀） 【 例 】 模擬簡單計(jì)算器 ， 該計(jì)算器只認(rèn) + * / 四個(gè)運(yùn)算符 ，輸入為整數(shù) 。Num1,int amp。每次在隊(duì)尾加入新元素，加入稱為 進(jìn)隊(duì) ，刪除稱為 出隊(duì) 。 【 例 】 鏈隊(duì)類模板。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有 0個(gè)或多個(gè)直接后繼。 兄弟結(jié)點(diǎn) ， 同一雙親的結(jié)點(diǎn)互稱為兄弟 。 二叉樹的基本性質(zhì)： 1．二叉樹的第 i層上最多有 2i1(i=1)個(gè)結(jié)點(diǎn)； 2．深度為 h的二叉樹中最多有 2h1個(gè)結(jié)點(diǎn)； 3．在任一棵二叉樹中，有 n0個(gè)葉子結(jié)點(diǎn)，有 n2個(gè)度為 2的 結(jié)點(diǎn)，則有 n0=n2+1。 T info。data){info=data。 遍歷二叉樹有不同次序，規(guī)定先左后右，令 L， R， V分別代表遍歷一個(gè)結(jié)點(diǎn)的左右子樹和訪問該結(jié)點(diǎn)的操作，有三種方式： 前序遍歷（ VLR） 中序遍歷（ LVR） 后序遍歷（ LRV） 二叉樹的遍歷（選讀） 遍歷實(shí) 例： 前序遍歷訪問次序?yàn)?ABDEGCFH。 //二叉樹的根指針 void InOrder(NodeT *Current)。} //空樹構(gòu)造函數(shù) ~BinaryTree(){Destory(root)。結(jié)果如圖 。 二叉排序樹的定義： 二叉排序樹或者是空樹或者是具有下述性質(zhì)的二叉數(shù)，其左子樹上所有結(jié)點(diǎn)的數(shù)據(jù)值均小于根結(jié)點(diǎn)的數(shù)據(jù)值；右子樹上所有結(jié)點(diǎn)的數(shù)據(jù)值均大于等于根結(jié)點(diǎn)的數(shù)據(jù)值，左子樹和右子樹又各是一棵二叉排序樹。data,NodeT *b){ if(b!=NULL){ NodeT *temp=b。 char *pc。 } 內(nèi)存的分配與釋放 【 例 】 【 例 】 動(dòng)態(tài)創(chuàng)建和刪除一個(gè) m*n個(gè)元素的數(shù)組。 } for(j=0。jn。i++) delete[] data[i]。 CGoods(string name,int amount ,float price){ cout調(diào)用三參數(shù)構(gòu)造函數(shù) endl。 對(duì)象與構(gòu)造函數(shù) 【 例 】 使用： int main(){ int n。 delete pc1。 coutpNameendl。\039。 coutpNameendl。 data){ info=data。 } 例 單鏈表類型模板 鏈表類成員函數(shù)： templatetypename TListT::List(){ head=tail=new NodeT()。 } //表頭指針與表尾指針均指向表頭結(jié)點(diǎn)，表示空鏈 例 單鏈表類型模板 鏈表類成員函數(shù)： templatetypename T NodeT* ListT::Find(T data){ NodeT *tempP=headlink。count++。 headlink=p。 tempP=tempPlink。tempPlink!=p) tempP=tempPlink。i16。 } //向后生成 list2 ()。 ()。 } //升序創(chuàng)建 list1 ()。 //英語，物理，數(shù)學(xué)和電子學(xué)成績 public: student(int=0,string=,char=39。\t39。\t39。 while(tempP!=NULL){ tempP()。 student n[h]={ student(6004327,張菲 ,39。,18,重慶路 95號(hào) ,78,95,81,88),}。 例 學(xué)生檔案的管理 coutlist1長度： ()endl。 coutlist1長度： ()endl。 return 0。}。 void Insert(const T amp。 //鏈尾插入 DblNodeT* Remove(DblNodeT* p)。} templatetypename T DblNodeT::DblNode(T data){ info=data。 //數(shù)據(jù)域 DblNodeT *llink,*rlink。 ()。 cout請(qǐng)輸入一個(gè)要求刪除的學(xué)生學(xué)號(hào) endl。ih。,19,北京路 58號(hào) ,80,85,90,78), student(6004121,關(guān)雨 ,39。 } coutendl。\t39。\t39。,int=0,string=, float=,float=,float=,float=)。} 例 學(xué)生檔案的管理 include class student{ int id 。 } else cout未找到 endl。 ()。 //隨機(jī)輸入 16個(gè)整數(shù) for(i=0。 return tempPRemoveAfter()。 //插在 tempP指向結(jié)點(diǎn)之前， tempQ之后 if(tail==tempQ) tail=tempQlink。} templatetypename Tvoid ListT::InsertRear(NodeT *p){ plink=taillink。 } 例 單鏈表類型模板 鏈表類成員函數(shù)： templatetypename Tvoid ListT::PrintList(){//顯示鏈表 NodeT* tempP=headlink。amp。 delete head。 } templatetypename T void NodeT::InsertAfter(NodeT* p){ plink=link。} int main(void){ student s1(范英明 ),s2(沈俊 ),s3。} //釋放字符串 例 實(shí)現(xiàn)深復(fù)制 復(fù)制賦值操作符： student amp。s){ coutCopy Constructor。 return 0。 pc=new CGoods(“夏利 2021”， 10， 118000)。 Amount=amount。 } 對(duì)象與構(gòu)造函數(shù) 【 例 】 類說明： class CGoods{ string Name。 //數(shù)組