cha003.pptVIP

3.1栈的类型定义 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈 特点：先进后出（FILO）或后进先出（LIFO） 顺序栈S 如何从后缀式求值？ 先找运算符， 再找操作数 队列的顺序存储结构 实现：用一组连续的存储单元依次存放从对头到对尾的元素 递归调用执行情况如下： 主程序 (1) print(w) w=3; 3 print(2); （1）w=3 top (2) 输出：3, 3, 3 w 2 print(1); （2）w=2 （1）w=3 top (3) 输出：2, 2 w 1 print(0); （3）w=1 （2）w=2 （1）w=3 top (4)输出：1 w 0 （4）w=0 （3）w=1 （2）w=2 （1）w=3 top w (3) 输出：2, 2 (2) 2 (1) 3 top (4)输出：1 (3) 1 (2) 2 (1) 3 top (2) 输出：3, 3, 3 (1 ) 3 top 返回 (3) 1 (2) 2 (1) 3 top (4) 0 结束 (1) 队列的定义及特点 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)——允许插入的一端 队头(front)——允许删除的一端 队列特点：先进先出(FIFO) a1 a2 a3…………………….an 入队 出队 front rear 队列Q=(a1,a2,……,an) 3.4 队列 a1 a2 a3…………………….an 端1 端2 入队 出队 入队 出队 双端队列 ADT Queue { 数据对象： D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0} 数据关系： R1＝{ a i-1,ai | ai-1, ai ∈D, i=2,...,n} 约定其中a1 端为队列头， an 端为队列尾 基本操作： 队列的类型定义 } ADT Queue 队列的基本操作： InitQueue(Q) DestroyQueue(Q) QueueEmpty(Q) QueueLength(Q) GetHead(Q, e) ClearQueue(Q) DeQueue(Q, e) EnQueue(Q, e) QueueTravers(Q, visit()) InitQueue(Q) 操作结果：构造一个空队列Q。DestroyQueue(Q)初始条件：队列Q已存在。 操作结果：队列Q被销毁， 不再存在。 QueueEmpty(Q)初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。 QueueLength(Q) 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。 GetHead(Q, e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头元素。 a1 a2 an … … ClearQueue(Q)初始条件：队列Q已存在。 操作结果：将Q清为空队列。 EnQueue(Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。 a1 a2 an e … … while (ch != EOF ch != \n) { switch (ch) { case # : Pop(S, c); break; case @: ClearStack(S); break;// 重置S为空栈 default : Push(S, ch); break; } ch = getchar(); // 从终端接收下一个字符 } ClearStack(S); // 重置S为空栈 if (ch != EOF) ch = getchar(); while (ch != EOF) { //EOF为全文结束符 将从栈底到栈顶的字符传送至调用过程的 数据区； 例四、 迷宫求解 通常用的是“穷举求解”的方法 求迷宫路径算法的基本思想是： 若当前位置“可通”，则纳入路径，继续前进; 若当前位置“不可通”，则后退，换方向继续探索; 若四周“均无通路”，则将当前位置从路径中删除出去。 设定当前位置的初值为入口位置； do