第3章栈和队列.ppt

1、第三章学习栈内存和队列，本章主要学习栈内存的概念、内存结构及其基本操作队列的概念、内存结构及其基本操作栈内存和队列的应用实例，本章学习栈内存的基本概念、内存结构和栈内存、栈内存输出等基本操作。 掌握：在处理实际问题中如何利用栈内存的特点来解决问题。 理解：栈内存在递归实现中发挥作用。 了解：基本队列概念、基本存储操作和入队、出队操作等。 了解队列在迷宫问题解决中的作用，以及如何使用队列解决实际问题。栈内存和队列是两种特殊的线性表，限制了操作受限的线性表3.1栈内存(stack) 3.2栈内存的应用3.3队列3.4队列应用，3.1.1栈内存的定义：只在表末进行插入或删除操作的线性表，表末栈内存，

2、标头堆栈底部(b 例1 :在家吃饭的碗通常洗干净后一个接一个放在一起。 使用时，只要一个接一个地拿去，一定要先拿去最上面的碗，最后取出最下面的碗。 例2 :在建筑工地中，使用的砖从下往上摞起来，使用时从最上面往上取出。 栈内存结构的基本操作： (1)初始化栈内存；(2)栈内存推式(s，data )；以及(3)栈内存(4)取得栈内存掌门人要素内容geet，栈内存掌门人指针top指示实际的栈内存掌门人位置，初始值为-1，栈内存、栈内存满、排列维数为M top=-1，堆栈为空，此时若发出堆栈，则下溢(underflow) top=M-1 SeqStack、*PSeqStack；运算实现、(1)初始化

3、空栈内存(2)判定栈内存空(3)输入栈内存(4)输出栈内存(5)读取栈内存掌门人要素、x、S-datas-top、结论：通过栈内存的插入和删除操作按顺序点击。 如果栈内存中元素的数量变化范围很大，或者不知道栈内存元素的数量，请考虑使用链存储结构。 以链存储结构表示的栈内存称为“链栈内存”。 链栈内存通常由无头节点的单网络链接表表示。 栈内存的插入删除操作只能在一端进行，但在单网络链接表中，由于在开头插入删除节点比末尾相对容易，所以将单网络链接表的开头作为栈内存的开头，即以单网络链接表的开头指针作为栈内存的开头指针。 2 .在链栈内存、图3-3中，在栈内存的链存储结构中，习语言节点结构为类型结构

4、节点数据类型数据； 结构节点*下一个； 堆栈节点，*堆栈节点； 类型结构堆栈节点顶部； 链接堆栈、*链接堆栈； 链路堆栈； 喀呖声s=(链接堆栈) malloc (sizeof (链接堆栈) )，链接栈内存中每个基本操作的算法如下所示。1 .初始化栈内存splinkstackinit _ link stack (void )/*初始化链栈内存、入口残奥仪表：空、门值：链栈内存指针、空为初始化失败*/PLinkStack S； 链接堆栈大小(链接堆栈):if (s )顶部=空。 返回(s )； intlinkstackpush _ link stack (链接堆栈，元素类型x )/*栈内存，门户

5、站残奥表：链栈内存指针，栈内存元素空，门值： 1栈内存成功，0失败p=(堆栈节点) malloc (sizeof p) printf (“内存溢出流”)； 返回(0)； p数据=x； 下一个=上一个。 s顶点=p； 返回(1)； 2 .输入栈内存、int Pop_LinkStack (PLinkStack S、DataType *x) /*输出栈内存、门值： 1表示输出栈内存成功、0表示失败、*x表示删除的要素值。 if (empty _ link stack (s ) )打印机(栈内存为空，无法从栈内存中输出)； 返回(0)； * x=s顶部数据； p=s顶点； 上下一个。上下一个。 自由(

6、p )； 返回(1)； 3 .栈内存输出，4 .获取栈内存元素内容获取int gettop _ link stack (plink stacks，DataType *x) /*栈内存元素获取入口残奥仪表：链栈内存指针，栈内存元素存储空间return (0)； * x=s顶部数据； 返回(1)； 5 .判断栈内存s是否为空intempty _ link stack (plink stacks )/*判断链栈内存是否为空，入口残奥仪表：链栈内存指针，门值： 1为栈内存空，0为栈内存非空*/return，3.2栈内存的应用例，例3-1数字算法思想： while(N0 )将N%r结果纳入栈内存。 N=

7、N/r； 提出while (栈内存非空)栈内存，输出原始栈内存的最上面的要素，例如3-2利用栈内存实现迷宫的求解： 1、问题说明：心理学家将一只老鼠从没有掌门人罩的大箱子的入口逼入迷宫。 迷宫中设置了很多墙壁，在前进方向上形成了多个障碍，心理学家将奶酪放在迷宫的唯一出口，在迷宫中找通道来吸引老鼠到达出口。 2、算法基本思想描述：利用回溯算法，从入口，向某个方向不断地试行，通过则达到新的一点，否则再试行一个从未试行过的方向。 如果所有方向都没有通道，就沿着原路向前一点走，改变另一条未试验的通道继续试验，直到找到出口，或者所有通道都继续试验，一条通道没有找到出口。 在启发式文明棍过程中，到达的每一

8、点的位置和启发式文明棍方向必须存储在一个栈内存中，以确保到达某一点时正确转向前一点。 数据结构的设定修正(1)迷宫的显示迷宫设为m行n列，由二次元数组mazemn表示一个迷宫，其中(1，1 )是入口，(m，n )是出口，mazemn，入口，出口，迷宫定义# define m6# define n8int maze 从某一点开始研究时，之间的点是8个方向，四个角的点是3个方向，其他边的点是5个方向，为了简化问题，在迷宫的周围添加了(2)探索文明棍方向的表示上述迷宫时，可以对每个点探索文明棍8个方向，将当前点的坐标设为(x，y )，并与其邻接为了便于求出新点的坐标，在一个结构阵列move8中放入从

9、正东开始按时修正前进的这些个8方向的坐标增量。 其中，x表示横轴的增量，y表示纵轴的增量。 (x，y 1)、(x，y-1 )、(x-1，y )、(x 1，y )、(x 1，y 1)、(x-1，y 1项目； 项目移动8=0、1、1、1、1、0、1、1、0、-1、-1、-1、- 0、-1、1。 (3)栈内存的表示，必须从前面的点的下一个方向开始探索，到达了某个地方的话哪儿也去不了。 因此，按压栈内存中不仅有依次到达的各点的坐标，也有从前一点到达本点的方向编号。栈内存表示# define maxsize 20类型defstructintx、y和d。 数据类型； typedefstructdataty

10、pedatamaxsize； 在顶部； SeqStack； (2)算法的设定校正；(1)防止重复到达某一点的想法为了避免死循环的发生，当到达某一点(I，j )时，使mazeij为-1，从而区别未到达的顶点。 可以在算法结束前恢复原来的迷宫。 (2)将算法描述栈内存初始化入口点坐标和初始启发式文明棍方向(设定为-1)放入栈内存，设定通过入口点将found设定为0 (找不到出口点)， 找不到从while点开始的下一个方向修正if (找到了方向)栈内存的最上面的元素的方向的值修正新的点，设定通过。将新的点位置和初始视图文明棍方位值放入栈内存if (新的点是终点) found=1 else /if (

11、找到)打印路径else表示无法找到可行走的方向，从该点开始无法行走，“在该迷宫中没有路径”、-1、-1、-1、-1、-1、-1一般来说，命令可以是常数，也可以是变量或常数。 按运算对象的个数划分运算符，有单目运算符、双目运算符、三目运算符的运算类型有算术运算、关系运算运算、逻辑运算。 边界符号包括左括号和右括号以及表达式的终止符。 运算符、边界符号统称为运算符。 为简单起见，本文讨论了仅包括双目标运算符的加法、减法、乘法、除法运算式，其中该命令是用单个二进制位字符表示的整数。 做评估公式时，公式中有(1)后缀表示： (3)前缀表示： (2)后缀表示：通常使用的公式都是中后缀表示。 例： 1 2

12、*(8-5)- 4/2，图3-7中缀，后缀表达式修正计算顺序，例3-3表达式评价，(1)中缀表达式评价：对象栈内存和运算符栈内存，例修正计算2(4-3)具体而言，只使用一个命令栈内存，从左向右扫描表达式，则为一个歌舞剧每当找到一个运算符时，从栈内存中取出两个命令进行当前的修正运算，并重新栈内存结果，直到整个栈内存结束。 算法的说明：读取公式的1个字符while (找不到终端查询密码) if (运算对象)被按入栈内存如果else/运算符从栈内存飞出两个，则将运算结果按入栈内存读取下一个字符的输出栈内存的最高位值，例修正运算2 (4-3)*6、 后缀表达式： 243-6*，(3)，中缀表达式转换为

13、后缀表达式，以满足表达式语法规则的字符串存储，转换过程初始化运算符栈内存，从左向右扫描表达式，如果扫描的是操作的运算符栈内存的最上面的运算符的优先级低于该运算符，则进入栈内存，继续后处理如果算子栈内存最上方的算子的优先级与该算子相等，则用括弧从算子栈内存中提取栈内存，继续进行后处理，直到最后算子的评价结束。 表达式“1 2*(8-5)- 4/2#”的评价过程如图3-8所示。 一般为了简单起见，首先在栈内存中加入终止符#，上述操作的算法步骤： (1)初始化运算符栈内存，将终止符#加入运算符栈内存，(2)判断读取表达式字符的(3)栈内存是否为空，如果为空则结束，否则进入(4)否则将运算符栈内存的掌

14、门人元素与其运算符进行比较，如果大于，则从运算符栈内存中提取栈内存运算符输出，小于(3)时，运算符进入运算符栈内存，如果读取下一个字符旋转(3)，则从运算符栈内存中提取栈内存，读取下一个字符，转(3)。算法说明：读取表达式字符while (找不到结束符) if (当前字符为命令)将该字符放入对象栈内存扫描下一个字符else/当前字符是运算符switch (当前运算符) case左括号：的栈内存扫描下一个字符case右括号：if (栈内存掌门人为左括号)栈内存输出。break，扫描下一个字符； else执行默认语句。 default: if (当前字符优先级=运算栈内存的最高优先级)是从运算栈内存弹出运算符从对象栈内存弹出两个对象进行修正计算， 将结果放入对象栈内存else将当前运算符放入运算符栈内存扫描下一个字符/switch结束/while结束输出对象栈内存的栈内存掌门人值，3.31递归定义递归是计程仪编程中最常见的设置纠正方法之一。 递归定义：如果对象部分包含自个儿或在自个儿中定义，则该对象被称为递归，或者如果对象被定义为在一个进程中直