【正文】 理結(jié)構(gòu)不同） ?，F(xiàn)考慮最簡單的 +、 、 *、 /四個運算符和結(jié)束符＝組成的算術(shù)表達式，只有 兩個優(yōu)先級 ，先 */，后 +。 從左向右掃描算術(shù)表達式 ，遇到 操作數(shù) ， 壓入數(shù)棧 ；遇到 運算符 ，則 與運算符棧棧頂?shù)倪\算符比較優(yōu)先級 ，若新的運算符優(yōu)先級高，或運算符棧空，則壓棧。 棧的應用（選讀） 【 例 】 模擬簡單計算器 ， 該計算器只認 + * / 四個運算符 ，輸入為整數(shù) 。 //使用鏈棧 Stackchar Ostack。Num1,int amp。 }。每次在隊尾加入新元素，加入稱為 進隊 ，刪除稱為 出隊 。 順序表隊列的缺點： 隊列 順序表隊列的改進： 邏輯上的循環(huán)隊列 注意，空隊時 rear=front，滿隊時必須空一個位置 隊列 循環(huán)隊列 浪費一個位置好像太可惜，特別在該位置中存放一個很大的對象時。 【 例 】 鏈隊類模板。 二叉樹的遍歷 二叉樹的概念 排序二叉樹 二叉樹的概念 （選讀） 樹（ Tree） 是由 n（ n≥0）個結(jié)點組成的有限集合。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有 0個或多個直接后繼。 葉結(jié)點 ， 度為 0的結(jié)點 ，如 G， I， J， K， L，M， N， O結(jié)點 。 兄弟結(jié)點 ， 同一雙親的結(jié)點互稱為兄弟 。 樹的術(shù)語： 二叉樹的概念（選讀） 二叉樹 （ Binary Tree） 是另一種獨立的樹形結(jié)構(gòu) 。 二叉樹的基本性質(zhì)： 1．二叉樹的第 i層上最多有 2i1(i=1)個結(jié)點； 2．深度為 h的二叉樹中最多有 2h1個結(jié)點； 3．在任一棵二叉樹中，有 n0個葉子結(jié)點，有 n2個度為 2的 結(jié)點，則有 n0=n2+1。 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 圖 完全二叉樹 二叉樹的概念（選讀） 下面給出鏈式儲存方式的二叉樹。 T info。 lchild=left。data){info=data。} //設置左指針 void setrightNodeT *right){rchild=right。 遍歷二叉樹有不同次序，規(guī)定先左后右，令 L， R， V分別代表遍歷一個結(jié)點的左右子樹和訪問該結(jié)點的操作，有三種方式： 前序遍歷（ VLR） 中序遍歷（ LVR） 后序遍歷（ LRV） 二叉樹的遍歷（選讀） 遍歷實 例： 前序遍歷訪問次序為 ABDEGCFH。 特別注意插入結(jié)點時 ， 第二參數(shù)為指針的引用 ！否則不能建立樹 。 //二叉樹的根指針 void InOrder(NodeT *Current)。data,NodeT * amp。} //空樹構(gòu)造函數(shù) ~BinaryTree(){Destory(root)。} //前序遍歷，公有函數(shù)為接口 void PostOrder(){PostOrder(root)。結(jié)果如圖 。 再由先序 C E F知 C為左子樹根結(jié)點，由中序 E C F知 E為 C左子樹，F(xiàn)為的右子樹。 二叉排序樹的定義： 二叉排序樹或者是空樹或者是具有下述性質(zhì)的二叉數(shù)，其左子樹上所有結(jié)點的數(shù)據(jù)值均小于根結(jié)點的數(shù)據(jù)值；右子樹上所有結(jié)點的數(shù)據(jù)值均大于等于根結(jié)點的數(shù)據(jù)值，左子樹和右子樹又各是一棵二叉排序樹。 2. 若 a1a0，令 a1為 a0左子樹的根結(jié)點，否則 a1為 a0右子樹的根結(jié)點。data,NodeT *b){ if(b!=NULL){ NodeT *temp=b。 } } return NULL。 char *pc。 strcpy(pc, 自由存儲區(qū)內(nèi)存的動態(tài)分配 )。 } 內(nèi)存的分配與釋放 【 例 】 【 例 】 動態(tài)創(chuàng)建和刪除一個 m*n個元素的數(shù)組。 int i,j。 } for(j=0。 return 1。jn。 return 0。i++) delete[] data[i]。 float Price。 CGoods(string name,int amount ,float price){ cout調(diào)用三參數(shù)構(gòu)造函數(shù) endl。 Total_value=price*amount。 對象與構(gòu)造函數(shù) 【 例 】 使用： int main(){ int n。 //調(diào)用默認構(gòu)造函數(shù) cout’輸入商品類數(shù)組元素數(shù) ’ endl。 delete pc1。 pName=NULL。 coutpNameendl。 } else pName=NULL。\039。s){ coutCopy Assign operator。 coutpNameendl。 s3=s2。 data){ info=data。 } templatetypename TNodeT* NodeT::RemoveAfter(){ NodeT* tempP=link。 } 例 單鏈表類型模板 鏈表類成員函數(shù)： templatetypename TListT::List(){ head=tail=new NodeT()。 while(headlink!=NULL){ tempP=headlink。 } //表頭指針與表尾指針均指向表頭結(jié)點，表示空鏈 例 單鏈表類型模板 鏈表類成員函數(shù)： templatetypename T NodeT* ListT::Find(T data){ NodeT *tempP=headlink。 return tempP。count++。\t39。 headlink=p。 tail=p。 tempP=tempPlink。 return tempP。tempPlink!=p) tempP=tempPlink。 Listint list1,list2。i16。i++){ P1=(a[i])。 } //向后生成 list2 ()。 cinj。 ()。 //清空 list1 for(i=0。 } //升序創(chuàng)建 list1 ()。char sex。 //英語，物理，數(shù)學和電子學成績 public: student(int=0,string=,char=39。} bool operator!=(student ele){return id!=。\t39。\t39。\t39。\t39。 while(tempP!=NULL){ tempP()。 例 學生檔案的管理 int main(){ const int h=4。 student n[h]={ student(6004327,張菲 ,39。,19,天津路 64號 ,88,75,91,68), student(6004118,劉蓓 ,39。,18,重慶路 95號 ,78,95,81,88),}。 (P1)。 例 學生檔案的管理 coutlist1長度： ()endl。 P1=(j)。 coutlist1長度： ()endl。ih。 return 0。 //生成一般結(jié)點的構(gòu)造函數(shù) DblNode()。}。 rlink=NULL。 void Insert(const T amp。 //打印鏈表 int Length()。 //鏈尾插入 DblNodeT* Remove(DblNodeT* p)。 public: DblList()。} templatetypename T DblNodeT::DblNode(T data){ info=data。}。 //數(shù)據(jù)域 DblNodeT *llink,*rlink。 (P1)。 ()。 delete P1。 cout請輸入一個要求刪除的學生學號 endl。 (P1)。ih。,18,上海路 37號 ,78,95,81,88), student(6004219,趙昀 ,39。,19,北京路 58號 ,80,85,90,78), student(6004121,關(guān)雨 ,39。 Nodestudent * P1。 } coutendl。} }。\t39。\t39。\t39。\t39。,int=0,string=, float=,float=,float=,float=)。string address。} 例 學生檔案的管理 include class student{ int id 。i++){ P1=(a[i])。 } else cout未找到 endl。 if(P1!=NULL){ P1=(P1)。 ()。 //向前生成 list1 P1=(a[i])。 //隨機輸入 16個整數(shù) for(i=0。 cout請輸入 16個整數(shù) endl。 return tempPRemoveAfter()。 while(tempPlink!=NULLamp。 //插在 tempP指向結(jié)點之前， tempQ之后 if(tail==tempQ) tail=tempQlink。 //tempQ指向 tempP前面的一個結(jié)點 while(tempP!=NULL){ if(pinfotempPinfo)break。} templatetypename Tvoid ListT::InsertRear(NodeT *p){ plink=taillink。 } coutendl。 } 例 單鏈表類型模板 鏈表類成員函數(shù)： templatetypename Tvoid ListT::PrintList(){//顯示鏈表 NodeT* tempP=headlink。 int count=0。amp。 //把頭結(jié)點后的第一個結(jié)點從鏈中脫離 delete tempP。 delete head。 //已在鏈尾 ,后面無結(jié)點 else link=tempPlink。 } templatetypename T void NodeT::InsertAfter(NodeT* p){ plink=link。} 例 實現(xiàn)深復制 例 單鏈表類型模板 template typename T NodeT::Node(){ link=NULL。} int main(void){ student s1(范英明 ),s2(沈俊 ),s3。//如原來已分配，應先撤銷，再重分配 if(){ //否則會發(fā)生內(nèi)存泄漏 if(pName=new char[strlen()+1]) strcpy(pName,)。} //釋放字符串 例 實現(xiàn)深復制 復制賦值操作符： student amp。} 析構(gòu)函數(shù)： student::~student(){ coutDestructorpNameendl。s){ coutCopy Constructor。 } 帶參數(shù) 構(gòu)造函數(shù)： student::student(char *pname){ coutConstructor。 return 0。 pc2=new CGoods[n]。 pc=new CGoods(“夏利 2021”， 10， 118000)。} }。 Amount=amount。 public: CGoods(){cout調(diào)用默認構(gòu)造函數(shù) endl。 } 對象與構(gòu)造函數(shù) 【 例 】 類說明： class CGoods{ string Name。 for (i=0。 //數(shù)組元素賦值 display(data)。im。j++){ data[j] = new double[n]。 //建立指向組成二維數(shù)組各行的指針數(shù)組 if ((data ) == 0){ cout Co