Data Structures:

Size: px

Start display at page:

Download "Data Structures:"

问饮张
7 years ago
Views:

1 Data Structures: Stacks 一. 何謂堆疊 (Stacks)? 後進先出 (LIFO, Last In First Out) 的有序數列加入與刪除資料只在頂端 (top) 進行加入資料稱為 push, 刪除資料稱為 pop 加入 p u s h 刪除 p o p 頂端 to p 資料 n 資料資料堆疊 = ( 資料, 資料,.., 資料 n ) 二. 以陣列製作堆疊最簡單之方法乃利用一維陣列下面為一陣列堆疊宣告之例子 ; #define N 00 /* N 為堆疊大小 */ int stack[n]; /* 陣列 stack 當作堆疊 */ int top= -; /* top 表頂端之位置 */ p.s stack[] 及 top 必須定義為全域變數 (Global Variable) Data Structure: Stacks

2 加入 d N -- N -- p+ Top=p Top=p+ p d 0 0 圖一 : 加入資料於陣列堆疊中因此加入資料 d 於堆疊之 push() 函數可簡述如下. 檢查堆疊是否已滿, 若已滿則加入失敗. 否則將堆疊頂端之指標 top 值加, 即 top 上移一格, 新資料在加入目前 top 所指之陣列元素位置中 N- Top =p p- N- p Top=p- Pop 時, 原 top 值為 p, 傳回 stack[top] 後,top 值減, 則頂端位置 top=p- 0 0 圖二 : 刪除堆疊頂端資料因此刪除堆疊頂端資料之 pop() 函數可簡述如下. 檢查堆疊是否空了, 若是空堆疊則刪除失敗. 否則傳回頂端資料後將 top 值減, 即 top 向下移一格 Data Structure: Stacks

3 範例一寫一程式可以執行 push, pop, +, -, exit 等功能其中 (). push: 加入資料於堆疊內 (). pop: 傳回並刪除堆疊的頂端資料 (3). +: 取出堆疊頂端兩筆資料相加後之結果在存回堆疊內 (4). - : 取出堆疊頂端兩筆資料相減後之結果在存回堆疊內 (5). exit: 直到輸入 exit 才結束程式之執行 ( 見課本 p.3- 範例 4) /**************************************************************/ #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <string.h> #define N 00 /* 陣列堆疊宣告 */ int stack[n]; int top=-; /***************************************************************** * push 函式部分 ( 加入資料於堆疊內 ) *****************************************************************/ void push(int d) /* 加入資料於堆疊內 */ if(top == N-) printf(" 堆疊滿了 \n"); /* 注意堆疊大小 */ exit(); /* 加入失敗, 執行結束 */ } /* end if */ stack[++top]=d; } /* end of push 函數 */ /***************************************************************** * pop 函式部分 ( 刪除堆疊的頂端資料 ) * *****************************************************************/ int pop() if(top == -) /* 注意空堆疊情形 */ printf(" 堆疊空了 \n"); exit(); /* 刪除失敗, 執行結束 */ } Data Structure: Stacks 3

4 } return(stack[top--]); /***************************************************************** * 主程式部分 *****************************************************************/ void main() int d, loop=; /*loop 表迴圈控制變數 */ char input[5]; clrscr(); /* 清除螢幕畫面 */ printf("*** 陣列堆疊 ***\n"); printf(" 可執行下列指令 : push, pop, +, -, exit\n\n"); do printf("==>"); scanf("%s",input); if(strcmp(input,"push")==0) /* 字串比較若相等則傳回之值 */ /* 此時作 push 動作 */ printf(" 輸入數值 :"); scanf("%d",&d); push(d); } /* end of if(strcmp(..) 指令 */ else if(strcmp(input,"pop")==0) /* 此時作 pop 動作 */ if(top == -) printf(" 堆疊空了 \n"); else printf("%d\n",pop()); else if(strcmp(input,"+")==0) push(pop()+pop()); else if(strcmp(input,"-")==0) push(pop()-pop()); else if(strcmp(input,"exit")==0) /* 此時 exit */ loop=0; else printf(" 輸入錯誤!\n"); } while(loop); /* 數值 loop= 0 代表 false, 此時迴圈結束 */ printf("bye-bye!\n"); } Data Structure: Stacks 4

5 三. 以串列指標避免全域變數使用指標形式亦可用來描述堆疊優點 : 在同一程式中可以供多種不同的堆疊使用, 且避免全域變數之使用, 缺點 : 函數之呼叫變得更複雜 /***************************************************************** * push 函式部分 ( 加入資料於堆疊內 ) * *****************************************************************/ void push(int d, int stack[ ], int *top ) /* 此處之 top 為一指標型區域變數 */ (*top)++; /* 指標指向頂端, 增量增加 */ stack[*top]=d; /* 儲存資料 d 於堆疊頂端 */ } /* end of push 函數 */ /***************************************************************** * pop 函式部分 ( 刪除堆疊的頂端資料 ) * *****************************************************************/ int pop(int stack[ ], int *top) int d; } d = stack[*top]; (*top)--; /* 減量減少 */ return(d); Data Structure: Stacks 5

6 四. 堆疊之應用一 : 副程式之呼叫假設有一個主程式 X 呼叫副程式 Y,, 副程式 Y 呼叫副程式 Z, 電腦之作業系統會以堆疊來儲存返回 (return) 之位址, 當副程式 Z 做完後, 會由堆疊彈回副程式 Y 之位址, 當副程式 Y 做完後, 再由堆疊彈回主程式 X 之位址主程式 X 副程式 Y 副程式 Z... Call Y Call Z Statement A.. Statement B. return.... return Statement B 位址 Statement A 位址五. 堆疊之應用二 : 代數運算式的求值計算. 運算式之組成一個運算式 (expression) 是由運算元 (operand) 運算子 (operator) 及間隔符號 (delimiter) 所構成以 C 語言為例, 運算式中包含下列三種符號 ; 運算元 (operand);0,,,3,.etc. 運算子 (operator) ;+,-,*,/,**,<,<=, >=, ++,!=, ++, --, =, +=,.. etc. 間隔符號 (delimiter) ;(,) Data Structure: Stacks 6

7 . 運算式之計算原則優先權 (precedence); 運算子運算原則優先權較高之運算子先執行結合性 (associatively) ; 優先權相同者, 則視其結合性而定. 結合性由左而右 (left to right), 則由左而右執行如 :(+) (-). 結合性由右而左 (right to left), 則由右而左執行如 : 次方 ($) 運算子性質運算子優先權結合性算術運算子次方 ($) *( 指標 ) +( 正號 ) 由右而左 - ( 負號 ) 高算術運算子 *( 乘號 ) /( 除號 ) %( 整數由左而右除號 ) 算術運算子 +( 加號 ) -( 減號 ) 由左而右關係運算子 < <= ==!= > >= 由左而右邏輯運算子 && (and) 由左而右低邏輯運算子 (or) 由左而右指定運算子 = ( 指定 ) 由右而左圖一 ; 常見運算子及優先權次序表格 Data Structure: Stacks 7

8 3. 運算式之表示法中序運算式 (Infix Order):< 運算元 > < 運算子 > < 運算元 > 將運算子置於兩運算元中間之表示法例如 : a+b, 3*-6 缺點 : 電腦無法一次依序讀取運算式因運算式可能含有括號, 且運算子優先順序不同後序運算式 (Postfix Order):< 運算元 > < 運算元 > < 運算子 > 將運算子置於兩運算元之後之表示法例如 : ab+, 3 * 6 - p.s 此法又稱為反波蘭記號法 ;RPN 其優點在於不必使用括號, 且運算子不具優先權 4. 後序運算式之計算表示法 (Evaluation of Postfix Expression) 規則如下 : 由左而右讀進後序運算式的每個字元 (Token) 判別字元, 若為運算元 (operand), 則將其放入堆疊中判別字元, 若為運算子 (operand), 則自堆疊中取出適當個數之運算元, ( 單元運算子, 取一個運算元 ; 二元運算子, 取兩個運算元 ), 並執行運算子所對應之計算, 並將計算結果放入堆疊中若字串結束 (end of string), 堆疊內唯一值即為所要結果 Data Structure: Stacks 8

9 單元運算子 (Unary Operator) 二元運算子 (Binary Operator) +( 正號 ) - ( 負號 )!(not) *( 乘號 ) /( 除號 ) +( 加號 ) -( 減號 ) && (and) (or) 圖二 ; 常見運算子 Start Initialize Stack Read Next Token End of String? yes Pop result from Stack no Operand? yes Push x to Stack Pop operand Perform operation Push results to stack Uinary no Binary or Unary? Binary Pop operands Perform operations Push results to stack 圖三 ; 後序運算式之流程圖 Data Structure: Stacks 9

10 範例 - 二計算後序運算式 : ( / + * $ 3 + ) 之值 Token Opnd Opnd Value Stack / + * $ , 6,,3 6,5,3,3,8,3,8,,3,4,7 7 7, 49 49,3 5 Data Structure: Stacks 0

11 範例 - 三以下為計算後序運算式值之程式 (p.s. 此程式只計算常見之二元運算元 ) # include <stdio.h> # include <math.h> # include <ctype.h> # include <stdlib.h> /* 陣列堆疊宣告 */ #define N 00 int stack[n]; /********************************************************************** * push 函式部分 ( stack[] 宣告為全域變數 ) *****************************************************************/ void push(int d, int *top ) /* 此處之 top 為一指標型區域變數 */ if (*top == N-) printf(" 堆疊滿了 \n"); /* 注意堆疊大小 */ exit(); /* exit 定義在 stdlib.h 中 */ /* exit(0) 表示正常,exit() 表示有誤 */ } /* end if */ else (*top)++; /* 指標指向頂端, 增量增加 */ stack[*top]=d; /* 儲存資料 d 於堆疊頂端 */ } /* end else */ } /* end of push 函數 */ Data Structure: Stacks

12 /********************************************************************** * pop 函式部分 ( stack[] 宣告為全域變數 ) *****************************************************************/ int pop(int *top) if (*top == -) /* 注意空堆疊情形 */ printf(" 堆疊空了 \n"); exit(); /* 刪除失敗, 執行結束 */ } else return(stack[(*top)--]); } /*************************************************************************** * oper 函數 ( 檢查有效二元運算子, 並計算該運算運用在其後兩參數之結果 ) * ***************************************************************************/ double oper(int symb, double op, double op) switch (symb) case + : return (op+op); /* 相加運算 */ case - : return (op-op); /* 相減運算 */ case * : return (op*op); /* 相乘運算 */ case / : return (op/op); /* 相除運算 */ case $ : return (pow(op,op)); /* 次方運算, pow 定義在 math.h 中 */ default : printf( %s, illegal operation ); exit(); /* 加入失敗, 執行結束 */ } /* end switch*/ } /* end oper 函數 */ /***************************************************************** * eva_postfix 函數 ( 計算後序運算式值 ) *****************************************************************/ double eval_postfix(char expr[]) Data Structure: Stacks

13 int c, position; double opnd, opnd, value; top = -; /* initialize stack*/ for (position = 0; (c = expr[position])!= \0 ; position++) /* 將儲存後序運算式從頭到尾依序讀出 */ /* 字串之 \0 為字串終止控制指令 */ if (isdigit(c)) /* 將自十進位數值字元轉換為可計算之 double */ else /* isdigit(c) 函數定義在 ctype.h 中 */ push( (double)(c 0 ),&top); /* c - 0 會將字元變數 c 之 ASCII 碼減去字元 0 之 ASCII 碼 */ /* 此時讀進之字元為 operator */ opnd = pop(&top); opnd = pop(&top); /* 取出堆疊最頂端的兩個運算元 */ value = oper(c, opnd, opnd); /* 並執行運算子所對應之計算 */ push(value, &top); /* 將計算結果放入堆疊中 */ } /* end else */ return (pop(&top)); /* 傳回堆疊內唯一值 */ } /* end eval_postfix */ /***************************************************************** * 主程式部分 *****************************************************************/ void main() char expr[n]; int position = 0; while ((expr[position++] = getchar())!= \n ) ; /* getchar() 函數定義在 ctype.h 中 */ /* 從系統開啟檔案或鍵盤中讀取單一字元 */ } /* end main*/ expr[--position] = \0 ; printf ( \n %s %s, the original postfix expression is, expr); /* 列印原始後序運算式 */ printf( \n %f, eval_postfix(expr)); /* 列印計算後之計算值 */ Data Structure: Stacks 3

14 六. 堆疊之應用三 : 中序運算式轉換為後序運算式方法一 : 算術運算式由中序變為後序可依下列三步驟進行 :. 將式子中的運算單元適當的加以括號, 此時須考慮運算子的運算優先順序. 將所有的運算子移到其對應的右括號 3. 將所有的括號去掉如將 A*B/C 化為後序表示式 () ( ( A * B ) / C) () ( ( A * B ) / C) =>( ( A B ) * C ) / (3) AB*C/ 再舉一例將 A-B/C+D*E-F%G 化成後序表示式 () ( ( ( A - ( B / C ) ) + ( D * E ) ) - ( F % G ) ) () ( ( ( A - ( B / C ) ) + ( D * E ) ) - ( F % G ) ) (3) A B C / - D E * + F G % - Data Structure: Stacks 4

15 方法二 : Start Initialize Stack Read Next Token A Operand? yes Print A no End of String? no (? yes yes Pop from Stack until empty Push this token Stop no )? yes Pop A from stack and print no A until ( ICP>ISP? yes Push A to Stack no Pop from Stack 圖四 ; 中序運算式轉換為後序運算式之流程圖規則如下 : 由左而右讀進中序運算式的每個字元 (Token) 判別字元, 若為運算元 (operand), 則直接輸出 Data Structure: Stacks 5

16 判別字元, 若為運算子 (operator), 則 () 若 Token 為 (, 則直接加入堆疊頂端 () 若 Token 之優先權 (ICP, In-Coming Priority) 高於堆疊頂端之優先權 (ISP, In-Stack Priority), 則直接加入堆疊頂端 (3) 若 Token 之優先權 (ICP) 小於或等於於堆疊頂端之優先權 (ISP), 則將堆疊中之運算子自頂端逐一取出並輸出, 直到堆疊頂端之運算子優先權低於 Token, 再將此 Token 放入堆疊中 (4) 若 Token 為 ), 則將堆疊中之運算子自頂端逐一取出並輸出, 直到取出對應之 ( 為止, 但 ( 不須輸出注意 : ) 永遠不會被放入堆疊中 (5) 若字串結束 (end of string, eos), 則將堆疊中所有運算子自頂端逐一取出並輸出, 值到堆疊空了符號 In-Stack Priority (ISP) In-Coming Priority (ICP) ( 5 ) * 3 3 / 3 3 % 3 3 operand 0 0 Data Structure: Stacks 6

17 範例四試將下列中序運算式 (infix) 轉換為後序運算式 (postfix): (( A - ( B + C ))*D)$(E+F) Step Token Postfix Stack ( ( ( (( 3 A A (( 4 - A ((- 5 ( A ((-( 6 B AB ((-( 7 + AB ((-(+ 8 C ABC ((-(+ 9 ) ABC+ ((- 0 ) ABC+- ( * ABC+- (* D ABC+-D (* 3 ) ABC+-D* 4 $ ABC+-D* $ 5 ( ABC+-D* $( 6 E ABC+-D*E $( 7 + ABC+-D*E $(+ 8 F ABC+-D*EF $(+ 9 ) ABC+-D*EF+ $ 0 ABC+-D*EF+$ Data Structure: Stacks 7

18 /* 變數宣告部分 */ #define N 00 /* N 為全域變數 */ typedef enumleft_paren,right_paren, plus, minus, times, divide, mode, operand} precedence; /* 定義優先順序之資料型態 */ precedence stack[n]; int ISP[]=,4,,,3,3,3,0}; /* 定義堆疊頂端之優先權 */ int ICP[]= 5,4,,,3,3,3,0}; /* 定義 Token 之優先權 */ /* get_token 函數 ( 讀取字元 Token, 並按照其優先順序分類 ) */ precedence get_token (char token) switch (token) /* 將讀進之 Token 量化並分類 */ case '(' : return left_paren; /* 此時 '(' 等於 left_paren = 0 */ case ')' : return right_paren; /* 此時 ')' 等於 right_paren = */ case '+' : return plus; /* 依此類推 */ case '-' : return minus; case '*' : return times; case '/' : return divide; case '%' : return mode; default : return operand; } /* end switch*/ } /* end get_token 函數 */ /* infix_to_postfix 函數 ( 將中序式轉換為計後序運算式 ) */ void infix_to_postfix(char expr[]) int position=0; /* 目前讀取位元之位置 */ char c; /* 讀取一個字元 */ precedence token; /* 分類後之 token */ top = -; /* initialize stack */ Data Structure: Stacks 8

19 for (position = 0; (c = expr[position])!= '\0'; position++) /* 將儲存中序運算式從頭到尾依序讀出 */ /* 字串之 '\0' 為字串終止控制指令 */ token = get_token(c); /* 讀取一個字元 */ switch (token) case operand : /* 此時 token 為運算元 */ printf("%c", c); break; case right_paren : while(stack[top]!= left_paren) /* 自堆疊頂端逐一取出並輸出, 直到取出 '(' 為止 */ print_symbol(stack[top]); pop(&top); /* 移除堆疊頂端之 '(', 不須印出 */ } /* end while */ break; default: if (empty(&top)) /* empty stack, push the token directly */ push(token, &top); else while ((!empty(&top)) && (ISP[stack[top]] >= ICP[token])) print_symbol(pop(&top)); push(token, &top); /* push token to stack */ } /* end else */ } /* end switch */ } /* end for */ do /* end of string, pop from stack until empty */ token = pop(&top); print_symbol(token); } while (!empty(&top)); } /* end infix_to_postfix */ p.s empty 及 print_symbol 函數須自行定義 Data Structure: Stacks 9

20 範例 - 五試將下列中序運算式 (infix) 轉換為後序運算式 (postfix): a * ( b + c / d e ) * f 輸入字元堆疊內容輸出字元說明 \0 習題. 將下列中序運算式轉換後序式 (a.) a + ( b c / d) * e (b.) (a - b + c ) / ( d e / f * g) (c.) (a - b ) - ( c + d ) $ e * f (d.) (a - b ) $ (c * ( d e ) + f) g. 將下列後序運算式轉為中序式 (a.) a b + c- (b.) a b c - * (c.) a b c + d e f - + $ (d.) a b c d e - + $ * f g * - 3. 求下列後序式之值 (a.) $ - (b.) * *\ 4. 將下列中序運算式轉換前序式 (a.) a + ( b c / d) * e (b.) (a - b + c ) / ( d e / f * g) (c.) (a - b ) - ( c + d ) $ e * f (d.) (a - b ) $ (c * ( d e ) + f) g Data Structure: Stacks 0

Microsoft PowerPoint - Fig03_Stack.ppt [相容模式]

Microsoft PowerPoint - Fig03_Stack.ppt [相容模式] 四堆疊與佇列 (Stack & Queue) 4-. 串列及鏈結串列 4-. 用陣列結構實作堆疊 4-3. 用鏈結串列實作堆疊 4-4. 堆疊的應用 4-5. 佇列 4-6. 用陣列結構實作佇列 4-7 7. 用鏈結串列實作佇列堆疊的基本觀念. 定義 : 4- 堆疊當將東西疊成一堆, 而取用的時候由上方來取出. 特性 : 先進後出, 後進先出 ( 號球先放, 但 3 號球會先拿出 ) 3 3