顺序栈基本操作实验报告.doc

数据结构 实验三 课程 数据结构 实验名称 顺序栈基本操作 第 页专业 班级 学号 姓名 实验日期： 年 月 日 评分 一 、实验目的1熟悉并能实现栈的定义和基本操作。2了解和掌握栈的应用。二 、实验要求1进行栈的基本操作时要注意栈后进先出的特性。2编写完整程序完成下面的实验内容并上机运行。3整理并上交实验报告。三、实验内容1编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。2编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。主要功能描述如下：（1）从键盘上输入表达式。（2）分析该表达式是否合法： a) 是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。 b) 是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。 c) 若是其它字符，则返回错误信息。 （3）若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。程序中应主要包含下面几个功能函数： l void initstack()：初始化堆栈 l int Make_str()：语法检查并计算 l int push_operate(int operate)：将操作码压入堆栈 l int push_num(double num)：将操作数压入堆栈 l int procede(int operate)：处理操作码 l int change_opnd(int operate)：将字符型操作码转换成优先级 l int push_opnd(int operate)：将操作码压入堆栈 l int pop_opnd()：将操作码弹出堆栈 l int caculate(int cur_opnd)：简单计算+，-，*，/ l double pop_num()：弹出操作数 四、实验步骤（描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果）第一题：#include using namespace std; #define STACK_INIT_SIZE 100 /存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量#define OVERFLOW -1#define OK 1#define NO -1#define NULL 0typedef int Status;typedef char SElemType;typedef struct SElemType *base; /在栈构造之前和销毁之后，base的值为NULL SElemType *top; /栈顶指针 int stacksize; /当前已分配的存储空间，以元素为单位 SqStack;Status Initstack(SqStack &S)/构造一个空栈S S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize= STACK_INIT_SIZE; return OK;/InitStackStatus StackEmpty(SqStack &S) if(S.base=S.top) return OK; else return NO;Status ClearStack (SqStack &S)/把S置为空if(S.base=S.top);return OK;Status DsetroyStack (SqStack &S)/销毁栈SS.base=NULL;return OK;Status Push(SqStack &S,SElemType e)/插入元素e为新的栈顶元素 if (S.top-S.base=S.stacksize) S.base=(SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) /存储分配失败 exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;/PushStatus Pop(SqStack &S,SElemType &c) /若栈不空，则删除S的栈顶元素，用c返回其值，并返回OK；否则返回ERROR if(S.top=S.base)return NO; c=*-S.top;return OK;/PopStatus GetTop(SqStack &S,SElemType &e)if (S.top=S.base) return NO;e=*(S.top-1);return OK;/GetTopint main() SqStack S; Initstack(S); cout输入要压到栈中的元素!endl; char c; while(c=getchar()!=n) Push(S,c); GetTop(S,c);cout栈顶元素为：cendl;/ClearStack (S); /DsetroyStack(S); for(int i=0;S.top!=S.base;i+) Pop(S,c); cout栈中第i+1元素的值:; coutcendl; return 0;第二题：#includeusing namespace std;#define STACK_SIZE 100#define STACKINCREMENT 10#define OVERFLOW -1#define OK 1#define NO 0typedef int Status;typedef char SElemType;typedef structSElemType *base;SElemType *top;int stacksize;SqStack;int main()char GetTop(SqStack &s);Status Initstack(SqStack &s); Status push_operate(SqStack &s,SElemType e); Status push_num(SqStack &s,int e);Status Stackempty(SqStack &s);Status pop_num(SqStack &s,int &c);Status pushoperate(SElemType operate);Status pushnum(SElemType num);Status caculate(SElemType a,SElemType operate,SElemType b);Status pop_operate(SqStack &s,SElemType &c);Status change(SElemType e);char Precede(SElemType a,SElemType b);char Operatecxz();int m;m=Operatecxz();coutm=s.stacksize)s.base=(SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;return OK;Status push_operate(SqStack &s,SElemType e)if(s.top-s.base=s.stacksize)s.base=(SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;return OK;Status pop_operate(SqStack &s,SElemType &c)if(s.top=s.base)return NO; c=*-s.top; return OK;Status pop_num(SqStack &s,int &c)if(s.top=s.base)return NO; c=*-s.top; return OK;char GetTop(SqStack &s)char c;if(s.top=s.base)return NO; c=*(s.top-1); return c;Status caculate(int a,SElemType operate,int b)int s;if(operate=+)s=a+b;if(operate=-)s=a-b;if(operate=*)s=a*b;if(operate=/)s=a/b; return s;Status In(SElemType c)if(c=+|c=-|c=*|c=/|c=#|c=(|c=)return OK;if(c=0&c;if(b=*|b=/|b=()return ;if(b=()return ;if(a=()if(b=)return =;if(b=+|b=-|b=*|b=/)return ;if(a=#)if(b=#)return =;if(b=+|b=-|b=*|b=/|b=()return ;if(b=)return ;return ;char Operatecxz()SqStack Operate,Num;char c,e,x;int num,a,b,flat=1,sz=0;Initstack(Operate);push_operate(Operate,#);Initstack(Num);c=getchar();while(c!=#|GetTop(Operate)!=#)if(In(c)=-1)coutinput error!endl;flat=0;break;if(In(c)!=1)if(sz=0)num=change(c); sz=1;c=getchar();continue;if(sz=1) num=num*10+change(c);c=getchar();continue;elseif(sz=1) push_num(Num,num);sz=0;x=GetTop(Operate);switch(Precede(GetTop(Operate),c)case :pop_num(Num,a);pop_operate(Operate,e);pop_num(Num,b);push_num(Num,caculate(b,e,a);break;pop_operate(Operate,e);if(e!=#)flat=0;if(flat=1)pop_num(Num,a);return a;if(flat=0)return 0;五实验结果与讨论（描述最终得到的结果，并进行分析说明，可能的误差原因）第一题：1 把主函数中的ClearStack (S);DsetroyStack(S)注释掉的结果： 2 不把ClearStack (S)注释掉，把栈清空： 3 不把DsetroyStack(S)注释掉，即销毁栈：出现一堆乱码，说明销毁成功。第二题的输出：1 正常输入表达式则输出：2 如果输入的表达式出错则输出：六实验总结：1 在写主函数时，如果是用void main的形式，那么可以不用有返回值，如果是int main或|status main的话，要有返回值，既末尾要有return语句。2 有时候写的没有出现问题，但运行的结果是Press anu key to continue 。程序肯定有错，但为什么会出现这种问题呢。3分号的忘记那还是很经常的，要加强注意。4原本把ClearStack (S);DsetroyStack(S)放在for循环之后，检查不出ClearStack (S);DsetroyStack(S)的函数是否正确。把它们for循环之前，GetTop(S,c)语句之后，再利用注释等的，就可以很明显的看出栈是否被清空或销毁。5 在做表达式的计算的时候一定要注意何时入栈何时出栈。如果如栈与出栈的情况判断不清楚就无法得出答案。6 在定义栈的时候Num中的元素最好使用int类型的而不是char类型的。因为这样会简化char Operatecxz()的计算复杂度。7 对于表达式的判错情况，根据题目中的提示对每次读入的字符进行判断。8 对于不是个位数的计算，首先用了个Status change(SElemType e) int m; m=e-48; return m;把每个字符转化成int型，然后再用sz作为标记直到读入的数不是数字为止。此时再将之前读入的数num压入Num栈中。9 对于优先级的判断按照书上给定的表格进行建立关系。注意优先级的判断为这个实验最为关键的，也是最需要细心的地方。只要有一个地方弄错，将导致整个实验都出错。