北理工數(shù)據(jù)結(jié)構(gòu)實驗報告

1、專業(yè)資料整理分享數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計實驗報告實驗二學院：自動化學院班級：學號：姓名：、實驗目的1、熟悉VC環(huán)境，學習使用C語言實現(xiàn)棧的存儲結(jié)構(gòu)。2、通過編程、上機調(diào)試，進一步理解棧的基本概念。3、鍛煉動手編程，獨立思考的能力。二、實驗內(nèi)容實現(xiàn)簡單計算器的功能,請按照四則運算加、減、乘、除、窯(八)和括號的優(yōu)先關(guān)系和慣例，編寫計算器程序。要求支持運算符：+、-、*、/、 ()和二: 從鍵盤輸入一個完整的表達式，以同車作為表達式輸入結(jié)束的標志； 輸入表達式中的數(shù)值均為大于等于零的整數(shù)，如果中間計算過程中出現(xiàn)小數(shù)也只取整進行計算。例如，輸入：4+2*5=輸出：14輸入：(4+2)*(2-10)=輸出：

2、-48三、程序設(shè)計1、概要設(shè)計為實現(xiàn)上述程序功能，應使用兩個棧，分別寄存操作數(shù)與運 算符。為此，需要棧的抽象數(shù)據(jù)結(jié)構(gòu)。(1)、棧的抽象數(shù)據(jù)類型定義為：ADT Stack數(shù)據(jù)對象：DMaJa ElemSet,i =1,2JH,n,n-0數(shù)據(jù)關(guān)系：R1= ai,ai g同 D,i=2,l|,n約定an端為棧頂，司端為棧底?；静僮鳎篒nitStack(&S)操作結(jié)果：創(chuàng)建一個空棧 SoGetTop(S,&e)初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。Push(&S,e)初始條件：棧S已存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop(&S,&

3、;e)初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，弁用e返回其值。In(m,a)操作結(jié)果：若m是運算符，返回TRUEPrecede(m, n)初始條件：m, n為運算符。操作結(jié)果：若m優(yōu)先級大于n,返回 >,反之亦然。Operation(a, theta,b)初始條件：a, b為整數(shù)，theta為運算符。操作結(jié)果：返回a與b運算的結(jié)果。EvaluateExpression(p口)初始條件：輸入合法的表達式。完美WORD格式編輯專業(yè)資料整理分享操作結(jié)果：返回表達式的值。ADT Stack(2)、宏定義#define STACK_INIT_SIZE 100# define STA

4、CKINCREMENT 10# define OVERFLOW -2# define OK 1# define ERROR 0# define TRUE 1# define FALSE 0(3)、主程序流程隨后調(diào)用最后輸出在屏計算弁返首先定義char型數(shù)組，將輸入的表達式存入。EvaluateExpression(expression)函數(shù)計算結(jié)果，幕上。(4)、模塊調(diào)用關(guān)系：由主函數(shù)模塊調(diào)用輸入模塊與求值模塊。求值模塊調(diào)用表達式轉(zhuǎn)化模塊與表達式求職模塊, 回表達式的值。最后主程序調(diào)用輸出模塊輸出結(jié)果。(5)、流程圖開始完美char c=表達式首字符專業(yè)資料整理分享2、詳細設(shè)計(1)、數(shù)據(jù)類型

5、設(shè)計typedef structchar *base;char *top;int stacksize;SqStack1;/定義運算符棧數(shù)據(jù)類型typedef structint *base;int *top;int stacksize;SqStack2; /定義操作數(shù)棧數(shù)據(jù)類型SqStackl OPTR; / 聲明運算符棧SqStack2 OPND; / 聲明操作數(shù)棧(2)、操作算法設(shè)計Status InitStack1(SqStack1 &S)/構(gòu)造運算符棧S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char);/申請空間if(!S.bas

6、e)exit(OVERFLOW);/ 存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStack1Status InitStack2(SqStack2 &S)/構(gòu)造操作數(shù)棧S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int);/申請空間if(!S.base)exit(OVERFLOW);/ 存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStack2char GetTop1(SqStack1

7、S)/取得運算符棧的棧頂元素char e;if(S.top=S.base) return ERROR; / ?？誩=*(S.top-1);return e;/GetTop1int GetTop2(SqStack2 S)/取得操作數(shù)棧的棧頂元素int e;if(S.top=S.base) return ERROR; / ?？誩=*(S.top-1);return e;/GetTop2Status Push1(SqStack1 &S,char e)/插入元素e為運算符棧的棧頂元素if(S.top-S.base>=S.stacksize)/ 棧滿，追加存儲空間S.base=(char*

8、)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S.base) exit(OVERFLOW);/ 存儲分配失敗S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Push1Status Push2(SqStack2 &S,int e)/插入元素e為操作數(shù)棧的棧頂元素if(S.top-S.base>=S.stacksize) / 棧滿，追加存儲空間S.base=(int*)realloc(S.base,(S.sta

9、cksize+STACKINCREMENT)*sizeof(int);if(!S.base) exit(OVERFLOW); /存儲分配失敗S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;/Push2Status Pop1(SqStack1 &S,char &e)/刪除表達式棧的棧頂元素弁用 e返回if(S.top=S.base) return ERROR; ?？誩=*-S.top;return OK;/Pop1Status Pop2(SqStack2 &S,int &am

10、p;e)/刪除表達式棧的棧頂元素弁用 e返回if(S.top=S.base) return ERROR; / ?？誩=*-S.top;return OK;/Pop2Status In(int m,char a)/判斷m若是運算符，返回TRUE否則返回FALSEfor(int n=0;an!='0'n+)if(m=an) return TRUE;return FALSE;/Inchar Precede(char m,char n)/判斷mV n的優(yōu)先級switch(m) case'+':case'-':if(n='+'|n='

11、;-'|n=')'11n='=')return '>'else return '<'break;case'*':case'/':case、case'%':if(n='(')return '<'else return '>'break;case'(':if(n=')')return '='else if(n='=')return ERROR;e

12、lse return '<'break;case')':if(n='(')return ERROR;else return '>'break;case'=':if(n='=')return '='else if(n=')')return ERROR;else return '<'break;default:return ERROR;break;其他情況，表達式有誤/ Precedeint Operation(int a,char th

13、eta,int b)/運算函數(shù)switch(theta)case'+':return a+b;break;case'-':return a-b;break;case'*':return a*b;break;case'/':return a/b;break;case'%':return a%b;break;case'A':return pow(a,b);break;default:return ERROR;break;/Operationint EvaluateExpression(char p)/主

14、要操作函數(shù)int a,b,t;char x,theta,temp10;char* num=temp;char* ex=p;/聲明指針I(yè)nitStack1(OPTR);Push1(OPTR,'=');InitStack2(OPND);char c=*p;while(c!='='|GetTop1(OPTR)!='=')if(!In(c,OP)/ 不是運算符進數(shù)組*(num+尸c;c=*(+ex);if(In(c,OP)/是運算符將數(shù)組壓入棧*num='0't=atoi(temp); /將temp數(shù)組轉(zhuǎn)化為整型數(shù)num=temp;指針指

15、回數(shù)組頭元素Push2(OPND,t);elseswitch(Precede(GetTop1(OPTR),c)case '<':/棧頂元素優(yōu)先級低Push1(OPTR,c);c=*(+ex);break;case '='：/脫括號弁接受下一字符Pop1(OPTR,x);c=*(+ex);break;case '>':/運算弁將結(jié)果入棧Pop1(OPTR,theta);Pop2(OPND,b);Pop2(OPND,a);Push2(OPND,Operation(a,theta,b);break;return GetTop2(OPND);

16、返回操作數(shù)棧頂元素 EvaluateExpression(3)、主函數(shù)設(shè)計int main()/主函數(shù)int result;char expression100; /聲明表達式數(shù)組printf("Please input the expression:");gets(expression); / 輸入數(shù)組result=EvaluateExpression(expression);printf("the result is :%dn",result);/輸出結(jié)果return 0;四、程序調(diào)試分析1、開始時，使用getchar函數(shù)輸入，但具有較大的弊端，只能

17、輸入0-9之間的整數(shù)，不能實現(xiàn)多位數(shù)及小數(shù)的計算。于是換為gets函數(shù)，將表達式作為整體存入數(shù)組中待處理。2、第一個問題解決后，出現(xiàn)了第二個問題：數(shù)據(jù)結(jié)構(gòu)混亂。由于gets函數(shù)得到的是char型，直接存入操作數(shù)棧后，以ASCII 碼形式存入，使得編譯通過但運行結(jié)果錯誤。后來分析原因后， 引入暫存數(shù)組，利用 atoi函數(shù)，將數(shù)組中的數(shù)轉(zhuǎn)化為整型，解 決了這一問題。3、在設(shè)計主要處理函數(shù)時，出現(xiàn)了多次編譯錯誤。后發(fā)現(xiàn) 是由于指針指向混亂造成。這主要是自己的思路不清， 導致程序混亂。后仔細繪制了流程圖，詳盡的分析了過程后，解決了該問 題。五、用戶使用說明1、本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件

18、為：Josegh.exe 。2、進入程序后，在 Please input the expression:后輸入待求表達式，以“二”結(jié)尾，弁敲回車。3、程序運行后即在屏幕上輸出計算結(jié)果。六、程序運行結(jié)果1、2、二；*C ： VD«cuaebts Hud 與NtinE£Adai口運triLt，!"里面霞umqiMbiig：kttlciilN=.一，Please input the expression =2,3A<52>+2*4*5=the result is ：12Press dcy key to coneinute七、程序清單#define STACK

19、_INIT_SIZE 100# define STACKINCREMENT 10# define OVERFLOW -2# define OK 1# define ERROR 0# define TRUE 1#define FALSE 0#include"stdio.h"#include"stdlib.h"#include"math.h"typedef int Status;char OP='+','-','*'/'(',')','',&#

20、39;=' 定義運算符數(shù)組typedef structchar *base;char *top;int stacksize;SqStack1; /定義運算符棧數(shù)據(jù)類型typedef structint *base;int *top;int stacksize;SqStack2; /定義操作數(shù)棧數(shù)據(jù)類型SqStackl OPTR; / 聲明運算符棧SqStack2 OPND; / 聲明操作數(shù)棧Status InitStack1(SqStack1 &S)/構(gòu)造運算符棧S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char);/申請空間if(

21、!S.base)exit(OVERFLOW);/ 存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status InitStack2(SqStack2 &S)/構(gòu)造操作數(shù)棧S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int);/申請空間if(!S.base)exit(OVERFLOW);/ 存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;char GetTop1(SqStack1 S)/取得運算符棧的棧頂元素ch

22、ar e;if(S.top=S.base) return ERROR; / 棧空e=*(S.top-1);return e;int GetTop2(SqStack2 S)/取得操作數(shù)棧的棧頂元素int e;if(S.top=S.base) return ERROR; / ?？誩=*(S.top-1);return e;Status Push1(SqStack1 &S,char e)/插入元素e為運算符棧的棧頂元素if(S.top-S.base>=S.stacksize)/ 棧滿，追加存儲空間S.base=(char*)realloc(S.base,(S.stacksize+STA

23、CKINCREMENT)*sizeof(char);if(!S.base) exit(OVERFLOW);/存儲分配失敗S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Push2(SqStack2 &S,int e)/插入元素e為操作數(shù)棧的棧頂元素if(S.top-S.base>=S.stacksize) / 棧滿，追加存儲空間S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int);if(

24、!S.base) exit(OVERFLOW); /存儲分配失敗S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop1(SqStack1 &S,char &e)/刪除表達式棧的棧頂元素弁用e返回if(S.top=S.base) return ERROR; 棧空e=*-S.top;return OK;Status Pop2(SqStack2 &S,int &e)/刪除表達式棧的棧頂元素弁用e返回if(S.top=S.base) return ERROR

25、; / 棧空e=*-S.top;return OK;Status In(int m,char a口)/判斷m若是運算符，返回TRUE否則返回FALSEfor(int n=0;an!='0'n+)if(m=an) return TRUE;return FALSE;char Precede(char m,char n)/判斷mV n的優(yōu)先級switch(m)case'+':case'-':if(n='+'|n='-'|n=')'|n='=')return '>'el

26、se return '<'break;case'*':case'/':case、case'%':if(n='(')return '<'else return '>'break;case'(':if(n=')')return '='else if(n='=')return ERROR;else return '<'break;case')':if(n='(&#

27、39;)return ERROR;else return '>'break;case'=':if(n='=')return '='else if(n=')')return ERROR;else return '<'break;default:return ERROR;break;其他情況，表達式有誤int Operation(int a,char theta,int b)/運算函數(shù)switch(theta)case'+':return a+b;break;case'-':return a-b;break;case'*':return a*b;break;case'/':return a/b;break;case'%':return a%b;break;case'A':return po