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

北京建筑工程学院理学院数据结构与算法课程 实验报告课程名称数据结构与算法 实验名称 栈的创建以及应用实验地点 机房203 日期_2012/4/3姓名 班级 学号 指导教师 成绩_【实验目的】l 熟悉并写出栈的逻辑结构表示l 实现栈的存储表示l 实现栈的操作【实验内容】 l 括号匹配【实验要求】l 在实验报告中写出栈的ADT表示；l 在实验报告中给出数据类型定义和核心算法和程序；l 在实验报告中罗列实验过程中出现的问题和解决的方法；l 打包上交调试后的完整程序，提交实验报告；l 实验之前写出实验报告的大概框架，实验过程中填写完整。l 实验时携带需要上机调试的程序；l 实验评分：实验之前预习占20%，实验报告书写情况占50%，运行情况30%。【实验步骤】1 栈的ADT表示ADT Stack数据对象：D=ai|ai ElemSet,i=1，2，n,n=0数据关系：R1=|ai-1,ai D,i=2,n约定an为栈顶端，a1为栈底端基本操作：Status InitStack(&s)操作结果：构造一个空栈s。Status Push( &s, e)初始条件：栈s已经存在。操作结果：插入元素e为新的栈顶元素。Status Pop( &s, &e)初始条件：栈s已经存在，并不为空。操作结果：删除s的栈顶元素，并用e返回其值。Status Check( &s, e)初始条件：栈s已经存在，并不为空。操作结果:判断括号是否匹配。Status EnterString( &s)ADT Stack2 数据类型定义和核心算法和程序 数据类型定义：typedef int Status;typedef char SElemType;typedef struct /栈的顺序存储表示SElemType* base;SElemType* top;int stacksize;SqStack;int x=0;SElemType a;SElemType e; 核心算法： 程序：#include #include #include #define TURE 1#define FALSE 0#define ERROR 0#define OK 1#define INFEASIBLE -1#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef char SElemType;typedef struct /栈的顺序存储表示SElemType* base;SElemType* top;int stacksize;SqStack;int x=0;Status InitStack(SqStack &s)/构造一个空栈Ss.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType);if (!s.base) exit(OVERFLOW);/内存分配失败s.top = s.base;s.stacksize = STACK_INIT_SIZE;return OK;Status Push(SqStack &s,SElemType e)/插入元素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.base+s.stacksize;s.stacksize += STACKINCREMENT;*s.top+ =e;return OK;Status Pop(SqStack &s,SElemType &e)/若栈不空，则删除s的栈顶元素，用e返回其值，并返回ok；否则返回error。if(s.top = s.base) return ERROR;e = * -s.top;return OK;/Status Check(SqStack &s,SElemType e)SElemType a;Pop(s,a);if( a=( & e=) |a=& e= |a=& e= )return TURE;return ERROR;Status EnterString(SqStack &s)SElemType e;while (1)scanf(%c,&e);if(e=(|e=|e=)Push(s,e);else if(e=)|e=|e=)if(!Check(s,e)return FALSE;break;else if(e!=n)x=1;return FALSE;break;elsebreak;void main()SqStack s;I