基本練習題 1 答 :(A) 2 答 :(B) 3 答 :(C) 4 答 :(B) 5 答 :(D) 6 答 :2 7 答 :(B) 8 答 : (A) A B C / D E * + F G / - (B) A B + C D - * E / (C) A B C * + E F + - 9 答 : (A) - + A * - / BCDE / F G (B) / * + A B C D E (C) - + A * B C + E F 10 答 : A + ( B / C D ) * E F / G 處理之中序式運算子處理動作句元堆疊 後序式 1. 運算元 A 規則 2. 直接輸出至後序式 A 2. 運算子 + 規則 3. 必須使用堆疊 堆疊規則 3. Push + A 3. 運算子 ( 規則 3. 必須使用堆疊 ( 堆疊規則 3. 直接 Push + A 4. 運算元 B 規則 2. 直接輸出至後序式 ( + AB 5. 運算子 / 規則 3. 必須使用堆疊 堆疊規則 3. / 的優先序比 ( 大, 故 Push / / ( + AB
6. 運算元 C 規則 2. 直接輸出至後序式 7. 運算子 - 規則 3. 必須使用堆疊 堆疊規則 3. 的優先序比 / 小, 故 Pop 得到 / 並輸出到後序式 接著 Push 8. 運算元 D 規則 2. 直接輸出至後序式 9. 運算子 ) 10. 運算子 * 規則 3. 必須使用堆疊 堆疊規則 2. 一直 Pop, 直到遇見 (, 兩者一同抵銷 規則 3. 必須使用堆疊 堆疊規則 3. * 的優先序比 + 大, 故 Push / 11. 運算元 E 規則 2. 直接輸出至後序式 12. 運算子 - 規則 3. 必須使用堆疊 堆疊規則 3. 的優先序比 * 小, 故 Pop 得到 * 並輸出到後序式 的優先序不比 + 大, 故 Pop 得到 + 並輸出到後序式 接著 Push / ( + - ( + - ( + ABC ABC/ ABC/D + ABC/D- * + * + ABC/D- ABC/D-E - ABC/D-E*+ 13. 運算元 F 規則 2. 直接輸出至後序式 - ABC/D-E*+F 14. 運算子 / 規則 3. 必須使用堆疊 堆疊規則 3. / 的優先序比 - 大, 故 Push / / - ABC/D-E*+F 15. 運算元 G 規則 2. 直接輸出至後序式 規則 4. 中序式已經讀完, 因此將堆疊中剩餘的運算子依序 Pop 到後序式 / ABC/D-E*+FG ABC/D-E*+FG/-
進階練習題 1 答 : ABC/D-E*+FG/- 處理句元處理動作運算元堆疊 1. 運算元 A 規則 2. 直接 Push A (=5) 2. 運算元 B 規則 2. 直接 Push 3. 運算元 C 規則 2. 直接 Push 3. 運算子 / 規則 3. 作兩次 Pop, 先 Pop 出來的 C 為第二運算元, 後 Pop 出來的 B 為第一運算元, 執行 B/C, 設為 X,Push(X) 4. 運算元 D 規則 2. 直接 Push 5. 運算子 - 規則 3. 作兩次 Pop, 先 Pop 出來的 D 為第二運算元, 後 Pop 出來的 X 為第一運算元, 執行 X-D, 設為 Y,Push(Y) 6. 運算元 E 規則 2. 直接 Push 7. 運算子 * 8. 運算子 + 規則 3. 作兩次 Pop, 先 Pop 出來的 E 為第二運算元, 後 Pop 出來的 Y 為第一運算元, 執行 Y*E, 設為 Z,Push(Z) 規則 3. 作兩次 Pop, 先 Pop 出來的 Z 為第二運算元, 後 Pop 出來的 A 為第一運算元, 執行 A+Z, 設為 T,Push(T) B (=6) A (=5) C (=2) B (=6) A (=5) X (=3) A (=5) D (=3) X (=3) A (=5) Y(=0) A (=5) E (=2) Y (=0) A (=5) Z (=0) A (=5) T (=5) 9. 運算元 F 規則 2. 直接 Push 10. 運算元 G 規則 2. 直接 Push 11. 運算子 / 11. 運算子 規則 3. 作兩次 Pop, 先 Pop 出來的 G 為第二運算元, 後 Pop 出來的 F 為第一運算元, 執行 F/G, 設為 W,Push(W) 規則 3. 作兩次 Pop, 先 Pop 出來的 W 為第二運算元, 後 Pop 出來的 T 為第一運算元, 執行 T W, 設為 Q,Push(Q) F (=9) T (=5) G (=3) F (=9) T (=5) W (=3) T (=5) Q(=2) 規則 4. 後序式已經讀完, 堆疊只剩一個元素, 即為結果 Q(=2)
2 答 : [3] [4] [5] [3] [4] [5] [2] [2] [6] B [6] [1] A [1] A [7] [7] [0] [8] [0] [8] [9] [9] (a) front = 0, rear = 1 (b) front = 0, rear = 2 [4] [4] [3] [5] [3] [5] C C [2] B [2] [6] B [6] [1] A [1] [7] [7] [0] [8] [0] [8] [9] [9] (c) front = 0, rear = 3 (d) front = 1, rear = 3 [4] [4] [3] [5] [3] [5] C D D C [2] B [2] [6] [6] [1] [1] [7] [7] [0] [8] [0] [8] [9] [9] (e) front = 1, rear = 4 (f) front = 2, rear = 4
[4] [4] [3] [5] [3] [5] D D E [2] [2] [6] [6] [1] [1] [7] [7] [0] [8] [0] [8] [9] [9] (g) front = 3, rear = 4 (h) front = 3, rear = 5
程式題 1 答 : int Top_Item(STACK *S, char *X) // peek the top item of stack S, if Stack is empty return FALSE if(is_empty(s)) return FALSE; *X = S->item[S->top]; return TRUE;
2 答 : #include <stdio.h> #define MAX_ITEM 9 #define FALSE 0 #define TRUE 1 typedef struct tagstack int Item[MAX_ITEM]; /* 資料欄位 */ int Top; STACK; int IsFull(STACK *S) if (S->Top == (MAX_ITEM-1)) return TRUE; else return FALSE; int Push(STACK *S,int X) if(isfull(s)) return FALSE; S->Top=S->Top+1; S->Item[S->Top]=X; return TRUE; int IsEmpty(STACK *S) if(s->top == -1) return TRUE; else return FALSE; int Pop(STACK *S,int *X) if(isempty(s)) return FALSE; *X=S->Item[S->Top]; S->Top--;
return TRUE ; void PrintStack( STACK *S) int i; if ( IsEmpty(S) ) printf("\n 堆疊為空 \n"); return ; printf("\n 堆疊內容由上到下 : \n"); for (i=s->top;i >= 0;i--) printf("%d ",S->Item[i]); printf("\n"); void main(void) int choose,flagcontinue=true; int data; STACK S; S.Top=-1; while(flagcontinue==true) PrintStack(&S); printf("\n(1)push 資料 (2)POP 資料 (0) 結束 : "); scanf("%d",&choose); switch(choose) case 0: FlagContinue = FALSE; /* 結束程式 */ case 1: printf(" 請輸入欲 PUSH 之資料 =>"); scanf("\n%d",&data); if(push(&s,data) == FALSE) printf(" 堆疊已滿,PUSH 失敗 "); case 2: if(pop(&s,&data) == FALSE) printf(" 堆疊已空,POP 失敗 "); else
printf("pop 出 : %d",data); default: printf(" 選項錯誤 ");
3 答 : #include <stdio.h> #include <math.h> #define MAX_OP 6 #define operator(c) ((c=='+') (c=='-') (c=='*') (c=='/') (c=='^'))?1:0 #define operands(c) ((c)>='a' && (c)<='z')?1:0 #define MAX_ITEM 100 typedef struct stk int item [MAX_ITEM]; int top; STACK; STACK S; char op[max_op]='(','+','-','*','/', ^ ); char prio[max_op]=0,1,1,2,2,3; char op_value[26]=10,30,6,9,8,11,12,13,7,8,22,56,77,76, 55,56,43,40,13,19,18,16,46,52,61,63; void in_to_post(); void push(); void pop(); int post_evaluate(); main() int i; char infix[max_item]; char postfix[max_item]; S.top=-1; printf(" 請輸入中序式, 例如 (a+b)*c-d/e :"); scanf("%s",infix); in_to_post(infix,postfix); printf(" 中序式 => %s \n 後序式 => %s",infix,postfix); printf("\n 若 =>"); for(i=0;i <26;i++) printf("%c=%d, ",(i+'a'),op_value[i]); printf("\n 上式之結果 = %d\n",post_evaluate(postfix));
void push(),pop(); int priority(); void in_to_post(char *infix,char *postfix) int i,j,,element; char token; i=j=0; while((token=infix[i])!= '\0') i=i+1; if(operands(token)) postfix [j++]=token; else if(token == '(') push(token); else if(token == ')') while (S.top >= 0) pop(&(int)element); if(element == '(') postfix [j++]=element; else if(operator(token)) while(s.top >= 0) element=s.item[s.top]; if(priority(token) <= priority (element)) pop(&(int)element); postfix[j++]=element; else push(token); while(s.top >= 0) pop(& element); postfix[j++]=element; postfix[j]='\0';
void push(int x) if (S.top < MAX_ITEM-1) S.top++; S.item[S.top]=x; void pop(int *x) if (S.top >= 0) *x=s.item[s.top]; S.top--; int priority(int c) int i=0; for(;i < MAX_OP;i++) if(op[i] == c) return(prio [i]); return(-1); int post_evaluate(char *postfix) char token; int evaluate(),op1,op2,result,i=0; while((token=postfix[i])!= '\0') i=i+1; if(operands(token)) push(op_value[token-'a']); else if(operator(token)) pop(&op2); pop(&op1); result=evaluate(token,op1,op2); push(result);
pop (&result); return(result); int evaluate(char optr,int op1,int op2) int result; switch(optr) case '+':result=op1+op2; case '-':result=op1-op2; case '*':result=op1*op2; case '/':result=op1/op2; case '^':result=pow(op1,op2); return(result);
4 答 : #include <stdio.h> #include <stdlib.h> long fact(int n) int i; long f=1; for (i=1; i<=n;i++) f = f * i; return(f); void main(void) int n; printf("please input a number less than or equal to 12 => "); scanf("%d",&n); /* 讀入數字 */ if(n > 12) /* 因大於 12 之階乘超出 long 所能表示之範圍 */ printf("the Answer is too large,overflow..."); exit(1); if(n < 0) /* 小於零之數不合法 */ printf("input error,number must > 0"); exit(1); printf("%d! = %ld\n",n,fact(n));
5 答 : #include<stdio.h> #include<stdlib.h> void main(void) int n; void hanoi(); printf("please input number =>"); scanf("%d",&n); /* 讀入數字 */ if(n > 100) /* 因大於 24 之遞迴數列超出 unsigned int 所能表示之範圍 */ printf("the number n is too large,end"); exit(1); if(n < 0) /* 小於零之數不合法 */ printf("input error,number must > 0"); exit(1); hanoi(n,'a','b','c'); printf(" 結束 \n"); /* 把 n 個盤子, 從 form 柱, 經由 by 柱, 搬往 to 柱 */ void hanoi(int n, char from, char by, char to) if(n > 0) hanoi(n-1, from, to, by); printf("move no. %d disk from '%c' to '%c' \n",n, from, to); hanoi(n-1, by, from, to);
6 答 : #include <stdio.h> #include <stdlib.h> #define FALSE 0 #define TRUE 1 typedef struct listnode int data; /* 資料欄位 */ struct listnode *next; NODE; typedef struct taglistqueue NODE *front,*rear; ListQueue; void PrintListQueue(ListQueue *LQ) NODE *p; for (p=lq->front; p!= NULL; p=p->next) printf("%d ",p->data); int Enqueue(ListQueue *LQ,int X) NODE *p; if((p=(node*)malloc(sizeof(node)))==null) return FALSE; p->data=x; p->next=null; if ( LQ->rear!= NULL ) LQ->rear->next=p; else LQ->front =p; LQ->rear = p; return TRUE; int Dequeue(ListQueue *LQ,int *X)
NODE *p=lq->front; if(p ==NULL) return FALSE; *X = p->data; LQ->front=p->next; free(p); return TRUE; void main(void) int choose; int data; ListQueue Q; Q.front=Q.rear=NULL; while(1) printf("\n 佇列內容由前到後 : \n"); PrintListQueue(&Q); printf("\n(1)enqueue 資料 (2)Dequeue 資料 (0) 結束 : "); scanf("%d",&choose); switch(choose) case 0: exit(0); /* 結束程式 */ case 1: printf(" 請輸入欲 Enqueue 之資料 =>"); scanf("\n%d",&data); if(enqueue(&q,data) == FALSE) printf(" 記憶體配置不成功,Enqueue 失敗 "); case 2: if(dequeue(&q,&data) == FALSE) printf(" 佇列已空,Dequeue 失敗 "); else printf("dequeue 出 : %d",data); default: printf(" 選項錯誤 ");
7 答 : #include<stdio.h> #include<stdlib.h> unsigned int Fib (int n) int i,fn,fn_1,fn_2; if (n==0) return 0; if (n==1) return 1; Fn_1=1; Fn_2=0; for(i=2; i<=n; i++) Fn = Fn_1 + Fn_2; Fn_2 = Fn_1; Fn_1 = Fn; return Fn; void main(void) int n; printf("please input number =>"); scanf("%d",&n); /* 讀入數字 */ if(n > 46) //* 因大於 46 之數列超出 unsigned int 所能表示之範圍 printf("the answer will be too large,end"); exit(1); if(n < 0) //* 小於零之數不合法 printf("input error,number must > 0"); exit(1); printf("fib(%d) = %d\n",n,fib(n));
8 答 : int Ackerman( int m, int n) int i; if ( m == 0 ) return ( n+1 ); if ( n == 0 ) return ( Ackerman(m-1, 1) ) ; i = Ackerman( m, n-1 ); return ( Ackerman(m-1, i ) ) ;