数据结构实验报告(栈,括号匹配)

《数据结构实验报告(栈,括号匹配)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、北京建筑工程学院理学院《数据结构与算法》课程实验报告课程名称《数据结构与算法》实验名称栈的创建以及应用实验地点机房203日期_2012/4/3姓名班级学号指导教师成绩_______【实验目的】l熟悉并写出栈的逻辑结构表示l实现栈的存储表示l实现栈的操作【实验内容】l括号匹配【实验要求】l在实验报告中写出栈的ADT表示；l在实验报告中给出数据类型定义和核心算法和程序；l在实验报告中罗列实验过程中出现的问题和解决的方法；l打包上交调试后的完整程序，提交实验报告；l实验之前写出实验报告的大概框架，实验过程中填

2、写完整。l实验时携带需要上机调试的程序；l实验评分：实验之前预习占20%，实验报告书写情况占50%，运行情况30%。【实验步骤】1．栈的ADT表示ADTStack{数据对象：D={aiai∈ElemSet,i=1，2，…，n,n>=0}数据关系：R1={ai-1,ai∈D,i=2,…,n}约定an为栈顶端，a1为栈底端基本操作：StatusInitStack(&s)操作结果：构造一个空栈s。StatusPush(&s,e)初始条件：栈s已经存在。操作结果：插入元素e为新的栈顶元素。St

3、atusPop(&s,&e)初始条件：栈s已经存在，并不为空。操作结果：删除s的栈顶元素，并用e返回其值。第-5-页共5页StatusCheck(&s,e)初始条件：栈s已经存在，并不为空。操作结果:判断括号是否匹配。StatusEnterString(&s)}ADTStack1．数据类型定义和核心算法和程序²数据类型定义：typedefintStatus;typedefcharSElemType;typedefstruct{//栈的顺序存储表示SElemTypebase;SElemTypetop;in

4、tstacksize;}SqStack;intx=0;SElemTypea;SElemTypee;²核心算法：²程序：#include#include#include#defineTURE1#defineFALSE0#defineERROR0#defineOK1#defineINFEASIBLE-1#defineOVERFLOW-2#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefint

5、Status;typedefcharSElemType;typedefstruct{//栈的顺序存储表示SElemTypebase;SElemTypetop;intstacksize;}SqStack;intx=0;第-5-页共5页StatusInitStack(SqStack&s){//构造一个空栈Ss.base=(SElemType)malloc(STACK_INIT_SIZEsizeof(SElemType));if(!s.base)exit(OVERFLOW);//内存分配失败s.top=s.b

6、ase;s.stacksize=STACK_INIT_SIZE;returnOK;}StatusPush(SqStack&s,SElemTypee){//插入元素e为新的栈顶元素if(s.top-s.base>=s.stacksize){//栈满追加存储空间。s.base=(SElemType)realloc(s.base,(s.stacksize+STACKINCREMENT)sizeof(SElemType));if(!s.base)exit(OVERFLOW);//内存分配失败s.top=s.ba

7、se+s.stacksize;s.stacksize+=STACKINCREMENT;}s.top++=e;returnOK;}StatusPop(SqStack&s,SElemType&e){//若栈不空，则删除s的栈顶元素，用e返回其值，并返回ok；否则返回error。if(s.top==s.base)returnERROR;e=--s.top;returnOK;}////////////////////////////////////////////////////////////////////

8、StatusCheck(SqStack&s,SElemTypee){SElemTypea;Pop(s,a);if(a=='('&&e==')'a=='['&&e==']'a=='{'&&e=='}')returnTURE;returnERROR;}StatusEnterString(SqStack&s){第-5-页共5页SElemTypee;while(1){scanf("%c",&e);if(e=='('e=='['e=='{')Push