数据结构实验报告二栈的应用.docVIP

数据结构实验指导书 姓名：修凌云 姓名：李赛赛 信息与计算科学教研室 实验一 栈及其应用 实验目的 ①熟悉栈的基本概念； ②熟练掌握并实现栈的基本操作以及两个栈共享一个存储空间。 ③应用栈实现表达式求值（可参考教材71页3.3应用举例）。 实验环境 计算机、vc++ 实验学时 4学时，必做实验。 实验步骤 有详细的设计步骤； 编辑源程序并进行调试； 进行运行测试，并结合情况进行调整； 对运行结果进行保存与分析； 把源程序以文件的形式提交； 实验内容 1．1．根据栈的存储结构，分别给出可执行的源代码。 实验要求： 能够对于不同的数据类型进行栈的初始化，入栈，出栈和取栈顶元素以及对栈的判空和销毁等操作。并且注意边界条件。要求有测试案例和输出结果。 程序运行效果示例： 程序源代码 #includeiostream.h const int StackSize=20; struct student { int age; int num; void printfinfo() { coutage = age num= numendl; } }; templateclass DataType class SeqStack { public: SeqStack(){top=-1;} //构造函数，初始化一个空栈 SeqStack(DataType a[],int n); void Push(DataType x); //入栈操作，将元素x入栈 DataType Pop(); //出栈操作，将栈顶元素弹出 DataType GetTop(); //取栈顶元素（并不删除） int Empty(); //判断栈是否为空 private: DataType data[StackSize]; //存放栈元素的数组 int top; //栈顶指针，为栈元素在数组中的下标 }; templateclass DataType SeqStackDataType::SeqStack(DataType a[],int n) { top = -1; for(int i=0;in;i++){ if(top==StackSize-1)throw数组元素个数超出栈存储个数; data[i]=a[i]; top=n-1; } } templateclass DataType void SeqStackDataType::Push(DataType x) { if(top==StackSize-1)throw上溢; data[++top]=x; } templateclass DataType DataType SeqStackDataType::Pop() { DataType x; if(top==-1)throw下溢; x=data[top--]; return x; } templateclass DataType DataType SeqStackDataType::GetTop() { DataType x; if(top==-1)throw下溢; x=data[top]; return x; } templateclass DataType int SeqStackDataType::Empty() { return top==-1? 1: 0; } #includeiostream.h templateclass DataType struct Node { DataType data; NodeDataType *next; }; templateclass DataType class LinkStack { public: LinkStack(){top=NULL;} //构造函数，初始化一个空链栈 LinkStack( DataType a[],int n ); ~LinkStack(); //析构函数，释放链栈中各节点的存储空间 void Push(DataType x); //入栈操作，将元素x入栈 DataType Pop(); //出栈操作，将栈顶元素出栈 Data