栈实验报告.docVIP

北京建筑大学 理学院《数据结构与算法》课程 实验报告 课程名称《数据结构与算法》 实验名称 栈的创建以及应用实验地点 基C-419 日期_2015-4-25 姓名 班级 学号 指导教师 成绩 【实验目的】 1．熟悉并写出栈的逻辑结构表示 2．实现栈的存储表示 3．实现线性表的操作 【实验内容】 括号匹配 【实验要求】 要求：在实验报告中写出栈的ADT表示； 在实验报告中给出数据类型定义和核心算法和程序； 在实验报告中罗列实验过程中出现的问题和解决的方法； 打包上交调试后的完整程序，提交实验报告； 实验之前写出实验报告的大概框架，实验过程中填写完整。 实验时携带需要上机调试的程序； 实验评分：实验之前预习占20%，实验报告书写情况占50%，运行情况30%。 【实验步骤】 实验中出现的问题以及解决方法： 代码里面用到getch（）报错，后来在前面提前声明头文件#includeconio.h可以运行。 不知道怎么实验括号的匹配检验，通过查资料了解到括号匹配检验的实现需要用switch,case,break,default等等语句来实现。 设定好的小中括号可以正常按代码运行，若遇到其他的大括号和数字等，也可以运行匹配成功，问题没有得到解决。 【实验结果】 1、ADT表示： ADT Stack{ InitStack(S)//构造一个空栈S GetTop(S,e)//取栈顶元素 Push(S,e)//插入新的栈顶元素 Pop(S,e)//删除栈顶元素 DestroyStack(S)//销毁栈 } 2、数据结构的定义： typedef struct //定义结构体 {selemtype *base; //定义栈底指针 selemtype *top; //定义栈顶指针 int stacksize; //定义栈的大小 } sqstack; //sqstack为结构体类型 3、核心算法与代码： #define STACKINCREAMENT 10 #define STACK_INIT_SIZE 100 #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int status ; typedef char Elemtype; #includestdio.h #includemalloc.h #includestdlib.h #includeconio.h typedef struct { Elemtype *base; Elemtype *top; status stacksize; }sqstack; status Init(sqstack *s) { s-base=(Elemtype *)malloc(STACK_INIT_SIZE*sizeof(Elemtype)); if(!s-base) exit(OVERFLOW); s-top=s-base; s-stacksize=STACK_INIT_SIZE ; return OK; } status Gettop(sqstack *s,Elemtype e) { if(s-top==s-base) return ERROR; e=*(s-top-1); return OK; } status push(sqstack *s,Elemtype e) { if(s-top-s-base=s-stacksize) { s-base=(Elemtype *)realloc(s-base,(s-stacksize+STACKINCREAMENT)*sizeof(Elemtype)); if(!s-base)exit(OVERFLOW); s-top=s-base+s-stacksize; s-stacksize+=STACKINCREAMENT; } *s-top++=e; return OK; } status pop(sqstack *s,Elemtype *e) {if(s-top==s-base) return ERROR; *e=*--s-top; return OK; } status stackempty(sqstack *s) {if(s-top==s-base) return OK; return ERROR; } status clearstack(sqstack *s) { if(s-top==s-base) return ERROR; s-top=s-base; retu