C語言程序設(shè)計(清華鄭莉安潁蓮)chap2

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

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

3、數(shù)據(jù)元素。頂?shù)臄?shù)據(jù)元素。 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈棧棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈棧C語言程序設(shè)計清華大學(xué) 鄭莉 安穎蓮Page 5棧的應(yīng)用舉例棧的應(yīng)用舉例 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 輸入任意一個非負(fù)十進制整數(shù)，輸出與其等值輸入任意一個非負(fù)十進制整數(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語言程序設(shè)計清華大學(xué) 鄭莉 安穎蓮Page 6棧的應(yīng)用舉例棧的應(yīng)用舉例行編輯程序行編輯程序 接收用戶輸入的程序或數(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語言程序設(shè)計清華大學(xué) 鄭莉 安穎蓮Page 7棧的應(yīng)用舉例棧的應(yīng)用舉例表達式求值表達式求值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語言程序設(shè)計清華大學(xué) 鄭莉 安穎蓮Page 8例例1 1 整數(shù)四功能計算器整數(shù)四功能計算器 題目：題目：- 編寫一個簡單的整數(shù)四功能計算器，要求先輸入操作編寫一個簡單的整數(shù)四功能計算器，要求先輸入操作數(shù)，后輸入操作符，輸入數(shù)，后輸入操作符，輸入qq時結(jié)束。時結(jié)束。 分析：分析：- 數(shù)據(jù)結(jié)構(gòu)：使用棧數(shù)據(jù)結(jié)構(gòu)：使用棧 - 算法要點：算法要點：輸入字符，若字符不是輸入字符，若字符不是+ +、- -、* *、/ /之一，進棧，再輸之一，進棧，再輸入，若字符是入，若字符是+ +、- -、* *、/

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

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

11、操作- 生成空隊列生成空隊列- 進隊進隊- 出隊出隊- 判斷隊滿和隊空判斷隊滿和隊空C語言程序設(shè)計清華大學(xué) 鄭莉 安穎蓮Page 12隊列的存儲結(jié)構(gòu)隊列的存儲結(jié)構(gòu) 隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)鏈隊列隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)鏈隊列- 具有頭指針和尾指針的單鏈表。具有頭指針和尾指針的單鏈表。 隊列的順序表示和實現(xiàn)隊列的順序表示和實現(xiàn)- 隊滿和隊空的情況隊滿和隊空的情況- 假溢出假溢出- 循環(huán)隊列循環(huán)隊列C語言程序設(shè)計清華大學(xué) 鄭莉 安穎蓮Page 13隊列的應(yīng)用舉例隊列的應(yīng)用舉例題目：用隊列處理備忘錄題目：用隊列處理備忘錄功能如下：功能如下：程序啟動后顯示下列菜單：程序啟動后顯示下列菜單： 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語言程序設(shè)計清華大學(xué) 鄭莉 安穎蓮Page 14隊列的應(yīng)用舉例隊列的應(yīng)用舉例 選選“1”1”時，提示用戶從鍵盤逐條輸入備忘錄內(nèi)容，時，提示用戶從鍵盤逐條輸入備忘錄內(nèi)容，當(dāng)輸入回車時，結(jié)束輸入當(dāng)輸入回車時，結(jié)束輸入, ,然后重新顯示上述菜單。然后重新顯示上述菜單。 選選“2”2”時，將備忘錄存入磁盤文件時，將備忘錄存入磁盤文件“memo”memo”中，然中，然后重新顯示上述菜單。后重新顯示上述菜單。 選選“

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

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

15、隊列的應(yīng)用舉例 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運行結(jié)果：黃色為屏幕顯示，白色為用戶輸入的數(shù)據(jù)。C語言程序設(shè)計清華大學(xué) 鄭莉 安穎蓮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語言程序設(shè)計清華大學(xué) 鄭莉 安穎蓮Page 18作作 業(yè)業(yè) 復(fù)習(xí)：復(fù)習(xí)：計算機程序程序設(shè)計基礎(chǔ)計算機程序程序設(shè)計基礎(chǔ)第第1010章章數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（嚴(yán)蔚敏