【文章內(nèi)容簡介】 時(shí)順序相反，最后進(jìn)棧的 an1最先出棧，而最先進(jìn)棧的 a0最后出棧。 a0 an2 …… a1 an1 bottom 進(jìn)棧 top top top top top 出棧 圖示為順序棧。其中棧底 bottom是指向棧數(shù)據(jù)區(qū)的下一單元，這樣判斷是否為空棧會(huì)更方便，只需 top與 bottom相同就是空棧。通常只有棧頂與操作有關(guān)。 棧 templatetypename Tclass Stack{ int top。 //棧頂指針（下標(biāo)） T *elements。 //動(dòng)態(tài)建立的元素 int maxSize。 //棧最大容納的元素個(gè)數(shù) public: Stack(int=20)。 //構(gòu)造函數(shù) ，棧如不指定大小，設(shè)為 20元素 ~Stack(){delete[ ] elements。} void Push(const T amp。data)。 //壓棧 T Pop()。 //彈出 ， top T GetElem(int i)。 //取數(shù)據(jù) ， top不變 void MakeEmpty(){top= 1。} //清空棧 bool IsEmpty() const{return top== 1。} //判?？? bool IsFull() const{return top==maxSize1。} //判棧滿 void PrintStack()。 }。 //輸出 棧內(nèi)所有數(shù)據(jù) 【 例 】 順序棧的類模板： 棧 void main(){ int i,a[10]={0,1,2,3,4,5,6,7,8,9},b[10]。 Stackint istack(10)。 for(i=0。i10。i++) (a[i])。 if(()) cout棧滿 endl。 ()。 for(i=0。i10。i++) b[i]=()。 if(()) cout棧空 endl。 for(i=0。i10。i++) coutb[i]39。\t39。 //注意先進(jìn)后出 coutendl。 ()。 //下溢出 } 棧 【 例 】 鏈棧的 結(jié)點(diǎn) 類模板： templatetypename Tclass Node{ //鏈棧結(jié)點(diǎn)類模板 T info。 NodeT *link。 public: Node(T data=0,NodeT *next=NULL){ info=data。 link=next。 } friend class StackT。 }。 top …… ^ …… 鏈棧 棧 鏈棧類模板 (無頭結(jié)點(diǎn)鏈表 )： templatetypename Tclass Stack{ //鏈棧類模板 NodeT *top。 //棧頂指針 public: Stack(){top=NULL。} ~Stack()。 //析構(gòu)函數(shù) void Push(const T amp。data)。 //壓棧 T Pop()。 //彈出 T GetTop()。 //取棧頂元素 void MakeEmpty()。 //清空棧 bool IsEmpty(){return top==NULL。} }。 棧的應(yīng)用（選讀） 順序棧和鏈棧邏輯功能是一樣，盡管這里兩個(gè)棧模板的成員函數(shù)功能選擇稍有出入，因?yàn)?順序?？梢噪S機(jī)訪問其中的元素 ， 而鏈棧只能順序訪問， 但邏輯上完全可以做到一樣（物理結(jié)構(gòu)不同） 。順序棧必須先開一定大小內(nèi)存空間，執(zhí)行起來簡單，速度快，可能溢出。 鏈棧內(nèi)存空間隨用隨開，不會(huì)溢出，但執(zhí)行復(fù)雜（不斷地動(dòng)態(tài)分配），速度慢。 順序棧和鏈棧比較： 棧的應(yīng)用（選讀） ?？捎糜?表達(dá)式的計(jì)算 ?，F(xiàn)考慮最簡單的 +、 、 *、 /四個(gè)運(yùn)算符和結(jié)束符＝組成的算術(shù)表達(dá)式，只有 兩個(gè)優(yōu)先級 ，先 */，后 +。 為實(shí)現(xiàn)運(yùn)算符的優(yōu)先級，采用兩個(gè)棧：一個(gè) 數(shù)棧 ，一個(gè) 運(yùn)算符棧 。數(shù)棧暫存操作數(shù)，運(yùn)算符棧暫存運(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=；參見上圖。 從左向右掃描算術(shù)表達(dá)式 ，遇到 操作數(shù) ， 壓入數(shù)棧 ；遇到 運(yùn)算符 ，則 與運(yùn)算符棧棧頂?shù)倪\(yùn)算符比較優(yōu)先級 ，若新的運(yùn)算符優(yōu)先級高，或運(yùn)算符棧空，則壓棧。否則將棧頂運(yùn)算符出棧，與數(shù)字棧出棧的兩個(gè)數(shù)據(jù)進(jìn)行運(yùn)算，結(jié)果壓入數(shù)棧，再將新運(yùn)算符壓棧。繼續(xù)掃描，直到遇到＝號，掃描結(jié)束。棧中數(shù)據(jù)繼續(xù)按前面規(guī)則出棧。 棧的應(yīng)用（選讀） 【 例 】 模擬簡單計(jì)算器 ， 該計(jì)算器只認(rèn) + * / 四個(gè)運(yùn)算符 ，輸入為整數(shù) 。 表達(dá)式結(jié)束符使用＝號 ， 清空棧用 ‘ c’字符 。 使用 ‘ z’字符表示結(jié)束 。 簡易計(jì)算器類定義： class Calculator{ Stackint Nstack。 //使用鏈棧 Stackchar Ostack。 public: Calculator(void){}。 void Cal(void)。 //計(jì)算器運(yùn)算程序 void GetTwoNum(int amp。Num1,int amp。Num2)。 //取數(shù) void Compute(char Opr)。 //讀算式 void Clear(void)。 }。 //清除 隊(duì)列 隊(duì)列的基本概念： 隊(duì)列 (Queue)也是一種限定存取位置的線性表。它 只允許在表的一端插入，而在另一端刪除 。允許插入的一端稱為 隊(duì)尾(rear)，允許刪除的一端叫做 隊(duì)頭 (front)。每次在隊(duì)尾加入新元素，加入稱為 進(jìn)隊(duì) ，刪除稱為 出隊(duì) 。隊(duì)列的這種特性正好與棧相反，叫做 先進(jìn)先出 FIFO(First In First Out)。 a0 a1 a2 … an1 … front 元素移動(dòng)方向 rear 圖 圖 ，隊(duì)尾 (rear)不斷向后移；而隨隊(duì)頭元素的出隊(duì)，則隊(duì)頭 (front)也不斷后移，即 位置在變 （如要位置不變， 移動(dòng)元素 工作量也太大）。 隊(duì)列 rear front A D C A B D E C F H G BCD進(jìn)隊(duì) A進(jìn)隊(duì) 空隊(duì) D C AB出隊(duì) EFGH進(jìn)隊(duì) rear front rear rear rear front front front 圖 順序隊(duì)列的插入和刪除 由圖可見：空隊(duì)時(shí)指針（下標(biāo)）front和 rear在一起都指向隊(duì)前方，當(dāng)有元素進(jìn)隊(duì)，則 rear后移；有元素出隊(duì)，則 front后移，最后分配給隊(duì)的前端不再被利用。 順序表隊(duì)列的缺點(diǎn)： 隊(duì)列 順序表隊(duì)列的改進(jìn)： 邏輯上的循環(huán)隊(duì)列 注意，空隊(duì)時(shí) rear=front，滿隊(duì)時(shí)必須空一個(gè)位置 隊(duì)列 循環(huán)隊(duì)列 浪費(fèi)一個(gè)位置好像太可惜，特別在該位置中存放一個(gè)很大的對象時(shí)。實(shí)際上 對象很大時(shí)，總是由索引（指針）來排隊(duì) 。若想利用這個(gè)空間，必然加一個(gè)標(biāo)志來表示隊(duì)空 /隊(duì)滿，進(jìn)隊(duì)出隊(duì)都要判斷，使用上更不方便。 用鏈表實(shí)現(xiàn)隊(duì)列無此問題 【 例 】 順序存儲(chǔ)方式的循環(huán)隊(duì)列類模板 。 【 例 】 鏈隊(duì)類模板。鏈?zhǔn)壮鲫?duì)，鏈尾入隊(duì)。無鏈表頭結(jié)點(diǎn)方式。 二叉樹（選讀） 樹形結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)，樹和二叉樹是常用的樹形結(jié)構(gòu)。 二叉樹的遍歷 二叉樹的概念 排序二叉樹 二叉樹的概念 （選讀） 樹（ Tree） 是由 n（ n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。如 n=0，稱為空樹。非空樹有一個(gè)特定的結(jié)點(diǎn)，它只有直接后繼，沒有直接前驅(qū)，稱之為根（ root）。除根以外的其它結(jié)點(diǎn)劃分為 m（ m≥0）個(gè)互不相交的有限集合 T0， T1， …… ， Tm1，每個(gè)集合又是一棵樹，稱為根的子樹（ subtree）。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有 0個(gè)或多個(gè)直接后繼。這是一個(gè)遞歸方法定義的數(shù)據(jù)結(jié)構(gòu)。 樹的概念： 二叉樹的概念（選讀） A B C D E F G I H J L K O N M ………… 0層 …… 1層 2層 3層 深度 圖 樹的示意圖 結(jié)點(diǎn) ， 包括數(shù)據(jù)項(xiàng)和多個(gè)指針項(xiàng) ， 指針項(xiàng)數(shù)目并不固定 ， 且無次序 。 結(jié)點(diǎn)的度 ， 結(jié)點(diǎn)所擁有的子樹數(shù)量 。 葉結(jié)點(diǎn) ， 度為 0的結(jié)點(diǎn) ，如 G， I， J， K， L，M， N， O結(jié)點(diǎn) 。 分支結(jié)點(diǎn) ， 度 ≥1的結(jié)點(diǎn) 。 孩子結(jié)點(diǎn) ， 若結(jié)點(diǎn) x有子樹 ， 則子樹根結(jié)點(diǎn)即為 x的孩子結(jié)點(diǎn) 。 樹的術(shù)語： 二叉樹的概念（選讀） A B C D E F G I H J L K O N M ………… 0層 …… 1層 2層 3層 深度 圖 樹的示意圖 雙親結(jié)點(diǎn) ， 若結(jié)點(diǎn) x有孩子 ， 它即為孩子的雙親 。 兄弟結(jié)點(diǎn) ， 同一雙親的結(jié)點(diǎn)互稱為兄弟 。 結(jié)點(diǎn)的層次 ， 從根到該結(jié)點(diǎn)所經(jīng)路徑上的分支條數(shù) 。 樹的深度 ,樹中結(jié)點(diǎn)的層次數(shù) 。 樹的度 ，樹中結(jié)點(diǎn)度的最大值。 樹的術(shù)語： 二叉樹的概念（選讀） 二叉樹 （ Binary Tree） 是另一種獨(dú)立的樹形結(jié)構(gòu) 。二叉樹是結(jié)點(diǎn)的一個(gè)有限集合 ， 該集合或?yàn)榭?， 或是由一個(gè)根結(jié)點(diǎn)及兩棵樹分別稱為左子樹和右子樹的 （ 注意有左右之分 ） 互不相交的二叉樹組成 ， 其中左右子樹分別可以為空子樹或均為空樹 。 這也是一個(gè)遞歸的定義 。 二叉樹的特點(diǎn)是：每個(gè)結(jié)點(diǎn)最多兩個(gè)孩子 ， 并且子樹有左右之分 。 二叉樹的基本性質(zhì)： 1．二叉樹的第 i層上最多有 2i1(i=1)個(gè)結(jié)點(diǎn)； 2．深度為 h的二叉樹中最多有 2h1個(gè)結(jié)點(diǎn)； 3．在任一棵二叉樹中，有 n0個(gè)葉子結(jié)點(diǎn)，有 n2個(gè)度為 2的 結(jié)點(diǎn)，則有 n0=n2+1。 樹的概念： 二叉樹的概念（選讀） 【 例 】 畫出有三個(gè)結(jié)點(diǎn)的所有二叉樹 。 解：結(jié)果見圖 ， 共 5種 。 圖 5種不同的三結(jié)點(diǎn)二叉樹 二叉樹的概念（選讀） 滿二叉樹和完全二叉樹： 分別如圖 ，完全二叉樹已有的結(jié)點(diǎn)排序與滿二叉樹相同。 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)絻?chǔ)存方式的二叉樹。每個(gè)結(jié)點(diǎn)有三個(gè)域：數(shù)據(jù)域、左孩子指針和右孩子指針，見圖 。 lchild rchild info 圖 二叉樹結(jié)點(diǎn) 二叉樹的概念（選讀） 二叉樹類結(jié)點(diǎn)類模板定義： templatetypename Tclass BinaryTree。 templatetypename Tclass Node{ NodeT *lchild,*rchild。 T info。 public: Node(){ lchild=NULL。 rchild=N