《栈和队列》PPT课件.ppt

3.1 栈 第3章 栈和队列,栈(Stack)是限定仅在表的一端（一般指表尾）进行插入和删除操作的线性表。 允许插入、删除的这一端称为栈顶(Top)，另一端称为栈底(Bottom)。栈的插入操作通常称为入栈或进栈(push)，而栈的删除操作则称为出栈或退栈(pop)。,3.1 栈 数据结构 第3章 栈和队列,假设栈S=(a0，a1，a2，an-1)，则a0称为栈底元素，an-1称为栈顶元素。栈中元素按a0，a1，a2，an-1的次序入栈，出栈的第一个元素应为栈顶元素an-1。也就是说，栈的操作是按后进先出的原则进行的。因此，栈又称为后进先出（Last In First Out）的线性表（简称LIFO表）。,栈底,栈顶,3.1 栈 数据结构 第3章 栈和队列,栈的基本运算如下： InitStack(s) ：栈初始化。 初始条件：栈s不存在 操作结果：构造了一个空栈。 StackEmpty (s) ：判栈空。 初始条件：栈s已存在 操作结果：若s为空栈则返回1，否则返回0。 Push (s，e) ：入栈。 初始条件：栈s已存在 操作结果：在栈s的顶部插入一个新元素e， e成为新的栈顶元素。栈发生变化。,3.1 栈 数据结构 第3章 栈和队列, Pop (s，e) ：出栈。 初始条件：栈s存在且非空 操作结果：将栈s的栈顶元素从栈中删除，并用e返回其值。栈发生变化。 GetTop (s，e) ：读栈顶元素。 初始条件：栈s存在且非空 操作结果：读栈顶元素并用e返回其值。栈不变化。,栈是一种特殊的线性表，因此栈也可采用两种存储结构： 顺序存储结构 链式存储结构,3.2 栈的存储结构及其基本运算的实现 数据结构 第3章 栈和队列,1. 顺序栈 （1）顺序栈的存储结构 顺序栈是指采用顺序存储结构存储的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针（下标）top，指示栈顶元素的当前位置。 对于用C语言描述的顺序栈通常用top=-1表示空栈；入栈时，栈顶指针top增1；出栈时，栈顶指针top减1。,3.2 栈的存储结构及其基本运算的实现 数据结构 第3章 栈和队列,3.2 栈的存储结构及其基本运算的实现 数据结构 第3章 栈和队列,top,top,top,top,顺序栈的类型定义如下： #define MAXSIZE 100 typedef int ElemType; typedef struct stack ElemType elemMAXSIZE; /存栈顺序表 int top; /栈顶下标 SQSTACK;,3.2 栈的存储结构及其基本运算的实现 数据结构 第3章 栈和队列,（2）顺序栈的基本操作 栈的初始化（即构造一个空栈） void InitStack(SQSTACK *ps) ps-top=-1; 判栈空 int StackEmpty (SQSTACK s) if (s.top=-1) return 1; else return 0; ,3.2 栈的存储结构及其基本运算的实现 数据结构 第3章 栈和队列, 入栈 int Push(SQSTACK *ps, ElemType e) if (ps-top=MAXSIZE-1) /判栈满 cout top+; ps-elemps-top=e; return 0; ,3.2 栈的存储结构及其基本运算的实现 数据结构 第3章 栈和队列,出栈 int Pop(SQSTACK *ps, ElemType *pe) if (ps-top=-1) /判栈空 cout elemps-top; ps-top-; return 0; ,3.2 栈的存储结构及其基本运算的实现 数据结构 第3章 栈和队列,读取栈顶元素 int GetTop(SQSTACK s, ElemType *pe) if (s.top=-1) /判栈空 printf (“Stack is emptyn“); return 1; *pe=s.elems.top; return 0; ,3.2 栈的存储结构及其基本运算的实现 数据结构 第3章 栈和队列,2. 链栈 （1）链栈的存储结构 链栈是指采用链式存储结构存储的栈。 链栈是一种特殊的单链表，即限定仅在表头进行插入和删除操作的单链表，因此链栈的结点结构与单链表的结点结构相同。,3.2 栈的存储结构及其基本运算的实现 数据结构 第3章 栈和队列,top,data next,栈顶,栈底,（1）链栈中指针的方向是从栈顶指向栈底（区别于顺序栈，顺序栈是将表尾作为栈顶）。 （2）链栈中没必要附加一个表头结点（因为在表头进行插入、删除操作，带头结点和不带头结点都是一样的）。,3.2 栈的存储结构及其基本运算的实现 数据结构 第3章 栈和队列,3.2 栈的存储结构及其基本运算的实现 数据结构 第3章 栈和队列,链栈的类型定义如下： typedef struct snode ElemType data; struct node *next; SNODE; SNODE top;,（2）链栈的基本操作 入栈 链栈的入栈操作，相当于在单链表的第一个结点之前进行插入操作。由于是链式存储，不需要像顺序存储那样需要判断栈是否为满。 void push (SNODE *pps, ElemType e) SNODE *p; p=new SNODE; p-data=e; p-next=*pps; *pps=p; ,3.2 栈的存储结构及其基本运算的实现 数据结构 第3章 栈和队列, 出栈 链栈的出栈操作相当于在单链表中删除第一个结点。 int pop (SNODE *pps, ElemType *pe) SNODE *p; if (*pps=NULL) /出栈前仍需判栈空 cout data; p = *pps; *pps=p-next; delete p; return 0; ,3.2 栈的存储结构及其基本运算的实现 数据结构 第3章 栈和队列,由于栈具有“后进先出”的特点，在程序设计中，尤其在系统软件的设计中，栈是应用最多的一种数据结构。输入输出中数制的转换，编译过程中常量表达式的计算，嵌套调用中返回地址和调用参数的传递以及各种递归函数的实现，都离不开栈。,3.3 栈的应用 数据结构 第3章 栈和队列,数制转换 将十进制数 N 转换为 r 进制数，其转换方法利用辗转相除法。 以N=1348，r=8为例，转换过程如下： N N / 8 （整除） N % 8（求余） 1348 168 4 低 168 21 0 21 2 5 2 0 2 高 结果为：（1348）10 =（2504）8,3.3 栈的应用 数据结构 第3章 栈和队列,void conversion(int N, int r) SQSTACK *ps; int x; InitStack(ps); /构造空栈 while(N) Push(ps, N%r); /余数入栈 N=N/r; /商作为被除数继续运算 while(!StackEmpty(*ps) Pop(ps, ,3.3 栈的应用 数据结构 第3章 栈和队列,3.3 栈的应用 数据结构 第3章 栈和队列,2. 迷宫求解,求迷宫中从入口到出口的所有路径，所求路径必须是简单路径，即某一位置不能重复走两遍。 求解思想：使用回溯法，即从入口出发，按某一方向向前探索，若能走通（未走过的），则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。 在求解过程中，为了保证无路可行时，能沿原路返回前一点以便继续下一个方向向前试探，则需要用一个栈来保存所能够到达的每一点的坐标及从该点前进的方向。,3.3 栈的应用 数据结构 第3章 栈和队列,需要解决的四个问题： （1）表示迷宫的数据结构 设迷宫为m行n列，利用mazem+2n+2 来表示一个带围墙的迷宫。mazeij=0或1，其中0表示通道，1表示墙（不通）。迷宫四周为围墙，因此值全部为1。迷宫可定义如下： #define M 6 /迷宫的实际行 #define N 8 /迷宫的实际列 int maze M+2N+2 ;,3.3 栈的应用 数据结构 第3章 栈和队列,（2）试探方向 对于迷宫的每个点，有8个方向可以试探。,3.3 栈的应用 数据结构 第3章 栈和队列,(x，y),(x，y+1),(x，y-1),(x+1，y),(x-1，y),(x-1，y+1),(x-1，y-1),(x+1，y-1),(x+1，y+1),3.3 栈的应用 数据结构 第3章 栈和队列,从正东开始沿顺时针进行的这8个方向的坐标增量，放在一个结构体数组move 8 中，在move 数组中，每个元素由两个域组成，x：横坐标增量，y：纵坐标增量。move数组为 ： typedef struct int x, y ; item ; item move8 ;,（3）栈的设计 当到达了某点而无路可走时，需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向序号。栈中元素是一个由行、列、方向组成的三元组，栈中元素的类型定义如下： #define MAXSIZE 100 typedef struct int x , y , d ; ElemType ; typedef struct stack ElemType elemMAXSIZE; /存栈顺序表 int top; /栈顶下标 SQSTACK; SQSTACK s ; /栈的定义,3.3 栈的应用 数据结构 第3章 栈和队列,（4）标志已走过的坐标 为防止重复到达某点，以避免发生死循环，一种方法是另外设置一个标志数组markmn，它的所有元素都初始化为0，一旦到达了某一点 ( i , j )后，使markij 置1，下次再试探这个位置时就不能再走了；另一种方法是当到达某点（i , j）后，使mazeij 置 1，以便区别未到达过的点，同样也能起到防止走重复点的目的。 这里使用后一种方法。,3.3 栈的应用 数据结构 第3章 栈和队列,int mazepath (int mazeM+2N+2, item move8) SQSTACK s; ElemType temp; int x,y,d,i,j; InitStack(,3.3 栈的应用 数据结构 第3章 栈和队列,if (mazeij=0) temp.x=x; temp.y=y; temp.d=d; /坐标及方向 Push ( /迷宫无路,3.3 栈的应用 数据结构 第3章 栈和队列,void printpath (SQSTACK s) ElemType temp; printf (“(%d,%d)-“, M, N); while (!StackEmpty(s) Pop ( ,3.3 栈的应用 数据结构 第3章 栈和队列,3 . 表达式求值 (1)表达式的表示方法 在计算机中，表达式可以有三种不同的表示方法。 设exp（表达式）=S1（第一操作数） OP（运算符） S2（第二操作数），则称 OP S1 S2为表达式的前缀表示法 S1 OP S2为表达式的中缀表示法； S1 S2 OP为表达式的后缀表示法。 例 已知中缀表达式=5+（4-3）*2 则前缀表达式（波兰式）为： +5*-432 后缀表达式（逆波兰式）为：543-2*+,3.3 栈的应用 数据结构 第3章 栈和队列,说明： （1）中缀式的运算规则：先乘除，后加减；从左算到右；先括号内，后括号外。 （2）前缀式的运算规则：从右至左按运算符出现的顺序作运算，且取紧靠运算符之后的两个相邻的数作运算。 （3）后缀式的运算规则：从左至右按运算符出现的顺序作运算，且取紧靠运算符之前的两个相邻的数作运算。,3.3 栈的应用 数据结构 第3章 栈和队列,结论： （1）在三种表示法中，操作数的相对次序不变。 （2）中缀式中须有括号，而前、后缀式不需括号。 （3）后缀式运算符出现的顺序与表达式的运算顺序相同。,3.3 栈的应用 数据结构 第3章 栈和队列,（2）算术表达式求值 介绍直接对中缀式求值的算法，至于先将中缀式转换成后缀式，再对后缀式求值的方法可阅读参考书。 运算符和界限符统称为算符。根据算术四则运算的规则（即中缀式的运算规则），任两个相继出现的算符1和2之间的优先关系至多是下面三种关系之一： 1 2 1的优先权高于2,3.3 栈的应用 数据结构 第3章 栈和队列,算符间的优先关系,3.3 栈的应用 数据结构 第3章 栈和队列,2,1,算法需两个栈。一个是运算符栈(OPTR) ；另一个是操作数或运算结果栈(OPND) 。算法的基本思想是： （1）首先置操作数栈为空栈；为了使表达式中第一个运算符能够进栈，首先将一个优先权最低的运算符#压入运算符栈中成为其栈底。 （2）从左向右依次读出表达式中的每一个字符， 若为操作数，则将其压入操作数栈中，接着读出下一个字符； 若为运算符，则和运算符栈的栈顶运算符比较优先权： 如果读出的运算符的优先权高于运算符栈栈顶运算符的优先权，则将其压入运算符栈中，接着读出下一个字符； 如果读出的运算符的优先权等于运算符栈栈顶运算符的优先权（即左右括号相遇），则从运算符栈中退出一个运算符（即左括号）； 如果读出的运算符的优先权低于运算符栈栈顶运算符的优先权，则从操作数栈连续退出两个操作数（先退出的是第二操作数，后退出的是第一操作数），从运算符栈中退出一个运算符，然后作相应的运算，并将运算结果压入操作数栈中。,3.3 栈的应用 数据结构 第3章 栈和队列,算法中还调用了两个函数。其中 Precede( )的功能是判断两个运算符1和2的优先关系； Operate( )的功能是求两数a和b作运算的结果。,3.3 栈的应用 数据结构 第3章 栈和队列,int Evaluation(char exp20) SQSTACK optr, opnd; char a,b,x,top,ch,result; int i; InitStack ( else,3.3 栈的应用 数据结构 第3章 栈和队列,switch (Precede(top,ch) case : Pop( ,3.3 栈的应用 数据结构 第3章 栈和队列,4. 栈与递归的实现 栈的一个重要应用是在程序设计语言中实现递归。 一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。,3.3 栈的应用 数据结构 第3章 栈和队列,复习递归,一、定义 若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；而且若一个过程直接地或简捷地调用自己，则称这个过程是递归的过程。,复习递归,二、递归方法 . 定义是递归的 （）阶乘 n! 当n=0时，n!=1； 当n0时，n!=n(n-1)! long factorial ( long n) if (n=0) return (1); else return n*factorial(n-1); ,. 定义是递归的,斐波那契数列 当n=0或1时，fib(n)=n; 当n1时， fib(n)=fib(n-1)+fib(n-2) long fib (long n) if(n=1) return (n); else return fib(n-1)+fib(n-2); ,. 定义是递归的,三点认识 对于一个较为复杂的问题，有时可分解为相对简单且解法相同或类似的子问题。如！ 当分解后的子问题可直接解决，就停止分解。可直接求解的问题，叫做递归结束条件。 递归定义的函数可简单用递归过程来编程求解。,复习递归（二、递归方法）,. 数据结构是递归的 链表结构定义是递归的 struct node int data; struct node *link; *head, *p;,. 数据结构是递归的,例 在一个非空链表中搜索值为a的结点，并打印它的值 void print (p) struct node *p; if(p!=NULL) if(p-data=a) printf(“%d”, p-data); else printf(p-link); ,例 （n阶Hanoi塔问题） 有三