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