云大数据结构课程教学课件栈和队列.ppt

* * * * * * * * * * * * * 第一节 栈 * b c 假设栈S=(a,b,c,d) 称a栈底元素,d为栈顶元素. 栈中元素按a,b,c,d的次序进栈, 退栈的元素应为栈顶元素。 栈 a 栈是限定存取只能在表的同一端执行的 线性表。其逻辑特点是LIFO。 基本操作 page45。 栈顶 栈底 * 顺序栈 顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 顺序栈的基本操作 Page 47. 第二节 栈的应用举例 * 数制转换 N=(N div d)*d + N mod d 其中:div为整除运算,mod为求余运算 例如(1348)10=(2504)8 N N div 8 N %8 1348 168 4 168 21 0 21 2 5 2 0 2 5 0 2 4 top * 括号匹配的检验 ( [ ] ( ) ) 或 [ ( [ ] [ ] ) ] 正确 [ ( ]或( [ ( ) )或 ( ( ) ] 不正确 对“左括弧”来说，后出现的比先出现的“优先”等待检验； 对“右括弧”来说，每个出现的右括弧要去找在它之前“最后”出现的那个左括弧去匹配。 显然，必须将先后出现的左括弧依次保存，为了反映这个优先程度，保存左括弧的结构用栈最合适。这样对出现的右括弧来说，只要栈顶元素相匹配即可。如果在栈顶的那个左括弧正好和它匹配，就可将它从栈顶删除。 * 括号错误可描述为：　　1．来的右括弧并非是所“期待”的；　　2．来的是“不速之客”，不该来的来了；　　3．直到结束，也没有到来所“期待”匹配的括弧。 这三种情况对应到栈的操作即为：　　1．和栈顶的左括弧不相匹配；　　2．栈中并没有左括弧等在那里；　　3．栈中还有左括弧没有等到和它相匹配的右括弧。 括号匹配的检验 * 括号匹配的检验 例:[ ( [ ] [ ] ) ] 读入1:[ 读入2:( 读入3:[ 读入4:] 读入5:[ 读入6:] 读入7:) 读入8:] 设置空栈s 左括号,压入栈 左括号,压入栈 左括号,压入栈 右括号,与栈顶元素消解 左括号,压入栈 右括号,与栈顶元素消解 右括号,与栈顶元素消解 右括号,与栈顶元素消解 只能与相应的左括号消解 否则不合法 在算法的开始和 结束,栈都应为空 ( [ [ * 迷宫求解 穷举求解：从入口出发，顺某一方向向前探索，若能走通，则继续往前走，否则沿原路退回，换一个方向在继续探索，直到所有可能的通路都探索到为止。 为了保证在任何位置能沿原路退回，需要用一个后进先出的结构来保存从入口到当前位置的路径。 * 迷宫求解 迷宫求解的基本思想是： 若当前位置可通，则纳入当前路径，并继续朝下一位置探索，即切换下一位置为当前位置，重复直至到达出口。 若当前位置不可通，则应顺着来向退回到前一通道块，然后朝着除来向之外的其它方向继续探索。 若该通道块的四周的4个方块均不可通，则应从当前路径上删除该通道块。 求得的路径上不能重复出现同一通道块。 迷宫求解 0 1 2 3 4 5 6 7 8 9 1 入 2 3 4 5 6 7 8 出 9 11 21 31 41 51 61 71 63 53 52 64 65 75 85 84 83 82 86 87 88 南－西－北－东 * 表达式求值 ? 第四节 队 列 * 队列 1 2 3 4 5 6 允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。 队列是一种先进先出（FIFO）的线性表 只允许表的一端进行插入，而在另一端删除元素 队尾 队头 * 链队列 Q.front Q.rear ^ Q.front Q.rear Q.front Q.rear Q.front Q.rear * 初始化建空队列时，令 front=rear=0，每当插入一个新的队尾元素后，尾指针 rear增1；每当删除一个队头元素之后，头指针 front增1。因此，在非空队列中，头指针始终指向队头元素，而尾指针指向队尾元素的“下一个”位置。 顺序队列到一定的时候将不能再插入新的元素,但它的空间并未占满,将顺序队列创造为一个环状的空间，成为循环队列. 队列的顺序表示和实现 F G * 循环队列 * 循环队列 a1 a2 a3 a4 a5 a6 a7 a8 队 列 满 * 判断循环队列空与满: 1:另设一个标志位以区分队列是空还是满. 2:少用一个空间, 约定以‘队列头指针在队列尾指针的下一位置上’作为队列呈满的标志。 循环队列 * 循环队列 判空： Q.front = Q.rear 判队列满： (Q.rear+1) %MAXSIZE == Q.front 队列的长度 Q.rear –