第02讲_线性表-顺序存储2009_9.ppt

2.3.3栈的应用之一------括号匹配 设一个表达式中可以包含三种括号：小括号、中括号和大括号，各种括号之间允许任意嵌套，如小括号内可以嵌套中括号、大括号，但是不能交叉。举例如下： ([]{}) 正确的 ([()]) 正确的 {([])} 正确的 {[(])} 不正确的 {(}[]) 不正确的 如何去检验一个表达式的括号是否匹配呢？大家知道当自左向右扫描一个表达式时，凡是遇到的开括号（或称左括号）都期待有一个和它对应的闭括号（或称右括号）与之匹配。 按照括号正确匹配的规则，在自左向右扫描一个表达式时，后遇到的开括号比先遇到的开括号更加期待有一个闭括号与之匹配。 可能会连续遇到多个开括号，且它们都期待寻求匹对的闭括号，所以必须将遇到的开括号存放好。又因为后遇到的开括号的期待程度高于其先前遇到的开括号的期待程度，所以应该将所遇到的开括号存放于一个栈中。这样，当遇到一个闭括号时，就查看这个栈的栈顶结点，如果它们匹配，则删除栈顶结点，如果不匹配，则说明表达式中括号是不匹配的，如果扫描它整个表达式后，这个栈是空的，则说明表达式中的括号是匹配的，否则表达式的括号是不匹配的。 判断表达式括号是否匹配的具体实现见算法2.14。 /*******************************************/ /* 判断表达式括号是否匹配 */ /* 文件名seqmatch.c，函数名match_huohao() */ /*******************************************/ int match_kuohao(char c[]) { int i=0; sequence_stack s; init_sequence_stack(s); while(c[i]!=#) { switch(c[i]) { case {: case [: case (:push(s,c[i]);break; case }:if(!is_empty_sequence_stack(s)get_top(s)=={} {pop(s);break;} else return 0; case ]:if(!is_empty_sequence_stack(s)get_top(s)==[] {pop(s);break;} else return 0; case ):if(!is_empty_sequence_stack(s)get_top(s)==() {pop(s);break;} else return 0; } i++; } return (is_empty_sequence_stack(s));/*栈空则匹配，否则不匹配*/ } 算法2.14判断表达式括号是否匹配 2.3.4栈的应用之二------算术表达式求值 2.4 队列 2.4.1 队列 队列是一种特殊的线性表，它的特殊性在于队列的插入和删除操作分别在表的两端进行。插入的那一端称为队尾，删除的那一端称为队首。队列的插入操作和删除操作也分别简称进队和出队。 对于一个队列： {k0, k1, k2, …, kn-1} 如果k0那端是队首，kn-1那端是队尾，则k0是这些结点中最先插入的结点，若要做删除操作，k0将首先被删除，所以说，队列是具有“先进先出”（FIFO,First In First Out）特点的线性结构。 队列类型的描述如下： ADT sequence_queue { 数据集合K：K={k1, k2,…, kn},n≥0，K中的元素是datatype类型 数据关系R：R={r} r={ ki, ki+1| i=1,2,…,n-1} 操作集合： (1) void init_sequence_queue(sequence_queue *sq) 队列（顺序存储）初始化 (2) int is_empty_sequence_queue(sequence_queue sq) 判断队列（顺序存储）是否为空 (3) void print_sequence_queue(sequence_queue sq) 打印队列（顺序存储）的结点值 * * 第2章 线性表及其顺序存储 提纲 2