大數(shù)據(jù)結(jié)構(gòu)與算法源代碼

1、實用標(biāo)準(zhǔn)文案課程說明：數(shù)據(jù)結(jié)構(gòu)一共四天課程，day01day04.CSD DataStructure DAY011 .基于順序表的堆棧2 .基于鏈?zhǔn)奖淼亩褩?基于順序表的堆棧棧是一種特殊的線性表，是限定在線性表表尾進(jìn)行插入刪除操作的線性表。由棧的概念衍生出幾個子概念，它們是：1）棧頂，即允許進(jìn)行插入、刪除操作的一端，又稱為表尾，用棧頂指針（）來指示棧頂2）棧底，即固定端，又稱為表頭3）空棧，即棧當(dāng)中沒有數(shù)據(jù)元素。順序棧是采用順序存儲結(jié)構(gòu)的棧，即使用一組連續(xù)的存儲單元（一般使用數(shù)組）來模 擬棧，依次存放棧中的數(shù)據(jù)元素。1.1 方案順序棧的基本操作包括：1）初始化操作，在初始化操作中將建立一個空棧

2、。2）判斷棧空，判斷棧中的數(shù)據(jù)元素個數(shù)是否為0。3）入棧，在棧中加入一個數(shù)據(jù)元素。4）出棧，在棧中刪除一個數(shù)據(jù)元素。5）取棧頂元素，將棧頂元素取出，但并不在棧中刪除該元素。1.2 步驟實現(xiàn)此案例需要按照如下步驟進(jìn)行。步驟一：定義棧在C語言中：1）定義一個一維數(shù)組來表示棧的順序存儲空間。2）定義一個變量來指出棧頂?shù)奈恢谩?）這兩方面的信息共同描述一個棧，可將它們用結(jié)構(gòu)體封裝在一起。代碼如下：2. typedef int DataType;3. struct Stack 4. DataType data LISTSIZE5. int; /除了記錄大小還可以記錄棧頂位置6. ;上述代碼中，以下代碼：

3、1. #define LISTSIZE100是用一個宏常量來定義順序表的容量，這樣定義的好處是當(dāng)需要修改順序表的容量的 時候，只需要修改該宏常量即可。上述代碼中，以下代碼：2. typedef int DataType;是將數(shù)據(jù)類型int起了一個別名叫做 DataType ,并在后面的程序中只使用 DataType , 而不使用int。這樣做的好處是當(dāng)堆棧中的數(shù)據(jù)類型發(fā)生變化時，只需要修改此句中的int為要改變的數(shù)據(jù)類型，即可將程序中所有數(shù)據(jù)變量的數(shù)據(jù)類型變成指定的類型。步驟二：初始化操作在主程序中，定義棧結(jié)構(gòu)體的變量。在初始化函數(shù)中將該變量中的棧頂指針初始化為0,表示為空棧。代碼如下：3.

4、void init (struct Stack* stack)4. 5. stack-> = 0;6. 7. intmain(intargc, constchar* argv|)8. 9. struct Stack stack;10. Hinit (&stack);11. 步驟三：判斷?？张袛鄺？諏嶋H上是判斷棧頂指針是否為0,因為當(dāng)棧頂指針為0時，代表棧中沒有數(shù)據(jù)元素。代碼如下：1. bool empty (struct Stack * stack) 2. return stack-> = 0;3. 步驟四：入棧入棧是在棧中加入一個數(shù)據(jù)元素，在入棧時，首先需要判斷棧是否為滿

5、，如果棧滿了,則就不能在向其中添加元素了，判斷棧是否滿的操作只有在順序存儲結(jié)構(gòu)才會出現(xiàn)，因為 采用順序存儲結(jié)構(gòu)的棧是要事先定義棧的容量的。然后將數(shù)據(jù)元素放入棧中，并使棧頂指 針加1,指向下一個位置。代碼如下：1. void push(struct Stack * stack, DataType d) 2. |if (stack-> =LISTSIZE3. return4. stack->data stack->+ = d;5. 上述代碼中，以下代碼：1. Bif (stack-> =LISTSIZE是判斷棧是否滿，判斷棧頂指針是否與棧的容量相等，如果是，則表示棧已經(jīng)滿了

6、。步驟五：出棧出棧操作實際上是將棧中的棧頂元素刪除，在出棧時，首先判斷棧是否為空，如果棧 為空則代表棧中已經(jīng)沒有數(shù)據(jù)元素了，此時是不可能進(jìn)行出棧操作的。然后，將棧頂指針 減1。代碼如下：2. void pop (struct Stack * stack) 3. if (empty (stack)4. return;5. stack-;6. 步驟六：取棧頂元素取棧頂元素操作實際上是僅返回棧頂元素，而棧頂指針并不變動。在取棧頂元素時， 首先也要判斷棧是否為空，因為空棧同樣是不可能有數(shù)據(jù)元素的。代碼如下：1. DataType Data(struct Stack * stack) 2. return

7、 stack->data stack-1;3. 1.3完整代碼本案例的完整代碼如下所示：1. #include <stdio. h>2. #include <stdbool .h>3.5. typedef int DataType;6. struct Stack 7. DataType dataLISTSIZE8. int; 處了記錄大小 還可以記錄棧頂位置9. ;10.11. void init (struct Stack * stack)12. 13. flstack-> = 0;14. 15.16. bool empty (struct Stack *

8、 stack) 17. return stack-> = 0;18. 19.20. void push(struct Stack * stack, DataType d) 21. |if (stack-> = LISTSIZE22. return;23. stack->data stack->+ = d;24. 25.26. void pop (struct Stack * stack) 27. flif (empty (stack)28. return;29. Hstack->-;30. 31.32. DataType Data(struct Stack * s

9、tack) 33. return stack->datastack-> -1;34. 35.36.37. int main()38. 39. struct Stack stack;40. Hinit (&stack);4.#define LISTSIZE10精彩文檔實用標(biāo)準(zhǔn)文案41. push(&stack, 30);42. push(&stack, 60);43. push(&stack, 80);44. 45. while (!empty (&stack) 46. (printf ("%d ", Data(&s

10、tack);47. Hpop (&stack);48. 49. flprintf ("n");50. 51. return 0;52. 2基于鏈?zhǔn)奖淼亩褩?.1 問題鏈棧是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，即使用一組不要求連續(xù)的存儲空間來模擬棧。每個棧 元素為一個節(jié)點， 每個節(jié)點中包含兩個域，一個是數(shù)據(jù)域，用于存儲棧元素的數(shù)據(jù)；另 個是指針域，用于存儲下一個棧元素的地址。2.2 方案鏈棧的基本操作包括：1)初始化操作，在初始化操作中將棧頂指針置空。2)判斷棧空，判斷棧頂指針是否為空。3)入棧，在棧中加入一個數(shù)據(jù)元素。4)出棧，在棧中刪除一個數(shù)據(jù)元素。5)取棧頂元素，將棧頂元素取

11、出，但并不在棧中刪除該元素。2.3 步驟實現(xiàn)此案例需要按照如下步驟進(jìn)行。步驟一：定義棧元素節(jié)點在C語言中：1)定義一個變量來表示棧元素的數(shù)據(jù)。2)定義一個指針來指向下一個棧元素的位置。3)這兩方面的信息共同描述一個棧元素節(jié)點，可將它們用結(jié)構(gòu)體封裝在一起。代碼如下：1. typedef int DataType;2. struct Stack 3. DataType data;4. struct Stack * next;5. ;上述代碼中，以下代碼：1. struct Stack * next;是定義了一個指向下一個棧元素的指針，由于下一個棧元素的數(shù)據(jù)類型與當(dāng)前棧元素 的數(shù)據(jù)類型相同，所以指針

12、的數(shù)據(jù)類型就是棧節(jié)點的指針數(shù)據(jù)類型。步驟二：初始化操作 在主程序中，定義棧頂指針。在初始化函數(shù)中將棧頂指針初始化為NULL表示為空棧。代碼如下：2. void init (struct Stack* )3. 4. 1* = NULL;5. 6. int main()7. 8. struct Stack *;9. Bnit(&);10. return 0;11. 上述代碼中，以下代碼：1. void init (struct Stack* )定義了初始化函數(shù)的函數(shù)頭，該函數(shù)有一個形參，是棧元素結(jié)構(gòu)體指針的指針。之所 以使用指針的指針，是因為棧頂指針在函數(shù)執(zhí)行過程中會被置空，而這種變化需要

13、帶回主 函數(shù)。步驟三：判斷?？张袛鄺？詹僮鲗嶋H上就是判斷棧頂指針是否為空。代碼如下所示：2. boolempty (struct Stack * )3. 4. flreturn=NULL;5. 步驟四：入棧入棧操作實際上就是在棧中加入一個數(shù)據(jù)元素，對于鏈棧，入棧操作本質(zhì)上就是在棧 中加入一個結(jié)點。代碼如下所示:1. void push(struct Stack* , DataType d)2. 3. struct Stack * newNode = (struct Stack *) malloc (sizeof(struct Stack);4. newNode ->data=d;5. n

14、ewNode ->next=*;6. *e = newNode ;7. 上述代碼中，以下代碼：1.void push(struct Stack* , DataType d)定義了入棧函數(shù)的函數(shù)頭，該函數(shù)有兩個形參，第一個是棧結(jié)構(gòu)的指針的指針，在這 里使用指針的指針，還是因為需要將棧頂指針的變化帶回主函數(shù)。第二個形參是需要入棧 的數(shù)據(jù)。1.上述代碼中，以下代碼:struct Stack * newNode = (struct Stack *) malloc (sizeof(struct Stack);是構(gòu)造一個新的棧元素節(jié)點。上述代碼中，以下代碼：1.newNode ->data =

15、 d;是將需要入棧的元素放入新的棧元素節(jié)點中。上述代碼中，以下代碼：1. newNode ->next = *;是將新創(chuàng)建的棧元素節(jié)點加入到棧中原棧頂元素的前面，成為新的棧頂元素。上述代碼中，以下代碼：2. * = newNode ;是棧頂指針指向新創(chuàng)建的棧頂元素。正是由于這行代碼，使棧頂指針發(fā)生了變化，而 這種變化需要帶回到主程序，所以函數(shù)的第一個形參必須是指針的指針。步驟五：出棧出棧操作實際上就是從棧中刪除棧頂位置的元素，對于鏈棧，出棧操作本質(zhì)上就是在 棧中刪除一個結(jié)點。代碼如下所示：3. void pop(struct Stack*)4. 5. flif (empty (*)6.

16、return;7. flstruct Stack * tempNode = *;8. *=(*)-> next;9. free(tempNode );10. 上述代碼中，以下代碼：1. if (empty (*)2. return是判斷鏈棧是否為空，如果棧為空是不能從棧中刪除元素的。上述代碼中，以下代碼：1. flstruct Stack * tempNode = *;2. *KH) =(*)-> next ；3. free(tempNode );首先用一個臨時指針保存原棧頂指針指向的棧元素地址，即出棧元素的地址，然后將 棧頂指針指向下一個元素，這樣棧中就減少了一個元素。最后釋放臨

17、時指針指向的元素， 即釋放出棧元素所占的存儲空間。步驟六：取棧頂元素取棧頂元素實際上就是將棧頂元素的值返回，對于鏈棧，本質(zhì)上是將棧頂節(jié)點的數(shù)據(jù) 返回。注意，在取棧頂元素時，首先要判斷棧是否為空，空棧是沒有數(shù)據(jù)元素的。代碼如下：1. void Data (struct Stack * , DataType* data)2. 3. flif (empty ()4. return;5. H* data = ->data;6. 2.4完整代碼本案例的完整代碼如下所示：1. #include <stdio. h>2. #include <stdlib .h>3. #incl

18、ude <stdbool .h>4.5. typedef int DataType;6. struct Stack 7. DataType data;8. flstruct Stack * next;9. ；10.11. voidinit (struct Stack*)12. 13. * = NULL;14. 15.16. boolempty (struct Stack * )17. 18. return= NULL;19. 20.21. void push (struct Stack*,DataTyped)22. 23. struct Stack * newNode = (str

19、uct Stack*) malloc(sizeof(struct Stack);24. newNode ->data = d;25. newNode ->next = *;26. 1* = newNode ;27. 28.29. void pop(struct Stack*)30. 31. if (empty (*)32. return;33. flstruct Stack * tempNode = *;34. * =(*)-> next;35. free(tempNode );36. 37.38. void Data (struct Stack * , DataType*

20、data)39. 40. Hif (empty ()41. return;42. H* data = ->data;43. 44.45.46. int main()47. 48. Hstruct Stack *;49.50.51.52.53.54.55.56.57.58.59.60.61.62.63.init(&);push(&, 30);push(&, 60);push(&, 80);while (!empty () int data;Data(, & data);printf ("%d ", data);pop (&

21、)；printf ("n");return 0;作業(yè):1 1.逆波蘭法求解四則運(yùn)算表達(dá)式在計算機(jī)中，表達(dá)式的處理是很重要的一項工作。表達(dá)式被分成中綴表達(dá)式和后綴表達(dá)式兩種形式。所謂中綴表達(dá)式就是我們?nèi)粘鴮懕磉_(dá)式的方法，操作數(shù)在兩邊，運(yùn)算符在中間，如1+2。這種表達(dá)式易于理解，但是很難被計算機(jī)解析。為了讓計算機(jī)能夠簡單地解析表達(dá)式，可采用后綴表達(dá)式。后綴表達(dá)式又被稱為逆波蘭表示法，是將運(yùn)算符至于操作數(shù)的后面，如中綴表達(dá)式1+2表示成后綴表達(dá)式為 12+。后綴表達(dá)式中的一個特點是不需要使用括號，就可以準(zhǔn)確地表示表達(dá)式的優(yōu)先級，如中綴表達(dá)式1+2*3表示成后綴表達(dá)式后為123*

22、-,而中綴表達(dá)式（1+2 ） *3表示成后綴表達(dá)式則為12+3* 。本案例的工作是先將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，然后計算后綴表達(dá)式。實現(xiàn)此案例需要按照如下步驟進(jìn)行。步驟一：定義兩個棧首先，定義一個字符數(shù)組，用于存放待轉(zhuǎn)換的字符串。定義一個“結(jié)果?！保糜诖娣呸D(zhuǎn)換過程中的每一步結(jié)果。定義一個“運(yùn)算符?！保糜诖娣呸D(zhuǎn)換過程中的運(yùn)算符。代碼如下所示:1. #include <stdio.h>2. #include <stdbool .h>3.4. #define LISTSIZE105. typedefint DataType;6.7. struct Stack 8. |D

23、ataType dataLISTSIZE9. int ; /處了記錄大小還可以記錄棧頂位置10. ；11.12. void init (structStack * stack)13. 14. Hstack-> =0;15. 16.17. void push (struct Stack * stack, DataType d)18. flstack->data stack->+ = d;19. 20.21. void pop (structStack *stack) 22. Hstack->-;23. 24.25. DataType (structStack*stack)

24、 26. return stack->datastack-> -1;27. 28.29. boolempty (structStack *stack) 30. return stack-> =0;31. 32.33. bool prior (char op1, char op2) 34. |return (op1 = '*' | op1 = '/') && (op2 ='+'| op2 ='-');35. 36.37. int main() 38. char expr = "1+2*3/

25、(4-1)"39. struct Stackres;/ 結(jié)果棧40. Hstruct Stackoper;/ 運(yùn)算符棧41. init(&res)；42. flinit (&oper);43. 步驟二：逐個讀取字符串中的字符，直到結(jié)束設(shè)置一個循環(huán)，逐個從字符數(shù)組expr中讀取字符，直到遇見字符'代碼如下所示：1. #include <stdio.h>2. #include <stdbool .h>3.4. #define LISTSIZE105. typedef int DataType ;6.7. struct Stack 8. BD

26、ataType dataLISTSIZE9. int ; /處了記錄大小還可以記錄棧頂位置10. ；11.12. void init (struct Stack * stack)13. 14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.stack-> = 0;void push (struct Stack * stack, DataType d) stack->data stack->+ = d;void pop (stru

27、ct Stack * stack) stack-;DataType (struct Stack * stack) return stack->datastack-1;bool empty (struct Stack * stack) return stack-> = 0;bool prior (char op1, char op2) return (op1 = '*' | op1 = '/') && (op2 ='+'| op2 ='-');int main () charexpr口 = "1

28、+2*3/(4-1)”;struct Stack res;/ 結(jié)果棧struct Stack oper;/ 運(yùn)算符棧 init (&res);init (&oper);for (int i =0; expri != '0' i+) char ch = expri;步驟三：將數(shù)字放入“結(jié)果棧”中判斷讀出的字符是否是數(shù)字，如果是數(shù)字，則將該數(shù)字放入“結(jié)果?！敝小４a如下所示:1. #include <stdio.h>2. #include <stdbool .h>3.4. #define LISTSIZE105. typedefint Dat

29、aType ;6.7. struct Stack 8. HDataType dataLISTSIZE9. int ; /處了記錄大小還可以記錄棧頂位置10. ；11.12. voidinit (struct Stack * stack)13. 14. stack-> = 0;15. 16.17. void push (struct Stack * stack, DataType d) 18. stack->data stack->+ = d;19. 20.21. void pop (struct Stack * stack) 22. Hstack->-;23. 24.2

30、5. DataType (struct Stack * stack) 26. return stack->datastack-> -1;27. 28.29. bool empty (struct Stack * stack) 30. return stack-> = 0;31. 32.33. bool prior (char op1, char op2) 34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.return (op1 = '*' | op1 = '/') &&am

31、p; (op2 ='+'| op2 ='-');int main () charexpr口 = "1+2*3/(4-1)”;struct Stack res;/ 結(jié)果棧struct Stack oper;/ 運(yùn)算符棧init (&res);init (&oper);for (inti =0; expr i != '0' ;i+)char ch = expri;/isdigit就是判斷字符是否是一個數(shù)字if (isdigit(ch) /如果是一個數(shù)字放到結(jié)果棧中push(&res, ch);步驟四：將左括號“(”放

32、入“運(yùn)算符?！迸袛嘧x出的字符是否是左括號“(”，如果是，則將該字符放入“結(jié)果?！敝?。代碼如下：1. #include <stdio.h>2. #include <stdbool .h>3.4. #define LISTSIZE105. typedef int DataType ;6.7. struct Stack 8. BDataType dataLISTSIZE9. int ; /處了記錄大小還可以記錄棧頂位置10. ；11.12. void init (struct Stack * stack)13.14.15.16.17.18.19.20.21.22.23.24.

33、25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.stack-> = 0;void push (struct Stack * stack, DataType d) stack->data stack->+ = d;void pop (struct Stack * stack) stack-;DataType (struct Stack * stack) return stack->datastack-1;bool empty (struct Stack * stack) ret

34、urn stack-> = 0;bool prior (char op1, char op2) return (op1 = '*' | op1 = '/') && (op2 ='+'| op2 ='-');int main () charexpr口 = "1+2*3/(4-1)”;struct Stack res;/ 結(jié)果棧struct Stack oper;/ 運(yùn)算符棧init (&res);init (&oper);for (int i =0; expri != '0&#

35、39; i+) char ch = expri;/isdigit就是判斷字符是否是一個數(shù)字if (isdigit (ch) /如果是一個數(shù)字放到結(jié)果站立49. push(& res, ch);50. else if( ch ='(')51. 1push(&oper, ch);53. .54. 步驟五：將“運(yùn)算符?！敝凶罄ㄌ枴?”前的運(yùn)算符放入“結(jié)果棧”中 判斷讀出的字符是否是右括號“)”，如果是，則設(shè)置循環(huán)，逐個將“運(yùn)算符棧”中的運(yùn)算符彈出并放入“結(jié)果?！敝小Ｖ钡接鲆娮罄ㄌ枴?”。代碼如下:1. #include <stdio. h>2. #incl

36、ude <stdbool .h>3.4. #define LISTSIZE105. typedef int DataType ;6.7. struct Stack 8. DataType data LISTSIZE9. int ; /處了記錄大小還可以記錄棧頂位置10. ；11.12. void init (structStack * stack)13. 14. Hstack-> =0;15. 16.17. void push (struct Stack * stack, DataType d) 18. flstack->data stack->+ = d;19.

37、 20.21. void pop (struct Stack * stack) 22. Hstack->-;23. 24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.53.54.55.56.57.58.59.DataType (struct Stack * stack) return stack->datastack-> -1;bool empty (struct Stack * stack) return stack-> = 0;bool pri

38、or (char op1, char op2) return (op1 = '*' | op1 = '/') && (op2 ='+'| op2 ='-');int main () charexpr口 = "1+2*3/(4-1)”;struct Stack res;/ 結(jié)果棧 struct Stack oper;/ 運(yùn)算符棧 init (&res);init (&oper);for (int i =0; expri != '0'i+)char ch = expri;/is

39、digit就是判斷字符是否是一個數(shù)字if (isdigit (ch) /如果是一個數(shù)字放到結(jié)果站立push(&res, ch); else if( ch ='(')push(&oper, ch);else if(ch =')') / ('符號前的運(yùn)算符 全部從 運(yùn)算符棧中彈出彈到 結(jié)果棧while (&oper) != '(') push (&res, (&oper);pop (&oper);pop(&oper);將左括號“(”扔掉。60. 61. 步驟六：運(yùn)算符放入“運(yùn)算符棧”讀出

40、的字符如果以上條件均為假，說明它不是數(shù)字、左括號“(”和右括號。那么由于一個表達(dá)式中僅由數(shù)字、運(yùn)算符和括號組成，刨除數(shù)字和括號，就只剩下運(yùn)算符 了。所以，這個讀出的字符一定是運(yùn)算符。將這個運(yùn)算符放入“運(yùn)算符?！敝小４a如下：1. #include <stdio. h>2. #include <stdbool .h>3.4. #define LISTSIZE105. typedef int DataType ;6.7. struct Stack 8. HDataType data LISTSIZE9. int ; /處了記錄大小還可以記錄棧頂位置10. ；11.12. v

41、oid init (structStack * stack)13. 14. Hstack-> =0;15. 16.17. void push (struct Stack * stack, DataType d) 18. stack->data stack->+ = d;19. 20.21. void pop (struct Stack * stack) 22. Hstack->-;23. 25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.53.54.55

42、.56.57.58.59.60.DataType (struct Stack * stack) return stack->datastack-> -1;bool empty (struct Stack * stack) return stack-> = 0;bool prior (char op1, char op2) return (op1 = '*' | op1 = '/') && (op2 ='+'| op2 ='-');int main () charexpr口 = "1+2*

43、3/(4-1)”;struct Stack res;/ 結(jié)果棧struct Stack oper;/ 運(yùn)算符棧init (&res);init (&oper);for (int i =0; expri != '0'i+)char ch = expri;/isdigit就是判斷字符是否是一個數(shù)字if (isdigit (ch) /如果是一個數(shù)字放到結(jié)果站立push(&res, ch); else if( ch ='(')push(&oper, ch);else if(ch =')') / ('符號前的 運(yùn)算符

44、 全部從 運(yùn)算符棧中彈出彈到 結(jié)果棧while (&oper) != '(') push (&res, (&oper);pop (&oper);pop (&oper);elsepush(&oper, ch);61. 62. 63. 步驟七：處理優(yōu)先級問題將這個運(yùn)算符放入“運(yùn)算符?！敝埃€應(yīng)該做優(yōu)先級的判斷，如果是優(yōu)先級相同， 也應(yīng)將“運(yùn)算符?！敝械倪\(yùn)算符彈出并放入“結(jié)果?！敝?，直到優(yōu)先級不同。此時有兩個 特殊情況需要排除，一個是“運(yùn)算符?！辈荒転榭?，當(dāng)“運(yùn)算符棧”為空時，就只有一個 運(yùn)算符了，此時不存在優(yōu)先級的問題；另一個是“運(yùn)

45、算符?！钡臈ｍ斣夭皇亲罄ㄌ査怯糜诟淖儍?yōu)先級的，左括號“（”和右括號“）”之間的運(yùn)算符在步驟五中已經(jīng)處理 了。代碼如下:1. #include <stdio. h>2. #include <stdbool .h>3.4. #define LISTSIZE105. typedef int DataType ;6.7. struct Stack 8. DataType data LISTSIZE9. int ; /處了記錄大小還可以記錄棧頂位置10. ；11.12. void init (struct Stack * stack)13. 14. flstack->

46、= 0;15. 16.17. void push (struct Stack * stack,DataType d) 18. Hstack->data stack->+ =d;19. 20.21. void pop (struct Stack *stack) 22. Bstack-;23. 24.25. DataType (struct Stack *stack) 26. return stack->datastack-> -1;27. 28.29. bool empty (struct Stack * stack) 30. return stack-> = 0;

47、31. 32.33. bool prior (char op1, char op2) 34. |return (op1 = '*' | op1= '/') && (op2 ='+'| op2 ='-');35. 36.37. int main() 38. char expr = "1+2*3/(4-1)"39. struct Stack res;/ 結(jié)果棧40. Hstruct Stack oper;/ 運(yùn)算符棧41. init (&res);42. flinit (&oper)

48、;43. 44. flfor (int i =0; expri != '0' i+)45. char ch = expri;46. /isdigit就是判斷字符是否是一個數(shù)字47. Hif (isdigit (ch) 48. 1/如果是一個數(shù)字放到結(jié)果站立49. push(&res, ch);50. 1 else if( ch ='(')51. push(&oper, ch);52. 1else if(ch =')') 53. / ('符號前的運(yùn)算符 全部從 運(yùn)算符棧中彈出彈到 結(jié)果棧54. Hwhile (&op

49、er) != '(') 55. push(&res, (&oper);56. pop (&oper);58. |pop (&oper);59. else 60. while(!empty (&oper) && (&oper) != '(' && ! prior (ch, (&oper) 61. push (&res, (&oper);62. Hpop (&oper);64.push(&oper, ch);66. 67. 上述代碼中，以下代碼：1

50、. |while(! empty (&oper) && (&oper) != '(' && ! prior (ch, (&oper) 由三個條件組成，第一個！empty(&oper) 是判斷“運(yùn)算符棧”是否為空；第二個(&oper) !='('是判斷“運(yùn)算符?！钡臈ｍ斣夭皇亲罄ㄌ?"("；第三個！prior(ch, (&oper)是判斷運(yùn)算符ch與“運(yùn)算符?！钡臈ｍ斣剡\(yùn)算符是否同級。函數(shù) prior的代碼如下：1. bool prior (char op1,

51、char op2) 2. Breturn (op1 = '*' | op1 = '/') && (op2 ='+'| op2 ='-');3. 步驟八：清空“運(yùn)算符?！痹O(shè)置循環(huán)，逐個將“運(yùn)算符?！敝惺Ｓ嗟倪\(yùn)算符放入“結(jié)果棧”中。代碼如下：1. #include <stdio. h>2. #include <stdbool .h>3.4. #define LISTSIZE105. typedef int DataType ;6.7. struct Stack 8. DataType data

52、LISTSIZE9. int ; /處了記錄大小還可以記錄棧頂位置10. ；11.12. voidinit (struct Stack * stack)13. 14. stack-> = 0;15. 16.17. void push (struct Stack * stack, DataType d) 18. Hstack->data stack->+ = d;19. 20.21. void pop (struct Stack * stack) 22. stack->-;23. 24.25. DataType (struct Stack * stack) 26. ret

53、urn stack->data stack-> -1;27. 28.29. bool empty (struct Stack * stack) 30. return stack-> = 0;31. 32.33. bool prior (char op1, char op2) 34. Breturn (op1 = '*' | op1= '/') && (op2 ='+'| op2 ='-');35. 36.37. int main () 38. flchar expr口 = "1+2*3/

54、(4-1)"39. struct Stack res;/ 結(jié)果棧40. flstruct Stack oper;/ 運(yùn)算符棧41. Hinit (&res);42. flinit (&oper);43. 44. flfor(int i =0; expri != '0' i+)45.46.47.48.49.50.51.52.53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.70.71.72.73.char ch = expri;/isdigit就是判斷字符是否是一個數(shù)字if (isdigit(ch) /

55、如果是一個數(shù)字放到結(jié)果站立push(&res, ch); else if( ch ='(')push(&oper, ch);else if(ch =')') / ('符號前的運(yùn)算符 全部從 運(yùn)算符棧中彈出彈到 結(jié)果棧while (&oper) != '(') push (&res, (&oper);pop (&oper);pop (&oper);elsewhile(!empty (&oper) && (&oper) != '(' && ! prior (ch, (&oper) push (&res, (&oper);pop (&oper);push(&oper, ch);/把運(yùn)算符棧剩余