数据结构栈的应用.doc

《数据结构栈的应用.doc》由会员分享，可在线阅读，更多相关《数据结构栈的应用.doc（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、?数据构造?实验报告实验序号：4 实验工程名称：栈的操作学号1407022228姓名王元专业、班网络工程2班实验地点1-314指导教师林仙丽实验时间一、实验目的及要求1. 熟悉栈的根本概念；2. 掌握栈的顺序存储构造；3掌握栈的应用。二、实验设备环境及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤1.栈的顺序表表示与实现的如下：#include #define MaxSize 100using namespace std;typedef int ElemType;typedef structElemType da

2、taMaxSize;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);elsest-top+; /移动栈顶位置st-datast-top=x; /元素进栈void Pop(SqStack *st,ElemType *e) /出栈if(st-top=-1)printf(栈下溢出n

3、);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 /引入栈us

4、ing namespace std;int main()int a;stacks;scanf(%d,&a);s.push(a); /入栈printf(%dn,s(); /取得栈顶元素输出s.pop(); /出栈return 0; 请根据以上程序，设计算法如下：判别一个算术表达式中的圆括号配对是否正确。四、 分析与讨论1.2.对上机实践结果进展分析，上机的心得体会。五、教师评语签名：日期：成绩附源程序清单：1.#include #define MaxSize 100using namespace std;typedef char ElemType;typedef structElemType d

5、ataMaxSize;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);elsest-top+; /移动栈顶位置st-datast-top=x; /元素进栈void Pop(SqStack *st,ElemType *e) /出栈if(st-top=-1)printf(栈下溢出

6、n);else*e=st-datast-top; /元素出栈st-top-; /移动栈顶位置int main()SqStack L;SqStack *st=&L;ElemType e,aMaxSize;int i,j=1,k;doInitStack(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

7、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;i

8、f(st-top =-1)printf(匹配成功n);elseprintf(匹配不成功，多了%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); /如

9、果为或者是，就入栈if(bi=)if(s.empty()=1 )/s.empty是判断函数，假设无栈顶元素就会返回1，说明栈为空，否那么就会返回0printf(不匹配n);break;if(s()=()/判断是否符合出栈的条件s.pop() ;/匹配就会出栈elseprintf(不匹配n);break;if(bi=)if(s.empty() =1) /判断栈是否为空printf(不匹配n);break;if(s()=)s.pop() ;elseprintf(不匹配n);break;if(s.empty()=1&bi=0) /调用函数，判断栈是否已经为空或者数组的右括号已经匹配完成printf(

10、匹配成功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;elseprintf(右括号多出，配对失败。n);goto loop;if(s.empty()=0)printf(左括号多出，配对失败。n);else printf(配对成功!n); loop:return 0;第 12 页