数据结构与算法——链表与栈概要.ppt

Status InitQueue (SqQueue Q) { // 构造一个空队列Q Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType)); if (!Q.base) exit (OVERFLOW); // 存储分配失败 Q.front = Q.rear = 0; return OK; } 3.4.3 循环队列 队列初始化算法 Status EnQueue (SqQueue Q, ElemType e) { // 插入元素e为Q的新的队尾元素 if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; //队列满 Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; } 3.4.3 循环队列 入队列算法 Status DeQueue (SqQueue Q, ElemType e) { // 若队列不空，则删除Q的队头元素， // 用e返回其值，并返回OK; 否则返回ERROR if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front+1) % MAXQSIZE; return OK; } 3.4.3 循环队列 出队列算法 分析以下两种状态如何求队列长度 3.4.3 循环队列 0 1 2 3 4 C D Sq.front Sq.rear 0 1 2 3 4 C D Sq.front Sq.rear int QueueLength(SqQueue Q) { return (Q.rear-Q.front+MaxSize)%MaxSize; } 3.4.3 循环队列 求队列长度算法 本章小结 熟练掌握： (1)栈、队列的定义、特点和性质； (2)ADT栈、ADT队列的设计和实现以及基本操作及 相关算法。 重点学习： ADT栈和队列在表达式求值、括号匹配、数制转换、迷宫求解中的应用，提高利用栈和队列解决实际问题的应用水平。 栈和队列是两种重要的线性结构。从数据结构角度，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表。从数据类型角度，它们是和线性表大不相同的两类重要的抽象数据类型。 * 3.2.4 迷宫求解 求解方法 “穷举求解”方法：从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。 为了保证在任何位置上都能沿原路退回，需要一个后进先出的结构来保存从入口到当前位置的路径。因此，求解迷宫通路算法需要应用“栈”来保存当前路径。 3.2.4 迷宫求解 四周墙壁解决办法如图 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 当前位置：在有哪些信誉好的足球投注网站过程中某一时刻所在图中某个方块位置。 当前位置可通：未承走到过的通道块，该方块既不在当前路径上，也不是曾经纳入过路径的通道块。 3.2.4 迷宫求解 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 下一位置：当前位置四周4个方向(东、南、西、北)上相邻的方块。 当前位置 (3,3) (3,2) (2,2) (1,2) (1,1) 当前路径 3.2.4 迷宫求解 算法思想 (1)若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口； (2)若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除了“来向”之外的其他方向继续探索； (3)若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。 设定当前位置的初值为入口位置； do｛ 若当前位置可通， 则｛将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为