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

数据结构实验指导书姓名：修凌云姓名：李赛赛信息与计算科学教研室 实验一 栈及其应用 实验目的熟悉栈的基本概念；熟练掌握并实现栈的基本操作以及两个栈共享一个存储空间。应用栈实现表达式求值（可参考教材71页3.3应用举例）。实验环境计算机、vc+实验学时 4学时，必做实验。实验步骤1、 有详细的设计步骤； 2、 编辑源程序并进行调试；3、 进行运行测试，并结合情况进行调整；4、 对运行结果进行保存与分析；5、 把源程序以文件的形式提交；实验内容11根据栈的存储结构，分别给出可执行的源代码。 实验要求：能够对于不同的数据类型进行栈的初始化，入栈，出栈和取栈顶元素以及对栈的判空和销毁等操作。并且注意边界条件。要求有测试案例和输出结果。程序运行效果示例：程序源代码#includeconst int StackSize=20;struct studentint age;int num;void printfinfo()coutage = age num= numendl;templateclass SeqStackpublic:SeqStack()top=-1; /构造函数，初始化一个空栈SeqStack(DataType a,int n); void Push(DataType x); /入栈操作，将元素x入栈DataType Pop(); /出栈操作，将栈顶元素弹出DataType GetTop(); /取栈顶元素（并不删除）int Empty(); /判断栈是否为空private:DataType dataStackSize; /存放栈元素的数组int top; /栈顶指针，为栈元素在数组中的下标;templateSeqStack:SeqStack(DataType a,int n)top = -1;for(int i=0;in;i+)if(top=StackSize-1)throw数组元素个数超出栈存储个数;datai=ai;top=n-1;templatevoid SeqStack:Push(DataType x)if(top=StackSize-1)throw上溢;data+top=x;templateDataType SeqStack:Pop() DataType x;if(top=-1)throw下溢;x=datatop-;return x;templateDataType SeqStack:GetTop()DataType x;if(top=-1)throw下溢;x=datatop;return x;templateint SeqStack:Empty()return top=-1? 1: 0;#includetemplatestruct NodeDataType data;Node *next;templateclass LinkStackpublic:LinkStack()top=NULL; /构造函数，初始化一个空链栈 LinkStack( DataType a,int n );LinkStack(); /析构函数，释放链栈中各节点的存储空间void Push(DataType x); /入栈操作，将元素x入栈DataType Pop(); /出栈操作，将栈顶元素出栈DataType GetTop(); /取栈顶元素（并不删除）int Empty()return top=NULL? 1: 0; /判空操作，判断链栈是否为空栈private:Node *top; /栈顶指针即链栈的头指针; template LinkStack:LinkStack( DataType a,int n)cout执行构造函数 endl;top=NULL;for (int i = 0;in;i+)Node *s = new Node;s-data= ai;s-next = top;top = s;template void LinkStack:Push(DataType x)Node *s = new Node;s-data = x;s-next = top;top = s;template DataType LinkStack:Pop()if(top = NULL)throw下溢;DataType x = top-data;Node *p=new Node;p=top;top = top-next;delete p;return x;template DataType LinkStack:GetTop()if(top!=NULL)return top-data;template LinkStack:LinkStack()cout执行析构函数endl;Node *p = new Node;p = top;while(top-next!=NULL)top = top-next;/coutdataendl;delete p;p = top;cout析构函数结束*endl;#include#includestack.h#includeLinkStack.hvoid main()int a10=4,2,0,56,1,32,7,13,9,6;char b10=a,b,d,g,r,h,y,i,t,o;student st10;for (int i = 0;i10; i +)sti .age = i+2; sti .num = 1000+i; cout测试顺序栈*/endl;coutint 类型 endl; SeqStack myIntStack(a,10);cout弹出栈顶元素为：myIntStack.Pop()endl;int z;cout请输入需人栈元素：z;myIntStack.Push(z);cout取栈顶元素、myIntStack.GetTop()endl;coutchar 类型 endl; SeqStack myCharStack(b,10);cout弹出栈顶元素为：myCharStack.Pop()endl;char ch;cout请输入需人栈元素：ch;myCharStack.Push(ch);cout取栈顶元素、myCharStack.GetTop()endl;coutstudent 类型 endl; SeqStack myStuStack(st,10);student t1,t2,t3;t1=myStuStack.Pop();cout弹出栈顶元素为：endl;t1.printfinfo();cout请输入需人栈元素：t2.age t2.num;myStuStack.Push(t2);t3=myStuStack.GetTop();cout取栈顶元素、endl;t3.printfinfo();cout测试链栈*/endl;coutint 类型 endl; LinkStack IntLinkStack(a,10);cout弹出栈顶元素为：IntLinkStack.Pop()endl;int y;cout请输入需人栈元素：y;IntLinkStack.Push(y);cout取栈顶元素、IntLinkStack.GetTop()endl;coutchar 类型 endl; LinkStack CharStack(b,10);cout弹出栈顶元素为：CharStack.Pop()endl;char ch1;cout请输入需人栈元素：ch1;CharStack.Push(ch1);cout取栈顶元素、CharStack.GetTop()endl;coutstudent 类型 endl; LinkStack StuStack(st,10);student t4,t5,t6;t4=StuStack.Pop();cout弹出栈顶元素为：endl;t4.printfinfo();cout请输入需人栈元素：t5.age t5.num;StuStack.Push(t5);t6=StuStack.GetTop();cout取栈顶元素、endl;t6.printfinfo();12结合栈的应用，实现双目运算的表达式求值，分别给出可执行的源代码和程序运行效果示例。程序运行效果示例： 程序源代码#include #include #include #includestack.hbool IsData(char x);bool IsSymbol(char x);int prior (char x);int compute(int x,int y,char z);int trans(char x);void main()/char str20;char a1 = #;int b1 = 0;/char str=3,+,7,*,2,-,6,#;/char str=3,-,4,*,2,+,6,#;/char str8=3,*,2,+,4,/,2,#;char str16;SeqStack Symbol(a,1);SeqStack Data(b,1);cout请输入需求值的表达式、以#结束stri;i+;while(stri-1!=#);/coutcompute(2,6,/)endl;for(int j=0;jprior(Symbol.GetTop()Symbol.Push(temp);elseif(prior(temp)=prior(Symbol.GetTop()int data1 = Data.Pop();int data2 = Data.Pop();char sym = Symbol.Pop();Data.Push(compute(data1,data2,sym);Symbol.Push(temp);if(temp=#)Symbol.Pop();if(Symbol.GetTop()!=#)int data1 = Data.Pop();int data2 = Data.Pop();char sym = Symbol.Pop();Data.Push(compute(data1,data2,sym);coutData.GetTop()endl;elsecoutData.GetTop() 47 & x 58)return true;elsereturn false;bool IsSymbol(char x)if(x=35|x=43|x=45|x=42|x=47)return true;elsereturn false;int prior(char x)switch(x)case +: return 1;break;case -: return 1;break; case *: return 2;break; case /: return 2;break;case #: return 0;break;default: couterrorendl;int compute(int x,int y,char z)switch(z)case +: return x+y; break;case -: return y-x; break;