数据结构栈的应用

数据结构栈的应用.专业资料.《数据结构》实验报告数据结构栈的应用全文共9页，当前为第1页。实验序号：4实验项目名称：栈的操作数据结构栈的应用全文共9页，当前为第1页。学号1407022228姓名王元专业、班网络工程2班实验地点1-314指导教师林仙丽实验时间一、实验目的及要求1.熟悉栈的基本概念；2.掌握栈的顺序存储结构；3．掌握栈的应用。二、实验设备（环境）及要求微型计算机；windows操作系统；MicrosoftVisualStudio6.0集成开发环境。三、实验内容与步骤1.栈的顺序表表示和实现的如下：#include<iostream>#defineMaxSize100usingnamespacestd;typedefintElemType;typedefstruct{ ElemTypedata[MaxSize]; inttop;}SqStack;voidInitStack(SqStack*st)//初始化栈{ st->top=-1;}intStackEmpty(SqStack*st)//判断栈为空{ return(st->top==-1);}voidPush(SqStack*st,ElemTypex)//元素进栈{ if(st->top==MaxSize-1) { printf("栈上溢出!\n"); } else { st->top++;//移动栈顶位置 st->data[st->top]=x;//元素进栈 }}voidPop(SqStack*st,ElemType*e)//出栈{ if(st->top==-1) { printf("栈下溢出\n"); } else { *e=st->data[st->top];//元素出栈 st->top--;//移动栈顶位置 }}intmain(){ SqStackL; SqStack*st=&L; ElemTypee; inti; InitStack(st); for(i=1;i<10;++i) { Push(st,i); printf("入栈元素是：%d\n",i); } for(i=1;i<10;++i) { Pop(st,e); printf("出栈元素是：%d\n",e); } 数据结构栈的应用全文共9页，当前为第2页。数据结构栈的应用全文共9页，当前为第2页。}改写以上程序，实现功能如下：调用栈操作函数实现判别一个算术表达式中的圆括号和方括号配对是否正确匹配。2.C/C++的库函数中已经实现了栈，实例如下：#include<stack>//引入栈usingnamespacestd;intmain(){ inta; stack<int>s; scanf("%d",&a); s.push(a);//入栈 printf("%d\n",s.top());//取得栈顶元素输出 s.pop();//出栈 return0;}请根据以上程序，设计算法如下：判别一个算术表达式中的圆括号配对是否正确。分析与讨论1.数据结构栈的应用全文共9页，当前为第3页。数据结构栈的应用全文共9页，当前为第3页。对上机实践结果进行分析，上机的心得体会。五、教师评语签名：日期：成绩附源程序清单：1.#include<iostream>#defineMaxSize100usingnamespacestd;typedefcharElemType;typedefstruct{ ElemTypedata[MaxSize]; inttop;}SqStack;voidInitStack(SqStack*st)//初始化栈{ st->top=-1;}intStackEmpty(SqStack*st)//判断栈为空{ return(st->top==-1);}voidPush(SqStack*st,ElemTypex)//元素进栈数据结构栈的应用全文共9页，当前为第4页。数据结构栈的应用全文共9页，当前为第4页。 if(st->top==MaxSize-1) { printf("栈上溢出!\n"); } else { st->top++;//移动栈顶位置 st->data[st->top]=x;//元素进栈 }}voidPop(SqStack*st,ElemType*e)//出栈{ if(st->top==-1) { printf("栈下溢出\n"); } else { *e=st->data[st->top];//元素出栈 st->top--;//移动栈顶位置 }}intmain(){ SqStackL; SqStack*st=&L; ElemTypee,a[MaxSize]; inti,j=1,k; do{ InitStack(st); gets(a); for(i=0;a[i]!='\0';i++) { if(a[i]=='('||a[i]=='{'||a[i]=='[')//左括号入栈 Push(st,a[i]); if(a[i]==')') { if(StackEmpty(st)==1)//判断栈是否为空 { printf("多了“(”，不匹配\n"); break;数据结构栈的应用全文共9页，当前为第5页。数据结构栈的应用全文共9页，当前为第5页。 else if('('==st->data[st->top])//匹配成功出栈 Pop(st,&e); else { printf("%c不匹配\n",a[i]); break; } } if(a[i]=='}') { if(StackEmpty(st)==1)//判断栈是否为空 { printf("多了“}”，不匹配\n"); break; } else if('{'==st->data[st->top])//匹配成功出栈 Pop(st,&e); else { printf("%c不匹配\n",a[i]); break; } } if(a[i]==']') { if(StackEmpty(st)==1)//判断栈是否为空 { printf("多了“]”，不匹配\n"); break; } else if('['==st->data[st->top])//匹配成功出栈 Pop(st,&e); else { printf("%c不匹配\n",a[i]); break; } } }数据结构栈的应用全文共9页，当前为第6页。数据结构栈的应用全文共9页，当前为第6页。 printf("匹配成功\n"); else printf("匹配不成功，多了%c。\n",st->data[st->top]); printf("是否继续匹配括号：（继续不要按“#”）\n"); scanf("%c",&e); k=getchar();//这是为了输入e时会敲回车键而加上去的 }while(e!='#');}2.（1）#include<stack>//引入栈usingnamespacestd;intmain(){ inta,i; charb[50]; stack<char>s;//声明了一个char型的栈,括号里面的可以改为任何基本类型 gets(b); for(i=0;b[i]!='\0';i++) { if(b[i]=='('||b[i]=='[') { s.push(b[i]); }//如果为"（"或者是"["，就入栈 if(b[i]==')') { if(s.empty()==1)//s.empty是判断函数，若无栈顶元素就会返回1，表明栈为空，否则就会返回0 { printf("不匹配\n"); break; } if(s.top()=='(')//判断是否符合出栈的条件 { s.pop();//匹配就会出栈 } else { printf("不匹配\n"); break; } } if(b[i]==']')数据结构栈的应用全文共9页，当前为第7页。数据结构栈的应用全文共9页，当前为第7页。 if(s.empty()==1)//判断栈是否为空 { printf("不匹配\n"); break; } if(s.top()=='[') { s.pop(); } else { printf("不匹配\n"); break; } } } if(s.empty()==1&&b[i]=='\0')//调用函数，判断栈是否已经为空或者数组的右括号已经匹配完成 printf("匹配成功\n"); if(s.empty()==0)//b[i]已经比较完了，但是若是栈里元素没有出栈，就不能说是匹配完全printf("匹配不成功\n"); return0;}（2）#include"iostream"#include<stack>//引入栈usingnamespacestd;intmain(){ inta; stack<char>s;//申请一个char型的栈 printf("输入回车键结束入栈\n"); while((a=getchar())!='\n')//一个一个的读入并匹配，若不匹配就跳出 { switch(a)//swith是一种条件语句 { case'[': case'(': s.push(a); continue;//[或(就进栈 case')':数据结构栈的应用全文共9页，当前为第8页。 case']':数据结构栈的应用全文共9页，当前为第8页。 if(s.empt