【正文】 //清空鏈表 //其它操作 }。 //刪除定結(jié)點(diǎn) void Print()。 //建立表頭結(jié)點(diǎn) ~DblList()。 //頭結(jié)點(diǎn) llink=NULL。 friend class DblListT。//前驅(qū) (左鏈 )、后繼 (右鏈 )指針 public: DblNode(T data)。 } //升序創(chuàng)建 list1 ()。 //清空 list1 for(i=0。 ()。 cinj。 } //向后生成 list2 ()。i++){ P1=(n[i])。m39。w39。 Liststudent list1,list2。 } 在 student類中采用 show()函數(shù)是一個無奈的選擇，因?yàn)椴迦脒\(yùn)算符 的重載在 ，那時就不需要改寫PrintList()，而在 student類中重載插入運(yùn)算符 。 例 學(xué)生檔案的管理 注意，鏈表類定義中輸出函數(shù) PrintList()改寫為：templatetypename Tvoid ListT::PrintList(){ NodeT* tempP=headlink。phy39。address39。\t39。} bool operator!=(student ele){return id!=。 //英語，物理，數(shù)學(xué)和電子學(xué)成績 public: student(int=0,string=,char=39。char sex。 } //升序創(chuàng)建 list1 ()。//清空 list1 for(i=0。 ()。 cinj。 } //向后生成 list2 ()。i++){ P1=(a[i])。i16。 Listint list1,list2。tempPlink!=p) tempP=tempPlink。 return tempP。 tempP=tempPlink。 tail=p。 headlink=p。\t39。count++。 return tempP。 } //表頭指針與表尾指針均指向表頭結(jié)點(diǎn)，表示空鏈 例 單鏈表類型模板 鏈表類成員函數(shù)： templatetypename T NodeT* ListT::Find(T data){ NodeT *tempP=headlink。 while(headlink!=NULL){ tempP=headlink。 } 例 單鏈表類型模板 鏈表類成員函數(shù)： templatetypename TListT::List(){ head=tail=new NodeT()。 } templatetypename TNodeT* NodeT::RemoveAfter(){ NodeT* tempP=link。 data){ info=data。 s3=s2。 coutpNameendl。s){ coutCopy Assign operator。\039。 } else pName=NULL。 coutpNameendl。 pName=NULL。 delete pc1。 //調(diào)用默認(rèn)構(gòu)造函數(shù) cout’輸入商品類數(shù)組元素?cái)?shù) ’ endl。 對象與構(gòu)造函數(shù) 【 例 】 使用： int main(){ int n。 Total_value=price*amount。 CGoods(string name,int amount ,float price){ cout調(diào)用三參數(shù)構(gòu)造函數(shù) endl。 float Price。i++) delete[] data[i]。 de_allocate(data)。i++) for (j=0。 //設(shè)置列 if (data[j] == 0){ cout Could not allocate. Bye ...。 return 1。 //列數(shù) 二維數(shù)組的動態(tài)創(chuàng)建： int main(){ double **data。 } 內(nèi)存的分配與釋放 【 例 】 【 例 】 動態(tài)創(chuàng)建和刪除一個 m*n個元素的數(shù)組。 strcpy(pc,“自由存儲區(qū)內(nèi)存的動態(tài)分配 )。 char *pc。 } } return NULL。data,NodeT *b){ if(b!=NULL){ NodeT *temp=b。 2. 若 a1a0，令 a1為 a0左子樹的根結(jié)點(diǎn)，否則 a1為 a0右子樹的根結(jié)點(diǎn)。 二叉排序樹的定義： 二叉排序樹或者是空樹或者是具有下述性質(zhì)的二叉數(shù)，其左子樹上所有結(jié)點(diǎn)的數(shù)據(jù)值均小于根結(jié)點(diǎn)的數(shù)據(jù)值；右子樹上所有結(jié)點(diǎn)的數(shù)據(jù)值均大于等于根結(jié)點(diǎn)的數(shù)據(jù)值，左子樹和右子樹又各是一棵二叉排序樹。 再由先序 C E F知 C為左子樹根結(jié)點(diǎn)，由中序 E C F知 E為 C左子樹，F(xiàn)為的右子樹。結(jié)果如圖 。} //前序遍歷，公有函數(shù)為接口 void PostOrder(){PostOrder(root)。} //空樹構(gòu)造函數(shù) ~BinaryTree(){Destory(root)。data,NodeT * amp。 //二叉樹的根指針 void InOrder(NodeT *Current)。 特別注意插入結(jié)點(diǎn)時 ， 第二參數(shù)為指針的引用 ！否則不能建立樹 。 遍歷二叉樹有不同次序，規(guī)定先左后右，令 L， R， V分別代表遍歷一個結(jié)點(diǎn)的左右子樹和訪問該結(jié)點(diǎn)的操作，有三種方式： 前序遍歷（ VLR） 中序遍歷（ LVR） 后序遍歷（ LRV） 二叉樹的遍歷（選讀） 遍歷實(shí) 例： 前序遍歷訪問次序?yàn)?ABDEGCFH。} //設(shè)置左指針 void setrightNodeT *right){rchild=right。data){info=data。 lchild=left。 T info。 1 2 3 4 5 6 7 9 8 10 11 14 13 12 15 圖 滿二叉樹 1 2 3 4 5 6 7 9 8 10 圖 完全二叉樹 二叉樹的概念（選讀） 下面給出鏈?zhǔn)絻Υ娣绞降亩鏄洹? 二叉樹的基本性質(zhì)： 1．二叉樹的第 i層上最多有 2i1(i=1)個結(jié)點(diǎn)； 2．深度為 h的二叉樹中最多有 2h1個結(jié)點(diǎn)； 3．在任一棵二叉樹中，有 n0個葉子結(jié)點(diǎn)，有 n2個度為 2的 結(jié)點(diǎn)，則有 n0=n2+1。 樹的術(shù)語： 二叉樹的概念（選讀） 二叉樹 （ Binary Tree） 是另一種獨(dú)立的樹形結(jié)構(gòu) 。 兄弟結(jié)點(diǎn) ， 同一雙親的結(jié)點(diǎn)互稱為兄弟 。 葉結(jié)點(diǎn) ， 度為 0的結(jié)點(diǎn) ，如 G， I， J， K， L，M， N， O結(jié)點(diǎn) 。每棵子樹的根結(jié)點(diǎn)有且僅有一個直接前驅(qū)，但可以有 0個或多個直接后繼。 二叉樹的遍歷 二叉樹的概念 排序二叉樹 二叉樹的概念 （選讀） 樹（ Tree） 是由 n（ n≥0）個結(jié)點(diǎn)組成的有限集合。 【 例 】 鏈隊(duì)類模板。 順序表隊(duì)列的缺點(diǎn)： 隊(duì)列 順序表隊(duì)列的改進(jìn)： 邏輯上的循環(huán)隊(duì)列 注意，空隊(duì)時 rear=front，滿隊(duì)時必須空一個位置 隊(duì)列 循環(huán)隊(duì)列 浪費(fèi)一個位置好像太可惜，特別在該位置中存放一個很大的對象時。每次在隊(duì)尾加入新元素，加入稱為 進(jìn)隊(duì) ，刪除稱為 出隊(duì) 。 }。Num1,int amp。 //使用鏈棧 Stackchar Ostack。 棧的應(yīng)用（選讀） 【 例 】 模擬簡單計(jì)算器 ， 該計(jì)算器只認(rèn) + * / 四個運(yùn)算符 ，輸入為整數(shù) 。 從左向右掃描算術(shù)表達(dá)式 ，遇到 操作數(shù) ， 壓入數(shù)棧 ；遇到 運(yùn)算符 ，則 與運(yùn)算符棧棧頂?shù)倪\(yùn)算符比較優(yōu)先級 ，若新的運(yùn)算符優(yōu)先級高，或運(yùn)算符?？眨瑒t壓?！，F(xiàn)考慮最簡單的 +、 、 *、 /四個運(yùn)算符和結(jié)束符＝組成的算術(shù)表達(dá)式，只有 兩個優(yōu)先級 ，先 */，后 +。 棧的應(yīng)用（選讀） 順序棧和鏈棧邏輯功能是一樣，盡管這里兩個棧模板的成員函數(shù)功能選擇稍有出入，因?yàn)?順序?？梢噪S機(jī)訪問其中的元素 ， 而鏈棧只能順序訪問， 但邏輯上完全可以做到一樣（物理結(jié)構(gòu)不同） 。 //彈出 T GetTop()。} ~Stack()。 } friend class StackT。 //下溢出 } 棧 【 例 】 鏈棧的 結(jié)點(diǎn) 類模板： templatetypename Tclass Node{ //鏈棧結(jié)點(diǎn)類模板 T info。i++) coutb[i]39。i++) b[i]=()。 if(()) cout棧滿 endl。 Stackint istack(10)。} //判棧空 bool IsFull() const{return top==maxSize1。 //壓棧 T Pop()。 //棧最大容納的元素個數(shù) public: Stack(int=20)。通常只有棧頂與操作有關(guān)。進(jìn)棧時最先進(jìn)棧的 a0在最下面， an1在最上面。而出棧時順序相反，最后進(jìn)棧的最先出棧，而最先進(jìn)棧的 a0最后出棧。 7. 3. 1 棧 7. 3. 3 隊(duì) 列 7. 3. 2 棧的應(yīng)用（選讀） 棧 棧的基本概念： 棧定義為只允許在表的一端進(jìn)行插入和刪除的線性表 。 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)。如要找前驅(qū)，必須從表頭開始搜索。 } link域值為 NULL。 定義復(fù)制構(gòu)造函數(shù)與類的實(shí)際意義和使用方式有關(guān)，并非只是深復(fù)制和淺復(fù)制的問題 。 清空該表 ， 再按升序生成鏈表并輸出 。 //創(chuàng)建結(jié)點(diǎn) (孤立結(jié)點(diǎn) ) NodeT*DeleteNode(NodeT* p)。 //打印鏈表 的數(shù)據(jù)域 void InsertFront(NodeT* p)。 //析構(gòu)函數(shù) void MakeEmpty()。 //以 List為友元類， List可直接訪問 Node的私有函數(shù) }。 data)。 templatetypename Tclass Node{ T info。 delete q。 plink=q。 4. 在單鏈表的 p節(jié)點(diǎn)后插入 ： 注意只有一種情況。amp。 //新結(jié)點(diǎn)放在原鏈表前方 headlink=p。 //建立頭結(jié)點(diǎn) headlink=NULL。 //鏈尾加空指針 ， 表示鏈結(jié)束 return head。 //每輸入一個數(shù)申請一個結(jié)點(diǎn) pinfo=data。 Node*head,*tail,*p。 單鏈表基本算法 帶表頭結(jié)構(gòu)的鏈表： 研究以上算法 ， 插在鏈表第一個結(jié)點(diǎn)之前與其他結(jié)點(diǎn)之前的算法有所不同 。 單鏈表基本算法 newnode infox info0 info1 但結(jié)構(gòu)成員決不能是結(jié)構(gòu)自身類型 ，即結(jié)構(gòu)不能自己定義自己，這會導(dǎo)致一個無窮遞歸的定義。 //數(shù)據(jù)為整型 struct node{ Datatype info。而線性表的 物理結(jié)構(gòu) 包括：順序表， 鏈表 。這樣的類對象，作為另一個類的成員對象使用時，就不會出任何問題。 淺復(fù)制與深復(fù)制 探討： 最后進(jìn)一步討論類的封裝。 淺復(fù)制與深復(fù)制 思考： 深入地考慮 【 例 】 ，如果數(shù)據(jù)域還有很多其他數(shù)據(jù)，甚至有好幾個是動態(tài)建立的 C字符串，深復(fù)制是不是太復(fù)雜