数据结构括号匹配实验.docx

课程名称: 《数据结构》课程设计
课程设计题目: 括号匹配
姓名:吴文龙
院系:计算机科学与技术学院
专业:计算机科学与技术
年级:13级计科二班
学号:E11314118
指导教师:王爱平
2015 年 09月 10 日
目录
1 课程设计的目的………………………1
2 需求分析………………………………3
3 课程设计报告内容……………………3
………………………………3
………………………………3
………………………………5

4 总结……………………………………7
5 程序清单………………………………8
6 参考文献………………………………7

(1) 熟练使用 C 语言编写程序,解决实际问题;
(2) 了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力;
(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;
(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;

本程序文件主要的功能是判断括号的匹配问题。
程序的执行是从事先输入好数据的文档中读取,然后对所读取的数据进行括号匹配行的判断。最后输出判断的结果。
程序函数主要有void InitStack(Stack *S)、ElemType GetTop(Stack S,ElemType *e)、void push(Stack *S,ElemType e)、ElemType pop(Stack *S,ElemType *e)、int Judge(ElemType a[])。
InitStack函数是用来初始化栈;GetTop函数是用来获取栈顶元素;push是用来把元素压栈、pop函数是用来把元素弹出栈、Judge函数是用来判断括号是否匹配。
3 括号匹配的设计

算法分析:
首先设置好一个栈,然后从文件中读入数据,在读入的数据时,从文件中读取的字符串存入到函数定义好的字符数组中。然后把该数组作为函数参数。当每读入一个‘(’或者是‘[’,就把这个元素压栈,若是读入的元素是‘]’或者是‘)’,就调用GetTop函数,来获取栈顶元素,如果获取的栈顶元素和该次读入的元素匹配而且栈不空的话,就说明该元素是匹配的,继续比较下一次的元素;如果获取的栈顶元素和该次读入的元素不匹配的话,就说明该元素是不匹配的,直接结束运行。当所有的‘)’或者是‘]’全部比较完成之后,栈仍然不空,说明栈中还剩有‘[’或者‘(’,括号不匹配。


void InitStack(Stack *S)//建造一个栈
{
S->base = (ElemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType));
if(!*S->base) printf("error");
S ->top = S ->base;//将栈设置为空栈
S->stacksize = STACK_INIT_SIZE;//将栈的空间大小设置为STACK_INIT_SIZE
}
建栈的操作首先将栈指针s->指向新开辟的内存空间。然后将栈顶指针s->top等于s->base。将栈置成空栈。
ElemType GetTop(Stack S,ElemType *e)//获取栈顶元素
{
if(!=)
{
*e=*(-1);
return *e;
}
}
该模块用于获取栈顶元素。
void push(Stack *S,ElemType e)//压栈函数
{
if(S->top-S->base>=S->stacksize)
{
S->base=(ElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S->base) printf("分配内存失败\n");
else
{
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
}
*S->top=e;
S->top++;
}
该模块用于将元素压栈。首先判断现有栈的空间是否够用,如果不够,就再分配内存。然后将元素e赋值给栈顶指针所指位置。最后将栈顶指针加一。
ElemType pop(Stack *S,ElemType *e)//出栈函数
{
if(S->top==S->base) printf("错误\n");
e