数据结构实验.docx

《数据结构实验.docx》由会员分享，可在线阅读，更多相关《数据结构实验.docx（16页珍藏版）》请在三一办公上搜索。

1、数据结构实验数据结构与算法统计 专业：班级：学号：姓名： 实验报告 一、 实验目的 1. 学习使用C+实现栈的存储结构；.通过编程、上机调试，进一步理解栈的基本概念； 2. 锻炼独立编程与思考的能力，提升实践能力。 二、 实验内容 简单计算器。 请按照四则运算加、减、乘、除、幂和括号的优先关系和惯例，编写计算器程序。要求： 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。 例如，输入：4+2*5= 输出：14 输出：-48 输入：(4+2)*(2-10)= 三、 程序设计 1、概要设计 为实现上述功能，应

2、该使用两个栈，分别寄存操作数和运算符。为此需要栈的抽象数据结构。 栈的抽象数据类型定义如下： ADT Stack 数据对象： D = ai | ai ElemSet, i=1,n，n0 数据关系： R1 = | ai-1,ai D, i=2, ,n 基本操作： InitStack1(SqStack1 &S) 操作结果：创建一个空栈S，以存储运算符 InitStack2(SqStack2 &S) 操作结果：创建一个空栈S，以存储操作数 Push1(SqStack1 &S,char e) 初始条件：栈S已存在 操作结果：插入运算符e作为新的栈顶元素 Push2(SqStack2 &S,int e)

3、 初始条件：栈S已存在 操作结果：插入操作数e作为新的栈顶元素 Precede(char d,char c) 初始条件：d，c为运算符 操作结果：若d优先级大于c,返回；若d优先级小于c,返回；若d优先级等于c,返回=； GetTop1(SqStack1 &S) 初始条件：栈S已存在且非空 操作结果：用e返回寄存运算符栈S的栈顶元素 GetTop2(SqStack2 &S) 初始条件：栈S已存在且非空 操作结果：用e返回寄存操作数栈S的栈顶元素 Pop1(SqStack1 &S,char &e) 初始条件：栈S已存在且非空 操作结果：删除寄存运算符栈S的栈顶元素 Pop2(SqStack2 &

4、S,int &e) 初始条件：栈S已存在且非空 操作结果：删除寄存操作数栈S的栈顶元素 Operate(int a,char theta,int b) 初始条件：a，b为整数，theta为运算符 操作结果：返回a与b运算的结果 Yunsuan 初始条件：输入合法的表达式 操作结果：返回表达式的值 ADT Stack 主程序流程 调用Yunsuan函数计算表达式的值，输出，在屏幕上打印出来。 各模块的调用关系 先由主函数调用计算求值模块；再由求值模块调用栈构造模块，表达式转换模块及表达式求值模块，计算并返回表达式的值；最后由主函数在屏幕上输出表达式的结果。 流程图 Y c进入操作数栈 返回运算结

5、果 输出运算结果 c!=+&c!=-&c!=*&c!=/&c!=&c!=(&c!=)&cc!=|GetTop1(OPTR)!= 开始 = 作为运算符栈的栈底字符 输入c case:操作数入栈顶2个数运算 Y N 结束 2、详细设计 数据类型设计 typedef struct char * base; char * top; int stacksize; SqStack1;/定义运算符栈数据类型 typedef struct int * base; int * top; int stacksize; SqStack2; /定义操作数栈数据类型 操作算法设计 int InitStack1(SqSt

6、ack1 &S) /构造运算符栈 S.base=(char*)malloc(STACK_INIT_SIZE *sizeof(char);/申请存储空间 if(!S.base) exit(OVERFLOW);/存储空间分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return 1; int InitStack2(SqStack2 &S)/构造操作数栈 S.base=(int *)malloc(STACK_INIT_SIZE * sizeof(int);/申请存储空间 if(!S.base) exit(OVERFLOW); /存储空间分配失败 S.

7、top=S.base; S.stacksize=STACK_INIT_SIZE; return 1; char GetTop1(SqStack1 &S)/取得运算符栈栈顶元素 char e; if(S.top=S.base)/栈空 return 0; e=*(S.top-1); return e; int GetTop2(SqStack2 &S) /取得操作数栈栈顶元素 char e; if(S.top=S.base) /栈空 e=*(S.top-1); return e; int Push1(SqStack1 &S,char e)/插入元素e作为运算符栈栈顶元素 if(S.top-S.bas

8、e=S.stacksize)/栈满，追加存储空间 S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char); *S.top+=e; return 1; int Push2(SqStack2 &S,int e)/插入元素e作为操作数栈栈顶元素 if(S.top-S.base=S.stacksize) /栈满，追加存储空间 S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int); *S.top+=e; if(!S.base)exi

9、t(OVERFLOW);/分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; if(!S.base)exit(OVERFLOW); /分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; return 0; return 1; int Pop1(SqStack1 &S,char &e)/删除运算符栈栈顶元素，并用e返回 if(S.top=S.base)/栈空 return 0; -S.top; e=*S.top; return 1; int Pop2(SqSta

10、ck2 &S,int &e)/删除运算符栈栈顶元素，并用e返回 if(S.top=S.base) /栈空 return 0; -S.top; e=*S.top; return 1; char Precede(char d,char c)/判断d与c的优先级 switch(c) case+:switch(d) case+:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break;

11、 case-:return ;break; case*:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case*:switch(d) case+:return ;break; case-:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case/:switch(d) case+:return ;bre

12、ak; case-:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case:switch(d) case+:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case(:return ;break; case=:return ;break; case(:switch(d) case+:return ;break; case-:return ;

13、break; case*:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case:return ;break; case(:return =;break; case):return ;break; case=:switch(d) case+:return ;break; case-:return ;break; case*

14、:return ;break; case/:return ;break; case:return ;break; case):return ;break; case=:return =;break; int Operate(int a,char theta,int b)/运算函数 switch(theta) case+:return (a+b); int Yunsuan/主要运算函数 char c,d,theta,x; int num,a,b; SqStack1 OPTR; SqStack2 OPND; InitStack1(OPTR);/构造运算符栈 InitStack2(OPND);/构造

15、操作数栈 Push1(OPTR,=); c=getchar; while(c!=|GetTop1(OPTR)!=) num=0; if(c!=+&c!=-&c!=*&c!=/&c!=&c!=(&c!=)&c!=)/不是运算符进入case-:return (a-b); case*:return (a*b); case/:return (a/b); case:return (pow(a,b); 操作数栈 while(c!=+&c!=-&c!=*&c!=/&c!=&c!=(&c!=)&c!=)/将输入的操作数的字符型转换为整型 Push2(OPND,num); num*=10; num+=(c-48

16、); c=getchar; else/若是运算符 d=GetTop1(OPTR); switch(Precede(d,c)/运算符优先级比较 case:Pop1(OPTR,theta);Pop2(OPND,b);Pop2(OPND,a);Push2(OPND,Operate(a,theta,b);break; /运算，并将运算结果放入操作数栈 return GetTop2(OPND);/返回操作数栈栈顶元素 主函数设计 void main int p; p=Yunsuan ;/进行计算 printf(%dn,p);/输出结果 四、 程序调试分析 1. 刚开始时没有思路，后来回顾了一下课上学习的

17、内容，有所启发，认识到解决该问题需要设计两个栈； 2. 自己在编写时，容易输错字符，有时候不易发现，很麻烦，仔细程度还有待提高，还需要多进行编程练习； 五、 用户使用说明 运行程序，输入运算表达式，以“=”结束，然后敲击回车键，即可输出表达式的运算结果。 六、程序运行结果 1、输入：4+2*5= 输出：14 2、输入：(4+2)*(2-10)= 输出：-48 3、输入：(4/3-2)*(2-6)= 输出：4 七、程序清单 #include #include #include #include #define STACK_INIT_SIZE 100 #define STACKINCREMENT

18、20 typedef struct char * base; char * top; int stacksize; SqStack1;/定义运算符栈数据类型 typedef struct int * base; int * top; int stacksize; SqStack2; /定义操作数栈数据类型 int InitStack1(SqStack1 &S); int InitStack2(SqStack2 &S); int Push1(SqStack1 &S,char e); int Push2(SqStack2 &S,int e); char Precede(char d,char c)

19、; char GetTop1(SqStack1 &S); int GetTop2(SqStack2 &S); int Pop1(SqStack1 &S,char &e); int Pop2(SqStack2 &S,int &e); int Operate(int a,char theta,int b); int Yunsuan; int Yunsuan/设计主要运算函数 char c,d,theta,x; int num,a,b; SqStack1 OPTR; SqStack2 OPND; InitStack1(OPTR);/构造运算符栈 InitStack2(OPND);/构造操作数栈 Pu

20、sh1(OPTR,=); c=getchar; while(c!=|GetTop1(OPTR)!=) num=0; if(c!=+&c!=-&c!=*&c!=/&c!=&c!=(&c!=)&c!=) /若不是运算符进入操作数栈 while(c!=+&c!=-&c!=*&c!=/&c!=&c!=(&c!=)&c!=) /将输入的操作数的字符型转换为整型 num*=10; num+=(c-48); c=getchar; Push2(OPND,num); else/若是运算符 d=GetTop1(OPTR); return GetTop2(OPND);/返回操作数栈栈顶元素 int InitStac

21、k1(SqStack1 &S) /构造运算符栈 S.base=(char*)malloc(STACK_INIT_SIZE *sizeof(char);/申请存储空间 if(!S.base) exit(OVERFLOW);/存储空间分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return 1; int InitStack2(SqStack2 &S)/构造操作数栈 S.base=(int *)malloc(STACK_INIT_SIZE * sizeof(int);/申请存储空间 if(!S.base) exit(OVERFLOW); /存储空间

22、分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return 1; char GetTop1(SqStack1 &S)/取得运算符栈栈顶元素 char e; if(S.top=S.base)/若是栈空 return 0; e=*(S.top-1); return e; int GetTop2(SqStack2 &S) /取得操作数栈栈顶元素 switch(Precede(d,c)/运算符优先级比较 case:Pop1(OPTR,theta); Pop2(OPND,b); Pop2(OPND,a); Push2(OPND,Operate(a,the

23、ta,b); break;/运算，并将运算结果放入操作数栈 char e; if(S.top=S.base) /若是栈空 return 0; e=*(S.top-1); return e; int Push1(SqStack1 &S,char e)/插入元素e作为运算符栈栈顶元素 if(S.top-S.base=S.stacksize)/栈满，追加存储空间 S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char); if(!S.base)exit(OVERFLOW); /分配失败 S.top=S.base+S

24、.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return 1; int Push2(SqStack2 &S,int e)/插入元素e作为操作数栈栈顶元素 if(S.top-S.base=S.stacksize) /栈满，追加存储空间 S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int); if(!S.base)exit(OVERFLOW);/分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREM

25、ENT; *S.top+=e; return 1; int Pop1(SqStack1 &S,char &e)/删除运算符栈栈顶元素，并用e返回 if(S.top=S.base)/若是栈空 return 0; -S.top; e=*S.top; return 1; int Pop2(SqStack2 &S,int &e)/删除运算符栈栈顶元素，并用e返回 if(S.top=S.base) /若是栈空 return 0; -S.top; e=*S.top; return 1; char Precede(char d,char c)/判断d与c的优先级 switch(c) case+:switch

26、(d) case+:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case*:switch(d) case+:ret

27、urn ;break; case-:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case/:switch(d) case+:return ;break; case-:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case:switch(d) case+:return ;break; case-:r

28、eturn ;break; case*:return ;break; case/:return ;break; case(:return ;break; case=:return ;break; case(:switch(d) case+:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case-:return ;break; case*:return ;break

29、; case/:return ;break; case:return ;break; case(:return =;break; case):return ;break; case=:switch(d) case+:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case:return ;break; case):return ;break; case=:return =;break; return 0; int Operate(int a,char theta,int b)/运算函数 switch(theta) case+:return (a+b); case-:return (a-b); case*:return (a*b); case/:return (a/b); case:return (pow(a,b); return 0; void main int p; p=Yunsuan;/进行计算 printf(%dn,p);/输出结果