數(shù)據(jù)結(jié)構(gòu)課程設計--算術(shù)表達式求值

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：18 大?。?9.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設計--算術(shù)表達式求值_第1頁

已閱讀1頁，還剩17頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設計　　題目算術(shù)表達式求值　　目錄　　問題描述　　基本要求</p&g

2、t;　　數(shù)據(jù)結(jié)構(gòu)的設計　　軟件模塊結(jié)構(gòu)圖　　程序設計思想　　程序流程圖　　源程序

3、　　調(diào)試分析　　測試數(shù)據(jù)　　用戶使用手冊　　十一、心得體會<p&g

4、t;　　一：問題描述　　從鍵盤上輸入算術(shù)表達式，包括括號；　　（1）判斷表達式是否是正常表達式；　　（2）計算出一般表達式（類似如a*b+c/d-e）的值；　?。?）并能實現(xiàn)一元多項式相加。<p&g

5、t;　　二：基本要求　?。?）程序?qū)λ斎氲挠堰_式作簡單的判斷，如表達式有錯能給出適當?shù)奶崾荆?lt;/p>　　（2）能處理單目運算符：十和一；　?。?）已知和，并且在A(x)和B(x)中指數(shù)相差很多，求A(x)=A(x)+B(x)。要求設計存儲結(jié)構(gòu)表示一元多項式，設計算法實現(xiàn)一元多

6、項式相加。　　三：數(shù)據(jù)結(jié)構(gòu)的設計　　任何一個表達式都是由操作符，運算符和界限符組成的。我們分別用順序棧來寄存表達式的操作數(shù)和運算符。棧是限定于緊僅在表尾進行插入或刪除操作的線性表。順序棧的存儲結(jié)構(gòu)是利用一組連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設指針top指示棧頂元素在順序棧中的位置，base為棧底指針

7、，在順序棧中，它始終指向棧底，即top=base可作為?？盏臉擞?，每當插入新的棧頂元素時，指針top增1，刪除棧頂元素時，指針top減1。　　ADT描述　　ADT Stack{　　數(shù)據(jù)對象：D={ |∈ElemSet,i=1,2,…，n, n≧0}&l

8、t;p>　　數(shù)據(jù)對象：R1={<>|,,i=2,…，n}　　約定端為棧頂，端為棧底。　　基本操作：　　InitStack(&S)　　操作結(jié)果：構(gòu)造一個空棧S。<

9、b>　　GetTop(S)　　初始條件：棧S已存在。　　操作結(jié)果：用P返回S的棧頂元素。　　Push(&S，ch)　　初始條件：棧S已存在。　　操作結(jié)果：插入元素ch為新的棧頂元素。</p&

10、gt;　　Pop(&S)　　初始條件：棧S已存在。　　操作結(jié)果：刪除S的棧頂元素。　　In(ch)　　操作結(jié)果：判斷字符是否是運算符，運算符即返回1。</p&g

11、t;　　Precede(c1, c2) 　　初始條件：c1,c2為運算符。　　操作結(jié)果：判斷運算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的。　　Operate(a,op,b)　　初始條件：a,b為整數(shù)，op為運算符。　　操作結(jié)

12、果：a與b進行運算，op為運算符，返回其值。　　num(n)　　操作結(jié)果：返回操作數(shù)的長度。　　EvalExpr()　　初始條件：輸入表達式合法。　　操作結(jié)果：返回表達式的最終結(jié)果。</

13、p>　　}ADT Stack　　四：軟件模塊結(jié)構(gòu)圖　　1.棧的基本功能。　　InitStack(Stack *s) 和InitStack2(Stack2 *s)分別構(gòu)造運算符棧與構(gòu)造操作數(shù)棧，Push(Stack *s,char ch) 運算符棧

14、插入ch為新的棧頂元素，Push2(Stack2 *s,int ch) 操作數(shù)棧插入ch為新的棧頂元素，Pop(Stack *s) 刪除運算符棧s的棧頂元素，用p返回其值，Pop2(Stack2 *s)刪除操作數(shù)棧s的棧頂元素，用p返回其值，GetTop(Stack s)用p返回運算符棧s的棧頂元素，GetTop2(Stack2 s) 用p返回操作數(shù)棧s的棧頂元素。　　2.其它

15、功能分析。　　(1)In(char ch) 判斷字符是否是運算符功能，運算符即返回1，該功能只需簡單的一條語句，return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')。</p&

16、gt;　　(2) Precede(char c1,char c2) 判斷運算符優(yōu)先權(quán)功能，該函數(shù)判斷運算符c1,c2的優(yōu)先權(quán)，具體優(yōu)先關系參照表1。　　(3) Operate(int a,char op,int b)操作數(shù)用對應的運算符進行運算功能。運算結(jié)果直接返回。　　(4) num(int n) 求操作數(shù)的長度功能，需要用ito

17、a函數(shù)把int型轉(zhuǎn)換成字符串型，strlen函數(shù)可求字符長度。　　(5) EvalExpr()主要操作函數(shù)運算功能。　　五：程序設計思想　　為了實現(xiàn)算符優(yōu)先算法。可以使用兩個工作棧。一個稱為OPTR，用以寄存運算符，另一個稱做OPND，用以寄存操作數(shù)或運算結(jié)果。</p&

18、gt;　　1.首先置操作數(shù)棧為空棧，表達式起始符”#”為運算符棧的棧底元素；　　2.依次讀入表達式，若是操作符即進OPND棧，若是運算符則和OPTR棧的棧頂運算符比較優(yōu)先權(quán)后作相應的操作，直至整個表達式求值完畢（即OPTR棧的棧頂元素和當前讀入的字符均為”#”）。　　數(shù)據(jù)存儲結(jié)構(gòu)設計</p

19、>　　因為表達式是由操作符，運算符和界限符組成的。如果只用一個char類型棧，不能滿足2位以上的整數(shù)，所以還需要定義一個int類型的棧用來寄存操作數(shù)。　　/* 定義字符類型棧 */　　typedef struct{ 　　int stacksize; <p&

20、gt;　　char *base; 　　char *top; 　　} Stack;　　/* 定義整型棧 */ 　　typedef struct{ 　　int stacksize; </p&

21、gt;　　int *base; 　　int *top; 　　} Stack2;　　六：程序流程圖　　1. Precede(char c1,char c2) 判斷運算符優(yōu)先權(quán)，

22、返回優(yōu)先權(quán)高的。　　算符間的優(yōu)先關系如下：　　表 1　　2. int EvalExpr()主要操作函數(shù)。算法概要流程圖：　　利用該算法對算術(shù)表達式3*(7-2)求值操作過程如下：<b&g

23、t;　　表2　　七：源程序　　#include <stdio.h> 　　#include <stdlib.h> 　　#include <string.h>

24、　　#define NULL 0 　　#define OK 1　　#define ERROR -1 　　#define STACK_INIT_SIZE 100　　#define STACKINCREMENT 20 <p&g

25、t;　　/* 定義字符類型棧 */ 　　typedef struct{ 　　int stacksize; 　　char *base; 　　char *top; 　　} Stack;</p

26、>　　/* 定義整型棧 */ 　　typedef struct{ 　　int stacksize; 　　int *base; 　　int *top; 　　} Stack2;</b

27、>　　/* ----------------- 全局變量--------------- */ 　　Stack OPTR;/* 定義運算符棧*/　　Stack2 OPND; /* 定義操作數(shù)棧 */ 　　char expr[255] = ""; /

28、* 存放表達式串 */ 　　char *ptr = expr; 　　int InitStack(Stack *s) //構(gòu)造運算符棧　　{ 　　s->base=(char *)malloc(STACK_INIT_SIZE*siz

29、eof(char)); 　　if(!s->base) return ERROR; 　　s->top=s->base;　　s->stacksize=STACK_INIT_SIZE;　　return OK; &

30、lt;b>　　} 　　int InitStack2(Stack2 *s) //構(gòu)造操作數(shù)棧　　{ 　　s->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int)); <p&g

31、t;　　if(!s->base) return ERROR; 　　s->stacksize=STACK_INIT_SIZE; 　　s->top=s->base; 　　return OK; 　　} </p&

32、gt;　　int In(char ch) //判斷字符是否是運算符，運算符即返回1　　{ 　　return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch=='

33、)'||ch=='#'); 　　} 　　int Push(Stack *s,char ch) //運算符棧插入ch為新的棧頂元素　　{ 　　*s->top=ch;

34、　　s->top++; 　　return 0; 　　} 　　int Push2(Stack2 *s,int ch)//操作數(shù)棧插入ch為新的棧頂元素 　　{ </

35、b>　　*s->top=ch; 　　s->top++; 　　return 0; 　　}　　char Pop(Stack *s) //刪除運算符棧s的棧頂元素，用p返回其值&l

36、t;/p>　　{ 　　char p;　　s->top--; 　　p=*s->top; 　　return p;</

37、p>　　} 　　int Pop2(Stack2 *s)//刪除操作數(shù)棧s的棧頂元素，用p返回其值 　　{ 　　int p;　　s-

38、>top--; 　　p=*s->top; 　　return p;　　}　　char GetTop(Stack s)//用p返回運算符棧s的棧頂元素<p&g

39、t;　　{ 　　char p=*(s.top-1); 　　return p; 　　}　　int GetTop2(Stack2 s) //用p返回操作數(shù)棧s的棧頂元素<

40、p>　　{ 　　int p=*(s.top-1); 　　return p; 　　}　　/* 判斷運算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的 */ 　　char P

41、recede(char c1,char c2) 　　{ 　　int i=0,j=0; 　　static char array[49]={　　'>', '>', '<',

42、 '<', '<', '>', '>', 　　'>', '>', '<', '<', '<', '>', '>',

43、;　　'>', '>', '>', '>', '<', '>', '>', 　　'>', '>', '>', '>', '<', &#

44、39;>', '>', 　　'<', '<', '<', '<', '<', '=', '!', 　　'>', '>', '&

45、gt;', '>', '!', '>', '>', 　　'<', '<', '<', '<', '<', '!', '='}; <p&g

46、t;　　switch(c1) 　　{ 　　/* i為下面array的橫標 */ 　　case '+' : i=0;break; 　　case '-' : i=1;break; &

47、lt;p>　　case '*' : i=2;break; 　　case '/' : i=3;break; 　　case '(' : i=4;break; 　　case ')' : i=5;break;

48、　　case '#' : i=6;break; 　　} 　　switch(c2) 　　{ 　　/* j為下面array的縱標 */ 　　c

49、ase '+' : j=0;break; 　　case '-' : j=1;break; 　　case '*' : j=2;break; 　　case '/' : j=3;break; 　　case '

50、;(' : j=4;break; 　　case ')' : j=5;break; 　　case '#' : j=6;break; 　　}　　return (array[7*i+j]); /* 返

51、回運算符 */ 　　} 　　/*操作函數(shù) */ 　　int Operate(int a,char op,int b) 　　{ 　　switch(op) &

52、lt;/p>　　{ 　　case '+' : return (a+b); 　　case '-' : return (a-b); 　　case '*' : return (a*b);

53、;　　case '/' : return (a/b); 　　} 　　return 0;　　} 　　int num(in

54、t n)//返回操作數(shù)的長度　　{ 　　char p[10];　　itoa(n,p,10);//把整型轉(zhuǎn)換成字符串型　　n=strlen(p);　　return n;<

55、;/b>　　}　　int EvalExpr()//主要操作函數(shù) 　　{ 　　char c,theta,x; int n,m;　　i

56、nt a,b; 　　c = *ptr++; 　　while(c!='#'||GetTop(OPTR)!='#') 　　{　　if(!In(c)) <p&

57、gt;　　{ if(!In(*(ptr-1))) ptr=ptr-1;　　m=atoi(ptr);//取字符串前面的數(shù)字段　　n=num(m); 　　Push2(&OPND,m); 　　ptr=ptr+n;

58、;　　c=*ptr++;　　} 　　else 　　switch(Precede(GetTop(OPTR),c)) 　　{ </p&g

59、t;　　case '<': 　　Push(&OPTR,c); 　　c = *ptr++; 　　break; 　　case '=': <p

60、>　　x=Pop(&OPTR); 　　c = *ptr++; 　　break; 　　case '>': 　　theta=Pop(&OPTR);

61、b=Pop2(&OPND); a=Pop2(&OPND); 　　Push2(&OPND,Operate(a,theta,b));　　break;　　}

62、　}　　return GetTop2(OPND); 　　} 　　int main( ) 　　{ 　　printf("請輸入正

63、確的表達式以'#'結(jié)尾:"); 　　do{ 　　gets(expr); 　　}while(!*expr); 　　InitStack(&OPTR); /* 初始化運算符棧 */

64、　　Push(&OPTR,'#'); /* 將#壓入運算符棧 */ 　　InitStack2(&OPND); /* 初始化操作數(shù)棧 */ 　　printf("表達式結(jié)果為:%d\n", EvalExpr());　　return 0; </

65、p>　　}　　八：調(diào)試分析　　1.運行成功后界面。　　2.輸入正確的表達式后。　　3.更改表達式，輸入有2位數(shù)的整數(shù)調(diào)試。&l

66、t;b>　　九：測試數(shù)據(jù)　　3*（7-2）=15　　12+（123*2）=258　　333+452=785　　44/4=11　　32/2+3*6+2*(5-3)=38

67、　　十：用戶使用手冊　　運行后直接輸入表達式，以換行符結(jié)束。當一個表達式處理后，按任意鍵退出界面，如需繼續(xù)，則重新打開界面。　　十一：心得體會　　這次課程設計讓我更加了解大一學到的C和上個學期學到

68、的數(shù)據(jù)結(jié)構(gòu)。課設題目要求不僅要求對課本知識有較深刻的了解，同時要求程序設計者有較強的思維和動手能力和更加了解編程思想和編程技巧。　　這次課程設計讓我有一個深刻的體會，那就是細節(jié)決定成敗，編程最需要的是嚴謹，如何的嚴謹都不過分，往往檢查了半天發(fā)現(xiàn)錯誤發(fā)生在某個括號，分號，引號，或者數(shù)據(jù)類型上。就像我在寫EvalExpr()函數(shù)時，忘了指針的地址符值不用加*號，這一點小小的錯誤也耽誤了我?guī)资昼?，?/p>

69、以說細節(jié)很重要。　　程序設計時，也不要怕遇到錯誤，在實際操作過程中犯的一些錯誤還會有意外的收獲，感覺課程設計很有意思。在具體操作中這學期所學的數(shù)據(jù)結(jié)構(gòu)的理論知識得到鞏固，達到課程設計的基本目的，也發(fā)現(xiàn)自己的不足之出，在以后的上機中應更加注意，同時體會到C語言具有的語句簡潔，使用靈活，執(zhí)行效率高等特點。發(fā)現(xiàn)上機的重要作用，特別算術(shù)表達式有了深刻的理解。

70、這個程序是我們2個人完成的，同時我認為我們的工作是一個團隊的工作，團隊需要個人，個人也離不開團隊，必須發(fā)揚團結(jié)協(xié)作的精神。某個人的離群都可能導致導致整項工作的失敗。實習中只有一個人知道原理是遠遠不夠的，必須讓每個人都知道，否則一個人的錯誤，就有可能導致整個工作失敗。團結(jié)協(xié)作是我們成功的一項非常重要的保證。而這次課程設計也正好鍛煉我們這一點，這也是非常寶貴的　　最后，感謝林老師在這次課程設計的悉心

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設計--算術(shù)表達式求值

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設計--算術(shù)表達式求值

文檔簡介

溫馨提示

最新文檔

評論

免費下載