数据结构实验3：栈子系统

验证性实验3：栈子系统班级学号20姓名施程程1．实验目的（1）掌握栈的特点及其描述方法。（2）用链式存储结构实现一个栈。（3）掌握建栈的各种基本操作。（4）掌握栈的几个典型应用的算法。2．实验内容（1）设计一个字符型的链栈。（2）编写进栈、出栈、显示栈中全部元素的程序。（3）编写一个把十进制整数转换成二进制数的应用程序。（4）编写一个把中缀表达式转换成后缀表达式（逆波兰式）的应用程序。（5）设计一个选择式菜单，以菜单方式选择上述操作。栈子系统***********************************************1---------进栈**2---------出栈**3---------显示**4---------数制转换**5---------逆波兰式**0---------返回***********************************************请选择菜单号（0--5）：3．实验程序（附zhan.cpp）#includestdio.h#includestdlib.h#defineSTACKMAX100typedefstructstacknode{intdata;structstacknode*next;}StackNode;typedefstruct{StackNode*top;}LinkStack;voidPush(LinkStack&s,intx){StackNode*p=newStackNode;p-data=x;p-next=s.top;s.top=p;}intPop(LinkStack&s,int&x){StackNode*p;if(s.top!=NULL){p=s.top;x=p-data;s.top=p-next;deletep;return1;}elsereturn0;}voidShowStack(LinkStacks){StackNode*p=s.top;if(p==NULL)printf(\n\t\t栈为空。);else{printf(\n\t\t栈元素为：);while(p!=NULL){printf(%6d,p-data);p=p-next;}printf(\n);}}voidConversion(intn){LinkStacks;intx;s.top=NULL;do{x=n%2;n=n/2;Push(s,x);}while(n);printf(\n\t\t转换后的二进制数值：);while(Pop(s,x))printf(%d,x);printf(\n);}voidSuffix(){charstr[STACKMAX];charstack[STACKMAX];charexp[STACKMAX];charch;intsum,i,j,t,top=0;printf(\n\t\t输入算术表达式(算术符只能包含+,-,*,/),以#结束:\n\t\t);fflush(stdin);i=0;do{i++;scanf(%c,&str[i]);}while(str[i]!='#'&&i!=STACKMAX);sum=i;t=1;i=1;ch=str[i];i++;while(ch!='#'){switch(ch){case'(':top++;stack[top]=ch;break;case')':while(stack[top]!='('){exp[t++]=stack[top--];exp[t++]=',';}top--;break;case'+':case'-':while(top!=0&&stack[top]!='('){exp[t++]=stack[top--];exp[t++]=',';}stack[++top]=ch;break;case'*':case'/':while(stack[top]=='*'||stack[top]=='/'){exp[t++]=stack[top--];exp[t++]=',';}stack[++top]=ch;break;case'':break;default:while(ch='0'&&ch='z'){exp[t++]=ch;ch=str[i++];}i--;exp[t++]=',';}ch=str[i++];}while(top!=0){exp[t++]=stack[top--];if(top!=0)exp[t++]=',';}printf(\n\t\t输入的中缀表达式是:);for(j=1;jsum;j++)printf(%c,str[j]);printf(\n\n\t\t后缀表达式是:);for(j=1;jt;j++)printf(%c,exp[j]);printf(\n);}voidmain(){LinkStacks;inti=1,j=1,val,n;charchoice;s.top=NULL;while(1){printf(\n);printf(\n\t\t栈子系统);printf(\n\t\t**********************);printf(\n\t\t*1--进栈*);printf(\n\t\t*2--出栈*);printf(\n\t\t*3--显示*);printf(\n\t\t*4--数制转换*);printf(\n\t\t*5--逆波兰式*);printf(\n\t\t*0--退出程序*);printf(\n\t\t**********************);printf(\n\t\t请选择菜单号(0--5):);fflush(stdin);choice=getchar();switch(choice){case'1':while(1){printf(\n\t\t输入一个整数('0'表示结束)并按回车:);scanf(%d,&val);if(val!=0)Push(s,val);elsebreak;}break;case'2':if(Pop(s,val))printf(\n\t\t出栈元素为:%6d,val);elseprintf(\n\t\t栈为空，没有元素可以出栈!\n);break;case'3':ShowStack(s);break;case'4':printf(\n\t\t请输入一个十进制正整数:);scanf(%d,&n);Conversion(n);break;case'5':Suffix();break;case'0':exit(0);default:printf(\n\t\t输入的菜单错误，请重新输入!\n);}}}4.运行结果5．实验小结本章主要要求我们掌握栈的特点及其描述方法，就是进栈、出栈、数字转换、逆波兰式等的程序是怎样的。这个实验要求设计的是一个字符型链栈，其中要求有进栈、出栈、显示栈中全部元素、把十进制转换成二进制以及中缀表达式转换成后缀表达式的程序。根据书上所给的参考程序，我自己先看了一遍，基本上能看懂，哪段程序是进栈的程序，哪段程序是表示出栈，显示栈中元素也能找到，数字转换和把中缀表达式转换成后缀表达式也知道是哪一段。在编译的时候这一次没有错误，我很高兴。在执行的时候，操作很简单，没有什么问题，看着结果的出现，怀着的是一种激动的心情。本次实验是成功的，在实验中我更好的理解了栈的运用，牢记了栈是后进先出的特点。