【教学课件】第3章栈和队列.ppt
( 4.5 )《【教学课件】第3章栈和队列.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第3章栈和队列.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第3章 栈和队列要求：了解栈的定义及特点，掌握栈表示和实现，重点是栈初始化、判断栈空和栈满、出栈和入栈操作；（注意栈顶的约定）栈的应用举例，重点是表达式求值；（了解波兰式、逆波兰式、中缀式等概念）栈与递归的实现；（系统工作栈）了解队列的定义及特点，掌握队列的表示和实现，重点是队列初始化、判断队空和队满、出队和入队操作；难点：循环队列。（离散事件模拟不要求）1第3章 栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DSn3.1 栈（stack）n栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶top，表头栈底bottom，不含元素的空表称空栈特点：先进后出（F
2、ILO）或后进先出（LIFO）ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)进栈插入元素出栈删除元素抽象数据类型定义2n栈的表示和实现顺序栈 一维数组sM 或先分配一个基本容量，逐段扩大，动态数组top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0base保持不变top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空3typedef struct SE
3、lemType *base;/保持不变，NULL 不存在栈SElemType *top;/栈顶，指向不用(空)元素，与定义不同int stacksize;SqStack;/(进)入栈 top+，出(退)栈 top-算法描述InitStack,DestroyStack,ClearStack,StackEmpty,StackLength,GetTop,Push,Pop,StackTraverse4构造一个空栈SStatus InitStack(SqStack&S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.ba
4、se)exit(OVERFLOW);/存储分配失败 S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;取栈顶元素Status GetTop(SqStack S,SElemType&e)if(S.top=S.base)return ERROR;e=*(S.top-1);return OK;5入栈算法Stutas Push(SqStack&S,SElemType e)if(S.top S.base=S.stacksize S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*
5、sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;/先赋值，再加指针 return OK;6出栈算法Status Pop(SqStack&S,SElemType&e)if(S.top=S.base)return ERROR;e=*-S.top;/先减指针，再取值 return OK;0M-1栈1底栈1顶栈2底栈2顶在一个程序中同时使用两个栈7链栈栈顶栈顶 .topdata link栈底结点定义入栈算法出栈算法typedef stru
6、ct node int data;struct node *link;JD;.栈底toptopxptop .栈底topq83.2 栈的应用举例数制转换 N （N div d）x d+N mod d算法 3.1 P48计算过程 入栈打印过程 出栈例 把十进制数159转换成八进制数(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top7329void conversion(int Num)/算法3.1 /对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 InitStack(S);/构造空栈 while(Num)Push(S,Num%
7、8);Num=Num/8;while(!StackEmpty(S)Pop(S,e);printf(%d,e);printf(n);/conversion10括号匹配的检验 园、方、花括号 嵌套匹配回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文字符串：“madam im adam”11void LineEdit()InitStack(S);ch=gether();while(ch!=EOF)while(ch!=EOF&ch!=n)switch(ch)case#:Pop(S,c
8、);case :ClearStack(S);default:Push(S,ch);ch=getchar();transfer;ClearStack(S);if(ch!=EOF)ch=gethar();DestroyStack(S);简单行编辑程序 逐行存入，退格，清行 算法 3.2 P50迷宫求解，地图四染色12n表达式求值 运算规则 中缀表达式 后缀表达式（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操作数运算符24+操作数运算符6-操作数运算符6-36*操作数运算
9、符6-18操作数运算符-1214算法基本思想 P531)操作符栈 OPTR的栈底元素为表达式起始符#，操作数栈 OPND为空2)依次读入字符：是操作数则入OPND栈，是操作符则要判断算法 3.4注意未考虑匹配，表达式必须正确表达式的前缀、中缀、后缀表示，其中表达式的前缀表示称为波兰式，表达式的后缀表示称为逆波兰式RPN（Reverse Polish Notation）。由于逆波兰式用的较多，习惯上称为波兰式。中缀表达式 算符优先法，括号，双堆栈前、后缀表达式 单堆栈，算符无优先级，无括号中缀 后缀15OperandType EvaluateExpression()/算法3.4 算术表达式求值的
10、算符优先算法。/设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;/s
11、witch /while return GetTop(OPND);/EvaluateExpression16后缀表达式求值步骤：1、读入表达式一个字符2、若是操作数，压入栈，转43、若是运算符，从栈中弹出2个数，将运算结果再压入栈4、若表达式输入完毕，栈顶即表达式值；若表达式未输入完，转1top4top43top735top例 计算 4+3*5后缀表达式：435*+top415top1917过程的嵌套调用r主主程程序序srrrs子子过过程程1rst子子过过程程2rst子子过过程程33.3 栈与递归的实现18例例 递归的执行情况分析递归的执行情况分析 递归过程及其实现递归：函数直接或间接的调用自
12、身叫实现：建立递归工作栈void print(int w)int i;if(w!=0)print(w-1);for(i=1;i1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题算法：执行情况：递归工作栈保存内容：形参n,x,y,z和返回地址返回地址用行编号表示n x y z 返回地址 21 main()int m;printf(Input number of disks”);scanf(%d,&m);printf(”Steps:%3d d
13、isks”,m);hanoi(m,A,B,C);(0)void hanoi(int n,char x,char y,char z)(1)(2)if(n=1)(3)move(1,x,z);(4)else(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)(9)ABC1233 A B C 03 A B C 02 A C B 63 A B C 02 A C B 61 A B C 6ABC3 A B C 02 A C B 622 main()int m;printf(Input the number of disks scanf(%d,&
14、m);printf(The steps to moving%3d hanoi(m,A,B,C);(0)void hanoi(int n,char x,char y,char z)(1)(2)if(n=1)(3)move(1,x,z);(4)else(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)(9)ABC3 A B C 02 A C B 61 C A B 8ABC3 A B C 02 A C B 63 A B C 03 A B C 02 A C B 623 main()int m;printf(Input the numbe
15、r of disks scanf(%d,&m);printf(The steps to moving%3d hanoi(m,A,B,C);(0)void hanoi(int n,char x,char y,char z)(1)(2)if(n=1)(3)move(1,x,z);(4)else(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)(9)ABC3 A B C 02 B A C 83 A B C 02 B A C 81 B C A 6ABC3 A B C 02 B A C 83 A B C 024 main()int m;p
16、rintf(Input the number of disks scanf(%d,&m);printf(The steps to moving%3d hanoi(m,A,B,C);(0)void hanoi(int n,char x,char y,char z)(1)(2)if(n=1)(3)move(1,x,z);(4)else(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)(9)ABC3 A B C 02 B A C 81 A B C 8ABC3 A B C 02 B A C 83 A B C 0栈空3 A B C 02
17、B A C 825递归的特性有限次递归调用，非递归出口 if或while语句递归的优缺点优点：结构清晰、易读，正确性易证明缺点：运行效率低，时空消耗大递归过程的模拟先写递归算法，再转化成非递归PASCAL版 英文版 Hanoi 非递归实质：系统管理的递归工作栈改为程序员管理26作业：3.63.73.8补：写一递归算法将单链表(无头结点)倒序27n队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 双端队尾(rear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出(FIFO)a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2
18、,an)双端队列a1 a2 a3.an 端1端2入队出队入队出队3.4 队列(Queue)28结点定义typedef struct QNode QElemType data;struct QNode *next;QNode,*QueuePtr;头结点 .front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾抽象数据类型定义 QueueEmpty，EnQueue，DeQueuetypedef struct QueuePtr front;QueuePtr rear;LinkQueue;链队列链队列 队列的链式表示和实现队列的链式表示和实现29fron
19、trearx入队xfrontreary入队xyfrontrearx出队xyfront rear空队front reary出队30入队算法 EnQueue出队算法 DeQueue最后一个元素出队后，队尾指针指向头结点If(Q.rear=p)Q.rear=Q.front;部分算法描述 P62 InitQueue DestroyQueue31实现：用一维数组实现sqMfront=-1rear=-1123450队空123450frontJ1,J2,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素；fro
20、nt指示队头元素前一位置初值front=rear=-1空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront队列的顺序存储结构32存在问题设数组大小为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出真溢出当front-1,rear=M-1时，再有元素入队发生溢出假溢出解决方案队首固定，每次出队剩余元素向下移动浪费时间循环队列循环队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;0M-1
21、1frontrear.实现：利用“模”运算入队：rear=(rear+1)%M;sqrear=x;出队：front=(front+1)%M;x=sqfront;队满、队空判定条件33012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front=rear队满：front=rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front=rear 队满：(rear+1)%M=front34入队算法：EnQueue(Q.rear+1)%MAXQS
22、IZE=Q.front 满队出队算法：DeQueueQ.front=Q.rear 空队 InitQueue QueueLength基本操作算法描述 P6435队列应用举例n离散事件模拟n划分子集问题n图的广度优先搜索n多任务操作系统中CPU调度，多队列，分时使用36问题描述：已知集合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,
23、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 划分子集问题37算法思想：利用循环筛选。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组所用数据结构冲突关系矩阵rij=1,i,j有冲突rij=0,i,j无冲突循环队列cqn数组resultn存放每个元素分组号工作数组newrn38工作过程初始状态：A中元素放于cq中，result和newr数组清零，组号group=1第一个元素出
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 教学课件 教学 课件 队列
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内