《数据结构试验3栈子系统.docx》由会员分享，可在线阅读，更多相关《数据结构试验3栈子系统.docx（8页珍藏版）》请在三一文库上搜索。
1、验证性实验3:栈子系统班级学号 20 姓名 施程程1. 实验目的(1) 掌握栈的特点及其描述方法。(2) 用链式存储结构实现一个栈。(3) 掌握建栈的各种基本操作。(4) 掌握栈的几个典型应用的算法。2. 实验内容(1) 设计一个字符型的链栈。(2) 编写进栈、出栈、显示栈中全部元素的程序。(3) 编写一个把十进制整数转换成二进制数的应用程序。(4) 编写一个把中缀表达式转换成后缀表达式(逆波兰式)的应用程序。(5) 设计一个选择式菜单，以菜单方式选择上述操作。栈子系统*1进 栈*2出 栈*3显 示*4数制转换*5逆波兰式*0返回*请选择菜单号（0-5 ）:3.实验程序（附 zhan.cpp
2、）#include <stdio.h>#include <stdlib.h>#define STACKMAX 100typedef struct stacknodeint data;struct stacknode *next;StackNode;typedef structStackNode *top;LinkStack;void Push （LinkStack &s,int x）StackNode *p=new StackNode;p->data=x;p->next=s.top;s.top=p;int Pop(LinkStack &s,i
3、nt &x)(StackNode *p;if(s.top!=NULL)(p=s.top;x=p->data;s.top=p->next;delete p;return 1;elsereturn 0;void ShowStack (LinkStack s)(StackNode *p=s.top;if (p=NULL)printf("ntt栈为空。");else(printf("ntt栈元素为：");while (p!=NULL)(printf("%6d”,p->data);p=p->next;printf(&quo
4、t;n");void Conversion(int n)(LinkStack s;int x;s.top=NULL;do(x=n%2;n=n/2;Push(s,x);while(n);printf("ntt转换后的二进制数值："); while (Pop(s,x) printf("%d”,x); printf("n");void Suffix()char strSTACKMAX;char stackSTACKMAX;char expSTACKMAX; char ch;int sum,i,j,t,top=0;printf(-ntt输入算
5、术表达式(算术符只能包含+,-,*,/),以#结束:ntt");fflush(stdin); i=0; do i+; scanf("%c”,&stri);while(stri!='#'&& i!=STACKMAX); sum=i; t=1; i=1; ch=stri; i+; while (ch!='#') switch (ch) case '(': top+; stacktop=ch; break; case ')':while (stacktop!='(') expt
6、+=stacktop-; expt+=',' top-; break; case '+': casewhile (top!=0 && stacktop!='(') expt+=stacktop-;expt+=','stack+top=ch;break;case '*':case '/':while(stacktop='*' | stacktop='/') expt+=stacktop-;expt+=','stack+top=ch;bre
7、ak;case '':break;default:while (ch>='0'&&ch<='z')expt+=ch;ch=stri+;i-;expt+=','ch=stri+;while (top!=0)expt+=stacktop-;if(top!=0)expt+=','printf("ntt输入的中缀表达式是：");for(j=1;j<sum;j+)printf("%c",strj);printf("nntt后缀表达式是：&qu
8、ot;);for(j=1;j<t;j+)printf("%c",expj);printf("n");void main()LinkStack s; int i=1,j=1,val,n; char choice;s.top=NULL;while(1)printf("n");printf("ntt栈子系统");printf("ntt*");printf("ntt* 1-进栈*"printf("ntt*2-出栈*"printf("ntt*3-显示
9、*"printf("ntt*4-数制转换*"printf("ntt*5-逆波兰式*"printf("ntt*0-退出程序*"printf("ntt*");printf("ntt 请选择菜单号(0-5):");fflush(stdin);choice=getchar();switch (choice)case '1':while (1)printf("ntt输入一个整数('0'表示结束)并按回车：");scanf("%d&qu
10、ot;,&val);if (val!=0)Push (s,val);elsebreak;break;case '2':if (Pop(s,val)printf("ntt出栈元素为：6d”,val);elseprintf("ntt栈为空，没有元素可以出栈！ n");break;case '3':ShowStack(s);break;case '4':printf("ntt请输入一个十进制正整数：");scanf("%d",&n);Conversion(n);bre
11、ak;case '5':Suffix();break;case '0':exit(0);default:printf("ntt输入的菜单错误，请重新输入！ n");4.运行结果-Ini x栈子系统彭示换式序转兰程进出显数逆退-12 3 4 5 0请选择菜单号0-5 ： 1输入一个整数叶表示结束）并按回车：i 输入一个整数叶表示结束）并按回车：2 输入一个整数叶表示结束）并按回车：3 输入一个整数叶表示结束）并按回车：4 输入一个整数叶表示结束）并按回车：$ 输入一个整数叶表示结束）并按回车：0-Ini x请选择菜单号0-5 ：栈子系统碧示换式
12、序&S制波出 进出显数逆退 _12 3 4 5 0请选择菜单号0-5 ： 3栈元素为：54321栈子系统碧示换式序&S制波出 进出显数逆退 _12 3 4 5 0请选择菜单号0-5 ：-Ini xcT "E： 数据结构Debug3. exe*栈子系统*12 3 4 5 0碧示换式序制波出 进出显数逆退 _*请选择菜单号0-5： 2出栈元素为：5栈子系统碧示换式序&S制波出 进出显数逆退 _12 3 4 5 0|口| X碧示换式序&S制波出 进出显数逆退 _12 3 4 5 0请选择菜单号0-5 ： 4 请输入一个十进制正整数：12 转换后的二进制数值：
13、1100栈子系统碧示换式序&S制波出 进出显数逆退 _12 3 4 5 0请选择菜单号0-5 ：cT "E： 数据结构Debug3. exe* * * *制波出 显数逆退 _ _ _ _请选择菜单号0-5 ： 5输入算术表达式算术符只能包含七一次,/,以林结束:3+5*7-93+2#输入的中缀表达式是：3+5*?-93+2后缀表达式是：3,5,7,土七93,-,2,+栈子系统碧示换式序&S制波出 进出显数逆退 _12 3 4 5 0输入的中缀表达式是二3+5*7-9X3+2后缀表达式是：LS，*,，93,-,2,+栈子系统一一耄示换式序 0 曹=程 制53 0进出显数
14、逆退 - -12 3 4 5 0请选择菜单号0-5 ： 0Press any key to cont inue5.实验小结本章主要要求我们掌握栈的特点及其描述方法，就是进栈、出栈、数字转换、逆波兰式等的程序是怎样的。这个实验要求设计的是一个字符型链栈，其中要求有进栈、出栈、显示栈中全部元素、 把十进制转换成二进制以及中缀表达式转换成后缀表达式的程序。根据书上所给的参考程 序，我自己先看了一遍，基本上能看懂，哪段程序是进栈的程序，哪段程序是表示出栈，显 示栈中元素也能找到，数字转换和把中缀表达式转换成后缀表达式也知道是哪一段。在编译的时候这一次没有错误，我很高兴。在执行的时候，操作很简单，没有什么问题，看着结果 的出现，怀着的是一种激动的心情。本次实验是成功的，在实验中我更好的理解了栈的运用，牢记了栈是后进先出的特点。