资源描述
单击此处编辑母版文本样式,第二级,第三级,第四级,Page,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,单击此处编辑母版标题样式,第,3,章 栈和队列,数据结构案例教程,Page,2,案例提出,迷宫问题,迷宫问题是取自心理学的一个经典实验。在该实验中,把一只老鼠从一个无顶大盒子的门中放入,在盒子中设置了许多墙,对行进方向形成了多处阻挡。盒子仅有一个出口,在出口处放置以块奶酪,吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验,一直到老鼠从入口走到出口,而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。,设计一个计算机程序对任意设定的矩形迷宫如下图所示,求出一条从入口到出口的通路,或得出没有通路的结论。,Page,3,3.2,知识点学习,3.2.1,栈,栈是一种特殊的线性表,用途十分广泛。将递归算法转换成非递归算法时常常会用到栈,实现二叉树的算法中也会使用栈。,栈是一种只能在一端进行插入或删除的线性表。表中允许进行插入、删除操作的一端称为栈顶(,top,),表的另一端称为栈底(,bottom,)。当栈中没有数据元素时,称为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。,Page,4,入栈,Page,6,3.2.1.3 栈的链式存储结构及其基本运算的实现,Page,7,(链栈中数据结点的类型,LinkStack,定义如下:,typedef int ElemType;,typedef struct linknode,ElemType data;/,数据域,struct linknode*next;/,指针域,LinkStack;,Page,8,前缀转后缀算法演示,Page,10,后缀转前缀算法演示,Page,11,栈解决迷宫问题算法演示,Page,13,3.2.2.2 队列的顺序存储结构及其基本运算的实现,顺序队列类型,SqQueue,定义如下:,#define MaxSize 100,typedef int ElemType;,typedef struct,ElemType elemMaxSize;,int front,rear;/,队首和队尾指针,SqQueue;,Page,15,队列操作,Page,16,循环队列满和空指针判断冲突,Page,18,3.2.2.3 队列的链式存储结构及其基本运算的实现,队列的链式存储结构是仅在表头删除和表尾插入的单链表,因此一个栈队列需要使用两个指针:指向队头元素的队首指针,front,和指向队尾元素的队尾指针,rear,。用于存储队列的单链表简称链队。如图,3.11,所示的链队列。,Page,19,链队中数据结点的类型,QNode,定义,typedef int ElemType;,typedef struct qnode,ElemType data;,struct qnode*next;,QNode;/,链队数据结点类型定义,Page,20,一个链队的动态变化过程,Page,21,3.2.2.4,队列的应用举例,求解报数问题,设有,n,个人站成一排,从左向右的编号分别为,1,n,,现在从左往右报数“,1,,,2,,,1,,,2,”,数到“,1,”的人出列,数到“,2,”的立即站到队伍的最右端。报数过程反复进行,直到,n,个人都出列为止。要求给出他们的出列顺序。,Page,22,3.3.2,用队列来解决迷宫问题,【算法思路】,用队列解决迷宫问题,本质上是一个广度优先算法(在教材的树和图章节中将学到)。这里不能用循环队列,只能用普通的顺序队列。原因是在找到出口后,程序要根据队列中保存的数据,通过回溯寻找迷宫的路径。而循环队列中的数据在出队和入队操作时被覆盖的。普通队列不会将出队元素真正从队列中删除,因为要利用它输出路径。,Page,24,谢谢观赏,谢谢观赏,
展开阅读全文