[工学]数据结构实验第6次课栈的应用.ppt

预备知识 链式存储结构： 栈空：S为空指针； 栈满：动态分配，除非溢出。,第6次课 栈的应用,一、实验目的： 理解栈是操作受限（插入push，删除pop）的线性表，受限的是插入删除的位置。 在链式存储结构下实现：StackEmpty，Push,Pop, 几个基本操作。 通过调用基本操作实现括号匹配算法。,引例 括号匹配的检验 表达式中有三种括号：“（”和“）”，“”和“”，“”和“”， 编写判别给定表达式中所含括号是否正确配对出现的算法,#include #include #define True 1 #define False 0 #define OK 1 #define ERROR 0 typedef int status; typedef char ElemType;,typedef struct SNode ElemType data; struct SNode *next; SNode, *LinkStack; status InitStack(LinkStack ,main() ElemType formula20; printf(“请输入一个带括号的表达式：“); scanf(“%s“,formula); if(Is_Match(formula) printf(“n 这个表达式括号是匹配的！“); else printf(“n 这个表达式括号不匹配！n“); return(1); ,status InitStack(LinkStack ,status Push(LinkStack ,status Pop(LinkStack ,status Is_Match(ElemType f20) LinkStack St; ElemType *p,c; InitStack(St); p=f; while(*p!=0) switch (*p) case (: if(!Push(St, *p) return(ERROR); break; case : if(!Push(St, *p) return(ERROR); break; case : if(!Push(St, *p) return(ERROR); break; case ): if(!Pop(St, c) return(ERROR); else if(c!=() return(ERROR); break; case : if(!Pop(St, c) return(ERROR); else if(c!=) return(ERROR); break; case : if(!Pop(St, c) return(ERROR); else if(c!=) return(ERROR); break; +p; if(StackEmpty(St) return(OK); else return(ERROR); ,二、实验内容： 1.写一个算法，识别依次读入的一个字符序列是否为形如序列1 提示：利用栈 ，利用已实现的基本操作,算法描述： 1.向后依次扫描字符序列，如果考察的字符不等于&则入栈，遇到&