【正文】 福州大學至誠學院 ? 棧 ? ? ? 棧的應用舉例 ? 數(shù)制轉換 ? 括號配對問題 ? 迷宮求解 ? * 棧和遞歸的實現(xiàn) ? 隊列 ? 抽象數(shù)據(jù)類型隊列的定義 ? 鏈隊列 隊列的鏈式表示與實現(xiàn) ? 循環(huán)隊列 隊列的順序表示與實現(xiàn) 第三章 棧和隊列 福州大學至誠學院 題目：將十進制數(shù) N轉換為其他進制數(shù)輸出 基本原理： N=(n div d)*d + n mod d “div”是整除運算， mod為求余運算。 數(shù)制轉換 福州大學至誠學院 top top 4 top 4 0 top 4 0 5 例如： (1348)10=(2504)8，其運算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 計算順序 輸出順序 top 4 0 5 2 福州大學至誠學院 棧 ? 棧的定義：操作受限制的線性表，只能在線性表的一端進行插入和刪除運算。 ? 棧 S=(a1， a2， a3， … an)按照按 a1… an的次序進棧，如圖： aa11aa22a a n 11a a n……棧頂棧 底彈棧入?！瓧ｍ敆?底彈棧入棧? 棧頂 Top：插入、刪除的這一端。 ? 棧底 Bottom:不做任何操作的另一端。 ? 空棧：表中沒有元素。 ? LIFO：棧的修改是按后進先出的原則進行的。 福州大學至誠學院 棧的抽象數(shù)據(jù)類型定義 ADT Stack { 數(shù)據(jù)對象： D = {ai | ai屬于 Elemset, (i=1,2,…,n, n≥0)} 數(shù)據(jù)關系： R1 = {＜ ai1,ai＞ |ai1,ai屬于 D,(i=2,3,…,n)} 約定 an為棧頂 , a1為棧底。 基本操作： InitStack(amp。S)。 DestroyStack(amp。S)。 ClearStack(amp。S)。 StackEmpty(S)。 StackLength(S) 。 GetTop(S,amp。e)。 Push(amp。S,e)。 Pop(amp。S,amp。e)。 StackTraverse(S,visit ()) }ADT Stack 福州大學至誠學院 棧的基本操作 ? InitStack(amp。S) ? 操作結果 :構造一個空的棧 S。 ? DestroyStack(amp。S) ?初始條件 : 棧 S已經(jīng)存在 。 ? 操作結果 : 銷毀棧 S。 福州大學至誠學院 棧的基本操作 ? StackEmpty(S) ?初始條件 : 棧 S已經(jīng)存在 。 ?操作結果 : 若棧 S為空棧 ， 則返回 TURE。否則返回 FALSE。 ? StackLength(S) ?初始條件 : 棧 S已經(jīng)存在 。 ? 操作結果 : 返回棧 S中的數(shù)據(jù)元素個數(shù) 。 ? GetTop(S,amp。e) ?初始條件 : 棧 S已經(jīng)存在且非空 。 ?操作結果 : 用 e返回棧 S中棧頂元素的值 。 福州大學至誠學院 ? StackTraverse(S,visit ()) ?初始條件 : 棧 S已經(jīng)存在且非空 。 ?操作結果 : 從棧底到棧頂依次對 S的每個元素調(diào)用函數(shù) visit ()。 一旦 visit ()失敗 ， 則操作失敗 。 福州大學至誠學院 棧的基本操作 ? Push(amp。S,e) ? 初始條件 : 棧 S已經(jīng)存在 。 ?操作結果 : 插入元素 e為新的棧頂元素 。 ? Pop(amp。S,amp。e) ?初始條件 : 棧 S已經(jīng)存在且非空 。 ?操作結果 : 刪除 S的棧頂元素并用 e返回其值 。 ? ClearStack(amp。S) ?初始條件 : 棧 S已經(jīng)存在 。 ?操作結果 : 將棧 S重置為空棧 。 福州大學至誠學院 棧的順序表示與實現(xiàn) (順序棧 ) define STACK_INIT_SIZE 100 define STACKINCREMENT 10 typedef struct{ SElemType *base。 /*在棧構造之前和銷毀之后， base的值為 NULL*/ SElemType *top。 /*棧頂指針 */ int stacksize。 /*當前已分配的存儲空間，以元素為單位*/ }SqStack。 福州大學至誠學院 順序棧示意圖 *base *top stacksize 初始 空 棧 *top = *base。 stacksize = STACK_INIT_SIZE *base *top stacksize ...... a1 ... ai an 順序棧 ?空棧的棧頂指針指向棧底 ?非空棧中的棧頂指針始終在棧頂元素的下一個位置 福州大學至誠學院 top 1 2 3 4 5 0 進棧 A 棧滿 B C D E F 設數(shù)組維數(shù)為 M top=base,?？?， 此時出棧，則下溢（ underflow) top=M,棧滿 ， 此時入棧 則上溢（ overflow) top top top top top 1 2 3 4 5 0 空棧 top base base top 出棧 top top ?？? base 棧底指針 base,始終指向棧底位置；棧頂指針 top,其初值指向棧底，始終在棧頂元素的下一個位置 1 2 3 4 5 0 A B top 福州大學至誠學院 順序棧的操作實現(xiàn) InitStack //構造一個空的棧 S Status InitStack(SqStack *s) { sbase=( SElemType *)malloc (STACK_INIT_SIZE * sizeof(SElemType))。 if(!s base) return(OVERFLOW)。 stop=sbase。 sstacksize = STACK_INIT_SIZE。 return OK。 } 福州大學至誠學院 順序棧的操作實現(xiàn) GetTop //返回棧 S中棧頂元素 Status GetTop(SqStack s, SElemType *e) { if ( == )return ERROR。 *e = *()。 return OK。 } s e *base *top stacksize ...... a1 ... ai an *e = *()。 福州大學至誠學院 *base *top stacksize ...... a1 ... ai an s *base *top stacksize ...... a1 ... ai an s 棧滿時，追加存儲空間 e *stop++ = e。 順序棧的操作實現(xiàn) —Push //插入元素 e為新的棧頂元素 福州大學至誠