北京建筑工程学院
理学院《数据结构与算法》课程 实验报告
课程名称《数据结构与算法》 实验名称 栈的创建以及应用实验地点机房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>|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 Stack
2． 数据类型定义和核心算法和程序
² 数据类型定义：
typedef int Status;
typedef char SElemType;
typedef struct {//栈的顺序存储表示
SElemType* base;
SElemType* top;
int stacksize;
}SqStack;
int x=0;
SElemType a;
SElemType e;
² 核心算法：
² 程序：
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#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 10
typedef int Status;
typedef char SElemType;
typedef struct {//栈的顺序存储表示
SElemType* base;
SElemType* top;
int stacksize;
}SqStack;
int x=0;
Status InitStack(SqStack &s){//构造一个空栈S
s.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;
}
else
break;
}
}
void main()
{
SqStack s;
InitStack(s);
if(EnterString(s))
printf("括号匹配\n");
else if(x==1)
printf("输入的不是括号\n");
else
printf("括号不匹配\n");
}
【实验结果】
第二篇：数据结构实验报告(栈_括号匹配) (1)
数据结构
课程设计报告
设计题目： 括号匹配
院 系 计算机学院
年 级 11 级
学 生 刘云飞
学 号 E01114295
指导教师 王爱平
起止时间 9-7/9-14
课程设计目的
1.熟悉并写出栈的逻辑结构表示
2.实现栈的存储表示
3.实现栈的操作
内容
括号匹配
课程设计要求
1.在实验报告中写出栈的ADT表示；
2.在实验报告中给出数据类型定义和核心算法和程序；
3.在实验报告中罗列实验过程中出现的问题和解决的方法；
4.打包上交调试后的完整程序，提交实验报告；
5.实验之前写出实验报告的大概框架，实验过程中填写完整。
6.实验时携带需要上机调试的程序；
7.实验评分：实验之前预习占20%，实验报告书写情况占50%，运行情况30%。
概要设计
1． 栈的ADT表示
ADT Stack{
数据对象：D={ai|ai∈ ElemSet,i=1，2，…，n,n>=0}
数据关系：R1={<ai-1,ai>|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 Stack
2． 数据类型定义和核心算法和程序
² 数据类型定义：
typedef int Status;
typedef char SElemType;
typedef struct {//栈的顺序存储表示
SElemType* base;
SElemType* top;
int stacksize;
}SqStack;
int x=0;
SElemType a;
SElemType e;
² 核心算法：
² 程序：
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#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 10
typedef int Status;
typedef char SElemType;
typedef struct {//栈的顺序存储表示
SElemType* base;
SElemType* top;
int stacksize;
}SqStack;
int x=0;
Status InitStack(SqStack &s){//构造一个空栈S
s.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;
}
else
break;
}
}
void main()
{
system("cls");
system("color 1f");
printf("\n@=========================================================@\n");
printf("| *********欢迎进入 括号匹配 系统************* |\n");
printf("| 姓名：刘云飞 学号：E01114295 |\n");
printf("@_________________________________________________________@\n");
SqStack s;
InitStack(s);
if(EnterString(s))
printf("括号匹配\n");
else if(x==1)
printf("输入的不是括号\n");
else
printf("括号不匹配\n");
}
【实验结果】
