数据结构第3章栈和队列.ppt

《数据结构第3章栈和队列.ppt》由会员分享，可在线阅读，更多相关《数据结构第3章栈和队列.ppt（80页珍藏版）》请在三一办公上搜索。

1、,特殊线性表,栈,队列,串,逻辑结构,逻辑结构,逻辑结构,物理结构,物理结构,物理结构,顺序栈,链式栈,顺序队列,顺序存储,链式队列,链式存储,栈的定义操作特性ADT定义,队列定义操作特性ADT定义,串的定义操作特性ADT定义,基本操作的实现时间性能,基本操作的实现时间性能,模式匹配,第三章 栈和队列,栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS,“取”操作必须在这端进行,“放”操作必须在同一端进行,3.1 栈（stack）定义：限定仅在表尾进行插入或删除操作的线性表。,表尾栈顶表头栈底不含元素的空表称空栈特点：先进后出（FILO）,抽象数据类型栈的定义,ADT Stack数据

2、对象：Dai|aiElemSet,i=0,1,.,n-1,n0 数据关系：R1|ai-1,aiD,i=1,.,n-1 约定an-1端为栈顶，a0端为栈底。基本操作：InitStack(ADT Stack,3.1.2 栈的表示与实现,顺序栈：是利用一块地址连续的存储单元来存放栈中的元素，同时要利用一个指针top 来指示栈顶元素的位置。,/-栈的顺序存储表示-#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef struct SElemType*base;SElemType*top;int stacksize;SqStack;,

3、顺序栈示意图,初始空栈,*top=*base;stacksize=STACK_INIT_SIZE,顺序栈,栈的几种状态示意图,栈顶指针top,指向实际栈顶后的空位置，初值为0,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow),栈空,Status InitStack(SqStack,在此存储结构下的基本操作实现:,Status Push(SqStack,Status Pop(SqStack,2.链栈（1）链栈的存储结构 链栈是指采用链式存储结构存储的栈。链栈是一种特殊的单链表，即

4、限定仅在表头进行插入和删除操作的单链表，因此链栈的结点结构与单链表的结点结构相同。,top,data next,栈顶,栈底,3.2 栈的应用举例,3.2.1 数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其中一个简单算法基于下列原理:N=(N div d)10d+N mod d例如:(1348)10=283+582+08+4=(2504)8 N N div 8 N mod 81348 168 4 168 21 0 21 25 2 0 2,结果：2 5 0 4,计算时从低位到高位顺序产生八进制数的各个数位,显示时按从高位到低位的顺序输出,void conversion()Init

5、Stack(s);/建空栈 scanf(“%d”,3.2.2 括号匹配的检验假设在表达式中（）或（）等为正确的格式，（）或（）或（）)均为不正确的格式。,则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。,例如：考虑下列括号序列：()1 2 3 4 5 6 7 8,到来的右括弧并非是所“期待”的；到来的是“不速之客”；直到结束，也没有到来所“期待”的括弧,分析可能出现的不匹配的情况:,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。,3）表达式检验结束

6、时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。,Status matching(SELemType*p)int flag=1;SELemType c;Stack1 S;InitStack1(S);while(*p,3.2.3 行编辑程序,行编辑器的功能为：接受用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端进行输入时，不能保证不出差错，所以在编辑程序中，“每接受一个字符即存入用户数据区”的做法不当。因此，在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。如果约定为退格符，以表示前一个字

7、符无效，为退行符，表示当前行所有字符均无效。则whli#ilr#e(s#*s)outchaputchar(*s=#+)应为while(*s)putchar(*s+),字符在存入缓冲区时是按“后进先出”的规律进行的，所以用栈表示输入缓冲区最合适。当从终端接受了一个字符后做如下判断：如果它既不是退格符也不是退行符，则将该字符压入栈顶；如果它是一个退格符，则从栈顶删去一个字符；如果它是一个退行符，则将栈清空。,void LineEdit()InitStack(S);/构造空栈Sch=getchar();/从终端接收第一字符while(ch!=EOF)/EOF为全文结束符 while(ch!=EOF,

8、3.2.4 迷宫求解 入口,出口,迷宫问题：求迷宫中从入口点到出口点所有可能的简单路径,所谓的简单路径是指：在求出的任何一条路径上，不能重现某一通道块，否则总有任意多条路径 迷宫问题是许多实际问题的抽象，求解这类问题时，没有现成的数学公式可以套用，只能采用系统化的试探方法。下面规定：通道用空格“”表示 墙壁用“#”表示 足迹用“0”表示 从入口点到当前立足点间，具有足迹标志的相连的通道块构成的简单路径叫当前路径 将迷宫模型用二维字符型数组表示：char mazen+1n+1;并假定入口为 maze00，出口为 mazenn 考虑一般情况，设 maze i j 为当前立足点，并纳入当前路径（即印

9、上足迹标志“0”），则从当前立足点继续试探的算法如下：,if maze i j 是出口then 打印刚找到的一条简单路径，并回溯一步；else if 东面的是通道块then 前进一步else if 南面的是通道块then 前进一步else if 西面的是通道块then 前进一步else if 北面的是通道块then 前进一步else 回溯一步,(i,j),东,南,西,北,前进一步：将下一通道块印上“0”作为当前立足点（切换当前立足 点），并保存原立足点的信息以便回溯。回溯一步：去掉当前立足点的足迹“0”;把最近的原立足点重新切换为当前立足点；试探尚未试探过的方向。上述的活动均需要在迷宫中移动，

10、并且具有方向性，这种活动可以使用二维数组下标增量技术来实现：行下标增量 di k 列下标增量 dj k 方向及其序号 k 东 0 南 1 西 2 北 3int di4=0,1,0,-1;int dj4=1,0,-1,0;,0,1,1,0,0,1,1,0,在上述的规定下：k=0 时，mazei+dikj+djk 为立足点的东面下一块；k=1 时，mazei+dikj+djk 为立足点的南面下一块；k=2 时，mazei+dikj+djk 为立足点的西面下一块；k=3 时，mazei+dikj+djk 为立足点的北面下一块；客体的表示方法设计：从上述的用试探法走迷宫的过程可知，其中 所管理的信息是

11、立足点的信息。可以用三元组（i,j,k)来表 示立足点，其中(i,j)表示立足点的位置信息，k 表示立足点 的下一个试探方向。可以将三元组定义成一个结构：struct items int i,j,k;数据的组织方法设计：考察上述用试探法走迷宫的过程：前进一步时，需要保存原立足点的信息；回溯一步时，需要取出最近的原立足点的信息，并且遵循 后保存的先取出的原则，即“后进先出”的原则，因此可以用栈 来记录立足点的信息。迷宫问题的算法框架：,1Stack s(sz);/栈初始化：创建一个大小为 sz 的栈，其数据元素类型为 items2items e;int k;3e.i=0;e.j=0;e.k=0;

12、s.Push(e);maze e.i e.j=0;/将入口作为立足点并入栈4while(!s.IsEmpty()/若栈不空则继续循环试探/若空表示已找到所有简单路径，可以结束程序5e=s.Pop();/出栈，准备试探下一方向或实现回溯一步操作6 if(e.k=4)maze e.i e.j=;/四个方向均试探完毕/消足迹,当再执行到 5 时回溯一步 else if(e.i=n,3.2.5 表达式求值1）问题的提出 设计一个小计算器:对键入的表达式进行求值。,高级语言中的赋值语句：变量=表达式；,2）表达式的构成 操作数+运算符+界符（如括号）3）表达式的求值：例 5+6(1+2)-4 按照四则运

13、算法则，上述表达式的计算过程为：5+6(1+2)-4=5+6 3-4=5+18-4=23-4=19,1,2,3,4,运算符和界限符统称为算符。根据算术四则运算的规则（即中缀式的运算规则），任两个相继出现的算符1和2之间的优先关系至多是下面三种关系之一：1 2 1的优先权高于2,算符间的优先关系,2,1,算法需两个栈。一个是运算符栈(OPTR)；另一个是操作数或运算结果栈(OPND)。算法的基本思想是：（1）首先置操作数栈为空栈；为了使表达式中第一个运算符能够进栈，首先将一个优先权最低的运算符#压入运算符栈中成为其栈底。（2）从左向右依次读出表达式中的每一个字符，若为操作数，则将其压入操作数栈中

14、，接着读出下一个字符；若为运算符，则和运算符栈的栈顶运算符比较优先权：如果读出的运算符的优先权高于运算符栈栈顶运算符的优先权，则将其压入运算符栈中，接着读出下一个字符；,如果读出的运算符的优先权等于运算符栈栈顶运算符的优先权（即左右括号相遇），则从运算符栈中退出一个运算符（即左括号）；如果读出的运算符的优先权低于运算符栈栈顶运算符的优先权，则从操作数栈连续退出两个操作数（先退出的是第二操作数，后退出的是第一操作数），从运算符栈中退出一个运算符，然后作相应的运算，并将运算结果压入操作数栈中。算法中还调用了两个函数。其中 Precede()的功能是判断两个运算符1和2的优先关系；Operate()

15、的功能是求两数a和b作运算的结果。,表达式求值示意图：5+6(1+2)-4,#,5,+,6,(,1,+,2,3,18,23,-,4,19,5,读入表达式过程：,+,6,(,1,+,2,),-,4,#,=19,1+2=3,63=18,5+18=23,23-4=19,一个直接调用自己或者通过一系列的调用语句间接地调用自己的函数，称为递归函数。很多数学函数是递归定义的，如阶乘函数 若n=0 若n0 2阶Fibonacci数列 若n=0 若n=1 其他情形,3.3 栈与递归的实现,递归函数执行过程的信息传递和控制转移可以用栈结构来实现。系统将整个程序运行时所需的空间安排在一个栈中，每当调用一个函数时，

16、就为它在栈顶分配一个存储区，每当退出一个函数时，就释放它所占用的存储区，当前工作的函数的数据区总在栈顶。例如，递归函数fact（4）的执行过程如图所示，,例 递归的执行情况分析,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，,递归调用执行情况如下：,Tower of Hanoi问题问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3n。要求将n个圆盘从A移到C，叠放顺序不变，移动过

17、程中遵循下列原则：每次只能移一个圆盘圆盘可在三个塔座上任意移动任何时刻，每个塔座上不能将大盘压到小盘上,解决方法：n=1时，直接把圆盘从A移到Cn1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题,main()/*Hanoi.txt*/int m;printf(Input the number of disks:);scanf(%d,void move(int h,char c,char f)printf(%d:%c-%cn,h,c,f)

18、;,main()int m;printf(Input number of disks”);scanf(%d,(8)(9),main()int m;printf(Input the number of disks scanf(%d,(8)(9),main()int m;printf(Input the number of disks scanf(%d,(8)(9),main()int m;printf(Input the number of disks scanf(%d,(8)(9),回文游戏：顺读与逆读字符串一样（不含空格）,1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依

19、次比较 若不等，非回文 若直到栈空都相等，回文,字符串：“madam im adam”,地图四染色问题,1,2,2,3,4,1,4,3,3,4,2,3,1#紫色 2#黄色3#红色4#绿色,“四染色”定理是计算机科学中著名定理之一，即可以用不多于四色对地图着色，使相邻的行政区域不重色。我们应用这个定理的结论，用回溯算法对一幅给定的地图染色。,算法思想：从第一号行政区开始逐一染色，每一个区域逐次用颜色1、2、3、4进行试探。若当前所取的色数与周围已染色的行政区不重色，则用栈记下该行政区的色数，否则依次用下一色数进行试探；若出现用1至4色均与相邻区域发生重色，则需退栈回溯，修改当前栈顶的色数，再进行

20、试探。直至所有行政区域都已分配合适的颜色。,void main(void)stack_init();push(0,1);while(!stack_empty()pop(x,c);if(c=5)colorx=0;continue;push(x,c+1);if(check(x,c,next)colorx=c;if(next!=-1)push(next,1);else goto end;end:for(x=0;x N;x+)printf(%d,colorx);,int check(int x,int c,int,排队只能排在尾部,排在对头的先得到服务;“插队”是不允许的.换言之,插入和删除只能在线性

21、表的两头分别进行;插入的一端称为队尾,删除的一端称为队头;其特点是:先进先出(FIFO),队列(Queues)是生活中“排队”的抽象,3.4 队列,抽象数据类型队列的定义ADT Queue数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：R1|ai-1,aiD,i=2,.,n 约定其中a1端为队列头,an端为队列尾基本操作：InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)ADT Queue,队列的顺序存储结构,J1,J2,J3,设两个指针front、rea

22、r，约定：rear指示队尾元素的下一个位置；front指示队头元素；初值front=rear=0,空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;,rear,J4,J5,J6,front,J7,J8,J9入队,溢出,存在问题：设分配的空间为M，则：当front=0,rear=M时，再有元素入队发生溢出真溢出当front0,rear=M时，再有元素入队发生溢出假溢出,解决方案队首固定，每次出队剩余元素向下移动,实现：利用“模”运算入队：rear=(rear+1)%M;sqrear=x;出队：front=(front+1)%M;x=sqfront;队满、队

23、空判定条件,循环队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;,浪费时间,初始状态,解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front=rear 队满：(rear+1)%M=front,队空：front=rear队满：front=rear,循环队列队列的顺序存储结构#define MAXQSIZE 100/最大队列长度typedef struct QElemType*base;/动态分配存储空间 int front;/头指针，若队列不空，指向队列头元素 int rear;/尾指针，若队列不空，指向队列尾元素的下

24、一个位置SqQueue;,Status InitQueue(SqQueue,int QueueLength(SqQueue Q)/求队列的长度 return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;,Status QueueEmpty(SqQueue Q)/判队列是否为空 if(Q.front=Q.rear)return ERROR;else return OK;,Status EnQueue(SqQueue,Status DeQueue(SqQueue,(a)空链队列,链队列,3.4.2 链队列-队列的链式表示与实现,(b)元素x入队列,(c)元素y入队列,(d)

25、元素x出队列,链队列存储结构的C语言描述:,typedef struct QNodeQElemType data;struct QNode*next;QNode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;,1）队列初始化运算,Status InitQueue(LinkQueue*Q)Q-front=Q-rear=(QueuPtr)malloc(sizeof(QNode);if(!Q-front)exit(OVERFLOW);Q-front-next=NULL;return OK;,2）队列入队运算 将结点加入

26、到队列Q的尾端,Status EnQuene(LinkQueue,3）队列出队运算 将队头元素删除,Status DeQueue(LinkQueue,当只有一个元素时，要修改尾指针,1）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源竞争问题；,3）离散事件的模拟-模拟实际应用中的各种排队现象；4）用于处理程序中具有先进先出特征的过程；,在操作系统课程中会讲到,队列的应用,队列的应用 理发店问题模拟仿真,理发店问题模拟仿真（问题分析）,K个理发师一条长凳（L个位置）n多顾客顾客随机来到，服务时间也不一样能否通过计算机仿真来得到：平均等待时间？服务策略是否最优？,三种不同的策略,先

27、到先服务小人物优先时间片轮转服务,问题：,顾客如何表达？顾客流如何表达？模拟服务流程如何实现？,队列的应用 理发店问题模拟仿真,struct int inTime;int servTime;int waitTime;C;,=t+rand()%20;,=minServeTime+R%(maxServeTime-minServeTime),chairs,Customer Queue,队列的应用 顾客流生成,Act as a Timer,本章学习要点1.掌握栈和队列类型的特点，并能在相应的应用问 题中正确选用它们。2.熟练掌握栈类型的两种实现方法，特别应注意栈 满和栈空的条件以及它们的描述方法。3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。4.理解递归算法执行过程中栈的状态变化过程。,