《顺序栈基本操作实验报告》由会员分享，可在线阅读，更多相关《顺序栈基本操作实验报告（11页珍藏版）》请在金锄头文库上搜索。
1、数据结构 实验三 课程 数据结构 实验名称 顺序栈基本操作 第 页专业 班级 学号 姓名 实验日期： 年 月 日 评分 一 、实验目的1熟悉并能实现栈的定义和基本操作。2了解和掌握栈的应用。二 、实验要求1进行栈的基本操作时要注意栈后进先出的特性。2编写完整程序完成下面的实验内容并上机运行。3整理并上交实验报告。三、实验内容1编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。2编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。主要功能描述如下：（1）从键盘上输入表达式。（2）分析该表达式是否合法： a) 是
2、数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。 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)：处理操作码
3、 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 /存储空间初始分配量#d
4、efine 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=(S
5、ElemType *)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
6、 (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
7、+=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; c
8、har 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
9、 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(S
10、qStack &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
11、.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
12、.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)ret
