数据结构第三章栈和队列ppt课件

1、 数据结构课程本章内容3.1 栈3.2 栈的运用举例3.3 队列中国科大数据结构3.1 栈3.1.1 3.1.1 栈的定义栈的定义栈栈stackstack：是限定仅在表尾进展插入和删除操作的线性表。又称为：是限定仅在表尾进展插入和删除操作的线性表。又称为后进先出后进先出last in first outlast in first out的线性表简称的线性表简称LIFOLIFO构造。构造。栈顶栈顶toptop：栈表尾端。：栈表尾端。栈底栈底bottombottom：栈表头端。：栈表头端。例：假设栈例：假设栈 S=(a1,a2,an) S=(a1,a2,an) ，那么，那么 a1 a1 称称为栈底

2、元素，为栈底元素，an an 为栈顶元素。栈中元素按为栈顶元素。栈中元素按a1,a2,an a1,a2,an 的次序进栈，退栈的第一个元的次序进栈，退栈的第一个元素应为栈顶元素。如右图所示。素应为栈顶元素。如右图所示。 出栈出栈 进栈进栈 栈顶栈顶 an . . . a2 栈底栈底 a1 栈的表示图栈的表示图中国科大数据结构3.1 栈3.1.2 3.1.2 栈的顺序存储构造栈的顺序存储构造定义：顺序栈即栈的顺序存储构造：是利用一组地址延续的存储定义：顺序栈即栈的顺序存储构造：是利用一组地址延续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针单元依次存放自栈底到栈顶的数据元素，同时附设指针

3、toptop指示栈指示栈顶元素在顺序栈中的位置。顶元素在顺序栈中的位置。C C言语描画言语描画typedef struct stack_tag typedef struct stack_tag elemtype elemtype * *elem; /elem; /指向存放数据元素的内存块指向存放数据元素的内存块 int top; /int top; /栈顶标识，栈顶标识，elemtopelemtop是栈顶元素是栈顶元素 int size; /int size; /栈的容量栈的容量 SQSTACK;SQSTACK;图形表示图形表示topbottomtopbottomtopbottomAABCDE

4、栈的顺序存储构造表示图栈的顺序存储构造表示图 中国科大数据结构3.1 栈p初始化栈初始化栈pint InitSqstack(SQSTACK *S, int n)p /初始化顺序栈，栈的容量是初始化顺序栈，栈的容量是n。胜利那么前往。胜利那么前往1，否那么前往，否那么前往0p S-elem=(elemtype *)malloc(n*sizeof(elemtype); /为数据元素分配内存为数据元素分配内存p if (S-elem=NULL) return 0; /初始化失败初始化失败p S-size=n; /设置栈的容量设置栈的容量p S-top=-1; /设置栈为空栈设置栈为空栈p retur

5、n 1;p p销毁栈销毁栈pvoid DestroySqstack(SQSTACK *S)p /释放栈所占有的内存释放栈所占有的内存p free(S-elem); /释放内存，并设置为释放内存，并设置为NULLp S-elem=NULL;p S-top=-1; /将其他成员设置成平安值将其他成员设置成平安值p S-size=0;p中国科大数据结构3.1 栈p入栈入栈pint Push(SQSTACK *S,elemtype e)p /在栈顶一端插入数据元素在栈顶一端插入数据元素e，操作胜利，那么前往，操作胜利，那么前往1，否那么前往，否那么前往0p if (IsSqstackFull(*S)r

6、eturn 0; /栈满，操作失败栈满，操作失败p S-top+; /top增增1p S-elemS-top=e; /将将e赋值成新的栈顶赋值成新的栈顶p return 1;pp出栈出栈pint Pop(SQSTACK *S,elemtype *e)p /获取栈顶数据元素，并删除栈顶。操作胜利，那么前往获取栈顶数据元素，并删除栈顶。操作胜利，那么前往1，否那么前往，否那么前往0p if (IsSqstackEmpty(*S) return 0; /假设栈空，操作失败假设栈空，操作失败p *e=S-elemS-top; /获取栈顶元素获取栈顶元素p S-top-; /删除栈顶删除栈顶p retu

7、rn 1;p中国科大数据结构3.1 栈p判别栈空、栈满判别栈空、栈满pint IsSqstackEmpty(SQSTACK S)p /假设栈空，那么前往假设栈空，那么前往1，否那么前往，否那么前往0p return S=-1; /top是栈顶标识，是是栈顶标识，是-1时表示空栈时表示空栈ppint IsSqstackFull(SQSTACK S)p /假设栈满，那么前往假设栈满，那么前往1，否那么前往，否那么前往0p return S=S.size-1; /top作为作为elem的下标，其最大值是的下标，其最大值是size-1 p中国科大数据结构3.1 栈3.1.3 栈的链式存储构造栈的链式存

8、储构造 data next S 栈顶栈顶 栈底栈底 链栈表示图链栈表示图 中国科大数据结构3.2 栈的运用举例3.2.1 数制转换数制转换十进制数十进制数N和其他和其他d进制数的转换是计算机实现计算的根本问进制数的转换是计算机实现计算的根本问题，其处理方法很多，其中一个是辗转相除法：题，其处理方法很多，其中一个是辗转相除法： N = ( N div d ) d + N mod d 其中：其中：div为整除运算，为整除运算，mod为为求余运算求余运算由于计算过程是从低位到高位顺序产生八进制数的各个数由于计算过程是从低位到高位顺序产生八进制数的各个数位，而输出应从高位到低位进展，恰好和计算过程相反

9、。因此，假位，而输出应从高位到低位进展，恰好和计算过程相反。因此，假设计算过程中得到八进制数的各位顺序进栈，那么按出栈序列打印设计算过程中得到八进制数的各位顺序进栈，那么按出栈序列打印输出的即为与输入对应的八进制数。输出的即为与输入对应的八进制数。 例如：例如：(1348)10(2504)8，其运算过程如下：，其运算过程如下：NN div 8 N mod 8 1348 / 168 余余 4 168 / 21 余 0 21 / 2 余 5 2 / 0 余 2中国科大数据结构3.2 栈的运用举例p算法算法3.1如下：如下：p void conversion ( ) /输入一个非负十进制整数，转换成

10、八进输入一个非负十进制整数，转换成八进制数。制数。pInitStack (S); /构造空栈构造空栈pscanf (“%d, N);pwhile (N) pPush (S, N%8);pN = N / 8;ppwhile (!StackEmpty(s) pPop (S, e);pprintf (“%d, e);pp /conversion中国科大数据结构3.2 栈的运用举例3.2.2 迷宫途径求解迷宫途径求解【义务描画】给定某个迷宫的规划及其入口和出口的坐标如图【义务描画】给定某个迷宫的规划及其入口和出口的坐标如图3_9所示，留所示，留意横坐标是从左向右的，但是纵坐标是从上向下的，迷宫中空白的

11、地方意横坐标是从左向右的，但是纵坐标是从上向下的，迷宫中空白的地方可以走，阴影的部分表示墙壁，走不通。设计算法找出从入口到出口的一可以走，阴影的部分表示墙壁，走不通。设计算法找出从入口到出口的一切途径。需求处理切途径。需求处理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

12、,0,0,0,1, 1,1,1,1,1,1,1,1,1,1,1,1 ;如何探求从入口到达出口的一切途径。如何探求从入口到达出口的一切途径。 深度优先探求深度优先探求+回溯：从当前位置出发，向四个方向探求，假设发现某方回溯：从当前位置出发，向四个方向探求，假设发现某方向的相邻位置可走，那么走过去，将那个位置当作当前位置继续探求。这向的相邻位置可走，那么走过去，将那个位置当作当前位置继续探求。这时需求将原当前位置保管在栈中。假设四个方向都走不通，那么退回到出时需求将原当前位置保管在栈中。假设四个方向都走不通，那么退回到出发点栈顶中的位置。走过的地方要打上发点栈顶中的位置。走过的地方要打上“已走标志

13、，回退时要将已走标志，回退时要将“已已走标志去除。走标志去除。0 1 2 3 4 5 6 7 8 901234入口(1,5)(8,1)出口10 1165中国科大数据结构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 200算法：void go(int mazeMN ,int x0,int y0 ,int xx ,int yy) /找出maze中从入口(x

14、,y)到出口(xx,yy)的一切途径 int x,y,x1,y1,v; SQSTACK s; /存放探求途径的栈 elemtype e; InitSqstack(&s,MAXSIZE); /初始化栈初始化栈将入口位置信息(x,y,0)入栈v0) /这次出栈是回退操作，去除原探求位置的已走标志 mazey+moveye.vx+movexe.v=0; while(v=4) /*按照顺时针顺序探求4个方向*/ x1=x+movexv; y1=y+moveyv; /获取当前位置(x,y)v方向的相邻位置坐标(x1,y1) if (x1=xx&y1=yy) /遇到出口 输出存放在s中的途

15、径 /*这条指令不是C语句*/ V+; /换一个方向继续探求 while(v0&x10&y1elem=(elemtype q-elem=(elemtype * *)malloc(n+1)malloc(n+1)* *sizeof(elemtype);sizeof(elemtype);p if(q-elem=NULL)return 0; / if(q-elem=NULL)return 0; /操作失败操作失败p q-front=q-rear=0; /q-front=q-rear=0; /队首指针、队尾指针都归零队首指针、队尾指针都归零p q-size=n+1; /q-size=n+

16、1; /设置容量设置容量p return 1; return 1; 中国科大数据结构3.3 队列p销毁队列销毁队列pvoid DestroySqqueue(SQQUEUE *q)p /销毁队列销毁队列p free(q-elem); /释放队列所占内存释放队列所占内存p q-elem=NULL; /将其他成员设置成平安值将其他成员设置成平安值p q-front=q-rear=0;p q-size=0;p p判别队空判别队空pint IsSqqueueEmpty(SQQUEUE q)p /假设队空，那么前往假设队空，那么前往1，否那么前往，否那么前往0p return q.front=q.rear

17、;p 中国科大数据结构3.3 队列p入队入队pint EnSqqueue(SQQUEUE *q, elemtype e)p /将数据元素将数据元素e入队，操作胜利前往入队，操作胜利前往1，否那么前往，否那么前往0p if(IsSqqueueFull(*q)return 0;p q-elemq-rear=e; /将将e放置在队列中放置在队列中p q-rear=(q-rear+1)%q-size; /队尾指针向后挪动队尾指针向后挪动p return 1;p p判别队满判别队满pint IsSqqueueFull(SQQUEUE q)p /假设队满，那么前往假设队满，那么前往1，否那么前往，否那么前

18、往0p return q.front=(q.rear+1)%q.size;p 中国科大数据结构3.3 队列p出队出队pint DeSqqueue(SQQUEUE *q, elemtype *e)p /将队首元素复制给将队首元素复制给*e,操作胜利前往操作胜利前往1，否那么前往，否那么前往0p if(IsSqqueueEmpty(*q)return 0; /假设队空，操作失败假设队空，操作失败p *e=q-elemq-front; /复制队首元素复制队首元素p q-front=(q-front+1)%q-size; /队首指针向后挪动队首指针向后挪动p return 1;p p获得队列长度获得队

19、列长度pint SqqueueLen(SQQUEUE q)p /前往队列长度前往队列长度p return (q.size+q.rear-q.front)%q.size; p中国科大数据结构3.3 队列3.3.3 链式队列链式队列数据类型定义：数据类型定义：typedef struct node_tag elemtype data; struct node_tag *next; NODE, *NODEPTR; /*定义单链表结点和指针类型定义单链表结点和指针类型*/typedef struct NODEPTR front,rear;/*队首队尾指针队首队尾指针*/ LKQUEUE;根本操作：根本

20、操作：1初始化空队初始化空队void InitLkqueue(LKQUEUE *Q) Q-front=Q-rear=NULL; 中国科大数据结构3.3 队列p销毁队列销毁队列pvoid DestroyLkqueue(LKQUEUE *Q)p NODEPTR p;p while(Q-front!=NULL)p p=Q-front;p Q-front=p-next; /*摘除队首结点摘除队首结点*/p free(p);p p Q-rear=NULL;p 中国科大数据结构3.3 队列p入队入队pint EnLkqueue(LKQUEUE int EnLkqueue(LKQUEUE * *Q,elem

21、type e)Q,elemtype e)p NODEPTR p; NODEPTR p;p p=(NODEPTR)malloc(sizeof(NODE); p=(NODEPTR)malloc(sizeof(NODE);p if(p=NULL)return 0; if(p=NULL)return 0;p p-data=e; p-data=e;p p-next=NULL; p-next=NULL;p if(Q-front=NULL) / if(Q-front=NULL) /假设队空，那么将队首队尾指针都指向结点假设队空，那么将队首队尾指针都指向结点p pp Q-front=Q-rear=p; Q-f

22、ront=Q-rear=p;p else elsep / /否那么将结点否那么将结点p p插入到队尾结点后面插入到队尾结点后面p Q-rear-next=p;Q-rear-next=p;p Q-rear=p; Q-rear=p;p p return 1; return 1;p 中国科大数据结构3.3 队列p出队出队pint DeLkqueue(LKQUEUE *Q,elemtype *e)p NODEPTR p;p if(Q-front=NULL)return 0;p p=Q-front;p Q-front=p-next;p if(Q-front=NULL)Q-rear=NULL; /假设队空

23、，那么将队尾指针置假设队空，那么将队尾指针置NULLp *e=p-data;p free(p);p return 1;p 中国科大数据结构3.3 队列p队列的运用举例队列的运用举例p【举例【举例1 1】汽车加油站。】汽车加油站。p 随着城市里汽车数量的急速增长，汽车加油站也渐随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的构造根本上是：入口和出口为单行渐多了起来。通常汽车加油站的构造根本上是：入口和出口为单行道，加油车道能够有假设干条。每辆车加油都要经过三段路程，第道，加油车道能够有假设干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加

24、油车道排队一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候分开。实践上，这三段都等候加油；第三段是进入出口处排队等候分开。实践上，这三段都是队列构造。假设用算法模拟这个过程，就需求设置加油车道数加是队列构造。假设用算法模拟这个过程，就需求设置加油车道数加2 2个队列。个队列。中国科大数据结构3.3 队列n【举例【举例2 2】模拟打印机缓冲区。】模拟打印机缓冲区。n 在主机将数据输出到打印机时，会出现主机速度在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的运用效率。为此人们想象了打印机