《數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏第3章課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏第3章課件.ppt（109頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第 三 章棧 和 隊(duì) 列 【 課 前 思 考 】1. 什 么 是 線 性 結(jié) 構(gòu) ？ 簡(jiǎn) 單 地 說(shuō) ， 線 性 結(jié) 構(gòu) 是 一 個(gè) 數(shù) 據(jù) 元 素 的 序 列 。2. 你 見(jiàn) 過(guò) 餐 館 中 一 疊 一 疊 的 盤(pán) 子 嗎 ？ 如 果 它 們 是 按1,2,n 的 次 序 往 上 疊 的 ， 那 么 使 用 時(shí) 候 的 次 序 應(yīng)是 什 么 樣 的 ？ 必 然 是 依 從 上 往 下 的 次 序 ， 即 n,2,1。 它 們遵 循 的 是 后 進(jìn) 先 出 的 規(guī) 律 ， 這 正 是 本 章 要 討 論 的棧 的 結(jié) 構(gòu) 特 點(diǎn) 。3. 在 日 常 生 活 中 ， 為 了 維 持 正 常 的

2、社 會(huì) 秩 序 而 出 現(xiàn)的 常 見(jiàn) 現(xiàn) 象 是 什 么 ？ 是 排 隊(duì) 。 在 計(jì) 算 機(jī) 程 序 中 ， 模 擬 排 隊(duì) 的 數(shù) 據(jù)結(jié) 構(gòu) 是 隊(duì) 列 。 【 學(xué) 習(xí) 目 標(biāo) 】 1. 掌 握 棧 和 隊(duì) 列 這 兩 種 抽 象 數(shù) 據(jù) 類(lèi) 型的 特 點(diǎn) ， 并 能 在 相 應(yīng) 的 應(yīng) 用 問(wèn) 題 中 正 確 選用 它 們 。 2. 熟 練 掌 握 棧 類(lèi) 型 的 兩 種 實(shí) 現(xiàn) 方 法 。 3. 熟 練 掌 握 循 環(huán) 隊(duì) 列 和 鏈 隊(duì) 列 的 基 本操 作 實(shí) 現(xiàn) 算 法 。 4. 理 解 遞 歸 算 法 執(zhí) 行 過(guò) 程 中 棧 的 狀 態(tài)變 化 過(guò) 程 。 棧 和 隊(duì) 列 是 在

3、程 序 設(shè) 計(jì) 中 被 廣 泛 使 用 的兩 種 線 性 數(shù) 據(jù) 結(jié) 構(gòu) ， 因 此 本 章 的 學(xué) 習(xí) 重 點(diǎn) 在于 掌 握 這 兩 種 結(jié) 構(gòu) 的 特 點(diǎn) ， 以 便 能 在 應(yīng) 用 問(wèn)題 中 正 確 使 用 ?！?知 識(shí) 點(diǎn) 】順 序 棧 、 鏈 棧 、 循 環(huán) 隊(duì) 列 、 鏈 隊(duì) 列【 重 點(diǎn) 和 難 點(diǎn) 】 【 學(xué) 習(xí) 指 南 】 在 這 一 章 中 ， 主 要 是 學(xué) 習(xí) 如 何 在 求 解 應(yīng)用 問(wèn) 題 中 適 當(dāng) 地 應(yīng) 用 棧 和 隊(duì) 列 ， 棧 和 隊(duì) 列 在兩 種 存 儲(chǔ) 結(jié) 構(gòu) 中 的 實(shí) 現(xiàn) 都 不 難 ， 但 應(yīng) 該 對(duì) 它們 了 如 指 掌 ， 特 別 要 注 意

4、 它 們 的 基 本 操 作 實(shí)現(xiàn) 時(shí) 的 一 些 特 殊 情 況 ， 如 棧 滿(mǎn) 和 棧 空 、 隊(duì) 滿(mǎn)和 隊(duì) 空 的 條 件 以 及 它 們 的 描 述 方 法 。 本 章 要求 必 須 完 成 的 算 法 設(shè) 計(jì) 題 為 ： 3.15， 3.17，3.19， 3.22， 3.27 ,3.28， 3.30， 3.31， 3.32。其 中 前 4個(gè) 主 要 是 練 習(xí) 棧 的 應(yīng) 用 ， 后 4個(gè) 主 要是 有 關(guān) 隊(duì) 列 的 實(shí) 現(xiàn) 方 法 的 練 習(xí) 。 通 常 稱(chēng) ， 棧 和 隊(duì) 列 是 限 定 插 入 和 刪 除只 能 在 表 的 “ 端 點(diǎn) ” 進(jìn) 行 的 線 性 表 。 線 性

5、表 棧 隊(duì) 列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in棧 和 隊(duì) 列 是 兩 種 常 用 的 數(shù) 據(jù) 類(lèi) 型 3.1 棧3.2 棧 的 應(yīng) 用 舉 例3.4 隊(duì) 列 目 錄3.3 棧 與 遞 歸 的 實(shí) 現(xiàn) 3.1 棧一 、 棧 的 定 義 棧 (stack)作 為 一 種 限 定 性 線 性 表 ， 是 將 線 性 表 的 插 入 和 刪 除運(yùn) 算 限 制 為 僅 在 表 的 一 端 進(jìn) 行 。 通 常 將 表 中 允 許 進(jìn) 行 插

6、 入 、 刪 除 操 作 的 一 端 稱(chēng) 為 棧 頂 (Top)，因 此 棧 頂 的 當(dāng) 前 位 置 是 動(dòng) 態(tài) 變 化 的 ， 它 由 一 個(gè) 稱(chēng) 為 棧 頂 指 針 的 位置 指 示 器 指 示 。 同 時(shí) 表 的 另 一 端 為 固 定 的 一 端 ， 被 稱(chēng) 為 棧 底(Bottom)。 當(dāng) 棧 中 沒(méi) 有 元 素 時(shí) 稱(chēng) 為 空 棧 。 棧 的 插 入 操 作 被 形 象 地稱(chēng) 為 進(jìn) 棧 或 入 棧 ， 刪 除 操 作 稱(chēng) 為 出 棧 或 退 棧 。 插 入 ： 最 先 放 入 棧 中 元 素 在 棧 底 ， 最 后 放 入 的 元 素 在 棧 頂 ； 刪 除 ： 最 后 放 入

7、的 元 素 最 先 刪 除 ， 最 先 放 入 的 元 素 最 后 刪 除 。 棧 是 一 種 后 進(jìn) 先 出 (Last In First Out)的 線 性 表 ， 簡(jiǎn) 稱(chēng) 為 LIFO表 。 an a2 a 1 進(jìn) 棧出 棧 棧 頂 棧 底 進(jìn) 棧出 棧 (a) 棧的示意圖 (b) 鐵路調(diào)序棧的表示圖 3.1 棧 進(jìn) 棧出 棧 棧 頂 棧 底 進(jìn) 棧出 棧 例 ： 設(shè) 一 個(gè) 棧 的 輸 入 序 列 為 A,B,C,D,則 借 助 一個(gè) 棧 所 得 到 的 輸 出 序 列 不 可 能 是 。(A) A,B,C,D (B) D,C,B,A (C) A,C,D,B (D) D,A,B,C 答

8、 :可 以 簡(jiǎn) 單 地 推 算 ,得 容 易 得 出 D,A,B,C是 不 可能 的 ,因 為 D先 出 來(lái) ,說(shuō) 明 A,B,C,D均 在 棧 中 ,按 照 入 棧順 序 ,在 棧 中 順 序 應(yīng) 為 D,C,B,A,出 棧 的 順 序 只 能 是D,C,B,A。 所 以 本 題 答 案 為 D。 二 、 棧 的 主 要 操 作 1.初 始 化 棧 ： InitStack( /在 棧 構(gòu) 造 前 和 銷(xiāo) 毀 后 base值 為 NULL SElemType *top; /棧 頂 指 針 int stacksize; SqStack; /當(dāng) 前 已 分 配 存 儲(chǔ) 空 間或 簡(jiǎn) 單 定 義 如

9、 下 ： #define M 100 int sM; int top; 圖 3.2 順 序 棧 中 的 進(jìn) 棧 和 出 棧 Top指 向 棧 頂 元 素初 態(tài) ： top=-1; 空 棧 ， 棧 中 無(wú) 元 素 ，進(jìn) 棧 ： top=top+1; stop=x;退 棧 ： 取 stop; top=top-1;棧 滿(mǎn) ： top=M-1;棧 溢 出 （ 上 溢 ） ， 不 能 再 進(jìn) 棧 （ 錯(cuò) 誤 狀態(tài) ）top=-1時(shí) 不 能 退 棧 ， 下 溢 （ 正 常 狀 態(tài) ， 常 作 控 制 條 件 ） （ 1） 構(gòu) 造 空 順 序 棧 算 法 :初 始 化 棧Status InitStack (

10、 SqStack if ( ! S.base ) exit ( OVERFLOW ); /為 棧 分 配 存 儲(chǔ) 空 間 失 敗S.top = S.base; / 令 棧 頂 指 針 = 棧 底 指 針/ 設(shè) 置 棧 的 當(dāng) 前 可 使 用 的 最 大 容 量S.stacksize = STACK_INIT_SIZE; return OK; / InitStack2.順 序 棧 基 本 操 作 的 實(shí) 現(xiàn) 如 下 : 程 序 描 述 ：/This program is to initialize a stack # include # include # include # define ST

11、ACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define OK 1 # define ERROR 0 typedef int SElemType; typedef struct /define structure SqStack() SElemType *base; SElemType *top; int stacksize; SqStack; int InitStack(SqStack if (!S.base) printf(“Allocate space failure !n“); return (ERROR); S.top=S.base;

12、 S.stacksize=STACK_INIT_SIZE; return (OK); /InitStack() end void main() /main() function SqStack S; if (InitStack(S) printf (Success! The stack has been created !n“); printf (.OK!n“); getch(); （2） 取順序棧的棧頂元素 Status GetTop ( SqStack S, SElemType / 如 果 棧 S 為 空 ， 則 返 回 ERROR e = *( S.top - 1); / 將 棧 頂 指

13、 針 減 1 后 所 指 向 的 單 元 內(nèi) 的 值 賦 給 e return OK; / GetTop （3）將 元 素 壓 入 順 序 棧 算 法 （進(jìn)棧）Status Push ( SqStack if ( ! S.base ) exit ( OVERFLOW ); / 追 加 存 儲(chǔ) 空 間 失 敗 S.top = S.base + S.stacksize; / 修 改 棧 頂 指 針 S.stacksize += STACKINCREMENT; / 修 改 當(dāng) 前 棧 的 存 儲(chǔ) 空 間 / if 結(jié) 束 *S.top += e; / 先 將 e 送 入 棧 頂 ， 然 后 將 棧

14、頂 指 針 加 1 return OK; / Push （4）將 元 素 彈 出 順 序 棧 算 法 （退棧）Status Pop ( SqStack / 如 果 棧 S 為 空 ， 則 返 回 ERROR e = *-S.top; / 先 令 top 減 1， 再 將 top 所 指 單 元 值 賦 給 e return OK; / Pop （5） 判棧空否 Int Empty ( SqStack S) / 如 果 棧 S 空 ， 返 回 1 ； 如 果 棧 S 不 空 ， 返 回 0 。if ( S.top = = S.base ) return 1; / 如 果 棧 S 為 空 ， 則

15、返 回 1else return 0; / 如 果 棧 S 為 空 ， 則 返 回 0 / Empty end 3 棧 的 共 享有 時(shí) ， 一 個(gè) 程 序 設(shè) 計(jì) 中 ， 需 要 使 用 多 個(gè) 同 一 類(lèi)型 的 棧 ,這 時(shí) 候 ， 可 能 會(huì) 產(chǎn) 生 一 個(gè) 棧 空 間 過(guò) 小 ， 容 量發(fā) 生 溢 出 ， 而 另 一 個(gè) 棧 空 間 過(guò) 大 ， 造 成 大 量 存 儲(chǔ) 單 元浪 費(fèi) 的 現(xiàn) 象 。 為 了 充 分 利 用 各 個(gè) 棧 的 存 儲(chǔ) 空 間 ， 這時(shí) 可 以 采 用 多 個(gè) 棧 共 享 存 儲(chǔ) 單 元 ， 即 給 多 個(gè) 棧 分 配 一個(gè) 足 夠 大 的 存 儲(chǔ) 空 間 ，

16、 讓 多 個(gè) 棧 實(shí) 現(xiàn) 存 儲(chǔ) 空 間 優(yōu) 勢(shì) 互補(bǔ) 。 棧 1頂 棧 2頂 棧 1底 棧 2底 圖 3-3 兩 個(gè) 棧 共 享 存 儲(chǔ) 單 元 示 意 圖 棧 空 ： top1=0,top2=M-1;棧 滿(mǎn) ： top1+1=top2 兩 個(gè) 棧 共 享 存 儲(chǔ) 單 元 可 用 如 下 C語(yǔ) 句 描 述 ：#define MAXSIZE 100 #define DUSTACKSIZE MAXSIZE typedef struct DuSqStack SElemType dataMAXSIZE; int top1; /top1 is the pointer of DuSqStack S1 i

17、nt top2; /top2 is the pointer of DuSqStack S2 int flag;DuSqStack; /或 ：#define MAXSIZE 100Struct duseqstack elemtype datamaxsize; int top2 ; /兩 個(gè) 棧 的 棧 頂 指 針 int flag; （1）兩個(gè)棧共享存儲(chǔ)單元的進(jìn)棧算法Status DuSqStackPush ( DuSqStack / 如 果 兩 個(gè) 棧 滿(mǎn) ， 則 返 回 ERROR else / 如 果 棧 未 滿(mǎn) ， 則 進(jìn) 行 入 棧 操 作 if ( ( S.flag ! = 1 )

18、/ 如 果 flag 不 為 1,2， 則 返 回 ERROR else / 如 果 flag 為 1 或 2， 則 入 棧 switch ( S.flag ) case 1 : / 標(biāo) 志 位 flag 為 1 S.dataS.top1 = x; / 元 素 x 入 棧 S1 S.top1+; / 修 改 棧 S1 的 棧 頂 指 針 break; case 2 : / 標(biāo) 志 位 flag 為 2 S.dataS.top2 = x; / 元 素 x 入 棧 S2 S.top2- -; / 修 改 棧 S2 的 棧 頂 指 針 break; / switch 結(jié) 束 return OK; /

19、 else 結(jié) 束 / else 結(jié) 束 / DuSqStackPush （2）兩個(gè)棧共享存儲(chǔ)單元的退棧算法Status DuSqStackPop ( DuSqStack / 如 果 flag 1,2， 則 返 回 ERRORelse / 如 果 flag 為 1 或 2， 則 出 棧switch ( S.flag ) case 1: / 標(biāo) 志 位 flag 為 1 if ( S.top1 0 ) / 如 果 棧 S1 不 空 ， 則 對(duì) S1 進(jìn) 行 操 作S.top1-; / 修 改 棧 S1 的 棧 頂 指 針 x = S.dataS.top1; / 元 素 x 出 棧 / if 結(jié)

20、束 else return ERROR; / 如 果 棧 S1 為 空 ， 則 返 回 ERROR break; case 2 : / 標(biāo) 志 位 flag 為 1 if ( S.top2next=NULL; （b）進(jìn)棧運(yùn)算Status Push_L ( LinkStack SElemType e ) / 將 元 素 e 插 入 到 棧 S 中 ， 成 為 新 的 棧 頂 元 素 q = ( LinkStack ) malloc ( sizeof ( SNode ) ); if ( ! q ) exit ( OVERFLOW ); / 存 儲(chǔ) 分 配 失 敗 q-data = e; q-nex

21、t = top-next; top-next = q; return OK; / Push_L （c）退棧運(yùn)算Status Pop_L ( LinkStack / 如 果 棧 S 為 空 ， 則 返 回 ERROR e = top-next-data; / 取 出 棧 頂 元 素 的 值 q = top-next; / q 指 向 棧 頂 元 素 top-next = q-next; / 刪 除 棧 頂 元 素 free (q); / 釋 放 棧 頂 元 素 所 占 的 空 間 return OK; / Pop_L （d）取棧頂元素Status GetTop_L ( LinkStack top

22、, SElemType / 如 果 棧 S 為 空 ， 則 返 回 ERROR else / 如 果 棧 S 不 空 ， 則 返 回 棧 頂 元 素 e = top-next-data; return OK; / else 結(jié) 束 / GetTop_L （5）判?？読nt empty(LinkStack *top) if(top-next=NULL) return(1); else return(0); 課 前 復(fù) 習(xí)設(shè) n 個(gè) 元 素 的 進(jìn) 棧 序 列 是 P1， P2， P3， ， Pn， 其 輸 出 序 列 是 1,2， 3， ， n， 若 P1=3，則 P2的 值 ( )。 A、 可

23、 能 是 2 B、 一 定 是 2C、 不 可 能 是 1 D、 一 定 是 1 一 、 數(shù) 制 轉(zhuǎn) 換 假 設(shè) 要 將 十 進(jìn) 制 數(shù) N轉(zhuǎn) 換 為 d進(jìn) 制 數(shù) ， 一 個(gè) 簡(jiǎn) 單 的 轉(zhuǎn) 換 算法 是 重 復(fù) 下 述 兩 步 ， 直 到 N等 于 零 ： X = N mod d (其 中 mod為 求 余 運(yùn) 算 )N = N div d (其 中 div為 整 除 運(yùn) 算 ) 計(jì) 算 過(guò) 程 從 低 位 到 高 位 ， 打 印 輸 出 從 高 位 到 低 位3.2 棧 的 應(yīng) 用 舉 例 棧 在 日 常 生 活 中 和 計(jì) 算 機(jī) 程 序 設(shè) 計(jì) 中 有 著 許 多 應(yīng) 用 ， 下 面

24、 僅介 紹 棧 在 計(jì) 算 機(jī) 中 的 應(yīng) 用 。 void Conversion(int N)/*對(duì) 于 任 意 的 一 個(gè) 非 負(fù) 十 進(jìn) 制 數(shù) N， 打 印 出 與 其 等 值 的 8進(jìn) 制 數(shù) */ Stack S; int x; /* S為 順 序 棧 或 鏈 棧 */ InitStack( while(N0) x=N%8; Push( /* 將 轉(zhuǎn) 換 后 的 數(shù) 字 壓 入 棧 S */ N=N/8; while(！ StackEmpty(S) Pop( printf(%d,x); 算 法 3.1 二 、 括 號(hào) 匹 配 問(wèn) 題 假 設(shè) 表 達(dá) 式 中 允 許 包 含 三 種

25、括 號(hào) :圓 括 號(hào) 、方 括 號(hào) 和 大 括 號(hào) 。 編 寫(xiě) 一 個(gè) 算 法 判 斷 表 達(dá) 式 中 的括 號(hào) 是 否 正 確 配 對(duì) 。 解 :設(shè) 置 一 個(gè) 括 號(hào) 棧 ,掃 描 表 達(dá) 式 ： 遇 到 左 括 號(hào)(包 括 (、 和 )時(shí) 進(jìn) 棧 ,遇 到 右 括 號(hào) 時(shí) ,若 棧 是 相 匹配 的 左 括 號(hào) ,則 出 棧 ,否 則 ,返 回 0。 若 表 達(dá) 式 掃 描 結(jié) 束 ,棧 為 空 ,返 回 1表 示 括 號(hào) 正確 匹 配 ,否 則 返 回 0。 int correct(char exp,int n) char stMaxSize; int top=-1,i=0,tag=1

26、; while (i-1) tag=0; /*若 棧 不 空 ,則 不 配 對(duì) */ return(tag); 三 、 行 編 輯 程 序功 能 ： 接 收 用 戶(hù) 從 終 端 輸 入 的 數(shù) 據(jù) 或 程 序 ， 并 存 入用 戶(hù) 的 數(shù) 據(jù) 區(qū) 。算 法 思 想 ： 設(shè) 輸 入 緩 沖 區(qū) 為 一 個(gè) 棧 結(jié) 構(gòu) ， 每 當(dāng) 從 終端 接 收 一 個(gè) 字 符 后 先 作 如 下 判 別 ： 若 它 既 不 是 退 格符 （ #） 也 不 是 退 行 符 （ ） ,則 將 該 字 符 入 棧 ； 若 是退 格 符 （ #） ， 則 從 棧 頂 刪 去 一 個(gè) 字 符 ； 若 是 退 行 符（

27、） ， 則 將 棧 清 空 。算 法 描 述 如 下 ： void LineEdit()InitStack(s);ch=getchar();While(ch!=EOF) /EOF為 全 文 結(jié) 束 符 while(ch!=EOFbreak; /當(dāng) 棧 非 空 時(shí) 退 棧 case “”:clearstack(s);break;/重 置 S為 空 棧 default:push(s,c);break;/有 效 字 符 進(jìn) 棧 ， 但 未 考 慮 棧 滿(mǎn) ch=getchar(); clearstack(s); if(ch!=EOF) ch=getchar(); destroystack(s); 五

28、 、 表 達(dá) 式 求 值 表 達(dá) 式 求 值 是 高 級(jí) 語(yǔ) 言 編 譯 中 的 一 個(gè) 基 本 問(wèn) 題 ， 是 棧 的 典 型 應(yīng) 用 實(shí) 例 。 任 何 一 個(gè) 表 達(dá) 式 都 是 由 操 作數(shù) (operand)、 運(yùn) 算 符 (operator)和 界 限 符(delimiter)組 成 的 。 操 作 數(shù) 既 可 以 是 常 數(shù) ， 也 可以 是 被 說(shuō) 明 為 變 量 或 常 量 的 標(biāo) 識(shí) 符 ； 運(yùn) 算 符 可 以 分為 算 術(shù) 運(yùn) 算 符 、 關(guān) 系 運(yùn) 算 符 和 邏 輯 運(yùn) 算 符 三 類(lèi) ； 基本 界 限 符 有 左 右 括 號(hào) 和 表 達(dá) 式 結(jié) 束 符 等 。 1.

29、無(wú) 括 號(hào) 算 術(shù) 表 達(dá) 式 求 值 表 達(dá) 式 計(jì) 算 程 序 設(shè) 計(jì) 語(yǔ) 言 中 都 有 計(jì) 算 表 達(dá) 式 的 問(wèn) 題 ， 這 是 語(yǔ) 言編 譯 中 的 典 型 問(wèn) 題 。 (1) 表 達(dá) 式 形 式 ： 由 運(yùn) 算 對(duì) 象 、 運(yùn) 算 符 及 必 要 的表 達(dá) 式 括 號(hào) 組 成 ； (2) 表 達(dá) 式 運(yùn) 算 ： 運(yùn) 算 時(shí) 要 有 一 個(gè) 正 確 的 運(yùn) 算 形 式順 序 。由 于 某 些 運(yùn) 算 符 可 能 具 有 比 別 的 運(yùn) 算 符 更 高 的 優(yōu) 先 級(jí) ， 因 此表 達(dá) 式 不 可 能 嚴(yán) 格 的 從 左 到 右 ， 見(jiàn) 圖 3.5。 圖 3.5 表 達(dá) 式 運(yùn) 算

30、及 運(yùn) 算 符 優(yōu) 先 級(jí) 圖 3.6 無(wú) 括 號(hào) 算 術(shù) 表 達(dá) 式 的 處 理 過(guò) 程 置 空 棧 OVS、OPTR 讀 字 符 W W是 操 作 符 OPTR?？?W優(yōu) 先 級(jí) OPTR棧 頂 優(yōu) 先 級(jí) 取 OVS頂 、 次 頂 和 OPTR頂 ， 形 成 運(yùn) 算 結(jié) 果 T(i),然 后 退 OVS頂 、 次 頂 和 OPTR頂 ， 將 T(i)置 入 OVS棧 頂 進(jìn) OVS 進(jìn) OPTR棧 W # 結(jié) 束 N Y Y Y N Y N N 2. 算 術(shù) 表 達(dá) 式 處 理 規(guī) 則 (1) 規(guī) 定 優(yōu) 先 級(jí) 表 。 (2) 設(shè) 置 兩 個(gè) 棧 ： OVS(運(yùn) 算 數(shù) 棧 )和 OP

31、TR(運(yùn) 算 符 棧 )。 (3) 自 左 向 右 掃 描 ， 遇 操 作 數(shù) 進(jìn) OVS， 遇 操 作 符 則 與 OPTR棧 頂 優(yōu) 先 數(shù) 比 較 ： 當(dāng) 前 操 作 符 OPTR棧 頂 , 當(dāng) 前 操 作 符 進(jìn) OPTR棧 ； 當(dāng) 前 操 作 符 OPTR棧 頂 ， OVS棧 頂 、 次 頂 和 OPTR棧 頂 ， 退棧 形 成 運(yùn) 算 T(i)， T(i)進(jìn) OVS棧 。 例 ： 實(shí) 現(xiàn) A/B C+D*E 的 運(yùn) 算 過(guò) 程 時(shí) 棧 區(qū) 變 化 情 況 如 圖3.7所 示 。 圖 3.7 A/B C+D*E運(yùn) 算 過(guò) 程 的 棧 區(qū) 變 化 情 況 示 意 圖 CBAOVS /O

32、PTR OPTR生 成 BC，運(yùn) 算 結(jié) 果 T(1) T(1)AOVS /OPTR OPTR/生 成 A/T(1),運(yùn) 算 結(jié) 果 T(2)T(2) / OPTR為空，進(jìn)棧 DT(2) 右邊界#OPTR * 生 成 D*E，運(yùn) 算 結(jié) 果 T(3)T(3)T(2) 生 成 T(3)T(2)，得 到T(4) T(4)E *右邊界#OPTR+ * 3. 帶 括 號(hào) 算 術(shù) 表 達(dá) 式 假 設(shè) 操 作 數(shù) 是 整 型 常 數(shù) ， 運(yùn) 算 符 只 含 加 、 減 、 乘 、除 等 四 種 運(yùn) 算 符 ， 界 限 符 有 左 右 括 號(hào) 和 表 達(dá) 式 起 始 、結(jié) 束 符 “ ” ， 如 ： （ 7

33、+15） *（ 23-28/4） 。 引 入 表 達(dá) 式 起 始 、 結(jié) 束 符 是 為 了 方 便 。 要 對(duì) 一 個(gè) 簡(jiǎn)單 的 算 術(shù) 表 達(dá) 式 求 值 ， 首 先 要 了 解 算 術(shù) 四 則 運(yùn) 算 的規(guī) 則 ， 即 ： (1) 從 左 算 到 右 ； (2) 先 乘 除 ， 后 加 減 ； (3) 先括 號(hào) 內(nèi) ， 后 括 號(hào) 外 。 運(yùn) 算 符 和 界 限 符 可 統(tǒng) 稱(chēng) 為 算 符 ， 它 們 構(gòu) 成 的 集合 命 名 為 OPTR。 根 據(jù) 上 述 三 條 運(yùn) 算 規(guī) 則 ， 在 運(yùn) 算 過(guò)程 中 ， 任 意 兩 個(gè) 前 后 相 繼 出 現(xiàn) 的 算 符 1和 2之 間的 優(yōu) 先

34、 關(guān) 系 必 為 下 面 三 種 關(guān) 系 之 一 ： 1 2， 1的 優(yōu) 先 權(quán) 高 于 2。 表 3-1 算 符 之 間 的 優(yōu) 先 關(guān) 系 實(shí) 現(xiàn) 算 符 優(yōu) 先 算 法 時(shí) 需 要 使 用 兩 個(gè) 工 作 棧 ： 一個(gè) 稱(chēng) 作 optr， 用 以 存 放 運(yùn) 算 符 ； 另 一 個(gè) 稱(chēng) 作 opnd，用 以 存 放 操 作 數(shù) 或 運(yùn) 算 的 中 間 結(jié) 果 。 算 法 的 基 本 過(guò)程 如 下 ： 首 先 初 始 化 操 作 數(shù) 棧 opnd和 運(yùn) 算 符 棧 optr， 并將 表 達(dá) 式 起 始 符 “ ” 壓 入 運(yùn) 算 符 棧 ； 依 次 讀 入 表 達(dá) 式 中 的 每 個(gè) 字

35、符 ， 若 是 操 作 數(shù) 則直 接 進(jìn) 入 操 作 數(shù) 棧 opnd， 若 是 運(yùn) 算 符 ， 則 與 運(yùn) 算 符棧 optr的 棧 頂 運(yùn) 算 符 進(jìn) 行 優(yōu) 先 權(quán) 比 較 ， 并 做 如 下 處理 ： (1) 若 棧 頂 運(yùn) 算 符 的 優(yōu) 先 級(jí) 低 于 剛 讀 入 的 運(yùn) 算符 ， 則 讓 剛 讀 入 的 運(yùn) 算 符 進(jìn) optr棧 ； (2) 若 棧 頂 運(yùn) 算 符 的 優(yōu) 先 級(jí) 高 于 剛 讀 入 的 運(yùn) 算符 ， 則 將 棧 頂 運(yùn) 算 符 退 棧 ， 送 入 ， 同 時(shí) 將 操 作 數(shù) 棧opnd退 棧 兩 次 ， 得 到 兩 個(gè) 操 作 數(shù) a、 b， 對(duì) a、 b進(jìn)

36、行 運(yùn) 算 后 ， 將 運(yùn) 算 結(jié) 果 作 為 中 間 結(jié) 果 推 入 opnd棧 ； (3) 若 棧 頂 運(yùn) 算 符 的 優(yōu) 先 級(jí) 與 剛 讀 入 的 運(yùn) 算符 的 優(yōu) 先 級(jí) 相 同 ， 說(shuō) 明 左 右 括 號(hào) 相 遇 ， 只 需 將 棧 頂 運(yùn)算 符 （ 左 括 號(hào) ） 退 棧 即 可 。 算 法 具 體 描 述 如 下 ： int ExpEvaluation()/*讀 入 一 個(gè) 簡(jiǎn) 單 算 術(shù) 表 達(dá) 式 并 計(jì) 算 其 值 。 operator和 operand分 別 為 運(yùn) 算 符棧 和 運(yùn) 算 數(shù) 棧 ， OPS為 運(yùn) 算 符 集 合 */ InitStack( InitSt

37、ack( Push( printf(nnPlease input an expression(Ending with ) :); c=getchar(); while(c!= |GetTop(optr)! = ) /* GetTop()通 過(guò) 函 數(shù) 值 返 回 棧 頂 元 素*/ if(!In(c,OP) Push( c=getchar(); else switch(Precede(GetTop(optr),c) case : Pop( Pop( Pop( v=Execute(a,theta,b); /* 對(duì) a和 b進(jìn) 行 op運(yùn) 算 */ Push( break; return (Get

38、Top(opnd); 例 求 表 達(dá) 式 1+2*3-4/2的 值 ， 棧 的 變 化 如 下 。 步 驟 操 作 數(shù) 棧 運(yùn) 算 符 棧 說(shuō) 明 開(kāi) 始 兩 棧 均 為 空1 1 1進(jìn) 入 操 作 數(shù) 棧+進(jìn) 入 運(yùn) 算 符 棧2進(jìn) 入 操 作 數(shù) 棧*進(jìn) 入 運(yùn) 算 符 棧3進(jìn) 入 操 作 數(shù) 棧退 棧2*3進(jìn) 入 操 作 數(shù) 棧退 棧 1+6進(jìn) 入 操 作 數(shù) 棧23456789 1 +1 2 +1 2 +1117 +*2 36 + *+ 步 驟 操 作 數(shù) 棧 運(yùn) 算 符 棧 說(shuō) 明 10 7 -進(jìn) 入 運(yùn) 算 符 棧4進(jìn) 入 操 作 數(shù) 棧/進(jìn) 入 運(yùn) 算 符 棧2進(jìn) 入 操 作 數(shù)

39、 棧退 棧4/2進(jìn) 入 操 作 數(shù) 棧退 棧7-2進(jìn) 入 操 作 數(shù) 棧11121314151617 7 4 -7 4 - /7 4 2 - /77 2 -5 當(dāng) 然 ， 算 術(shù) 表 達(dá) 式 除 了 簡(jiǎn) 單 求 值 外 ， 還 會(huì) 涉 及 到 算 術(shù)表 達(dá) 式 的 兩 種 表 示 方 法 ， 即 中 綴 表 示 法 和 后 綴 表 示 法 。中 綴 表 達(dá) 式 求 值 較 麻 煩 （ 須 考 慮 運(yùn) 算 符 的 優(yōu) 先 級(jí) ， 甚至 還 要 考 慮 圓 括 號(hào) ） ， 而 后 綴 表 達(dá) 式 求 值 較 方 便 （ 無(wú)須 考 慮 運(yùn) 算 符 的 優(yōu) 先 級(jí) 及 圓 括 號(hào) ） 。 下 面 將

40、介 紹 算 術(shù)表 達(dá) 式 的 中 綴 表 示 和 后 綴 表 示 及 它 們 的 求 值 規(guī) 律 ， 例 如 ， 對(duì) 于 下 列 各 中 綴 表 達(dá) 式 ： （ 1） 3/5+8（ 2） 18-9*(4+3)（ 3） (25+x)*(a*(a+b)+b)對(duì) 應(yīng) 的 后 綴 表 達(dá) 式 為 ：(1)3 5 / 8 +(2)18 9 4 3 + * - (3)25 x + a a b + * b + * 4.中 綴 表 達(dá) 式 變 成 等 價(jià) 的 后 綴 表 達(dá) 式 將 中 綴 表 達(dá) 式 變 成 等 價(jià) 的 后 綴 表 達(dá) 式 ， 表 達(dá) 式 中 操 作 數(shù) 次序 不 變 ， 運(yùn) 算 符 次 序

41、 發(fā) 生 變 化 ， 同 時(shí) 去 掉 了 圓 括 號(hào) 。 轉(zhuǎn) 換 規(guī) 則是 ： 設(shè) 立 一 個(gè) 棧 ， 存 放 運(yùn) 算 符 ， 首 先 棧 為 空 ， 編 譯 程 序 從 左 到右 掃 描 中 綴 表 達(dá) 式 ， 若 遇 到 操 作 數(shù) ， 直 接 輸 出 ， 并 輸 出 一 個(gè) 空格 作 為 兩 個(gè) 操 作 數(shù) 的 分 隔 符 ； 若 遇 到 運(yùn) 算 符 ， 則 必 須 與 棧 頂 比較 ， 運(yùn) 算 符 級(jí) 別 比 棧 頂 級(jí) 別 高 則 進(jìn) 棧 ， 否 則 退 出 棧 頂 元 素 并 輸出 ， 然 后 輸 出 一 個(gè) 空 格 作 分 隔 符 ； 若 遇 到 左 括 號(hào) ， 進(jìn) 棧 ； 若

42、遇到 右 括 號(hào) ， 則 一 直 退 棧 輸 出 ， 直 到 退 到 左 括 號(hào) 止 。 當(dāng) 棧 變 成 空時(shí) ， 輸 出 的 結(jié) 果 即 為 后 綴 表 達(dá) 式 。 將 中 綴 表 達(dá) 式 (1+2)*(8-2)/(7-4)變 成 等 價(jià) 的 后 綴 表 達(dá)式 。 現(xiàn) 在 用 棧 來(lái) 實(shí) 現(xiàn) 該 運(yùn) 算 ， 棧 的 變 化 及 輸 出 結(jié) 果 如 下 步 驟 棧 中 元 素 輸 出 結(jié) 果 說(shuō) 明1 ( （ 進(jìn) 棧2 ( 1 輸 出 13 ( + 1 +進(jìn) 棧4 ( + 1 2 輸 出 2 5 1 2 + +退 棧 輸 出 ， 退 棧 到 （止6 * 1 2 + *進(jìn) 棧7 * ( 1 2

43、+ （ 進(jìn) 棧8 * ( ( 1 2 + （ 進(jìn) 棧9 * ( ( 1 2 + 8 輸 出 8 10 * ( ( - 1 2 + 8 - 進(jìn) 棧 11 * ( ( - 1 2 + 8 2 輸 出 212 * ( 1 2 + 8 2 - -退 棧 輸 出 ， 退 棧 到（ 止13 * ( / 1 2 + 8 2 - / 進(jìn) 棧14 * ( / ( 1 2 + 8 2 - （ 進(jìn) 棧15 * ( / ( 1 2 + 8 2 - 7 輸 出 7 16 * ( / ( - 1 2 + 8 2 - 7 - 進(jìn) 棧17 * ( / ( - 1 2 + 8 2 - 7 4 輸 出 418 * ( / 1 2

44、 + 8 2 - 7 4 - -退 棧 輸 出 ， 退 棧 到（ 止19 * 1 2 + 8 2 - 7 4 - / /退 棧 輸 出 ， 退 棧 到（ 止20 1 2 + 8 2 - 7 4 - / * *退 棧 并 輸 出 步 驟 棧 中 元 素 輸 出 結(jié) 果 說(shuō) 明 5.后 綴 表 達(dá) 式 的 求 值 將 中 綴 表 達(dá) 式 轉(zhuǎn) 換 成 等 價(jià) 的 后 綴 表 達(dá) 式 后 ， 求 值 時(shí) ，不 需 要 再 考 慮 運(yùn) 算 符 的 優(yōu) 先 級(jí) ， 只 需 從 左 到 右 掃 描 一 遍后 綴 表 達(dá) 式 即 可 。 具 體 求 值 步 驟 為 ： 設(shè) 置 一 個(gè) 棧 ， 開(kāi) 始時(shí) ， 棧

45、 為 空 ， 然 后 從 左 到 右 掃 描 后 綴 表 達(dá) 式 ， 若 遇 操 作數(shù) ， 則 進(jìn) 棧 ； 若 遇 運(yùn) 算 符 ， 則 從 棧 中 退 出 兩 個(gè) 元 素 ， 先退 出 的 放 到 運(yùn) 算 符 的 右 邊 ， 后 退 出 的 放 到 運(yùn) 算 符 左 邊 ，運(yùn) 算 后 的 結(jié) 果 再 進(jìn) 棧 ， 直 到 后 綴 表 達(dá) 式 掃 描 完 畢 。 此 時(shí) ，棧 中 僅 有 一 個(gè) 元 素 ， 即 為 運(yùn) 算 的 結(jié) 果 。 例 ， 求 后 綴 表 達(dá)式 ： 1 2 + 8 2 - 7 4 - / *的 值 ，棧 的 變 化 情 如 下 ： 步 驟 棧 中 元 素 說(shuō) 明1 1 1進(jìn)

46、棧2 1 2 2進(jìn) 棧3 遇 +號(hào) 退 棧 2和 14 3 1+2=3的 結(jié) 果 3進(jìn) 棧5 3 8 8進(jìn) 棧 6 3 8 2 2進(jìn) 棧7 3 遇 -號(hào) 退 棧 2和 88 3 6 8-2=6的 結(jié) 果 6進(jìn) 棧9 3 6 7 7進(jìn) 棧10 3 6 7 4 4進(jìn) 棧 步 驟 棧 中 元 素 說(shuō) 明11 3 6 遇 -號(hào) 退 棧 4和 712 3 6 3 7-4=3的 結(jié) 果 3進(jìn) 棧13 3 遇 /號(hào) 退 棧 3和 614 3 2 6/3=2的 結(jié) 果 2進(jìn) 棧15 遇 *號(hào) 退 棧 2和 3 16 6 3*2=6進(jìn) 棧17 6 掃 描 完 畢 ， 運(yùn) 算 結(jié) 束 從 上 可 知 ， 最 后

47、求 得 的 后 綴 表 達(dá) 式 之 值 為 6， 與 用中 綴 表 達(dá) 式 求 得 的 結(jié) 果 一 致 ， 但 后 綴 式 求 值 要 簡(jiǎn) 單得 多 。 五 、 求 解 迷 宮 問(wèn) 題 求 迷 宮 問(wèn) 題 就 是 求 出 從 入 口 到 出 口 的 路 徑 。 在求 解 時(shí) ,通 常 用 的 是 “ 窮 舉 求 解 ” 的 方 法 ,即 從 入口 出 發(fā) ,順 某 一 方 向 向 前 試 探 ,若 能 走 通 ,則 繼 續(xù) 往前 走 ； 否 則 沿 原 路 退 回 ,換 一 個(gè) 方 向 再 繼 續(xù) 試 探 ,直 至 所 有 可 能 的 通 路 都 試 探 完 為 止 。 為 了 保 證 在任

48、何 位 置 上 都 能 沿 原 路 退 回 (稱(chēng) 為 回 溯 ),需 要 用 一個(gè) 后 進(jìn) 先 出 的 棧 來(lái) 保 存 從 入 口 到 當(dāng) 前 位 置 的 路 徑 。 首 先 用 如 圖 3.3所 示 的 方 塊 圖 表 示 迷 宮 。 對(duì)于 圖 中 的 每 個(gè) 方 塊 ,用 空 白 表 示 通 道 ,用 陰 影 表 示墻 。 所 求 路 徑 必 須 是 簡(jiǎn) 單 路 徑 ,即 在 求 得 的 路 徑 上不 能 重 復(fù) 出 現(xiàn) 同 一 通 道 塊 。 為 了 表 示 迷 宮 ,設(shè) 置 一 個(gè) 數(shù) 組 mg,其 中 每 個(gè) 元 素 表 示一 個(gè) 方 塊 的 狀 態(tài) ,為 0時(shí) 表 示 對(duì) 應(yīng) 方

49、塊 是 通 道 ,為 1時(shí) 表 示對(duì) 應(yīng) 方 塊 為 墻 ,如 圖 3.3所 示 的 迷 宮 ,對(duì) 應(yīng) 的 迷 宮 數(shù) 組 mg如 下 : int mgM+1N+1= /*M=10,N=10*/ 1,1,1,1,1,1,1,1,1,1, 1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1;

50、while (棧 不 空 )若 當(dāng) 前 位 置 可 通 ， 則 將 當(dāng) 前 位 置 插 入 棧 頂 ； / 納 入 路 徑 若 該 位 置 是 出 口 位 置 ， 則 算 法 結(jié) 束 ； / 此 時(shí) 棧 中 存 放 的 是 一 條 從 入 口 位 置 到 出 口 位 置 的 路 徑 否 則 切 換 當(dāng) 前 位 置 的 北 鄰 方 塊 為 新 的 當(dāng) 前 位 置 ； 否 則 若 棧 不 空 且 棧 頂 位 置 尚 有 其 他 方 向 未 被 探 索 ， 則 設(shè) 定 新 的 當(dāng) 前 位 置 為 沿 順 時(shí) 針 方 向 旋 轉(zhuǎn) 找 到 的 棧 頂 位 置 的 下 一 相 鄰 塊 ； 若 棧 不 空

51、但 棧 頂 位 置 的 四 周 均 不 可 通 ， 則 刪 去 棧 頂 位 置 ； / 從 路 徑 中 刪 去 該 通 道 塊 若 棧 不 空 ， 則 重 新 測(cè) 試 新 的 棧 頂 位 置 ， 直 至 找 到 一 個(gè) 可 通 的 相 鄰 塊 或 出 棧 至 棧 空 ； 算 法 描 述 ： void mgpath() /*路 徑 為 :(1,1)-(M-2,N-2)*/ int i,j,di,find,k; top+; /*初 始 方 塊 進(jìn) 棧 */ Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1; while (top-1) /*棧 不 空

52、 時(shí) 循 環(huán) */ i=Stacktop.i;j=Stacktop.j;di=Stacktop.di; if (i=M-2 for (k=0;k=top;k+) printf(t(%d,%d),Stackk.i,Stackk.j); if (k+1)%5=0) printf(n); printf(n); return; find=0; while (didata+Sum(head-next); 3)問(wèn) 題 的 求 解 方 法 是 遞 歸 的 有 些 問(wèn) 題 的 解 法 是 遞 歸 的 ,典 型 的 有 Hanoi問(wèn) 題 求解 ,該 問(wèn) 題 描 述 是 ： 設(shè) 有 3個(gè) 分 別 命 名 為 X,

53、Y和 Z的 塔 座 ,在 塔 座 X上 有 n個(gè) 直 徑 各 不 相 同 ,從 小 到 大 依 次 編 號(hào) 為1,2,n的 盤(pán) 片 ,現(xiàn) 要 求 將 X塔 座 上 的 n個(gè) 盤(pán) 片 移 到 塔 座Z上 并 仍 按 同 樣 順 序 疊 放 ,盤(pán) 片 移 動(dòng) 時(shí) 必 須 遵 守 以 下 規(guī)則 ： 每 次 只 能 移 動(dòng) 一 個(gè) 盤(pán) 片 ； 盤(pán) 片 可 以 插 在 X,Y和 Z中 任 一 塔 座 ； 任 何 時(shí) 候 都 不 能 將 一 個(gè) 較 大 的 盤(pán) 片 放 在較 小 的 盤(pán) 片 上 。 設(shè) 計(jì) 遞 歸 求 解 算 法 ,并 將 其 轉(zhuǎn) 換 為 非遞 歸 算 法 。 設(shè) Hanoi(n,x,y,

54、z)表 示 將 n個(gè) 盤(pán) 片 從 x通 過(guò) y移 動(dòng) 到 z上 ,遞 歸 分 解 的 過(guò) 程 是 ： Hanoi(n,a,b,c)Hanoi(n-1,a,c,b)；move(n,a,c):將 第n個(gè) 圓 盤(pán) 從a移 到c；Hanoi(n-1,b,a,c) 3 2 1 a 32 1 a b c 3 2 1 a b c 3 2 1 a b c 3 2 1 a b c b c 321 a b c 3 2 1 a b c 3 2 1 a b c圖 Hanoi塔 的 遞 歸 函 數(shù) 運(yùn) 行 示 意 圖 3、 遞 歸 模 型 遞 歸 模 型 是 遞 歸 算 法 的 抽 象 ,它 反 映 一 個(gè) 遞 歸 問(wèn)

55、 題的 遞 歸 結(jié) 構(gòu) ,例 如 ,前 面 的 遞 歸 算 法 對(duì) 應(yīng) 的 遞 歸 模 型 如 下 ： fun(1)=1 (1) fun(n)=n*fun(n-1) n1 (2) 其 中 ,第 一 個(gè) 式 子 給 出 了 遞 歸 的 終 止 條 件 ,第 二 個(gè) 式子 給 出 了 fun(n)的 值 與 fun(n-1)的 值 之 間 的 關(guān) 系 ,我 們 把第 一 個(gè) 式 子 稱(chēng) 為 遞 歸 出 口 ,把 第 二 個(gè) 式 子 稱(chēng) 為 遞 歸 體 。 實(shí) 際 上 ,遞 歸 思 路 是 把 一 個(gè) 不 能 或 不 好 直 接 求 解 的“ 大 問(wèn) 題 ” 轉(zhuǎn) 化 成 一 個(gè) 或 幾 個(gè) “ 小

56、問(wèn) 題 ” 來(lái) 解 決 ,再 把這 些 “ 小 問(wèn) 題 ” 進(jìn) 一 步 分 解 成 更 小 的 “ 小 問(wèn) 題 ” 來(lái) 解決 ,如 此 分 解 ,直 至 每 個(gè) “ 小 問(wèn) 題 ” 都 可 以 直 接 解 決 (此時(shí) 分 解 到 遞 歸 出 口 )。 但 遞 歸 分 解 不 是 隨 意 的 分 解 ,遞 歸分 解 要 保 證 “ 大 問(wèn) 題 ” 與 “ 小 問(wèn) 題 ” 相 似 ,即 求 解 過(guò) 程與 環(huán) 境 都 相 似 。 fun(5) d1:fun(4) d2:fun(3) d3:fun(2) d4:fun(1) 返 回 1 fun(2)=2 fun(3)=6 fun(4)=24 fun(5

57、)=120 求 解 fun(5)的 過(guò) 程 如 下 ： 5! 4 遞 歸 問(wèn) 題 的 優(yōu) 點(diǎn) 通 過(guò) 上 面 的 例 子 可 看 出 ， 遞 歸 既 是 強(qiáng) 有 力 的 數(shù) 學(xué) 方 法 ， 也 是 程 序 設(shè) 計(jì) 中 一 個(gè) 很 有 用 的 工 具 。 其 特 點(diǎn) 是 對(duì) 遞 歸 問(wèn) 題 描述 簡(jiǎn) 捷 ， 結(jié) 構(gòu) 清 晰 ， 程 序 的 正 確 性 容 易 證 明 。 5、 消 除 遞 歸 的 原 因 其 一 ： 有 利 于 提 高 算 法 時(shí) 空 性 能 ， 因 為 遞 歸 執(zhí) 行 時(shí) 需要 系 統(tǒng) 提 供 隱 式 棧 實(shí) 現(xiàn) 遞 歸 ， 效 率 低 且 費(fèi) 時(shí) 。 其 二 ： 無(wú) 應(yīng) 用

58、遞 歸 語(yǔ) 句 的 語(yǔ) 言 設(shè) 施 環(huán) 境 條 件 ， 有 些計(jì) 算 機(jī) 語(yǔ) 言 不 支 持 遞 歸 功 能 ， 如 FORTRAN語(yǔ) 言 中 無(wú) 遞 歸 機(jī) 制 。 其 三 ： 遞 歸 算 法 是 一 次 執(zhí) 行 完 ， 這 在 處 理 有 些 問(wèn) 題時(shí) 不 合 適 ， 也 存 在 一 個(gè) 把 遞 歸 算 法 轉(zhuǎn) 化 為 非 遞 歸 算 法 的 需 求 。 3.4 隊(duì) 列 a1 a2 . an 入 隊(duì) 隊(duì) 頭 隊(duì) 尾 出 隊(duì) 圖 3-13 隊(duì) 列 示 意 圖 隊(duì) 列 簡(jiǎn) 稱(chēng) 隊(duì) ,它 也 是 一 種 運(yùn) 算 受 限 的 線 性 表 ,其 限制 僅 允 許 在 表 的 一 端 進(jìn) 行 插 入

59、,而 在 表 的 另 一 端 進(jìn) 行刪 除 。 我 們 把 進(jìn) 行 插 入 的 一 端 稱(chēng) 做 隊(duì) 尾 (rear),進(jìn) 行 刪 除的 一 端 稱(chēng) 做 隊(duì) 首 (front)。 向 隊(duì) 列 中 插 入 新 元 素 稱(chēng) 為 進(jìn) 隊(duì) 或 入 隊(duì) ,新 元 素 進(jìn) 隊(duì)后 就 成 為 新 的 隊(duì) 尾 元 素 ； 從 隊(duì) 列 中 刪 除 元 素 稱(chēng) 為 出 隊(duì)或 離 隊(duì) ,元 素 出 隊(duì) 后 ,其 后 繼 元 素 就 成 為 隊(duì) 首 元 素 。 二 、 隊(duì) 列 的 基 本 運(yùn) 算 1. 初 始 化 操 作 ： InitQueue( /*數(shù) 據(jù) 域 */ struct QNode *next; /*指 針

60、 域 */ Qnode,*QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue; rear 頭 front an 頭 front a1 a2 rear （ a） 空 鏈 隊(duì) 列 (b)非 空 鏈 隊(duì) 鏈 隊(duì) 列 的 基 本 操 作（ 1） 初 始 化 操 作 。 int InitQueue(LinkQueue if(!Q.front) exit(OVERFLOW); Q-front-next=NULL; return OK; （ 2） 入 隊(duì) 操 作 。 Status EnQueue(LinkQueue p=(Que

61、uePtr* )malloc(sizeof(QNode); if(!p) exit(OVERFLOW); p-data=e; p-next=NULL; Q-rear-next=p; Q-rear=p; return OK; （ 3） 出 隊(duì) 操 作 。 int DeQueue(LinkQueue if(Q-front=Q-rear) return ERROR; p=Q-front-next; e=p-data; Q-front-next=p-next; /* 隊(duì) 頭 元 素 p出 隊(duì) */ if(Q-rear=p) /* 如 果 隊(duì) 中 只 有 一 個(gè) 元 素 p， 則 p出 隊(duì) 后 成 為

62、空 隊(duì) */ Q-rear=Q-front; free(p); /* 釋 放 存 儲(chǔ) 空 間 */ return OK; 2. 循 環(huán) 隊(duì) 列 :隊(duì) 列 的 順 序 表 示 和 實(shí) 現(xiàn) 圖 3.15 隊(duì) 列 的 基 本 操 作 Queue6543210rearfront (1) 空 隊(duì) 列 543210rearfront cbad(2) a、b、c、d依次入 隊(duì) 543210rearfront d(3) a、b、c出隊(duì) 543210rearfront def(4) e、f入隊(duì) 用 一 組 連 續(xù) 的 存 儲(chǔ) 單 元 依 次 存 放 隊(duì) 列 的 元 素 ， 并 設(shè) 兩 個(gè) 指 針 front、r

63、ear分 別 指 示 隊(duì) 頭 和 隊(duì) 尾 元 素 的 位 置 。front： 指 向 實(shí) 際 的 隊(duì) 頭 ； rear： 指 向 實(shí) 際 隊(duì) 尾 的 下 一 位 置 。初 態(tài) ： front rear 0； 隊(duì) 空 ： front rear;隊(duì) 滿(mǎn) ： rear M; 入 隊(duì) ： qrear=x; rear rear+1; 出 隊(duì) ： x=qfront;front=front+1; 圖 3.16 循 環(huán) 隊(duì) 列 0123 54 rear front(a) 空 隊(duì) 列 0123 54 e6e7e8e3e4 e5 0123 54(b) 隊(duì) 列 滿(mǎn) (b) 一 般 情 況front rear e3e

64、4 e5front rear 假 溢 出 的 解 決 方 法 ：（ 1） 將 隊(duì) 中 元 素 向 隊(duì) 頭 移 動(dòng) ； （ 2） 采 用 循 環(huán) 隊(duì) 列 ： q0接 在 QM-1之 后初 態(tài) ： front rear 0或 M-1； 隊(duì) 空 ： front rear;入 隊(duì) ： qrear=x； rear ( rear+1)%M; 出 隊(duì) ： x=qfront; front=(front+1)%M;隊(duì) 滿(mǎn) ： 留 一 個(gè) 空 間 不 用 (rear+1)%M=front; 或 另 設(shè) 一 個(gè) 標(biāo) 志 以 區(qū) 分 隊(duì) 空 和 隊(duì) 滿(mǎn) 。 循 環(huán) 隊(duì) 列 的 類(lèi) 型 定 義 ： define MAX

65、SIZE 100 /*隊(duì) 列 的 最 大 長(zhǎng) 度 */typedef struct QElemType element MAXSIZE ; /* 隊(duì) 列 的 元 素 空 間 */ int front; /*頭 指 針 指 示 器 */ int rear ; /*尾 指 針 指 示 器 */SeqQueue; 循 環(huán) 隊(duì) 列 的 基 本 操 作 ：（ 1） 初 始 化 操 作 。 void InitQueue（ SeqQueue （ 2） 入 隊(duì) 操 作 。 int EnterQueue(SeqQueue *Q, QueueElementType x) /*將 元 素 x入 隊(duì) */ if(Q-

66、rear+1)%MAXSIZE=Q-front) /*隊(duì) 列 已 經(jīng) 滿(mǎn) 了 */ return ERROR; Q-element Q-rear =x; Q-rear=(Q-rear+1)%MAXSIZE; /* 重 新 設(shè) 置 隊(duì) 尾 指 針 */ return OK; /*操 作 成 功 */ （ 3） 出 隊(duì) 操 作 。 int DeQueue(SeqQueue e=Q-element Q-front ; Q-front=(Q-front+1)%MAXSIZE; /*重 新 設(shè) 置 隊(duì) 頭 指 針 */ return OK; /*操 作 成 功 */ 鍵 盤(pán) 輸 入 循 環(huán) 緩 沖 區(qū) 問(wèn) 題 有 兩 個(gè) 進(jìn) 程 同 時(shí) 存 在 于 一 個(gè) 程 序 中 。 其 中 第 一 個(gè) 進(jìn) 程在 屏 幕 上 連 續(xù) 顯 示 字 符 “ A” ， 與 此 同 時(shí) ， 程 序 不 斷 檢 測(cè) 鍵盤(pán) 是 否 有 輸 入 ， 如 果 有 的 話 ， 就 讀 入 用 戶(hù) 鍵 入 的 字 符 并 保 存到 輸 入 緩 沖 區(qū) 中 。 在 用 戶(hù) 輸 入 時(shí) ， 鍵 入 的 字 符 并 不 立 即 回