《数据结构严蔚敏C语言版第三章课件.ppt》由会员分享，可在线阅读，更多相关《数据结构严蔚敏C语言版第三章课件.ppt（76页珍藏版）》请在三一办公上搜索。
1、3.1.1 栈的定义及基本运算,3.1 栈(Stack),假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出(LIFO)表。,栈是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当栈中没有元素时称为空栈。,例、一叠书或一叠盘子。,栈顶,栈底,抽象数据类型栈,ADT Stack 数据对象:D=ai|ai ElemSet,i=1,2,n(n=0)数据关系：R=|ai-1,
2、ai D,i=2,3,n 约定an端为栈顶，a1端为栈底。基本操作:InitStack(&S)操作结果:建立一个空栈S DestroyStack(&S)初始条件：栈S已存在 操作结果:栈S被销毁,ClearStack(&S)初始条件：栈S已存在 操作结果:将S栈清空StackEmpty(S)初始条件：栈S已存在 操作结果：若栈S为空栈，返回true,否则返回falseStackLength(S)初始条件：栈S已存在 操作结果:返回S的元素个数GetTop(S,&e)/读栈顶元素 初始条件：栈S已存在且非空 操作结果:用e返回栈顶元素,Push(&S,e)/入栈 初始条件：栈S已存在 操作结果:
3、将元素e插入到栈顶Pop(&S,&e)/出栈 初始条件：栈S已存在且非空 操作结果:删除S的栈顶元素，用e返回StackTraverse(S,visit()初始条件：栈S已存在且非空 操作结果:从栈底到栈顶依次对S的每个元素调用visit()ADT Stack,由于栈的逻辑结构与线性表相同，因此线性表的存储结构对栈也适应。,3.1.2 栈的表示和实现,顺序栈 链栈,栈的顺序存储结构简称为顺序栈，由于栈底位置是固定不变的，所以可以将栈底位置设置在数组两端的任何一端；而栈顶位置是随着入栈和出栈操作而变化的.,顺序栈,顺序栈的类型定义如下：#define STACK_INIT_SIZE 100#de
4、fine STACKINCREMENT 10 typedef struct SElemType*base;/栈底指针，base=NULL表明栈不存在 SElemType*top;/栈顶指针,top=base为栈空的标志 int stacksize;/栈当前可以使用的最大容量 SqStack;,栈顶指针top,指向栈底位置,入栈,A,出栈,栈满,B,C,D,E,F,设数组大小为stacksizetop=base,栈空，此时出栈，则下溢（underflow)top=stacksize,栈满，此时入栈，则上溢（overflow),栈空,顺序栈的入栈与出栈,在一个程序中同时使用两个栈,1、构造一个空栈
5、 Status InitSatck(SqStack/end InitSatck,基本操作的算法描述,2、返回栈顶元素 Status GetTop(SqStack S，SElemTtype/end GetTop,3、入栈Status Push(SqStack/end Push,4、出栈 Status Pop(SqStack/end Pop,栈顶,.,top,data,next,栈底,链栈,其操作与线性链表类似,3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 行编辑程序 3.2.5 表达式求值,3.2 栈的应用举例,十进制n和其它进制数d的转换是计算机实现计算的基本问题,其解决方法很
6、多,其中一个简单算法基于下列原理:n=(n div d)*d+n mod d(其中:div为整除运算,mod为求余运算)例如(1348)10=(2504)8，其运算过程如下：,3.2.1 数制转换,例如：（1348)10=(2504)8，其运算过程如下：,计算顺序,输出顺序,n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,算法3.1 void conversion()/十进制转换为等值的八进制 Initstack(S);scanf(“%d”,N);while(N)Push(S,N%8);N=N/8;while(!StackEmpty(S)P
7、op(S,e);printf(“%d”,e);/end conversion,假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例：()()1 2 3 4 5 6 7 8,3.2.2 括号匹配的检验,分析出现的不匹配的情况:,到来的右括号不是所“期待”的;,1）凡出现左括号，则入栈；,2）凡出现右括号，首先检查栈是否空.若栈空，则表明该“右括号”多余,否则和栈顶元素比较，若相匹配，则“左括号出栈”,否则表明括号不匹配.,3）表达式检验结束时，若栈空，则表明表达式中括号匹配,否则表明“左括号”有余,算法的设计思想：,Status matching(strin
8、g,检验括号匹配的算法：,在用户输入程序或数据时，允许用户输入出差错，当发现有误时，可以及时更正。方法是：设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。假设退格符“#”表示前一个字符无效；退行符“”表示当前行中的字符全无效。,3.2.3 行编辑程序,假设从终端接受了这样两行字符 whli#ilr#e（s#*s)outchaputchar(*s=#+);,则实际有效的是下列两行：while(*s)putchar(*s+);,void LineEdit()InitStack(S);/栈S设为输入缓冲区 ch=getchar();while(ch!=eof)while(ch
9、!=eof/end LineEdit,行编辑程序算法：,3.2.5 表达式求值,例如：3*（7 2）（1）算术四则运算的规则：a.从左算到右 b.先乘除，后加减 c.先括号内，后括号外 由此，此表达式的计算顺序为：3*（7 2）=3*5=15,（2）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符1和2，都要比较优先权关系。算符优先法所依据的算符间的优先关系见教材P53表3.1由表可看出，右括号)和井号#作为2时级别最低；由c规则得出：*，/，+，-为1时的优先权低于（，高于）由a规则得出：（=）表明括号内运算，已算完。#=#表明表达式求值完毕。令OP=+，-，*，/，（，），#,
10、3.2.5 表达式求值,（3）算法思想：设两个栈：操作符栈 OPTR，操作数栈 OPND栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底 元素为表达式起始符#；依次读入字符：是操作数则入OPND栈，是操作符则要判断：if 操作符(1)栈顶元素，压入OPTR栈。,3.2.5 表达式求值,例 求表达式3*(7-2),Status EvaluateExpression(OperandType/End EvaluateExpression,3.2.4 迷宫求解 入口,出口,求迷宫路径算法的基本思想是：,若当前位置“可通”，则纳入路径，继续前进;,若当前位置“不可通”，则后退，换方向继续
11、探索;,若四周“均无通路”，则将当前位置从路径中删除出去。,设当前位置为入口位置do if(当前位置可通)当前位置插入栈顶;if(该位置是出口位置)结束 else 切换当前位置的东邻方块为新的当前位置;else if(栈不空栈顶位置尚有其它方向未经探索)设定新的当前位置为顺时针方向旋转找到的顶点 位置的下一个邻块;if(栈不空且栈顶位置的四周均不通)删去栈顶元素位置,直至找到一个可通的相邻块或 出栈或栈空;while(栈不空);,求迷宫中一条从入口到出口的路径的算法思想：,Type struct int ord;/通道块在路径上的序号 PosType seat;/通道块在迷宫中的“坐标位置”i
12、nt di;/从此通道块走向下一通道块的方向SElemType;/栈元素类型Status MazePath(MazeType maze,PosType start,PosType end)InitStack(S);curpos=start;/当前位置为入口位置 curstep=1;/探索第一步 do if(Pass(curpos)/当前位置可以通过 footprint(curpos);/留下足印 e=(curstep,curpos,1);Push(S,e);/加入路径 if(curpos=end)return(TRUE);/到达终点 curpose=NextPos(curpos,1);/下一个
13、位置是当前位置的东邻 curstep+;,else/当前位置不通 if(!StackEmpty(S)Pop(S,e);while(e.di=4/end MazePath,一、函数的嵌套调用,3.3 栈与递归的实现,二、递归函数及其实现,3.3 栈与递归的实现,递归：函数直接或间接的调用自身实现：建立递归工作栈,例1 递归的执行情况分析-n!,int fact(int w)if(w=0)fact=1;else fact=w*fact(w-1);,main()int f;f=fact(3);print(f);,3.3 栈与递归的实现,递归过程三要素:1.定义出口2.把一个大的问题划分成同类型的子问
14、题3.解的合成,3.3 栈与递归的实现,int fact(int w)1if(w=0)2 fact=1;3else 4fact=w*fact(w-1);,top,递归调用执行情况如下：,int fact(int w)1if(w=0)2 fact=1;3else 4fact=w*fact(w-1);,3,3*fact(2);,top,w,递归调用执行情况如下：,int fact(int w)1if(w=0)2 fact=1;3else 4fact=w*fact(w-1);,3,3*fact(2);,w,2,2*fact(1);,top,w,递归调用执行情况如下：,1,1*fact(0);,top
15、,w,int fact(int w)1if(w=0)2 fact=1;3else 4fact=w*fact(w-1);,3,3*fact(2);,w,2,2*fact(1);,w,递归调用执行情况如下：,1,1*fact(0);,top,w,int fact(int w)1if(w=0)2 fact=1;3else 4fact=w*fact(w-1);,3,3*fact(2);,w,2,2*fact(1);,w,递归调用执行情况如下：,int fact(int w)1if(w=0)2 fact=1;3else 4fact=w*fact(w-1);,3,3*fact(2);,w,2,2*fact
16、(1);,w,1,1*fact(0);,w,top,fact(1)=1,递归调用执行情况如下：,int fact(int w)1if(w=0)2 fact=1;3else 4fact=w*fact(w-1);,3,3*fact(2);,w,2,2*fact(1);,w,1,1*fact(0);,w,fact(1)=1,top,fact(2)=2,递归调用执行情况如下：,int fact(int w)1if(w=0)2 fact=1;3else 4fact=w*fact(w-1);,3,3*fact(2);,w,2,2*fact(1);,w,1,1*fact(0);,w,fact(1)=1,fa
17、ct(2)=2,top,fact(3)=6,递归调用执行情况如下：,例2：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问题，依次类推，直至转化成只有一个圆盘
18、的Hanoi问题,执行情况递归工作栈保存内容：形参n,x,y,z和返回地址返回地址用行编号表示,main()int m;printf(Input number of disks);scanf(%d,(8)(9),main()int n;printf(Input the number of disks scanf(%d,(8)(9),main()int n;printf(Input the number of disks scanf(%d,(8)(9),main()int n;printf(Input the number of disks scanf(%d,(8)(9),3.4 队列3.4.1
19、 抽象数据类型队列的定义队列的定义及特点定义：队列是限定只能在表的一端进行插入，而在表的另一端进行删除的线性表。队尾(rear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出(FIFO),ADT Queue 数据对象：D=ai|ai QElemSet,i=1,2,n,n=0 数据关系：R=|ai-1,ai D,i=2,n 基本操作:InitQueue(&Q)操作结果:构造一个空队列Q DestroyQueue(&Q)初始条件:队列已存在 操作结果:队列Q被销毁，不再存在,抽象数据类型队列的定义,ClearQueue(&Q)初始条件:队列已存在 操作结果:将Q清为空队列Queu
20、eEmpty(Q)初始条件:队列已存在 操作结果:若Q为空队列，返回true,否则返回falseQueueLength(Q)初始条件:队列已存在 操作结果:返回Q的元素个数GetHead(Q,&e)初始条件:队列Q非空 操作结果:用e返回队头元素,EnQueue(&Q,e)/入队 初始条件:队列已存在 操作结果:插入元素e为Q的新队尾元素DeQueue(&Q,&e)/出队 初始条件:队列Q非空 操作结果:删除Q的队头元素，用e返回QueueTraverse(Q,visit()初始条件:队列Q非空 操作结果:从队头到队尾，依次对Q的每个数据元素调 用函数visit().一旦visit()失败，则
21、操作失败ADT Queue,队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，将链队列的类型LinkQueue定义为一个结构类型：,3.4.2 链队列,typedef struct QNode QElemType data;struct QNode*next;QNode,*QueuePtr;,typedef struct QueuePtr front;QueuePtr rear;LinkQueue;,LinkQueue Q;,队列：,出队端,入队端,空队列：,1.构造一个空队
22、列 void InitQueue(LinkQueue/end InitQueue,链队列上实现的基本运算：,2.销毁队列void DestoryQueue(LinkQueue/end while/end DestoryQueue,3.入队void EnQueue(LinkQueue/end EnQueue,4.出队Status DeQueue(LinkQueue/end DeQueue,注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。,3.4.3 循环队列的顺序存储结构和实现（用一维数组实现sqM
23、）,J1,J2,J3,设两个指针front,rear,约定：front指示队头元素；rear指示队尾元素的下一个位置；初值front=rear=0,入队列：sqrear+=x;,空队列条件：front=rear,出队列：x=sqfront+;,存在问题设数组维数为M，则：当front=0,rear=M时，再有元素入队发生溢出真溢出当front0,rear=M时，再有元素入队发生溢出假溢出解决方案队首固定，每次出队后剩余元素向下移动浪费时间循环队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;,实现：利用“模”运算入队：rear=(rear+1)%
24、M;sqrear=x;出队：front=(front+1)%M;x=sqfront;,队空：front=rear,解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间 队空：front=rear 队满：(rear+1)%M=front,队满：front=rear,循环队列类型说明：#define QueueSize 100 typedef Struct int front;int rear;QElemType*base;或QElemType dataQueueSize;SqQueue;,基本操作的算法描述,1.构造空队列void InitQueue(SqQueue,2.返回队列长度
25、int QueueLength(SqQueue Q)Return(Q.rear-Q.front+QueueSize)%QueueSize;,基本操作的算法描述,3.入队Status EnQueue(SqQueue,基本操作的算法描述,4.出队 Status DeQueue(SqQueue,void menu()printf(n*nn);printf(1-EnQueue a data in the Queue.n);printf(2-DeQueue the Queuefront data in the Queue.n);printf(3-PrintFront.n);printf(6-Exit.n
26、);printf(*nn);,void menuselect(SqQueue*Q)int k,done=1;ET e;while(done)menu();printf(please choose:);scanf(%d,void main()SqQueue Q;int i,j;ET e;InitQueue(,必须熟练掌握这些算法.InitQueue(&Q)DestroyQueue(&Q)ClearQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)EnQueue(&Q,e)DeQueue(&Q,&e),循环队列的基本操作,本章小结,理解栈和队列这两种抽象数据类型的特点及与线性表的异同熟悉顺序栈和链栈的组织方法以及基本运算的实现理解递归算法,掌握链队列和循环队列的组织方法、简单算法实现队满、队空的判断条件及其描述,上机作业,1 利用栈实现数制转换，能够实现10进制到2，4，8进制的转换，要求C代码能够运行，严格实现的基本操作。2 编程实现循环队列的基本操作，队列的大小为10，验证队列的正确性，设队列元素是字符。要求C代码能够运行，严格实行队列的基本操作。,
