【正文】 ， 其中左右子樹分別可以為空子樹或均為空樹 。 樹的度 ，樹中結(jié)點度的最大值。 結(jié)點的層次 ， 從根到該結(jié)點所經(jīng)路徑上的分支條數(shù) 。 樹的術(shù)語： 二叉樹的概念（選讀） A B C D E F G I H J L K O N M ………… 0層 …… 1層 2層 3層 深度 圖 樹的示意圖 雙親結(jié)點 ， 若結(jié)點 x有孩子 ， 它即為孩子的雙親 。 分支結(jié)點 ， 度 ≥1的結(jié)點 。 結(jié)點的度 ， 結(jié)點所擁有的子樹數(shù)量 。這是一個遞歸方法定義的數(shù)據(jù)結(jié)構(gòu)。除根以外的其它結(jié)點劃分為 m（ m≥0）個互不相交的有限集合 T0， T1， …… ， Tm1，每個集合又是一棵樹，稱為根的子樹（ subtree）。如 n=0，稱為空樹。 二叉樹（選讀） 樹形結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)，樹和二叉樹是常用的樹形結(jié)構(gòu)。鏈?zhǔn)壮鲫?，鏈尾入隊? 用鏈表實現(xiàn)隊列無此問題 【 例 】 順序存儲方式的循環(huán)隊列類模板 。實際上 對象很大時，總是由索引（指針）來排隊 。 隊列 rear front A D C A B D E C F H G BCD進(jìn)隊 A進(jìn)隊 空隊 D C AB出隊 EFGH進(jìn)隊 rear front rear rear rear front front front 圖 順序隊列的插入和刪除 由圖可見：空隊時指針（下標(biāo)）front和 rear在一起都指向隊前方，當(dāng)有元素進(jìn)隊，則 rear后移；有元素出隊，則 front后移，最后分配給隊的前端不再被利用。隊列的這種特性正好與棧相反，叫做 先進(jìn)先出 FIFO(First In First Out)。允許插入的一端稱為 隊尾(rear)，允許刪除的一端叫做 隊頭 (front)。 //清除 隊列 隊列的基本概念： 隊列 (Queue)也是一種限定存取位置的線性表。 //讀算式 void Clear(void)。Num2)。 //計算器運(yùn)算程序 void GetTwoNum(int amp。 public: Calculator(void){}。 簡易計算器類定義： class Calculator{ Stackint Nstack。 表達(dá)式結(jié)束符使用＝號 ， 清空棧用 ‘ c’字符 。棧中數(shù)據(jù)繼續(xù)按前面規(guī)則出棧。否則將棧頂運(yùn)算符出棧，與數(shù)字棧出棧的兩個數(shù)據(jù)進(jìn)行運(yùn)算，結(jié)果壓入數(shù)棧，再將新運(yùn)算符壓棧。 棧的使用 (表達(dá)式運(yùn)算 ) ： 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：運(yùn)算符 (a) (b) (c) (d) (e) 設(shè)有： a+b*cd/e=；參見上圖。 為實現(xiàn)運(yùn)算符的優(yōu)先級，采用兩個棧：一個 數(shù)棧 ，一個 運(yùn)算符棧 。 順序棧和鏈棧比較： 棧的應(yīng)用（選讀） ?？捎糜?表達(dá)式的計算 。順序棧必須先開一定大小內(nèi)存空間，執(zhí)行起來簡單，速度快，可能溢出。} }。 //取棧頂元素 void MakeEmpty()。 //壓棧 T Pop()。 //析構(gòu)函數(shù) void Push(const T amp。 //棧頂指針 public: Stack(){top=NULL。 }。 link=next。 NodeT *link。 ()。\t39。i10。 if(()) cout?？?endl。i10。 ()。i++) (a[i])。 for(i=0。 //輸出 棧內(nèi)所有數(shù)據(jù) 【 例 】 順序棧的類模板： 棧 void main(){ int i,a[10]={0,1,2,3,4,5,6,7,8,9},b[10]。} //判棧滿 void PrintStack()。} //清空棧 bool IsEmpty() const{return top== 1。 //彈出 ， top T GetElem(int i)。data)。 //構(gòu)造函數(shù) ，棧如不指定大小，設(shè)為 20元素 ~Stack(){delete[ ] elements。 //動態(tài)建立的元素 int maxSize。 棧 templatetypename Tclass Stack{ int top。其中棧底 bottom是指向棧數(shù)據(jù)區(qū)的下一單元，這樣判斷是否為空棧會更方便，只需 top與 bottom相同就是空棧。而出棧時順序相反，最后進(jìn)棧的 an1最先出棧，而最先進(jìn)棧的 a0最后出棧。 棧 棧的基本操作： 參見下圖，設(shè)給定棧 s=(a0， a1， …… ， an1)，稱 a0為棧底， an1為棧頂。所以棧又稱作 后進(jìn)先出（ LIFO： Last In First Out）的線性表 。 進(jìn)棧時最先進(jìn)棧的在最下面，最后的在最上面，后來居上。允許進(jìn)行插入和刪除的一端叫做 棧頂 (top)，而另一端叫 棧底 (bottom)。 棧與隊列的基本操作及其應(yīng)用 棧和隊都是特殊的線性表， 限制存取位置 的線性結(jié)構(gòu)，可以由順序表實現(xiàn)，也可以由鏈表實現(xiàn)。 pllinkrlink指示本結(jié)點的前驅(qū)結(jié)點的后繼結(jié)點，即本結(jié)點，間接訪問符 可以連續(xù)使用 。雙向鏈表經(jīng)常采用 帶頭結(jié)點的循環(huán)鏈表方式 。為了克服這一缺點，可采用 雙向鏈表 （ Double Linked List)。 雙向鏈表（選讀） 雙向鏈表引入： 考慮單鏈表只能找后繼。該函數(shù)與 Node的有參構(gòu)造函數(shù)功能基本相同。 link=NULL。 通常對 Node類復(fù)制的結(jié)果應(yīng)是一個孤立結(jié)點： template typename T NodeT::Node(Node amp。 單鏈表類型模板 討論復(fù)制構(gòu)造函數(shù)： 在本例中沒有給出 Node類的復(fù)制構(gòu)造函數(shù)，并非可以使用默認(rèn)的復(fù)制構(gòu)造函數(shù)，而是避開了所有使用它的情況，本例中函數(shù)的參數(shù)和返回值僅使用指向 Node的指針，類定義中也沒有用復(fù)制方式初始化。 在本例中程序只需調(diào)用類模板中的成員函數(shù)就可以完成所有鏈表操作。 然后給出一個整數(shù)在一個鏈表中查找 ， 找到后刪除它 ， 再輸出該表 。 }。 //按 升序生成鏈表 NodeT*CreatNode(T data)。 //可用來 向前生成鏈表 void InsertRear(NodeT* p)。 //計算 單鏈表長度 void PrintList()。 //清空鏈表 ，只余表頭結(jié)點 NodeT* Find(T data)。 //構(gòu)造函數(shù) ，生成頭結(jié)點 (空鏈表 ) ~List()。 定義鏈表類 : templatetypename Tclass List{ NodeT *head,*tail。 //刪除當(dāng)前結(jié)點的后繼 結(jié)點 friend class ListT。 //生成 一般結(jié)點的構(gòu)造函數(shù) void InsertAfter(NodeT* p)。 //生成 頭結(jié)點的構(gòu)造函數(shù) Node(const T amp。 //數(shù)據(jù)域 NodeT *link。 定義結(jié)點類： templatetypename Tclass List。 //如果要把該節(jié)點移入另一個鏈中 ， 則可將 q返回 。 plink=qlink。 } 單鏈表基本算法 5. 刪除單鏈表節(jié)點 *p后面節(jié)點： void del (node *p){ node *q。 qlink=plink。 void insert(node *p,Datatype x){ node *q=new node。 //p為 NULL則未找到 } 返回值為指針 p， 指向鏈表中找到的結(jié)點 。pinfo!=data) p=plink。 while(p!=NULLamp。 //頭結(jié)點放新結(jié)點之前 } return head。 plink= headlink 。 while(cindata){ //建立的總是第一個結(jié)點 p=new node。 head=new node。 //返回頭指針 } 單鏈表基本算法 head ^ info0 P ^ P info1 2. 向前生成鏈表算法： node *createup(){ node *head,*p。 } //尾指針到鏈尾 taillink=NULL。 //添入數(shù)據(jù) taillink= p。 while(cindata){ //回車結(jié)束 p=new(node)。 head=new node。 單鏈表基本算法 head tail p info1 tail p info0 tail ^ 1. 向后生成鏈表算法： node *createdown(){ Datatype data。 要使算法中沒有特殊者 ， 可以給每一個鏈表加上一個 表頭結(jié)點 ， 如下圖所示 。 p ^ infon1 ^ 插在隊尾： 只要工作指針 p找到隊尾 ， 即可鏈在其后： p→ link=newnode； =NULL。 即： newnode→ link=p； //或 newnode→ link=q→ link；可用于插入某結(jié)點之后 q→ link=newnode； 單鏈表基本算法 infox newnode head head 插在鏈?zhǔn)祝? 首先新結(jié)點的 link指針指向 info0所在結(jié)點 ， 然后 ， head指向新結(jié)點 。 插入算法有 三種 情況，我們希望在單鏈表中包含數(shù)據(jù)infoi的結(jié)點之前插入一個新元素，則 infoi可在第一個結(jié)點，或在中間結(jié)點，如未找到，則把新結(jié)點插在鏈尾結(jié)點之后。 單鏈表基本算法 單鏈表的第一個結(jié)點的地址可通過鏈表的表頭指針 head找到， head在使用中千萬不可丟失，否則鏈表整個丟失，內(nèi)存也發(fā)生泄漏。 在 C/C++中允許結(jié)構(gòu)（或?qū)ο螅┏蓡T是 結(jié)構(gòu)自身的指針類型 ，通過指針引用自身這種類型的結(jié)構(gòu)。 node *link。 節(jié)點定義如下： typedef int Datatype。 單鏈表基本算法 雙向鏈表 (選讀 ) 單鏈表基本算法 單鏈表 （ Singly Linked list） ： 每個數(shù)據(jù)元素占用一個節(jié)點 （ Node） 。線性表的邏輯結(jié)構(gòu)是 n個數(shù)據(jù)元素的有限序列（ a1,a2,…,an ）。這表明 聚合實現(xiàn)了完善的封裝 。標(biāo)準(zhǔn)string類模板就是典型的例子。封裝的更高境界是在該類對象中一切都是完備的、自給自足的，不僅有數(shù)據(jù)和對數(shù)據(jù)的操作，還包括資源的動態(tài)安排和釋放。在使用中，把它作為一個成員對象，就像使用 string類對象那樣。如果在 student類中使用 string類而不是 C字符串，就不要再考慮深復(fù)制問題了。由此可見， 構(gòu)造函數(shù)并非僅做初始化工作 。 //復(fù)制賦值操作符 檢驗 主函數(shù) 和 運(yùn)行結(jié)果 淺復(fù)制與深復(fù)制 提示： 自由存儲區(qū)內(nèi)存是最常見的需要自定義復(fù)制構(gòu)造函數(shù)的資源，但不是唯一的，還有打開文件等也需要自定義復(fù)制構(gòu)造函數(shù)。s)。 //析構(gòu)函數(shù) student amp。s)。 //默認(rèn)構(gòu)造函數(shù) stu