【正文】 為棧頂。} //清空棧 bool IsEmpty() const{return top== 1。i10。 //壓棧 T Pop()。棧中數(shù)據(jù)繼續(xù)按前面規(guī)則出棧。允許插入的一端稱為 隊尾(rear)，允許刪除的一端叫做 隊頭 (front)。除根以外的其它結點劃分為 m（ m≥0）個互不相交的有限集合 T0， T1， …… ， Tm1，每個集合又是一棵樹，稱為根的子樹（ subtree）。 二叉樹的特點是：每個結點最多兩個孩子 ， 并且子樹有左右之分 。} //取得結點數(shù)據(jù) void setinfo(const T amp。 templatetypename Tclass BinaryTree{ NodeT *root。 A B C D E F G H I J K 圖 例 按同樣 方法推出 A的右子樹。 排序二叉樹 （選讀） 排序二叉樹（選讀） templatetypenameTNodeT* BinaryTreeT::Find(const T amp。//釋放 pc所指向的 n個字符的內存空間 return 0。i++) for (j=0。}。 //動態(tài)建立數(shù)組 ， 不能初始化 ， 調用 n次默認構造函數(shù) …… delete pc。 if(pName) pName[0]=39。} template typename T NodeT::Node(const T amp。 } //刪除 (釋放 )脫離下來的結點 tail=head。} templatetypename Tvoid ListT::InsertFront(NodeT *p){ plink=headlink。amp。 (P1)。 (P1)。name39。 例 學生檔案的管理 注意，鏈表類定義中輸出函數(shù) PrintList()改寫為：templatetypename Tvoid ListT::PrintList(){ NodeT* tempP=headlink。m39。 ()。 friend class DblListT。 //刪除定結點 void Print()。//前驅 (左鏈 )、后繼 (右鏈 )指針 public: DblNode(T data)。 cinj。w39。 math39。 bool operator(student ele){return id。 ()。i16。} templatetypename T NodeT* ListT::CreatNode(T data){ NodeT*tempP=new NodeT(data)。 while(tempP!=NULL){ couttempPinfo39。 } templatetypename Tvoid ListT::MakeEmpty(){//清空鏈表 NodeT *tempP。 student s4=s1。 if(){ if(pName=new char[strlen()+1]) strcpy(pName,)。 //調用三參數(shù)構造函數(shù) pc1=new CGoods()。 int Amount。 //建立各行 if (data[j] == 0){ cout Could not allocate. Bye ...。 //在運行時確定，可輸入 25 pc=new char[n]。要 生成二叉排序樹 的過程為： 1. 令 a0為二叉樹的根結點。} //中序遍歷，公有函數(shù)為接口 void PreOrder(){PreOrder(root)。 二叉樹的遍歷（選讀） 【 例 】 二叉樹類模板 （ 其中二叉樹生成借用二叉排序樹 ，見下節(jié) ） 。} Node(T data,NodeT *left=NULL , NodeT *right=NULL){ info=data。 樹的度 ，樹中結點度的最大值。 二叉樹（選讀） 樹形結構是一類重要的非線性數(shù)據(jù)，樹和二叉樹是常用的樹形結構。 //讀算式 void Clear(void)。 棧的使用 (表達式運算 ) ： N c b a ＊ ＋ O ＊ ＋ a t1 d e N a t1 d e ＋ ＋ ／ － O ／ － － ＋ O － ＋ N t1 a t2 t1 a t2 t3 a N t3 a N ＋ O ＋ O b*ct1 d/et2 t1t2t3 a+t3t4 N：數(shù)棧 O：運算符 (a) (b) (c) (d) (e) 設有： a+b*cd/e=；參見上圖。 //棧頂指針 public: Stack(){top=NULL。i10。data)。 進棧時最先進棧的在最下面，最后的在最上面，后來居上。 link=NULL。 //計算 單鏈表長度 void PrintList()。 定義結點類： templatetypename Tclass List。 while(p!=NULLamp。 while(cindata){ //Ctrl+z結束 p=new(node)。 單鏈表基本算法 雙向鏈表 (選讀 ) 單鏈表基本算法 單鏈表 （ Singly Linked list） ： 每個數(shù)據(jù)元素占用一個結點 （ Node） 。 //復制賦值操作符 檢驗 主函數(shù) 和 運行結果 淺復制與深復制 提示： 自由存儲區(qū)內存是最常見的需要自定義復制構造函數(shù)的資源，但不是唯一的，還有打開文件等也需要自定義復制構造函數(shù)。 obj1 obj1 obj2 淺復制與深復制復制 當 淺復制 析構時，如用默認的析構函數(shù)，則動態(tài)分配的 自由存儲區(qū) 對象不能回收。 無名對象的生命期并不依賴于建立它的作用域，比如在函數(shù)中建立的動態(tài)對象在函數(shù)返回后仍可使用 。 //刪除（釋放）三維數(shù)組 delete [] bp。 內存的分配與釋放 動態(tài)分配數(shù)組與 標準字符串類 ： 標準字符串類 string就是采用動態(tài)建立數(shù)組的方式解決數(shù)組溢出的問題的，例 ，在 string類對象中都是自動完成的，在程序中不需要也不允許再顯式地為 string進行動態(tài)內存的分配與釋放。對所創(chuàng)建的變量或對象，都是通過該指針來間接操作的，而 動態(tài)創(chuàng)建的對象本身沒有名字。尤其是數(shù)組。 內存的分配與釋放 數(shù)組動態(tài)分配格式： 指針變量名 =new 類型名 [下標表達式 ]。這與數(shù)組的嵌套定義相一致。程序員無需顯式聲明它為靜態(tài)的，系統(tǒng)自動定義為靜態(tài)的。 類對象初始化： new后面類（ class）類型可以有參數(shù)。 //帶參數(shù) 構造函數(shù) student(student amp。在需要時可以無條件地安全使用。 在 C/C++中允許結構（或對象）成員是 結構自身的指針類型 ，通過指針引用自身這種類型的結構。 單鏈表基本算法 帶表頭結構的鏈表： 研究以上算法 ， 插在鏈表第一個結點之前與其他結點之前的算法有所不同 。 //建立頭結點 headlink=NULL。 plink=q。 //以 List為友元類， List可直接訪問 Node的私有函數(shù) }。 清空該表 ， 再按升序生成鏈表并輸出 。 info0 infon1 .’.’.’.’.’.’ info1 head (a) 非空表 head (b)空表 雙向鏈表（選讀） 雙向鏈表的訪問： 假設指針 p指向雙向循環(huán)鏈表的某一個結點，那么， pllink指示 P所指結點的 前驅結點 ， prlink指示 后繼結點。通常只有棧頂與操作有關。 Stackint istack(10)。 //下溢出 } 棧 【 例 】 鏈棧的 結點 類模板： templatetypename Tclass Node{ //鏈棧結點類模板 T info。 棧的應用（選讀） 順序棧和鏈棧邏輯功能是一樣，盡管這里兩個棧模板的成員函數(shù)功能選擇稍有出入，因為 順序棧可以隨機訪問其中的元素 ， 而鏈棧只能順序訪問， 但邏輯上完全可以做到一樣（物理結構不同） 。 //使用鏈棧 Stackchar Ostack。 順序表隊列的缺點： 隊列 順序表隊列的改進： 邏輯上的循環(huán)隊列 注意，空隊時 rear=front，滿隊時必須空一個位置 隊列 循環(huán)隊列 浪費一個位置好像太可惜，特別在該位置中存放一個很大的對象時。 葉結點 ， 度為 0的結點 ，如 G， I， J， K， L，M， N， O結點 。 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 圖 完全二叉樹 二叉樹的概念（選讀） 下面給出鏈式儲存方式的二叉樹。} //設置左指針 void setrightNodeT *right){rchild=right。data,NodeT * amp。 再由先序 C E F知 C為左子樹根結點，由中序 E C F知 E為 C左子樹，F(xiàn)為的右子樹。 } } return NULL。 int i,j。 return 0。 Total_value=price*amount。 pName=NULL。s){ coutCopy Assign operator。 } templatetypename TNodeT* NodeT::RemoveAfter(){ NodeT* tempP=link。 return tempP。 tail=p。 Listint list1,list2。 cinj。char sex。\t39。 例 學生檔案的管理 int main(){ const int h=4。 (P1)。ih。 rlink=NULL。 public: DblList()。 (P1)。 (P1)。 Nodestudent * P1。\t39。string address。 if(P1!=NULL){ P1=(P1)。 cout請輸入 16個整數(shù) endl。 //tempQ指向 tempP前面的一個結點 while(tempP!=NULL){ if(pinfotempPinfo)break。 int count=0。 //已在鏈尾 ,后面無結點 else link=tempPlink。//如原來已分配，應先撤銷，再重分配 if(){ //否則會發(fā)生內存泄漏 if(pName=new char[strlen()+1]) strcpy(pName,)。 } 帶參數(shù) 構造函數(shù)： student::student(char *pname){ coutConstructor。} }。 for (i=0。 //建立指向組成二維數(shù)組各行的指針數(shù)組 if ((data ) == 0){ cout Could not allocate. Bye ...。 算法：用中序遍歷即可，但遞歸慢，下面為迭代查找算法。 排序二叉樹 （選讀） 二叉排序樹 （ Binary Sorting Tree） 又稱二叉搜索樹 （ Binary Search Tree） ， 是一種特殊結構的二叉數(shù) ，作為一種排序和查找的手段 ， 對應有序表的對半查找 ，通常亦被稱為數(shù)表 。 //插入結點 ， 參數(shù)為引用！ void