CH3嶘和队列.ppt
第三章 栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS 3.1 栈（stack）3.2 栈的应用举例 3.3 队列 3.4 队列应用举例3.1.1栈的定义v定义：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈v特点：先进后出（FILO）或后进先出（LIFO）ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)3.1 栈（stack）栈顶（栈顶（top)top)：允许插入和删除允许插入和删除的一端；的一端；栈底（栈底（bottom):bottom):不允许插入和不允许插入和删除的一端。删除的一端。1.顺序栈top=-1123450栈空栈顶指针top,指向实际栈顶位置，初值为-1top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=-1,栈空，此时出栈，则下溢（underflow)top=M-1,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空3.1.2栈的存储实现和运算实现l存储结构的实现#define MAXSIZE 1000typedef struct datatype dataMAXSIZE;int top;SeqStack;l运算实现(1)置空栈(2)判栈空(3)入栈(4)出栈(5)取栈顶元素S-top=-1123450栈空S-top123450进栈xS-topS-datas-top栈顶栈顶 .topdata next栈底q结点定义q入栈算法q出栈算法typedef struct node int data;struct node *next;StackNode,*LinkStack;.栈底toptopxptop .栈底topq2.链栈3.2 栈的应用举例例3-1数制转换问题：将十进制N转换为r进制的数。例 把十进制数159转换成八进制数(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732算法思想：while(N0)将N%r结果进栈;N=N/r;while(栈非空)出栈并输出原栈顶元素;例3-2利用栈实现迷宫的求解：1、问题描述：心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多墙壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。2、算法基本思想描述：利用回溯法，从入口处出发，按某一方向不断试探，若能走通，则到达新点，否则试探另一未试探过的方向。若所有的方向均没有通路，则沿原路返回前一点，换一个未试探过的通路继续试探，直到找到出口，或所有的通路都试探过，未找到一条通路回到出口点。在试探过程中，为保证在到达某一点无路时，能正确返回前一点，需要用一个栈来保存到达的每一点的位置及试探方向。3、设计：1）数据结构的设计 （1）迷宫的表示 设迷宫为m行n列，利用二维数组mazemn来表示一个迷宫，其中(1，1)为入口，(m，n)为出口，mazemn=0或1，其中0表示通路，1表示不通。011101111010111101000001011101111001100001100110123 45 67 8123456入口出口011101111010111101000001011101111001100001100110迷宫定义#define m 6#define n 8int mazem+2n+2 当从某点向试探时，之间点有8个方向可以试探，而四个角点有3个方向，其他边缘点有5个方向，为使问题简单化,在迷宫的四周加了一层，表示墙壁，这样每个点的试探方向为8。11111111111111111111111111111111123 45 67 8 9012345670 （2）试探方向的表示 在上述表示迷宫的情况下，每个点有8个方向可以试探，设当前点的坐标为（x，y），与其相邻的8个点的坐标可根据与该点的相邻方位得到。为了方便求出新点的坐标，将从正东开始沿顺时针进行的这8个方向的坐标增量放在一个结构数组move8中，其中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）（x，y）试探方向的表示typedef struct int x,y;item;item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1;（3）栈的表示 当到达了某点无路可走，需从前一点的下一个方向试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还有从前一点到达本点的方向序号。栈的表示#define MAXSIZE 20typedef struct int x,y,d;datatype;typedef struct datatype dataMAXSIZE;int top;SeqStack;2）算法的设计 （1）防止重复到达某点的考虑 为避免发生死循环，当到达某点（i，j）后，使mazeij置-1，以便区分未到达过的顶点。算法结束前可恢复原迷宫。（2）算法描述 栈初始化；将入口点坐标及初始试探方向（设为-1）入栈,并将入口点设置为已走过；设置found为0(未找到出口点);1，1，-1top while（未找到&栈非空）将栈顶元素赋值给x;从x点出发寻找下一个可以走的方位；if(找到方位)修改栈顶元素的方位值;计算新点,并设置为已走过;将新点位置及初始试探方位值进栈;if(新点是结束点)found=1;else /没找到可走的方位,说明从该点出发已无路可走 出栈;if(找到)打印路径;else 打印“该迷宫无路径”01110111101011110100000101110111100110000110011011111111111111111111111111111111123 45 67 8 90123456701，1，1top2，2，-11，1，12，2，13，3，-11，1，12，2，13，3，03，4，03，5，03，6，03，7，-1-1-1-1-1-1-1-11，1，-1top1，1，02，2，13，3，03，4，03，5，03，6，03，7，-101110111101011110100000101110111100110000110011011111111111111111111111111111111123 45 67 8 9012345670-1-1-1-1-1-1-1-11，1，02，2，13，3，03，4，03，5，03，6，0-1-1-1-11，1，02，2，13，3，03，4，03，5，03，6，34，5，15，6，05，7，05，8，26，8，-1例3-3表达式求值 中缀表达式 后缀表达式（RPN)a*b+c ab*c+a+b*c abc*+a+(b*c+d)/e abc*d+e/+(1)中缀表达式求值：对象栈和运算符栈例 计算 2+(4-3)*6对象栈算符栈2+对象栈算符栈2+16*对象栈算符栈2+6对象栈算符栈8对象栈算符栈2+(对象栈算符栈2+(4-3对象栈算符栈2+1(对象栈算符栈2+1左括号在栈外优先级最高右括号遇到左括号，左括号直接出栈在栈外优先级最高左括号在栈内优先级比-低算法描述：读入表达式一个字符;while(未遇到结束符)if(当前字符是运算对象)将该字符入对象栈;扫描下一个字符;else/当前字符是运算符 switch(当前运算符)case 左括号:进栈;扫描下一个字符;break;case 右括号:if(栈顶是左括号)出栈;扫描下一个字符;break;else 执行default语句；default:if(当前字符优先级1)1.定义：定义：在调用一个函数的过程中直接或间接地调用该函数本身。直接调用直接调用int f(x)int x;int y,z;.z=f(x);return(2*z);f 函数调用 f函数int f1(x)int x;int y,z;.z=f2(y);return(2*z);int f2(t)int t;int a,c;.c=f1(a);return(3+c);间间接接调调用用f 1函数调用 f2函数f 2函数调用 f1函数main()int m,n=3;m=fact(n);R1:printf(“%d!=%dn”,n,m);例如：写一函数求例如：写一函数求n!int fact(int n)int f;if(n=0)f=1;else R2:f=fact(n-1)*n;return f;以求3的阶乘为例：fac(3)=3*fac(2)fac(2)=2*fac(1)fac(1)=1fac(2)=2*1fac(3)=3*2*1下下推推回回代代利用栈实现递归调用利用栈实现递归调用n=3R1fact(3);R2:f=3*fact(2)n=2R2n=3R1返回返回f=3*2*1n=3R11R22R23R10R2主程序主程序R1:输出输出f(3);fact(2);R2:f=2*fact(1)fact(1);R2:f=1*fact(0)返回返回fact(0);f=1返回返回f=2*1;n=2R2n=3R1n=2R2n=3R1n=1R2返回返回f=1*1n=2R2n=3R1n=1R2输出输出63.3.1队列的定义及特点n定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表q队尾(rear)允许插入的一端q队头(front)允许删除的一端n队列特点：先进先出(FIFO)a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an)3.3 队列q链队列n结点定义typedef struct node datatype data;struct node *next;QNode;QNode *front,*rear;头结点 .front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾3.3.2队列 的存储实现及运算实现头结点frontrear头结点 .q-front队头队尾q-reartypedef struct node datatype data;struct node *next;QNode;typedef struct QNode *front,*rear;LQueue;LQueue *q;头结点q-frontq-rearv链队列基本运算实现结点定义（1）创建一个带头结点的空队头结点q-frontq-rear（2）判队空（3）入队q-frontq-rearx入队xq-frontq-reary入队xyfrontrearx出队xyfront reary出队（4）出队v队列的顺序存储结构1、顺序队#define MAXSIZE 1000typedef struct datatype dataMAXSIZE;int front,rear;SeQueue;SeQueue *sq;sq-rear123450J1J2J3sq-front约定：sq-rear指示队尾元素；Sq-front指示队头元素前一位置front=-1rear=-1123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front初值sq-front=sq-rear=-1空队列条件：sq-front=sq-rear入队列：sq-data+sq-rear=x;出队列：x=sq-data+sq-front;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfrontn存在问题设数组维数为MAXSIZE，则：q当front=-1,rear=MAXSIZE-1时，再有元素入队发生溢出真溢出q当front-1,rear=MAXSIZE-1时，再有元素入队发生溢出假溢出n解决方案q队首固定，每次出队剩余元素向下移动浪费时间q循环队列实现：利用“模”运算入队：sq-rear=(sq-rear+1)%MAXSIZE;sq-datasq-rear=x;出队：sq-front=(sq-front+1)%MAXSIZE;队满、队空判定条件0MAXSIZE-11sq-frontsq-rear.u基本思想：把队列设想成环形让sq-data0接在sq-dataMAXSIZE-1之后，若sq-rear+1=MAXSIZE,则令sq-rear=0;2、循环队列012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：sq-front=sq-rear队满：sq-front=sq-rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：sq-front=sq-rear 队满：(sq-rear+1)%MAXSIZE=sq-frontJ4J5J6012345rearfrontJ8J7（1）置空队v按第一种解决方法的循环队列实现存储结构#define MAXSIZE 1000typedef struct datatype dataMAXSIZE;int front,rear;int num;C_SeQueue;C_SeQueue *sq;012345rearfront置空队（2）入队（3）出队（4）判队空3.4队列应用举例例3-5求迷宫的最短路径1、算法基本思想描述：从迷宫入口点出发，向四周搜索，记下所有一步能到达的坐标点；然后依次从这些点出发，再记下所有一步能到达的坐标点，.依此类推，直到到达迷宫的出口点为止，然后从迷宫出口点沿搜索路径回溯。这样就找到了一条迷宫的最短路径，否则迷宫无路径。由于先到达的点先搜索，故用先进先出的数据结构队列来保存已到达的坐标点。0 1 1 1 0 1 1 11 0 1 0 1 0 1 00 1 0 0 1 1 1 10 1 1 1 0 0 1 11 0 0 1 1 0 0 00 1 1 0 0 1 1 01 2 3 456 7 8123456（1，1）（2，2）（3，3）（3，1）（3，4）（2，4）（4，5）（1，5）（4，1）（5，2）（4，6）（5，6）（2，6）（5，3）（6，1）（5，7）（6，5）（6，4）（5，8）（6，8）2、设计：1）数据结构的设计 （1）迷宫的表示#define m 6#define n 8 int mazem+2n+2（2）试探方向的表示typedef struct int x,y;item;item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1;（3）队列的表示 在找到出口点之后，需要沿搜索路径回溯，所以到达某点时，不仅要记下该点的坐标，还要记下该点的前驱。#define num 50typedef struct int x,y；int pre;SqType;SqType sqnum；int front，rear；2）算法的设计 （1）防止重复到达某点的考虑 为避免发生死循环，当到达某点（i，j）后，使mazeij置-1，以便区分未到达过的顶点。算法结束前可恢复原迷宫。（2）队列头、尾指针的指向 队头指针指向搜索的出发点，当找到一个可到达点，就入队；当8个方位都搜索完毕，队头指针往后移一个（出队，但原位置值依然存在，方便最后回溯）。（3）算法描述 队列头、尾指针栈初始化（=-1）；将入口点的前驱设置为-1，入队；将入口点设置为已走过；将是否找到出口点信息found赋值为0（未找到）；while（未找到&队列非空）队头指针后移指向当前搜索点，并将它赋值给x；for i=1 to 8 搜索x点的8个方向 if（找到一个可走点）就将该点坐标及前驱值（front）入队；将该点设置为已走过；if（该点是出口点）found=1；if(找到)回溯打印最短路径；else 打印“该迷宫没有路径”;
