资源描述:
《数据结构括号匹配检验》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、《数据结构与算法》课程设计报告题目:括号匹配检验四.算法思想利用栈来判断括号是否匹配时,遇到左括号就进栈,遇到右括号则左括号出栈,代表这对括号匹配,如果右括号进栈时,栈为空,则说明缺少左括号,若表达式扫描完栈为空,则说明表达式的括号匹配,否则说明表达式缺少左括号。五.算法设计·程序流程图开始给定判断的表达式检验函数左括号右括号入栈找栈顶元素是否与它配配对删除栈顶,继续不配对,则不匹配栈空匹配栈不空不匹配结束·算法用到的抽象数据类型定义:1.ADTStack{数据对象:D={ai
2、ai∈ElemSet,i=1,2,…,n,n≥0}数据关系:R1={
3、ai-
4、1,ai∈D,i=2,…,n}约定an端为栈顶,a1端为栈底。基本操作:(1)InitStack(&S);操作结果:构造一个空栈S。(2)StackEmpty(S);初始条件:栈S已存在。操作结果:若栈S为空栈,则返回TURE,否则FALUSE。(3)StackFull(S);初始条件:栈S已存在。操作结果:若栈S为满,则返回TURE,否则FALUSE.(4)GetTop(S,&e);初始条件:栈S已存在且非空。操作结果:用e返回S的栈顶元素。(5)Push(&S,e);初始条件:栈S已存在。操作结果:插入元素e为新的栈顶元素。(1)Pop(&S,&e);初始条件:栈S已
5、存在且非空。操作结果:删除S的栈顶元素,并用e返回其值。}ADTStack·算法中函数编号及功能要求:1.voidInitStack(SeqStack*S):初始化,构造一个空栈S2.IsEmpty(SeqStack*S):判断栈S为空栈时返回值为真,反之为假3.IsFull(SeqStack*S):判断栈S为满栈时返回值为真,反之为假4.Push(SeqStack*S,StackElementTypex):插入元素x为新的栈顶元素5.Pop(SeqStack*S,StackElementType*x):将栈S的栈顶元素弹出,放到x所指的存储空间中6.GetTop(Seq
6、Stack*S,StackElementType*x):将栈S的栈顶元素弹出,放到x所指的存储空间中,但栈顶指针保持不变7.Match(charch,charstr):进行括号的匹配8.BracketMatch(char*str):str[]中为输入的字符串,利用堆栈技术来检查该字符串中的括号是否匹配·函数之间的调用关系(子程序编号见上):主函数调用函数8函数8调用函数1、2、4、5、6、7六.C语言实现的程序清单/*******括号匹配的检验********/#defineTRUE1#defineFALSE0#defineStack_Size50#defineStack
7、ElementTypechar#include"stdio.h"/*顺序栈*/typedefstruct{StackElementTypeelem[Stack_Size];/*用来存放栈中元素的一维数组*/inttop;/*用来存放栈顶元素的下标,top为-1表示空栈*/}SeqStack;/*初始化*/voidInitStack(SeqStack*S){/*构造一个空栈S*/S->top=-1;}/*判栈空*/intIsEmpty(SeqStack*S)/*判断栈S为空栈时返回值为真,反之为假*/{return(S->top==-1?TRUE:FALSE);}/*判栈满
8、*/intIsFull(SeqStack*S)/*判断栈S为满栈时返回值为真,反之为假*/{return(S->top==Stack_Size-1?TRUE:FALSE);}intPush(SeqStack*S,StackElementTypex){if(S->top==Stack_Size-1)return(FALSE);/*栈已满*/S->top++;S->elem[S->top]=x;return(TRUE);}intPop(SeqStack*S,StackElementType*x){/*将栈S的栈顶元素弹出,放到x所指的存储空间中*/if(S->top==-1)
9、/*栈为空*/return(FALSE);else{*x=S->elem[S->top];S->top--;/*修改栈顶指针*/return(TRUE);}}/*取栈顶元素。*/intGetTop(SeqStack*S,StackElementType*x){/*将栈S的栈顶元素弹出,放到x所指的存储空间中,但栈顶指针保持不变*/if(S->top==-1)/*栈为空*/return(FALSE);else{*x=S->elem[S->top];return(TRUE);}}/*进行匹配*/intMatch(charch,ch