【正文】 點(diǎn)的構(gòu)造函數(shù) Node(const T amp。 定義結(jié)點(diǎn)類： templatetypename Tclass List。 plink=qlink。 qlink=plink。 //p為 NULL則未找到 } 返回值為指針 p， 指向鏈表中找到的結(jié)點(diǎn) 。 while(p!=NULLamp。 plink= headlink 。 head=new node。 } //尾指針到鏈尾 taillink=NULL。 while(cindata){ //Ctrl+z結(jié)束 p=new(node)。 單鏈表基本算法 head tail p info1 tail p info0 tail ^ 1. 向后生成鏈表算法： node *createdown(){ Datatype data。 p ^ infon1 ^ 插在隊尾： 只要工作指針 p找到隊尾 ， 即可鏈在其后： p→ link=newnode； =NULL。 即： newnode→ link=p； //或 newnode→ link=q→ link；可用于插入某結(jié)點(diǎn)之后 q→ link=newnode； 單鏈表基本算法 infox newnode 插入算法有 三種 情況，我們希望在單鏈表中包含數(shù)據(jù) infoi的結(jié)點(diǎn)之前插入一個新元素，則 infoi可在第一個結(jié)點(diǎn)，或在中間結(jié)點(diǎn)，如未找到，則把新結(jié)點(diǎn)插在鏈尾結(jié)點(diǎn)之后。 }。 head不可丟失，否則鏈表整個丟失，內(nèi)存發(fā)生泄漏。 單鏈表基本算法 雙向鏈表 (選讀 ) 單鏈表基本算法 單鏈表 （ Singly Linked list） ： 每個數(shù)據(jù)元素占用一個結(jié)點(diǎn) （ Node） 。這表明 聚合實(shí)現(xiàn)了完善的封裝 。封裝的更高境界是在該類對象中一切都是完備的、自給自足的，不僅有數(shù)據(jù)和對數(shù)據(jù)的操作，還包括資源的動態(tài)安排和釋放。如果在 student類中使用 string類而不是 C字符串，就不要再考慮深復(fù)制問題了。 //復(fù)制賦值操作符 檢驗 主函數(shù) 和 運(yùn)行結(jié)果 淺復(fù)制與深復(fù)制 提示： 自由存儲區(qū)內(nèi)存是最常見的需要自定義復(fù)制構(gòu)造函數(shù)的資源，但不是唯一的，還有打開文件等也需要自定義復(fù)制構(gòu)造函數(shù)。 //析構(gòu)函數(shù) student amp。 //默認(rèn)構(gòu)造函數(shù) student(char *pname)。 這時先復(fù)制對象主體，再為 obj2分配一個 自由存儲區(qū) 對象，最后用 obj1的 自由存儲區(qū) 對象復(fù)制 obj2的 自由存儲區(qū) 對象。 obj1 obj1 obj2 淺復(fù)制與深復(fù)制復(fù)制 當(dāng) 淺復(fù)制 析構(gòu)時，如用默認(rèn)的析構(gòu)函數(shù)，則動態(tài)分配的 自由存儲區(qū) 對象不能回收。 【 例 】 演示自由存儲區(qū)對象分配和釋放。 如果沒有默認(rèn)的構(gòu)造函數(shù) ， 則不能創(chuàng)建對象數(shù)組 。 pc=new CGoods。 無名對象的生命期并不依賴于建立它的作用域，比如在函數(shù)中建立的動態(tài)對象在函數(shù)返回后仍可使用 。 內(nèi)存的分配與釋放 4． 內(nèi)存泄漏（ memory leak）和重復(fù)釋放 。 3. new()和 delete()是可以重載的 ，它們都是類的靜態(tài)成員函數(shù)。刪除一個指針 p（ delete p。 //刪除（釋放）三維數(shù)組 delete [] bp。 //二級指針 cp=new float [1] [30] [20]。 //建立由 15個 30*20數(shù)組組成的數(shù)組； 注意 cp等效于三維數(shù)組名，但沒有指出其邊界，即最高維的元素數(shù)量，就像指向字符的指針即等效一個字符串 ,不要把指向字符的指針，說成指向字符串的指針 。 3. 沒有初始化式（ initializer）， 不可對數(shù)組初始化 。 內(nèi)存的分配與釋放 動態(tài)分配數(shù)組與 標(biāo)準(zhǔn)字符串類 ： 標(biāo)準(zhǔn)字符串類 string就是采用動態(tài)建立數(shù)組的方式解決數(shù)組溢出的問題的，例 ，在 string類對象中都是自動完成的，在程序中不需要也不允許再顯式地為 string進(jìn)行動態(tài)內(nèi)存的分配與釋放。 如果 delete語句中少了方括號 ， 因編譯器認(rèn)為該指針是指向數(shù)組第一個元素的指針 ， 會產(chǎn)生 回收不徹底 的問題 （ 只回收了第一個元素所占空間 ） ， 加了方括號后就轉(zhuǎn)化為指向數(shù)組的指針 ， 回收整個數(shù)組 。 注意這時釋放了 pi所指的目標(biāo)的內(nèi)存空間，也就是撤銷了該目標(biāo)，稱動態(tài)內(nèi)存釋放（ dynamic memory deallocation），但 指針 pi本身并沒有撤銷 ，該指針?biāo)純?nèi)存空間并未釋放。 分配對象時， new表達(dá)式調(diào)用庫操作符 new()： int *pi=new int(0)。對所創(chuàng)建的變量或?qū)ο?，都是通過該指針來間接操作的，而 動態(tài)創(chuàng)建的對象本身沒有名字。 內(nèi)存的分配與釋放 當(dāng)程序運(yùn)行到需要動態(tài)分配變量或?qū)ο髸r ， 必須向系統(tǒng) 申請取得自由存儲區(qū) 中的一塊所需大小的存貯空間 ， 用于存貯該變量或?qū)ο?。 （選讀） 棧與隊列的基本操作及其應(yīng)用 鏈表與鏈表的基本操作 第七章 動態(tài)內(nèi)存分配與數(shù)據(jù)結(jié)構(gòu) 內(nèi)存 的分配與釋放 對象 與構(gòu)造函數(shù) 淺復(fù)制與深復(fù)制 靜態(tài)存儲分配： 無論全局或局部變量 (對象 )，編譯器在 編譯時 都可以根據(jù)該變量(對象 )的類型知道所需內(nèi)存空間的大小，從而系統(tǒng)在適當(dāng)?shù)臅r候為它們分配確定的存儲空間。第七章 動態(tài)內(nèi)存分配與數(shù)據(jù)結(jié)構(gòu) 本章首先介紹程序運(yùn)行時 動態(tài)內(nèi)存分配 （ dynamic memory allocation）的概念與方法。尤其是數(shù)組。 當(dāng)不再使用該變量或?qū)ο髸r ， 也就是它的生命結(jié)束時 ， 要 顯式釋放 它所占用的存貯空間 ， 這樣系統(tǒng)就能進(jìn)行再次分配 ， 做到重復(fù)使用有限的資源 。 動態(tài)分配與釋放： 內(nèi)存的分配與釋放 一般定義變量和對象時要用標(biāo)識符命名，稱 命名對象 ，而動態(tài)的稱 無名對象 (請注意與棧區(qū)中的臨時對象的區(qū)別，兩者完全不同：生命期不同，操作方法不同，臨時變量對程序員是透明的 )。 pi現(xiàn)在所指向的變量的存儲空間是由庫操作符 new()分配的，位于程序的自由存儲區(qū)中，并且該對象未命名。 內(nèi)存的分配與釋放 數(shù)組動態(tài)分配格式： 指針變量名 =new 類型名 [下標(biāo)表達(dá)式 ]。 delete [ ]的方括號中 不需要 填 數(shù)組元素數(shù) ，系統(tǒng)自知。 【 例 】 動態(tài)數(shù)組的建立與撤銷 內(nèi)存的分配與釋放 動態(tài)分配數(shù)組的特點(diǎn)： 1. 變量 n在編譯時沒有確定的值，而是在運(yùn)行中輸入， 按運(yùn)行時所需分配空間 ，這一點(diǎn)是動態(tài)分配的優(yōu)點(diǎn)，可克服數(shù)組“大開小用”的弊端，在表、排序與查找中的算法，若用動態(tài)數(shù)組，通用性更佳。 內(nèi)存的分配與釋放 （選讀） 多維數(shù)組動態(tài)分配： new 類型名 [下標(biāo)表達(dá)式 1] [下標(biāo)表達(dá)式 2]……。這與數(shù)組的嵌套定義相一致。 bp=new float [30] [20]。 //刪除（釋放）二維數(shù)組 【 例 】 動態(tài)創(chuàng)建和刪除一個 m*n個元素的數(shù)組 的分配與釋放 指針使用的要點(diǎn)： 1. 動態(tài)分配失敗 。）實(shí)際意思是刪除了 p所指的目標(biāo)（變量或?qū)ο蟮龋?，釋放了它所占的自由存儲區(qū)空間，而不是刪除ｐ本身，釋放自由存儲區(qū)空間后，ｐ成了空懸指針。程序員無需顯式聲明它為靜態(tài)的，系統(tǒng)自動定義為靜態(tài)的。 new與 delete 是配對使用的， delete只能釋放 自由存儲區(qū) 空間。但必須記住釋放該對象所占 自由存儲區(qū) 空間，并只能釋放一次，在函數(shù)內(nèi)建立，而在函數(shù)外釋放是一件很容易 失控 的事，往往會出錯。 //分配自由存儲區(qū)空間，并構(gòu)造一個無名的 CGoods對象； ……. delete pc。 類對象初始化： new后面類（ class）類型可以有參數(shù)。 淺復(fù)制與深復(fù)制 淺復(fù)制： 默認(rèn)復(fù)制構(gòu)造函數(shù) ，可用一個類對象初始化另一個類對象，稱為默認(rèn)的 按成員復(fù)制， 而不是對整個類對象的 按位復(fù)制。如果在析構(gòu)函數(shù)中有“ delete p。 obj1 obj2 淺復(fù)制與深復(fù)制 【 例 】 定義復(fù)制構(gòu)造函數(shù) （ copy structor）和復(fù)制賦值操作符（ copy Assignment Operator）實(shí)現(xiàn)深復(fù)制。 //帶參數(shù) 構(gòu)造函數(shù) student(student amp。 operator=(student amp。 如果類對象需要動態(tài)分配資源應(yīng)該由構(gòu)造函數(shù)完成，而釋放資源由析構(gòu)函數(shù)完成，這時類也需要一個自定義的復(fù)制構(gòu)造函數(shù)，實(shí)現(xiàn)對象的深復(fù)制。也就是說， 動態(tài)內(nèi)存分配和深復(fù)制應(yīng)該放在一個適當(dāng)?shù)膶用嫔?，一個更單純的類定義中，如 string類。在需要時可以無條件地安全使用。 鏈表與鏈表的基本操作 線性表 是最簡單，最常用的一種數(shù)據(jù)結(jié)構(gòu)。 一個結(jié)點(diǎn)包含兩個域 ， 一個域存放數(shù)據(jù)元素 info， 其數(shù)據(jù)類型由應(yīng)用問題決定；另一個存放指向該鏈表中下一個結(jié)點(diǎn)的指針 link。 單鏈表基本算法 結(jié)點(diǎn)定義如下： typedef int Datatype。 在 C/C++中允許結(jié)構(gòu)（或?qū)ο螅┏蓡T是 結(jié)構(gòu)自身的指針類型 ，通過指針引用自身這種類型的結(jié)構(gòu)。 單鏈表基本算法 newnode infox info0 info1 單鏈表基本算法 帶表頭結(jié)構(gòu)的鏈表： 研究以上算法 ， 插在鏈表第一個結(jié)點(diǎn)之前與其他結(jié)點(diǎn)之前的算法有所不同 。 Node*head,*tail,*p。 //每輸入一個數(shù)申請一個結(jié)點(diǎn) pinfo=data。 //鏈尾加空指針 ， 表示鏈結(jié)束 return head。 //建立頭結(jié)點(diǎn) headlink=NULL。 //新結(jié)點(diǎn)放在原鏈表前方 headlink=p。amp。 4. 在單鏈表的 p結(jié)點(diǎn)后插入 ： 注意只有一種情況。 plink=q。 delete q。//前向引用聲明 templatetypename Tclass Node{ T info。 data)。 //以 List為友元類， List可直接訪問 Node的私有函數(shù) }。 //析構(gòu)函數(shù) void MakeEmpty()。 //打印鏈表 的數(shù)據(jù)域 void InsertFront(NodeT* p)。 //創(chuàng)建結(jié)點(diǎn) (孤立結(jié)點(diǎn) ) NodeT*DeleteNode(NodeT* p)。 清空該表 ， 再按升序生成鏈表并輸出 。 定義復(fù)制構(gòu)造函數(shù)與類的實(shí)際意義和使用方式有關(guān)，并非只是深復(fù)制和淺復(fù)制的問題 。 } link域值為 NULL。如要找前驅(qū)，必須從表頭開始搜索。 info0 infon1 .’.’.’.’.’.’ info1 head (a) 非空表 head (b)空表 雙向鏈表（選讀） 雙向鏈表的訪問： 假設(shè)指針 p指向雙向循環(huán)鏈表的某一個結(jié)點(diǎn)，那么， pllink指示 P所指結(jié)點(diǎn)的 前驅(qū)結(jié)點(diǎn) ， prlink指示 后繼結(jié)點(diǎn)。 7. 3. 1 棧 7. 3. 3 隊 列 7. 3. 2 棧的應(yīng)用（選讀） 棧 棧的基本概念： 棧定義為只允許在表的一端進(jìn)行插入和刪除的線性表 。而出棧時順序相反，最后進(jìn)棧的最先出棧，而最先進(jìn)棧的最后出棧。進(jìn)棧時最先進(jìn)棧的 a0在最下面， an1在最上面。通常只有棧頂與操作有關(guān)。 //棧最大容納的元素個數(shù) public: Stack(int=20)。 //壓棧 T Pop()。} //判棧空 bool IsFull() const{return top==maxSize1。 Stackint istack(10)。 if(()) cout棧滿 endl。i++) b[i]=()。i++) coutb[i]39。 //下溢出 } 棧 【 例 】 鏈棧的 結(jié)點(diǎn) 類模板： templatetypename Tclass Node{ //鏈棧結(jié)點(diǎn)類模板 T info。 } friend class StackT。} ~Stack()。 //彈出 T GetTop()。 棧的應(yīng)用（選讀） 順序棧和鏈棧邏輯功能是一樣，盡管這里兩個棧模板的成員函數(shù)功能選擇稍有出入，因為 順序?？梢噪S機(jī)訪問其中的元素 ， 而鏈棧只能順序訪問， 但邏輯上完全可以做到一樣（物