堆栈和队列.ppt

文档介绍：1 栈栈的应用举例的应用举例例1:括号匹配的检验假设一个算法表达式中包含圆括号、方括号和花括号三种类型的括号,编写一个判别表达式中括号是否正确配对的函数。设计思路:用栈暂存左括号 2 void ExpIsCorrect (char exp[], int n) //判断有 n个字符的字符串 exp 左右括号是否配对正确{SeqStack myStack ; int i; char c; StackInitiate (&myStack ); for(i=0;i<n;i++) {if((exp[i]=='(')||(exp[i]== '[')||(exp[i]== '{')) StackPush (&myStack , exp[i]); else if(exp[i] == ')' && StackNotEmpty (myStack ) && StackTop (myStack , &c) && c == '(') StackPop (&myStack , &c); 3 else if(exp[i] == ')' && StackNotEmpty (myStack ) && StackTop (myStack , &c) && c != '(') { printf ("左右括号配对次序不正确! \n"); return;} else if(exp[i] == ']' && StackNotEmpty (myStack ) && StackTop (myStack , &c) && c == '[') StackPop (&myStack , &c); else if(exp[i] == ']' && StackNotEmpty (myStack ) && StackTop (myStack , &c) && c != '[') { printf ("左右括号配对次序不正确! \n"); return; } 4 else if(exp[i] == '}' && StackNotEmpty (myStack ) && StackTop (myStack , &c) && c == '{') StackPop (&myStack , &c); else if(exp[i] == '}' && StackNotEmpty (myStack ) && StackTop (myStack , &c) && c != '{') {printf ("左右括号配对次序不正确! \n");return;} else if(((exp[i] == ')') || (exp[i] == ']') || (exp[i] == '}')) && ! StackNotEmpty (myStack )) { printf ("右括号多于左括号! \n"); return;} } 5 if( StackNotEmpty (myStack )) printf ("左括号多于右括号! \n"); else printf ("左右括号匹配正确! \n"); } 6 队列队列一、队列的基本概念一、队列的基本概念 1、队列定义 1、队列定义 3、存储结构 3、存储结构 4、运算规则 4、运算规则 5、实现方式 5、实现方式 2、逻辑结构 2、逻辑结构只能在表的一端进行插入操作,在表的另一端进行删除操作的线性表。队尾插入队头删除与线性表相同,仍为一对一关系。顺序队列或链队列,以循环顺序队列更常见。只能在队首和队尾运算,且访问结点时依照先进先出( FIFO )的原则。关键是掌握入队和出队操作,具体实现依顺序队或链队的不同而不同。基本操作:入队或出队,建空队列,判队空或队满等操作。 7 队列( Queue )是仅在表尾进行插入操作,在表头进行删除操作的线性表。它是一种先进先出(FIFO) 的线性表。例如:队列 Q= (a 1 , a 2 , a 3 , ……….,a n-1 , a n) 在队尾插入元素称为入队入队;在队首删除元素称为出队出队。当队列中没有数据元素时称为空队列。队首队尾 8 注:队列的实现方式是本节重点, 注:队列的实现方式是本节重点, 关键是掌握入队和出队操作。具体实现依存储结构(链队列或顺序队列)的不同而不同。 (模拟事件发生的先后顺序, 例如 CPU 芯片中的指令译码队列) ; (一个 CPU 执行多个作业) ; 3. 简化程序设计。答: 问:为什么要设计队列?它有什么独特用途? 9 二、队列抽象数据类型数据集合: {a 0,a 1,…,a i,…,a n-1}a i的数据类型为 D