数据结构栈的应用.pdf
数据结构实验报告 实验序号：4 实验项目名称：栈的操作 学 号 1407022228 姓 名 王元 专业、班 网络工程 2 班 实验地点 1-314 指导教师 林仙丽 实验时间 一、实验目的及要求 1.熟悉栈的基本概念；2.掌握栈的顺序存储结构；3 掌握栈的应用。二、实验设备（环境）及要求 微型计算机；windows 操作系统；Microsoft Visual Studio 6.0 集成开发环境。三、实验内容与步骤 1.栈的顺序表表示和实现的如下：#include#define MaxSize 100 using namespace std;typedef int ElemType;typedef struct ElemType dataMaxSize;int top;SqStack;void InitStack(SqStack*st)/初始化栈 st-top=-1;int StackEmpty(SqStack*st)/判断栈为空 return(st-top=-1);void Push(SqStack*st,ElemType x)/元素进栈 if(st-top=MaxSize-1)printf(栈上溢出!n);else st-top+;/移动栈顶位置 st-datast-top=x;/元素进栈 void Pop(SqStack*st,ElemType*e)/出栈 if(st-top=-1)printf(栈下溢出n);else *e=st-datast-top;/元素出栈 st-top-;/移动栈顶位置 int main()SqStack L;SqStack*st=&L;ElemType e;int i;InitStack(st);for(i=1;i10;+i)Push(st,i);printf(入栈元素是：%dn,i);for(i=1;i10;+i)Pop(st,e);printf(出栈元素是：%dn,e);return 0;改写以上程序，实现功能如下：调用栈操作函数实现判别一个算术表达式中的圆括号和方括号配对是否正确匹配。2.C/C+的库函数中已经实现了栈，实例如下：#include /引入栈 using namespace std;int main()int a;stacks;scanf(%d,&a);s.push(a);/入栈 printf(%dn,s.top();/取得栈顶元素输出 s.pop();/出栈 return 0;请根据以上程序，设计算法如下：判别一个算术表达式中的圆括号配对是否正确。四、分析与讨论 1.2.对上机实践结果进行分析，上机的心得体会。五、教师评语 签名：日期：成绩 附源程序清单：1.#include#define MaxSize 100 using namespace std;typedef char ElemType;typedef struct ElemType dataMaxSize;int top;SqStack;void InitStack(SqStack*st)/初始化栈 st-top=-1;int StackEmpty(SqStack*st)/判断栈为空 return(st-top=-1);void Push(SqStack*st,ElemType x)/元素进栈 if(st-top=MaxSize-1)printf(栈上溢出!n);else st-top+;/移动栈顶位置 st-datast-top=x;/元素进栈 void Pop(SqStack*st,ElemType*e)/出栈 if(st-top=-1)printf(栈下溢出n);else *e=st-datast-top;/元素出栈 st-top-;/移动栈顶位置 int main()SqStack L;SqStack*st=&L;ElemType e,aMaxSize;int i,j=1,k;do InitStack(st);gets(a);for(i=0;ai!=0;i+)if(ai=(|ai=|ai=)/左括号入栈 Push(st,ai);if(ai=)if(StackEmpty(st)=1)/判断栈是否为空 printf(多了“(”，不匹配n);break;else if(=st-data st-top)/匹配成功出栈 Pop(st,&e);else printf(%c不匹配n,ai);break;if(ai=)if(StackEmpty(st)=1)/判断栈是否为空 printf(多了“”，不匹配n);break;else if(=st-data st-top)/匹配成功出栈 Pop(st,&e);else printf(%c不匹配n,ai);break;if(ai=)if(StackEmpty(st)=1)/判断栈是否为空 printf(多了“”，不匹配n);break;else if(=st-data st-top)/匹配成功出栈 Pop(st,&e);else printf(%c不匹配n,ai);break;if(st-top=-1)printf(匹配成功n);else printf(匹配不成功，多了%c。n,st-data st-top);printf(是否继续匹配括号：（继续不要按“#”）n);scanf(%c,&e);k=getchar();/这是为了输入 e 时会敲回车键而加上去的 while(e!=#);2.（1）#include /引入栈 using namespace std;int main()int a,i;char b50;stacks;/声明了一个 char型的栈,括号里面的可以改为任何基本类型 gets(b);for(i=0;bi!=0;i+)if(bi=(|bi=)s.push(bi);/如果为（或者是，就入栈 if(bi=)if(s.empty()=1)/s.empty是判断函数，若无栈顶元素就会返回1，表明栈为空，否则就会返回 0 printf(不匹配n);break;if(s.top()=()/判断是否符合出栈的条件 s.pop();/匹配就会出栈 else printf(不匹配n);break;if(bi=)if(s.empty()=1)/判断栈是否为空 printf(不匹配n);break;if(s.top()=)s.pop();else printf(不匹配n);break;if(s.empty()=1&bi=0)/调用函数，判断栈是否已经为空或者数组的右括号已经匹配完成 printf(匹配成功n);if(s.empty()=0)/bi已经比较完了，但是若是栈里元素没有出栈，就不能说是匹配完全 printf(匹配不成功n);return 0;（2）#include iostream#include /引入栈 using namespace std;int main()int a;stacks;/申请一个 char型的栈 printf(输入回车键结束入栈n);while(a=getchar()!=n)/一个一个的读入并匹配，若不匹配就跳出 switch(a)/swith 是一种条件语句 case:case(:s.push(a);continue;/或(就进栈 case):case:if(s.empty()=0)s.pop();continue;else printf(右括号多出，配对失败。n);goto loop;if(s.empty()=0)printf(左括号多出，配对失败。n);else printf(配对成功!n);loop:return 0;
