数据结构三章栈和队列.ppt

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

1、数据结构第三章栈和队列,本章内容3.1 栈3.2 栈的应用举例3.3 队列,3-3,3.1 栈,3.1.1 栈的定义栈（stack）：是限定仅在表尾进行插入和删除操作的线性表。又称为后进先出（last in first out）的线性表（简称LIFO结构）。栈顶（top）：栈表尾端。栈底（bottom）：栈表头端。例：假设栈 S=(a1,a2,an)，则 a1 称为栈底元素，an 为栈顶元素。栈中元素按a1,a2,an 的次序进栈，退栈的第一个元素应为栈顶元素。如右图所示。,3-4,3.1 栈,3.1.2 栈的顺序存储结构定义：顺序栈（即栈的顺序存储结构）：是利用一组地址连续的存储单元依次存放

2、自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。C语言描述typedef struct stack_tag elemtype*elem;/指向存放数据元素的内存块 int top;/栈顶标识，elemtop是栈顶元素 int size;/栈的容量 SQSTACK;图形表示,3-5,3.1 栈,初始化栈int InitSqstack(SQSTACK*S,int n)/初始化顺序栈，栈的容量是n。成功则返回1，否则返回0 S-elem=(elemtype*)malloc(n*sizeof(elemtype);/为数据元素分配内存 if(S-elem=NULL)return

3、0;/初始化失败 S-size=n;/设置栈的容量 S-top=-1;/设置栈为空栈 return 1;销毁栈void DestroySqstack(SQSTACK*S)/释放栈所占有的内存 free(S-elem);/释放内存，并设置为NULL S-elem=NULL;S-top=-1;/将其他成员设置成安全值 S-size=0;,3-6,3.1 栈,入栈int Push(SQSTACK*S,elemtype e)/在栈顶一端插入数据元素e，操作成功，则返回1，否则返回0 if(IsSqstackFull(*S)return 0;/栈满，操作失败 S-top+;/top增1 S-elemS-

4、top=e;/将e赋值成新的栈顶 return 1;出栈int Pop(SQSTACK*S,elemtype*e)/获取栈顶数据元素，并删除栈顶。操作成功，则返回1，否则返回0 if(IsSqstackEmpty(*S)return 0;/如果栈空，操作失败*e=S-elemS-top;/获取栈顶元素 S-top-;/删除栈顶 return 1;,3-7,3.1 栈,判断栈空、栈满int IsSqstackEmpty(SQSTACK S)/如果栈空，则返回1，否则返回0 return S.top=-1;/top是栈顶标识，是-1时表示空栈int IsSqstackFull(SQSTACK S)

5、/如果栈满，则返回1，否则返回0 return S.top=S.size-1;/top作为elem的下标，其最大值是size-1,3-8,3.1 栈,3.1.3 栈的链式存储结构,3-9,3.2 栈的应用举例,3.2.1 数制转换十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个是辗转相除法：N=(N div d)d+N mod d（其中：div为整除运算，mod为求余运算）,由于计算过程是从低位到高位顺序产生八进制数的各个数位，而输出应从高位到低位进行，恰好和计算过程相反。因此，若计算过程中得到八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进

6、制数。,例如：(1348)10(2504)8，其运算过程如下：NN div 8 N mod 8 1348/168 余 4,168/21 余 0,21/2 余 5,2/0 余 2,3-10,3.2 栈的应用举例,算法3.1如下：void conversion()/输入一个非负十进制整数，转换成八进制数。InitStack(S);/构造空栈scanf(“%d”,N);while(N)Push(S,N%8);N=N/8;while(!StackEmpty(s)Pop(S,e);printf(“%d”,e);/conversion,3-11,3.2 栈的应用举例,3.2.2 迷宫路径求解【任务描述】给

7、定某个迷宫的布局及其入口和出口的坐标（如图3_9所示，注意横坐标是从左向右的，但是纵坐标是从上向下的），迷宫中空白的地方可以走，阴影的部分表示墙壁，走不通。设计算法找出从入口到出口的所有路径。需要解决2个问题：迷宫在计算机中如何表示。int maze 12=1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,1,0,0,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,0,0,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1;如何探

8、索从入口到达出口的所有路径。深度优先探索+回溯：从当前位置出发，向四个方向探索，如果发现某方向的相邻位置可走，则走过去，将那个位置当作当前位置继续探索。这时需要将原当前位置保存在栈中。如果四个方向都走不通，则退回到出发点（栈顶中的位置）。走过的地方要打上“已走标记”，回退时要将“已走”标记清除。,3-12,3.2 栈的应用举例,typedef struct int x,y;/位置坐标 int v;/探索方向 elemtype;int movex5=0,0,1,0,-1;int movey5=0,-1,0,1,0;#define M 27#define N 25#define MAXSIZE 2

9、00算法：void go(int mazeMN,int x0,int y0,int xx,int yy)/找出maze中从入口(x,y)到出口(xx,yy)的所有路径 int x,y,x1,y1,v;SQSTACK s;/存放探索路径的栈 elemtype e;InitSqstack(/初始化栈,3-13,3.2 栈的应用举例,e.x=x0;e.y=y0;e.v=0;Push(/换一个方向继续探索,while(v0/(x1,y1)不通，换一个方向探索/while循环结束时，说明(x,y)的4个方向都探索过了，应该回退一步/while stack,3-14,3.2 栈的应用举例,3.2.3 斐波

10、那契问题【任务描述】斐波那契序列中第n项的递归定义如下，设计算法求得第n项斐波那契序列项的值。【递归算法】int Fibo(int n)/斐波那契序列项求解的递归算法 int val;if(n=1|n=2)return 1;/到达递归终点 val=Fibo(n-1)+Fibo(n-2);/递归调用 return val;,3-15,3.2 栈的应用举例,斐波那契问题非递归算法首先将问题Fibo(n)入栈。接着进入一个循环：弹出栈顶问题，如果是递归终点，则求值累加；否则将Fibo(n)递归分解为Fibo(n-1)和Fibo(n-2)，并将它们分别入栈，直到栈空为止。适用条件由P(n)递归分解产生

11、两个问题规模更小的问题P(n1)和P(n2)，它们的求解相互独立，相互之间不构成求解条件。,3-16,3.2 栈的应用举例,递归问题的非递归算法设计中栈的作用保存暂时不能求解的问题，等待条件具备时，再将问题出栈进行求解。被保存的问题，通常是递归分解的结果。,3-17,3.2 栈的应用举例,int Fibonacci(int n)/*非递归算法*/SQSTACK s;int val=0,k;InitSqstack(,3-18,3.3 队列,3.3.1 队列的定义队列（queue）：是一种先进先出（first in first out，缩写为FIFO）的线性表。它只允许在表的一端进行插入，而在另一

12、端删除元素。,3-19,3.3 队列,3.3.2 队列的顺序存储结构定义：队列的顺序存储结构：是利用一组地址连续的存储单元依次存放从队列头到队列尾的数据元素，同时附设指针front 和 rear分别指示队列头元素及队列尾元素的位置。图形表示,(a)空队列(b)J1、J2和J3相继入队列(c)J1和J2相继被删除(d)J4、J5和J6相继插入队列之后J3和J4被删除,3-20,3.3 队列,数据类型定义：typedef struct elemtype*elem;/*指向存放队列数据元素的数组*/int front,rear;/*分别是队首和队尾下标，也称为队首指针和队尾指针*/int size;

13、/*数组elem的容量*/SQQUEUE;基本操作初始化空队int InitSqqueue(SQQUEUE*q,int n)/初始化，容量设为n。成功返回1，否则返回0，容量为n的顺序队列，需要容量是n+1数组 q-elem=(elemtype*)malloc(n+1)*sizeof(elemtype);if(q-elem=NULL)return 0;/操作失败 q-front=q-rear=0;/队首指针、队尾指针都归零 q-size=n+1;/设置容量 return 1;,3-21,3.3 队列,销毁队列void DestroySqqueue(SQQUEUE*q)/销毁队列 free(q-

14、elem);/释放队列所占内存 q-elem=NULL;/将其他成员设置成安全值 q-front=q-rear=0;q-size=0;判断队空int IsSqqueueEmpty(SQQUEUE q)/如果队空，则返回1，否则返回0 return q.front=q.rear;,3-22,3.3 队列,入队int EnSqqueue(SQQUEUE*q,elemtype e)/将数据元素e入队，操作成功返回1，否则返回0 if(IsSqqueueFull(*q)return 0;q-elemq-rear=e;/将e放置在队列中 q-rear=(q-rear+1)%q-size;/队尾指针向后移

15、动 return 1;判断队满int IsSqqueueFull(SQQUEUE q)/如果队满，则返回1，否则返回0 return q.front=(q.rear+1)%q.size;,3-23,3.3 队列,出队int DeSqqueue(SQQUEUE*q,elemtype*e)/将队首元素复制给*e,操作成功返回1，否则返回0 if(IsSqqueueEmpty(*q)return 0;/如果队空，操作失败*e=q-elemq-front;/复制队首元素 q-front=(q-front+1)%q-size;/队首指针向后移动 return 1;获得队列长度int SqqueueLen

16、(SQQUEUE q)/返回队列长度 return(q.size+q.rear-q.front)%q.size;,3-24,3.3 队列,3.3.3 链式队列数据类型定义：typedef struct node_tag elemtype data;struct node_tag*next;NODE,*NODEPTR;/*定义单链表结点和指针类型*/typedef struct NODEPTR front,rear;/*队首队尾指针*/LKQUEUE;基本操作：1初始化空队void InitLkqueue(LKQUEUE*Q)Q-front=Q-rear=NULL;,3-25,3.3 队列,销毁

17、队列void DestroyLkqueue(LKQUEUE*Q)NODEPTR p;while(Q-front!=NULL)p=Q-front;Q-front=p-next;/*摘除队首结点*/free(p);Q-rear=NULL;,3-26,3.3 队列,入队int EnLkqueue(LKQUEUE*Q,elemtype e)NODEPTR p;p=(NODEPTR)malloc(sizeof(NODE);if(p=NULL)return 0;p-data=e;p-next=NULL;if(Q-front=NULL)/如果队空，则将队首队尾指针都指向结点p Q-front=Q-rear=

18、p;else/否则将结点p插入到队尾结点后面 Q-rear-next=p;Q-rear=p;return 1;,3-27,3.3 队列,出队int DeLkqueue(LKQUEUE*Q,elemtype*e)NODEPTR p;if(Q-front=NULL)return 0;p=Q-front;Q-front=p-next;if(Q-front=NULL)Q-rear=NULL;/如果队空，则将队尾指针置NULL*e=p-data;free(p);return 1;,3-28,3.3 队列,队列的应用举例【举例1】汽车加油站。随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车

19、加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加2个队列。,3-29,3.3 队列,【举例2】模拟打印机缓冲区。在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，

20、而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。,3-30,3.3 队列,【举例3】CPU分时系统 在一个带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使CPU正常工作。,3-31,习题,本章习题参见教师网页：http:/,