【正文】 L。 while(cindata){ //Ctrl+z結束 p=new(node)。 head=new node。 while(p!=NULLamp。 qlink=plink。 定義結點類： templatetypename Tclass List。 //刪除當前結點的后繼 結點 friend class ListT。 //計算 單鏈表長度 void PrintList()。 然后給出一個整數在一個鏈表中查找 ， 找到后刪除它 ， 再輸出該表 。 link=NULL。雙向 鏈表經常采用 帶頭結點的循環(huán)鏈表方式 。 進棧時最先進棧的在最下面，最后的在最上面，后來居上。其中棧底 bottom是指向棧數據區(qū)的下一單元，這樣判斷是否為空棧會更方便，只需 top與 bottom相同就是空棧。data)。 //輸出 棧內所有數據 【 例 】 順序棧的類模板： 棧 void main(){ int i,a[10]={0,1,2,3,4,5,6,7,8,9},b[10]。i10。 ()。 //棧頂指針 public: Stack(){top=NULL。} }。 棧的使用 (表達式運算 ) ： 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：數棧 O：運算符 (a) (b) (c) (d) (e) 設有： a+b*cd/e=；參見上圖。 簡易計算器類定義： class Calculator{ Stackint Nstack。 //讀算式 void Clear(void)。 隊列 rear front A D C A B D E C F H G BCD進隊 A進隊 空隊 D C AB出隊 EFGH進隊 rear front rear rear rear front front front 圖 順序隊列的插入和刪除 由圖可見：空隊時指針（下標）front和 rear在一起都指向隊前方，當有元素進隊，則 rear后移；有元素出隊，則 front后移，最后分配給隊的前端不再被利用。 二叉樹（選讀） 樹形結構是一類重要的非線性數據，樹和二叉樹是常用的樹形結構。 結點的度 ， 結點所擁有的子樹數量 。 樹的度 ，樹中結點度的最大值。 圖 5種不同的三結點二叉樹 二叉樹的概念（選讀） 滿二叉樹和完全二叉樹： 分別如圖 ，完全二叉樹已有的結點排序與滿二叉樹相同。} Node(T data,NodeT *left=NULL , NodeT *right=NULL){ info=data。} //取得右子樹 void setleft(NodeT *left){lchild=left。 二叉樹的遍歷（選讀） 【 例 】 二叉樹類模板 （ 其中二叉樹生成借用二叉排序樹 ，見下節(jié) ） 。 //后序遍歷 void Insert(const T amp。} //中序遍歷，公有函數為接口 void PreOrder(){PreOrder(root)。由先序中的 B C E F D G知 B為左子樹根結點，由中序中的 E C F B D G知 E C F為其左子樹，而 DG為右子樹。要 生成二叉排序樹 的過程為： 1. 令 a0為二叉樹的根結點。 else temp=templchild。 //在運行時確定，可輸入 25 pc=new char[n]。 //行數與列數 二維數組的動態(tài)創(chuàng)建： int main(){ double **data。 //建立各行 if (data[j] == 0){ cout Could not allocate. Bye ...。//略 de_allocate(data)。 int Amount。 Price=price。 //調用三參數構造函數 pc1=new CGoods()。} 例 實現深復制 默認構造函數： student::student(){ coutConstructor。 if(){ if(pName=new char[strlen()+1]) strcpy(pName,)。 student::operator=(student amp。 student s4=s1。 link=p。 } templatetypename Tvoid ListT::MakeEmpty(){//清空鏈表 NodeT *tempP。tempPinfo!=data) tempP=tempPlink。 while(tempP!=NULL){ couttempPinfo39。 taillink=p。} templatetypename T NodeT* ListT::CreatNode(T data){ NodeT*tempP=new NodeT(data)。 } //本函數所用方法可省一個工作指針，與 InsertOrder比較 例 單鏈表類型模板 例 單鏈表類型模板主函數 void main(){ Nodeint * P1。i16。 例 單鏈表類型模板主函數 cout請輸入一個要求刪除的整數 endl。 ()。string name。 bool operator(student ele){return id。 age39。 math39。 } 在 student類中采用 show()函數是一個無奈的選擇，因為插入運算符 的重載在 ，那時就不需要改寫PrintList()，而在 student類中重載插入運算符 。w39。i++){ P1=(n[i])。 cinj。 //清空 list1 for(i=0。//前驅 (左鏈 )、后繼 (右鏈 )指針 public: DblNode(T data)。 //一般結點 llink=NULL。 //刪除定結點 void Print()。 //建立表頭結點 ~DblList()。 friend class DblListT。 } //升序創(chuàng)建 list1 ()。 ()。 } //向后生成 list2 ()。m39。 Liststudent list1,list2。 例 學生檔案的管理 注意，鏈表類定義中輸出函數 PrintList()改寫為：templatetypename Tvoid ListT::PrintList(){ NodeT* tempP=headlink。eng39。name39。 float eng, phy, math, electron。 (P1)。 delete P1。 (P1)。 for(i=0。amp。 //找第一個比插入結點大的結點，由 tempP指向 tempQ=tempP。} templatetypename Tvoid ListT::InsertFront(NodeT *p){ plink=headlink。 while(tempP!=NULL){ tempP=tempPlink。 } //刪除 (釋放 )脫離下來的結點 tail=head。 return tempP。} template typename T NodeT::Node(const T amp。} else pName=NULL。 if(pName) pName[0]=39。 if(pName=new char[strlen(pname)+1]) strcpy(pName,pname)。 //動態(tài)建立數組 ， 不能初始化 ， 調用 n次默認構造函數 …… delete pc。 【 例 】 演示自由存儲區(qū)對象分配和釋放。}。im。i++) for (j=0。 return 1。//釋放 pc所指向的 n個字符的內存空間 return 0。 第七章 動態(tài)內存分配與數據結構 完 謝謝！ 內存的分配與釋放 【 例 】 【 例 】 動態(tài)數組的建立與撤銷 include iostream include cstring using namespace std； int main(){ int n。 排序二叉樹 （選讀） 排序二叉樹（選讀） templatetypenameTNodeT* BinaryTreeT::Find(const T amp。 其定義也是遞歸的 。 A B C D E F G H I J K 圖 例 按同樣 方法推出 A的右子樹。 //刪除樹 二叉樹的遍歷（選讀） public: BinaryTree(){root=NULL。 templatetypename Tclass BinaryTree{ NodeT *root。 所謂 “ 訪問 ” 指對結點施行某些操作 ， 但不破壞它原來的數據結構 。} //取得結點數據 void setinfo(const T amp。 templatetypename Tclass Node{ NodeT *lchild,*rchild。 二叉樹的特點是：每個結點最多兩個孩子 ， 并且子樹有左右之分 。 樹的術語： 二叉樹的概念（選讀） A B C D E F G I H J L K O N M ………… 0層 …… 1層 2層 3層 深度 圖 樹的示意圖 雙親結點 ， 若結點 x有孩子 ， 它即為孩子的雙親 。除根以外的其它結點劃分為 m（ m≥0）個互不相交的有限集合 T0， T1， …… ， Tm1，每個集合又是一棵樹，稱為根的子樹（ subtree）。 用鏈表實現隊列無此問題 【 例 】 順序存儲方式的循環(huán)隊列類模板 。允許插入的一端稱為 隊尾(rear)，允許刪除的一端叫做 隊頭 (front)。 //計算器運算程序 void GetTwoNum(int amp。棧中數據繼續(xù)按前面規(guī)則出棧。 順序棧和鏈棧比較： 棧的應用（選讀） ?？捎糜?表達式的計算 。 //壓棧 T Pop()。 link=next。i10。i++) (a[i])。} //清空棧 bool IsEmpty() const{return top== 1。 //動態(tài)建立的元素 int maxSize。 棧 棧的基本操作： 參見下圖，設給定棧 s=(a0， a1， …… ， an1)，稱 a0為棧底， an1為棧頂。 棧與隊列的基本操作及其應用 棧和隊都是特殊的線性表， 限制存取位置 的線性結構，可以由順序表實現，也可以由鏈表實現。 雙向鏈表（選讀） 雙向鏈表引入： 考慮單鏈表只能找后繼。 單鏈表類型模板 討論復制構造函數： 在本例中沒有給出 Node類的復制構造函數，并非可以使用默認的復制構造函數