1、C語言程序設計清華大學 鄭莉 安穎蓮第十二講第十二講 數(shù)據(jù)結構基礎數(shù)據(jù)結構基礎（二）（二）計算機程序程序設計基礎計算機程序程序設計基礎第第1010章章數(shù)據(jù)結構數(shù)據(jù)結構（嚴蔚敏（嚴蔚敏 等等 編著）第編著）第3 3章章C語言程序設計清華大學 鄭莉 安穎蓮Page 2本講主要內容本講主要內容 棧的概念和基本操作棧的概念和基本操作 棧的存儲結構棧的存儲結構 棧的應用舉例棧的應用舉例 隊列的概念和基本操作隊列的概念和基本操作 隊列的存儲結構隊列的存儲結構 隊列的應用舉例隊列的應用舉例C語言程序設計清華大學 鄭莉 安穎蓮Page 3棧的概念和基本操作棧的概念和基本操作 棧的定義棧的定義- 棧是限定僅在表

2、尾進行插入或刪除操作的線性表。棧是限定僅在表尾進行插入或刪除操作的線性表。- 表尾稱為表尾稱為棧頂棧頂，表頭稱為，表頭稱為棧底棧底。不含元素的空表稱。不含元素的空表稱為空棧。為空棧。- 棧又稱為棧又稱為后進先出（后進先出（LIFOLIFO）的線性表。的線性表。 棧的基本操作棧的基本操作- 生成空棧生成空棧- 進棧進棧- 出棧出棧- 查詢棧頂結點查詢棧頂結點- 判斷棧是否為空判斷棧是否為空C語言程序設計清華大學 鄭莉 安穎蓮Page 4棧的存儲結構棧的存儲結構 棧的順序存儲結構順序棧棧的順序存儲結構順序棧利用一組地址連續(xù)的存儲單元依次存放自棧底到棧利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)?/p>

3、數(shù)據(jù)元素。頂?shù)臄?shù)據(jù)元素。 棧的鏈式存儲結構鏈棧棧的鏈式存儲結構鏈棧C語言程序設計清華大學 鄭莉 安穎蓮Page 5棧的應用舉例棧的應用舉例 數(shù)制轉換數(shù)制轉換 輸入任意一個非負十進制整數(shù)，輸出與其等值輸入任意一個非負十進制整數(shù)，輸出與其等值的八進制數(shù)。的八進制數(shù)。void conversion()void conversion() InitStack(S); InitStack(S); scanf(%d,N); scanf(%d,N); while(N) while(N) push(S,N%8); n=n/8; push(S,N%8); n=n/8; while(!StackEmpty) whi

4、le(!StackEmpty) Pop(S,e); printf(%d,e); Pop(S,e); printf(%d,e); C語言程序設計清華大學 鄭莉 安穎蓮Page 6棧的應用舉例棧的應用舉例行編輯程序行編輯程序 接收用戶輸入的程序或數(shù)據(jù)，存入用戶的數(shù)據(jù)區(qū)接收用戶輸入的程序或數(shù)據(jù)，存入用戶的數(shù)據(jù)區(qū)“#”#”表示退格符，表示退格符，“”表示退行符。表示退行符。void LineEdit()void LineEdit() InitStack(S); InitStack(S); ch=getchar(); ch=getchar(); while(ch!=EOF) while(ch!=EOF)

5、 while(ch!=EOF & ch!=n) while(ch!=EOF & ch!=n) switch (ch) switch (ch) case #:Pop(S,c); case #:Pop(S,c); case :ClearStack(S); case :ClearStack(S); default:Push(S,ch); default:Push(S,ch); ch=getchar(); ch=getchar(); ClearStack(S); ClearStack(S); if(ch!=EOF) ch=getchar(); if(ch!=EOF) ch=getchar(); Des

6、troyStack(S); DestroyStack(S); C語言程序設計清華大學 鄭莉 安穎蓮Page 7棧的應用舉例棧的應用舉例表達式求值表達式求值OperandType EvaluateExpression()OperandType EvaluateExpression() InitStack(OPTR); InitStack(OPND); InitStack(OPTR); InitStack(OPND); Push(OPTR,#); c=getchar(); Push(OPTR,#); c=getchar(); while(c!=#|GetTop(OPTR)!=#) while(c!

7、=#|GetTop(OPTR)!=#) if(!In(c,OP) if(!In(c,OP) Push(OPND,c); c=getchar(); Push(OPND,c); c=getchar(); else else switch(Precede(GetTop(OPTR),c) switch(Precede(GetTop(OPTR),c) case: case: case: Pop(OPTR,theta); Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Pop(OPND,b); Pop(OPND,a); Push(OPND, Push(OPND, Op

8、erate(a,theta,b); Operate(a,theta,b); break; break; C語言程序設計清華大學 鄭莉 安穎蓮Page 8例例1 1 整數(shù)四功能計算器整數(shù)四功能計算器 題目：題目：- 編寫一個簡單的整數(shù)四功能計算器，要求先輸入操作編寫一個簡單的整數(shù)四功能計算器，要求先輸入操作數(shù)，后輸入操作符，輸入數(shù)，后輸入操作符，輸入qq時結束。時結束。 分析：分析：- 數(shù)據(jù)結構：使用棧數(shù)據(jù)結構：使用棧 - 算法要點：算法要點：輸入字符，若字符不是輸入字符，若字符不是+ +、- -、* *、/ /之一，進棧，再輸之一，進棧，再輸入，若字符是入，若字符是+ +、- -、* *、/

9、/之一，則把棧中兩個操作數(shù)之一，則把棧中兩個操作數(shù)依次彈出，進行運算，再把運算結果壓進棧，再輸入依次彈出，進行運算，再把運算結果壓進棧，再輸入字符，直到輸入的字符為字符，直到輸入的字符為“q”q”表示結果輸入。表示結果輸入。 程序：程序：12-1.c12-1.cC語言程序設計清華大學 鄭莉 安穎蓮Page 9例例1 1 整數(shù)四功能計算器整數(shù)四功能計算器 ：6 6 ：4 4 ：+ + 1010 ：7 7 ：- - 3 3 ：4 4 ：* * 1212 ：q q運行結果：白色字代表輸入的數(shù)據(jù)，黃色字代表輸出的結果。C語言程序設計清華大學 鄭莉 安穎蓮Page 10棧的應用舉例棧的應用舉例子程序調用

10、子程序調用由于棧有后進先出的特點，在高級語言由于棧有后進先出的特點，在高級語言中，調用子程序時利用棧來傳遞參數(shù)和返回中，調用子程序時利用棧來傳遞參數(shù)和返回地址。地址。C語言程序設計清華大學 鄭莉 安穎蓮Page 11隊列的概念和基本操作隊列的概念和基本操作 隊列的定義隊列的定義- 隊列是只允許在表的一端進行插入，另一端進行刪隊列是只允許在表的一端進行插入，另一端進行刪除操作的線性表。除操作的線性表。- 允許插入的一端叫做允許插入的一端叫做隊尾隊尾，允許刪除的一端稱為，允許刪除的一端稱為隊頭隊頭。- 隊是一種隊是一種先進先出（先進先出（FIFOFIFO）的線性表。的線性表。 棧的基本操作棧的基本

11、操作- 生成空隊列生成空隊列- 進隊進隊- 出隊出隊- 判斷隊滿和隊空判斷隊滿和隊空C語言程序設計清華大學 鄭莉 安穎蓮Page 12隊列的存儲結構隊列的存儲結構 隊列的鏈式表示和實現(xiàn)鏈隊列隊列的鏈式表示和實現(xiàn)鏈隊列- 具有頭指針和尾指針的單鏈表。具有頭指針和尾指針的單鏈表。 隊列的順序表示和實現(xiàn)隊列的順序表示和實現(xiàn)- 隊滿和隊空的情況隊滿和隊空的情況- 假溢出假溢出- 循環(huán)隊列循環(huán)隊列C語言程序設計清華大學 鄭莉 安穎蓮Page 13隊列的應用舉例隊列的應用舉例題目：用隊列處理備忘錄題目：用隊列處理備忘錄功能如下：功能如下：程序啟動后顯示下列菜單：程序啟動后顯示下列菜單： 1 1-input

12、 memo 2 2-save memo to file 3 3-load memo from file 4 4-list memo 5 5-delete memo item 0 0-exitC語言程序設計清華大學 鄭莉 安穎蓮Page 14隊列的應用舉例隊列的應用舉例 選選“1”1”時，提示用戶從鍵盤逐條輸入備忘錄內容，時，提示用戶從鍵盤逐條輸入備忘錄內容，當輸入回車時，結束輸入當輸入回車時，結束輸入, ,然后重新顯示上述菜單。然后重新顯示上述菜單。 選選“2”2”時，將備忘錄存入磁盤文件時，將備忘錄存入磁盤文件“memo”memo”中，然中，然后重新顯示上述菜單。后重新顯示上述菜單。 選選“

13、3”“3”時，從文件時，從文件“memo”memo”中讀取備忘錄隊列，然中讀取備忘錄隊列，然后重新顯示上述菜單。后重新顯示上述菜單。 選選“4”“4”時，輸出備忘錄隊列內容，然后重新顯示上時，輸出備忘錄隊列內容，然后重新顯示上述菜單。述菜單。 選選“5”5”時，刪除已完成的事件（隊頭）。時，刪除已完成的事件（隊頭）。C語言程序設計清華大學 鄭莉 安穎蓮Page 15隊列的應用舉例隊列的應用舉例分析分析- 數(shù)據(jù)結構：數(shù)據(jù)結構：使用隊列，定義指針數(shù)組，存放備忘錄隊列。使用隊列，定義指針數(shù)組，存放備忘錄隊列。- 算法要點：算法要點：定義幾個函數(shù)分別實現(xiàn)輸入、存文件、從文件中讀、輸定義幾個函數(shù)分別實現(xiàn)

14、輸入、存文件、從文件中讀、輸入、刪除隊頭和顯示菜單的功能。入、刪除隊頭和顯示菜單的功能。主函數(shù)用兩層循環(huán)，外層循環(huán)用主函數(shù)用兩層循環(huán)，外層循環(huán)用for( ; ;)for( ; ;)，無終止的，無終止的執(zhí)行循環(huán)體，內層循環(huán)用執(zhí)行循環(huán)體，內層循環(huán)用switchswitch語句，當語句，當switchswitch括號中括號中表達式的值通過調用顯示菜單的函數(shù)得到，每一個表達式的值通過調用顯示菜單的函數(shù)得到，每一個casecase對應一個函數(shù)，通過調用執(zhí)行相應的功能。對應一個函數(shù)，通過調用執(zhí)行相應的功能。程序：程序：12-2.c12-2.cC語言程序設計清華大學 鄭莉 安穎蓮Page 16隊列的應用舉例

15、隊列的應用舉例 1 1-input memo 2 2-save memo to file 3 3-load memo from file 4 4-list memo 5 5-delete memo item 0 0-exit please input your select: 1運行結果：黃色為屏幕顯示，白色為用戶輸入的數(shù)據(jù)。C語言程序設計清華大學 鄭莉 安穎蓮Page 17 Input the 1st item:aaa Input the 2st item:bbb Input the 3st item:ccc Input the 4st item:ddd Input the 5st item:(回車） 重新顯示主菜單 please input your select: 4 No.1:aaa No.1:aaa No.2:bbb No.2:bbb No.3:ccc No.3:ccc No.4:ddd No.4:ddd 重新顯示主菜單 please input your select: 0C語言程序設計清華大學 鄭莉 安穎蓮Page 18作作 業(yè)業(yè) 復習：復習：計算機程序程序設計基礎計算機程序程序設計基礎第第1010章章數(shù)據(jù)結構數(shù)據(jù)結構（嚴蔚敏