数据结构zmz4栈和队列

1、数据结构大家好 第三章 栈和队列1Park manage2Park manage3Park manage4Park manage5Park manage61、停车场特点先进后出，2、如何存储3、数据操作：进场，出场Park manage7Railway Switching Network8Railway Switching Network9123银行业务模拟10银行业务模拟123111、其特点是先进先出2、如何存储3、数据操作：到达，离开，求队长等银行业务模拟12312栈和队列是两种特殊的线性表是操作受限的线性表，称限定性数据结构限定插入和删除只能在表的“端点”进行的线性表 线性表 栈 队列I

2、nsert(L, i, x) Insert(St, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(St, n) Delete(Q, 1) 1ina1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an)ana1a2.出栈进栈栈st=(a1,a2,an)13 栈（stack）栈的逻辑结构栈的存储结构栈的应用14 栈的逻辑结构栈的定义和特点定义：特殊的线性表，所有的操作限定仅在表尾进行表尾栈顶(top)，表头栈底(bottom)，不含元素的空表称空栈特点：先进后出（FILO）ana1a2.栈底栈顶.出栈进栈栈st=(a1

3、,a2,an)栈的运算：建空栈 取栈顶元素 入栈 出栈15基本操作：InitStack(&S)操作结果：构造一个空栈 SDestroyStack(&S)初始条件：栈 S 已存在操作结果：栈 S 被销毁StackEmpty(S)初始条件：栈 S 已存在操作结果：空栈，返回 TRUE;否则 FALSEStackLength(S)初始条件：栈 S 已存在操作结果：返回 S 的元素个数，即栈的长度ClearStack(&S)初始条件：栈 S 已存在操作结果：将 S 清为空栈栈的抽象数据类型定义16基本操作：GetTop(S, &e)初始条件：栈 S 已存在且非空操作结果：用 e 返回 S 的栈顶元素P

4、ush(&S, e)初始条件：栈 S 已存在操作结果：插入元素 e 为新的栈顶元素Pop(&S, &e)初始条件：栈 S 已存在且非空操作结果：删除 S 的栈顶元素，并用 e 返回其值StackTraverse(S, visit()初始条件：栈 S 已存在且非空操作结果：依次对S 的每个元素调用函数visit()栈的抽象数据类型定义17栈的存储结构顺序栈链栈18实现：用一维数组aStackSizetop=-1123450栈空栈顶指针top,指向实际栈顶的位置，初值为-1top123450入栈Atop出栈栈满BCDEF设数组大小为mtop=-1,栈空，此时出栈，则下溢top=StackSize-

5、1,栈满，此时入栈，则上溢123450ABCDEFtoptoptoptoptoptop栈空st+top=ex=sttop-栈的顺序存储结构顺序栈19#define StackSize 50typedef struct int top; int aStackSize; SqStack; SqStack S;/*假设数据元素为整型变量*/void InitStack(SqStack S) s.top= -1 ;建立空栈：123450top=-1栈的基本操作在顺序栈中的实现20Status Push(SqStack s , int e) if(s.top=StackSize-1) /栈满 print

6、f(“栈满”); return false; s.top+; s.aS.top=e; s.a+S.top=e; return true;元素e入栈：123450ABCDtopEtop栈的基本操作在顺序栈中的实现算法时间复杂度：O(1)21status Pop( SqStack s，int &x ) if(s.top = -1) /栈空,则无法出栈 printf(“栈已空！”)； return false; x =s.as.top; s.top - -; x= s.as.top-; return true;元素出栈：123450ABCDtopEtop栈的基本操作在顺序栈中的实现算法时间复杂度：O

7、(1)22ABCDE操作序列：出栈序列： 元素A入栈A A 元素B入栈B B 元素C入栈C C能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE？栈的基本操作在顺序栈中的实现23 DE操作序列：出栈序列： 元素A入栈A 元素B入栈B 元素C入栈 元素C出栈CC 元素B出栈B能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE？栈的基本操作在顺序栈中的实现24 DE操作序列：出栈序列： 元素A入栈A 元素B入栈 元素C入栈 元素C出栈C 元素B出栈B 元素D入栈D D 元素D出栈D 元素A出栈A能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE？栈的基本操作在顺序栈中的实现25

8、E操作序列：出栈序列： 元素A入栈 元素B入栈 元素C入栈 元素C出栈C 元素B出栈B 元素D入栈 元素D出栈D 元素A出栈A 元素E入栈EE 元素E出栈E能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE？栈的基本操作在顺序栈中的实现可以得到26栈的基本操作在顺序栈中的实现思考题：请同学完成以下出栈序列的运算1. B,D,C,E,A2. C,B,A,D,E3. C,D,B,E,A4. A,C,E,D,B27按a,b,c,d顺序进栈，有几种出栈序列？复习栈的概念思考题：请同学完成以下出栈序列的运算1. B,D,E,C,A2. C,D,A,B,E3. A,C,B,D,E4. B,E,C,A

9、,D栈的逻辑结构有什么特点？28anan-1 .a2a1顺序栈栈底栈顶h栈的链式存储an an-1 a1a2 思考 链栈是否需要另外设置头指针？ 建立链栈适合用哪种插入法？ 链栈的基本操作的实现。top栈的链式存储结构链栈29结点定义typedef struct int data; struct StackNode *next;StackNode, *LinkStack;栈顶 .top栈底anan-1a1an-2栈的链式存储结构链栈30入栈算法topep核心三步： p-data= e; p-next= S.top; S.top=p; 栈的链式存储结构链栈栈顶 .栈底ana1an-1top栈顶算

10、法时间复杂度：O(1)31出栈算法top栈的链式存储结构链栈栈顶p栈顶top .栈底anan-1a1an-2核心三步： p=S.top; （e=p-data; ） S.top=p-next; free(p);算法时间复杂度：O(1)32栈的应用函数的嵌套调用递归的实现回文游戏递归函数汉诺塔问题斐波那契数列多进制转换括号匹配的检验迷宫问题地图四染色表达式求值行编辑程序33紫色 黄色红色绿色Stack栈的应用地图四染色问题34A B C D E F G 1223414334231# 紫色 2# 黄色3# 红色4# 绿色回溯法ABDEFGC栈的应用地图四染色问题35寻找一条从入口到出口的通路。812

11、3456781234567前进方向： 上(北)、下(南)、左(西)、右(东)东南北西 走步规则：首先从向下开始，按照逆时针方向搜索下一步可能前进的位置入口出口栈的应用迷宫问题36栈8123456781234567(1,1)i(2,1)i(3,1)i(4,1)i(5,1)i(6,1)(7,1)i穷举求解栈的应用迷宫问题回溯法深度优先搜索37栈8123456781234567(1,1)i(2,1)i(3,1)i(4,1)i(5,1)i(6,1)(7,1)i (5,2)i(5,3)i(6,3)i(6,4)i(8,8)iiiiii栈的应用迷宫问题回溯法深度优先搜索穷举求解38 八皇后问题，是一个古老而

12、著名的问题，是回溯算法的典型例题。 该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，问有多少种摆法。八皇后问题高斯认为有76种方案。1854年在柏林不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。39农夫带一只狼、一只羊和一棵白菜在河的南岸需要全部转运到北岸农夫过河问题40条件：一条小船只能容下农夫和一件物品只有农夫能撑船当农夫不在时狼会吃羊，羊也会吃白菜农夫过河问题41问：怎么才能安全地过河？农夫过河问题42农夫过河问题43void main() int a,b,sum; . . sum = add(a,b); .in

13、t add(int x, int y) int sum; sum=square(x+y); return sum;int square(int x) return x*x;main主程序addmainmainmainadd函数1mainaddsquare函数2mainaddsquare栈的应用函数嵌套调用函数嵌套调用规则:后调用的函数先返回内存管理实行“栈式管理”44例 数字金字塔 (w=3)void jzt(int w) int i; if ( w!=0) jzt(w-1); for(i=1;i0T(n)=O(2n)47相传在很久很久以前，在中东地区的一个寺庙里，几个和尚整天不停地移动着64

14、个盘子，日复一日，年复一年，移盘不止。移盘的规则是：。据说当所有64个盘子全部移完的那一天是世界的末日ABC每次只能移一个圆盘圆盘可在三个塔座上任意移动任何时刻不能将大盘压到小盘上Tower of Hanoi栈的应用递归实现 按直径从小到大叠放，形如宝塔48 求解思路ABC?49 求解思路ABCOk!50ABC 求解思路?51ABC 求解思路52ABC 求解思路53ABC 求解思路Ok!递归54 算法void hanoi(int n,char A,char B,char C) if(n=1) move(1,A,C); else hanoi(n-1,A,C,B); move(n,A,C); ha

15、noi(n-1,B,A,C); 递归工作栈：返回地址 n A B C (1)(2)(3)(4)(5)(6)(7)(8)(9)55 算法运行void hanoi(int n,char A,char B,char C)(1) (2) if(n=1)(3) move(1,A,C);(4) else(5) hanoi(n-1,A,C,B);(6) move(n,A,C);(7) hanoi(n-1,B,A,C);(8) (9) n个盘子需要移动 次，64个盘子大约需 。假设每秒移动一次，约需一万亿年；一微秒一次，约需一百万年T(n)=O(2n)56 3.4 队列 （Queue）队列的逻辑结构 队列的存

16、储结构 队列的应用 57队列的逻辑结构队列的定义及特点定义：队列也是操作受限的线性表；在表的一端进行插入，在表的另一端进行删除队尾(rear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出(FIFO)a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an)队列的运算：置空队 取队头 入队 出队58基本操作：InitQueue(&Q)操作结果：构造一个空队列 QDestroyQueue(&Q)初始条件：队列 Q 已存在操作结果：队列 Q 被销毁QueueEmpty(Q)初始条件：队列 Q 已存在操作结果：空队列，返回 TRUE;否则 FALSEQueueL

17、ength(Q)初始条件：队列 Q 已存在操作结果：返回 Q 的元素个数，即队列的长度ClearQueue (&Q)初始条件：队列 Q 已存在操作结果：将 Q 清为空队列队列的抽象数据类型定义59GetHead(Q, &e)初始条件：队列 Q 已存在且非空操作结果：用 e 返回 Q 的队头元素EnQueue(&Q, e)初始条件：队列 Q 已存在操作结果：插入元素 e 为Q的新的队尾元素DeQueue(&Q, &e)初始条件：队列Q 已存在且非空操作结果：删除 Q 的队头元素，并用 e 返回其值QueueTravers(Q, visit()初始条件：队列 Q 已存在且非空操作结果：依次对Q 的

18、每个元素调用函数visit()队列的抽象数据类型定义基本操作：60a1 a2 a3.an 端1端2入队出队出队入队双端队列与超队列a1 a2 a3.an 端1端2入队出队入队双端队列超队列61队列的存储结构链队列顺序队列62初值：Q.front=0 Q.rear=-1;实现rear1234QSIZE-10队空Q.front=Q.rear+1front入队J1溢出J2J3J4J5J6rearrearrearrearrearrear真队列的顺序存储结构入队列：Q.a+rear=e;真溢出条件：Q.front=0;Q.rear=QSIZE-1;#define QSIZE 50 /最大队列长度type

19、def structint a QSIZE; int front; /队头指针，指向队头元素 int rear; /队尾指针，若队列不空， /指向队尾元素 的下一个位置SqQueue; SqQueue Q;631234SIZE-10front出队J1J2J3J4J5J6rearfrontfrontfront溢出假实现队列的顺序存储结构出队列：e=Q.afront+;typedef struct . SqQueue;SqQueue Q;void EnQueue(SqQueue Q,int e) / 入队 if(Q.rear=QSIZE-1 & Q.front=0)printf(“队列溢出”)；

20、else Q.a+rear = x; /在队尾插入x void DeQueue(SqQueue Q,int &e) / 出队 if(Q.front=Q.rear+1)printf(“队列已空”)； else e=Q.afront+;假溢出条件：Q.front != 0;Q.rear=SIZE-1;64方案一：队首固定，每次出队，剩余元素下移123450frontJ1出队J1J2J3J4rear真溢出条件：Q.front=0;Q.rear=QSIZE-1;假溢出条件：Q.front != 0;Q.rear=QSIZE-1;队列的顺序存储结构假溢出问题解决方案rear65123450frontJ2

21、出队J2J3J4rearrear缺点：浪费时间方案一：队首固定，每次出队，剩余元素下移真溢出条件：Q.front=0;Q.rear=QSIZE-1;假溢出条件：Q.front != 0;Q.rear=QSIZE-1;队列的顺序存储结构假溢出问题解决方案66J4J5J6123450frontrear方案二：循环队列，把队列设想成环形，首尾相接J4J5J6450123rearfront实现：If (Q.rear=QSIZE-1) Q.rear=Q.rear-QSIZE真溢出条件：Q.front=0;Q.rear=QSIZE-1;假溢出条件：Q.front != 0;Q.rear=QSIZE-1;队

22、列的顺序存储结构假溢出问题解决方案实现：If (Q.front=QSIZE) Q.front=Q.front-QSIZE67利用“ -QSIZE 运算实现循环队列循环队列中：队空条件：Q.Front = Q.rear+1溢出条件：Q.Front = Q.rear+1?队列的顺序存储结构循环队列少放一个数据：此时溢出条件改为：Q.Front = Q.rear+268实现循环队列队列的顺序存储结构循环队列void EnQueue(SqQueue Q,int e) / 入队 if (Q.front=Q.rear+2) printf(“队列溢出”)； else Q.a+rear = x; /在队尾插入

23、x if (Q.rear=QSIZE-1) Q.rear=-1;69实现循环队列队列的顺序存储结构循环队列void DeQueue(SqQueue Q,int &e) / 出队 if (Q.front=Q.rear+1) printf(“队列已空”)； else x=Q.afront+; if (Q.front=QSIZE) Q.front=0;70实现循环队列队列的顺序存储结构循环队列int Queuelength 思考：求队列的长度？71a1 a2 anai a1 a2 ai an队头front队尾rear出队入队Q.front队头队尾设队首、队尾指针front和rear,front指向头结点，rear指向队尾结点定义：ty