【教学课件】第3章栈和队列.ppt

1,第3章 栈和队列,要求：了解栈的定义及特点，掌握栈表示和实现，重点是栈初始化、判断栈空和栈满、出栈和入栈操作；（注意栈顶的约定）栈的应用举例，重点是表达式求值；（了解波兰式、逆波兰式、中缀式等概念）栈与递归的实现；（系统工作栈）了解队列的定义及特点，掌握队列的表示和实现，重点是队列初始化、判断队空和队满、出队和入队操作；难点：循环队列。（离散事件模拟不要求）,2,第3章 栈和队列,栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS3.1 栈（stack）栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶top，表头栈底bottom，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）,进栈插入元素出栈删除元素,抽象数据类型定义,3,栈的表示和实现顺序栈 一维数组sM 或先分配一个基本容量，逐段扩大，动态数组,栈顶指针top,指向实际栈顶后的空位置，初值为0base保持不变,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow),栈空,4,typedef struct SElemType*base;/保持不变，NULL 不存在栈SElemType*top;/栈顶，指向不用(空)元素，与定义不同int stacksize;SqStack;/(进)入栈 top+，出(退)栈 top-,算法描述InitStack,DestroyStack,ClearStack,StackEmpty,StackLength,GetTop,Push,Pop,StackTraverse,5,构造一个空栈SStatus InitStack(SqStack,取栈顶元素Status GetTop(SqStack S,SElemType,6,入栈算法Stutas Push(SqStack,7,出栈算法Status Pop(SqStack,在一个程序中同时使用两个栈,8,链栈,结点定义,入栈算法,出栈算法,typedef struct node int data;struct node*link;JD;,9,3.2 栈的应用举例,数制转换 N（N div d）x d+N mod d算法 3.1 P48计算过程 入栈打印过程 出栈,10,void conversion(int Num)/算法3.1/对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 InitStack(S);/构造空栈 while(Num)Push(S,Num%8);Num=Num/8;while(!StackEmpty(S)Pop(S,e);printf(%d,e);printf(n);/conversion,11,括号匹配的检验 园、方、花括号 嵌套匹配,回文游戏：顺读与逆读字符串一样（不含空格）,1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文,字符串：“madam im adam”,12,void LineEdit()InitStack(S);ch=gether();while(ch!=EOF)while(ch!=EOF,简单行编辑程序 逐行存入，退格，清行 算法 3.2 P50,迷宫求解，地图四染色,13,地图四染色问题,1,2,2,3,4,1,4,3,3,4,2,3,1#紫色 2#黄色3#红色4#绿色,14,表达式求值 运算规则,中缀表达式 后缀表达式（RPN)a*b+c ab*c+a+b*c abc*+a+(b*c+d)/e abc*d+e/+,中缀表达式：操作数栈和运算符栈 P53表3.1优先关系,例 计算 2+4-3*6,15,算法基本思想 P531)操作符栈 OPTR的栈底元素为表达式起始符#，操作数栈 OPND为空2)依次读入字符：是操作数则入OPND栈，是操作符则要判断算法 3.4注意未考虑匹配，表达式必须正确,表达式的前缀、中缀、后缀表示，其中表达式的前缀表示称为波兰式，表达式的后缀表示称为逆波兰式RPN（Reverse Polish Notation）。由于逆波兰式用的较多，习惯上称为波兰式。中缀表达式 算符优先法，括号，双堆栈前、后缀表达式 单堆栈，算符无优先级，无括号中缀 后缀,16,OperandType EvaluateExpression()/算法3.4 算术表达式求值的算符优先算法。/设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=getchar();while(c!=#|GetTop(OPTR)!=#)if(!In(c,OP)Push(OPND,c);c=getchar();/不是运算符则进栈 else switch(precede(GetTop(OPTR),c)case:/退栈并将运算结果入栈 Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;/switch/while return GetTop(OPND);/EvaluateExpression,17,后缀表达式求值步骤：1、读入表达式一个字符2、若是操作数，压入栈，转43、若是运算符，从栈中弹出2个数，将运算结果再压入栈4、若表达式输入完毕，栈顶即表达式值；若表达式未输入完，转1,例 计算 4+3*5,后缀表达式：435*+,18,过程的嵌套调用,3.3 栈与递归的实现,19,例 递归的执行情况分析,递归过程及其实现递归：函数直接或间接的调用自身叫实现：建立递归工作栈,void print(int w)int i;if(w!=0)print(w-1);for(i=1;i=w;+i)printf(“%3d,”,w);printf(“/n”);,运行结果：1，2，2，3，3，3，,20,递归调用执行情况如下：,Tower of Hanoi问题问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则：每次只能移一个圆盘圆盘可在三个塔座上任意移动任何时刻，每个塔座上不能将大盘压到小盘上,解决方法：n=1时，直接把圆盘从A移到Cn1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题算法：,执行情况：递归工作栈保存内容：形参n,x,y,z和返回地址返回地址用行编号表示,22,main()int m;printf(Input number of disks”);scanf(%d,(8)(9),23,main()int m;printf(Input the number of disks scanf(%d,(8)(9),24,main()int m;printf(Input the number of disks scanf(%d,(8)(9),25,main()int m;printf(Input the number of disks scanf(%d,(8)(9),26,递归的特性有限次递归调用，非递归出口 if或while语句递归的优缺点优点：结构清晰、易读，正确性易证明缺点：运行效率低，时空消耗大递归过程的模拟先写递归算法，再转化成非递归PASCAL版 英文版 Hanoi 非递归实质：系统管理的递归工作栈改为程序员管理,27,作业：3.63.73.8补：写一递归算法将单链表(无头结点)倒序,28,队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 双端队尾(rear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出(FIFO),双端队列,3.4 队列(Queue),29,结点定义,typedef struct QNode QElemType data;struct QNode*next;QNode,*QueuePtr;,设队首、队尾指针front和rear,front指向头结点，rear指向队尾,抽象数据类型定义 QueueEmpty，EnQueue，DeQueue,typedef struct QueuePtr front;QueuePtr rear;LinkQueue;,链队列 队列的链式表示和实现,30,31,入队算法 EnQueue,出队算法 DeQueue最后一个元素出队后，队尾指针指向头结点If(Q.rear=p)Q.rear=Q.front;,部分算法描述 P62,InitQueue DestroyQueue,32,实现：用一维数组实现sqM,J1,J2,J3,设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1,空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;,队列的顺序存储结构,33,存在问题设数组大小为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出真溢出当front-1,rear=M-1时，再有元素入队发生溢出假溢出解决方案队首固定，每次出队剩余元素向下移动浪费时间循环队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;,实现：利用“模”运算入队：rear=(rear+1)%M;sqrear=x;出队：front=(front+1)%M;x=sqfront;队满、队空判定条件,34,队空：front=rear队满：front=rear,解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front=rear 队满：(rear+1)%M=front,35,入队算法：EnQueue(Q.rear+1)%MAXQSIZE=Q.front 满队,出队算法：DeQueueQ.front=Q.rear 空队,InitQueue QueueLength,基本操作算法描述 P64,36,队列应用举例,离散事件模拟划分子集问题图的广度优先搜索多任务操作系统中CPU调度，多队列，分时使用,37,问题描述：已知集合A=a1,a2,an，及集合上的关系R=(ai,aj)|ai,ajA,ij，其中(ai,aj)表示ai与aj间存在冲突关系。要求将A划分成互不相交的子集A1,A2,Ak,(kn)，使任何子集中的元素均无冲突关系，同时要求分子集个数尽可能少,例 A=1,2,3,4,5,6,7,8,9 R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)可行的子集划分为：A1=1,3,4,8 A2=2,7 A3=5 A4=6,9,划分子集问题,38,算法思想：利用循环筛选。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组所用数据结构冲突关系矩阵rij=1,i,j有冲突rij=0,i,j无冲突循环队列cqn数组resultn存放每个元素分组号工作数组newrn,39,工作过程初始状态：A中元素放于cq中，result和newr数组清零，组号group=1第一个元素出队，将r矩阵中第一行“1”拷入newr中对应位置，这样，凡与第一个元素有冲突的元素在newr中对应位置处均为“1”,下一个元素出队若其在newr中对应位置为“1”，有冲突，重新插入cq队尾，参加下一次分组若其在newr中对应位置为“0”,无冲突，可划归本组；再将r矩阵中该元素对应行中的“1”拷入newr中如此反复，直到9个元素依次出队，由newr中为“0”的单元对应的元素构成第1组,将组号group值“1”写入result对应单元中令group=2,newr清零，对cq中元素重复上述操作，直到cq中front=rear,即队空，运算结束,40,算法描述,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),41,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),42,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),43,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),44,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),45,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),46,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),47,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),48,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),49,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),50,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),51,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),52,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),53,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),54,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),55,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),56,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),57,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),58,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),59,算法描述,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),可行的子集划分为：A1=1,3,4,8 A2=2,7 A3=5 A4=6,9,60,作业3.113.12,