《高频与算法资料课件》由会员分享，可在线阅读，更多相关《高频与算法资料课件（36页珍藏版）》请在金锄头文库上搜索。
1、第三章 栈和队列,栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS 3.1 栈（stack） 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈 特点：先进后出（FILO）或后进先出（LIFO）,只允许在一端插入和删除的线性表 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 特点 后进先出 (LIFO),栈 ( Stack ),退栈,进栈,a0,an-1,an-2,top,bottom,栈的存储结构 顺序栈 实现：一维数组sM,栈顶指针top,指向实际栈顶 后的空位置，初值为0,进栈,A,出栈,栈满,
2、B,C,D,E,F,设数组维数为M top=0,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow),栈空,top,空栈,top,top,top,top,top,a 进栈,b 进栈,a,a,b,a,b,c,d,e,e 进栈,a,b,c,d,e,f 进栈溢出,a,b,d,e,e 退栈,c,top,c 退栈,b 退栈,a,b,a,a 退栈,空栈,top,a,b,d,d 退栈,c,top,a,b,c,top,top,入栈算法,出栈算法,在一个程序中同时使用两个栈,双栈共享一个栈空间,b0 t0 t1 b1,0 maxSize-1,V,栈的链接表示 链式
3、栈,链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 适合于多栈操作,top,链栈,结点定义,入栈算法,出栈算法,typedef struct node int data; struct node *link; JD;,栈的应用 过程的嵌套调用,例 递归的执行情况分析,递归过程及其实现 递归：函数直接或间接的调用自身叫 实现：建立递归工作栈,void print(int w) int i; if ( w!=0) print(w-1); for(i=1;i=w;+i) printf(“%3d,”,w); printf(“/n”); ,Ch3_10.c,运行结果： 1，
4、2，2， 3，3，3，,递归调用执行情况如下：,Tower of Hanoi问题 问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则： 每次只能移一个圆盘 圆盘可在三个塔座上任意移动 任何时刻，每个塔座上不能将大盘压到小盘上,解决方法： n=1时，直接把圆盘从A移到C n1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题
5、 算法：,执行情况： 递归工作栈保存内容：形参n,x,y,z和返回地址 返回地址用行编号表示,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,
6、 (8) (9) ,回文游戏：顺读与逆读字符串一样（不含空格）,1.读入字符串 2.去掉空格（原串） 3.压入栈 4.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文,多进制输出：,字符串：“madam im adam”,表达式求值,中缀表达式 后缀表达式（RPN) a*b+c ab*c+ a+b*c abc*+ a+(b*c+d)/e abc*d+e/+,中缀表达式：操作数栈和运算符栈,例 计算 2+4-3*6,后缀表达式求值步骤： 1、读入表达式一个字符 2、若是操作数，压入栈，转4 3、若是运算符，从栈中弹出2个数，将运算结果再压入栈 4、若表达式输入完毕，栈顶即表达式
7、值； 若表达式未输入完，转1,例 计算 4+3*5,后缀表达式：435*+,地图四染色问题,1,2,2,3,4,1,4,3,3,4,2,3,1# 紫色 2# 黄色 3# 红色 4# 绿色,3.2 队列 队列的定义及特点 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)允许插入的一端 队头(front)允许删除的一端 队列特点：先进先出(FIFO),双端队列,队列 ( Queue ),定义 队列是只允许在一端删除，在另一端插入的顺序表 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特性 先进先出(FIFO, First In F
8、irst Out),a0 a1 a2 an-1,front,rear,链队列 结点定义,typedef struct node int data; struct node *link; JD;,设队首、队尾指针front和rear, front指向头结点，rear指向队尾,队列的进队和出队,front,rear,空队列,front,rear,A进队,A,front,rear,B进队,A B,front,rear,C, D进队,A B C D,front,rear,A退队,B C D,front,rear,B退队,C D,front,rear,E,F,G进队,C D E F G,C D E F
9、G,front,rear,H进队,溢出,队列的进队和出队原则,进队时队尾指针先进一 rear = rear + 1， 再将新元素按 rear 指示位置加入。 出队时队头指针先进一 front = front + 1， 再将下标为 front 的元素取出。 队满时再进队将溢出出错； 队空时再出队将队空处理。 解决办法之一：将队列元素存放数组首尾 相接，形成循环(环形)队列。,入队算法,出队算法,队列的顺序存储结构 实现：用一维数组实现sqM,J1,J2,J3,设两个指针front,rear,约定： rear指示队尾元素； front指示队头元素前一位置 初值front=rear=-1,空队列条件
10、：front=rear 入队列：sq+rear=x; 出队列：x=sq+front;,存在问题 设数组维数为M，则： 当front=-1,rear=M-1时，再有元素入队发生溢出真溢出 当front-1,rear=M-1时，再有元素入队发生溢出假溢出 解决方案 队首固定，每次出队剩余元素向下移动浪费时间 循环队列 基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;,实现：利用“模”运算 入队： rear=(rear+1)%M; sqrear=x; 出队： front=(front+1)%M; x=sqfront; 队满、队空判定条件,队空：front
11、=rear 队满：front=rear,解决方案： 1.另外设一个标志以区别队空、队满 2.少用一个元素空间： 队空：front=rear 队满：(rear+1)%M=front,队列存放数组被当作首尾相接的表处理。 队头、队尾指针加1时从maxSize -1直接进到0，可用语言的取模(余数)运算实现。 队头指针进1: front = (front+1) % maxSize; 队尾指针进1: rear = (rear+1) % maxSize; 队列初始化：front = rear = 0; 队空条件：front = rear; 队满条件：(rear+1) % maxSize = front,
12、循环队列 (Circular Queue),入队算法：,出队算法：,队列应用举例 划分子集问题 问题描述：已知集合A=a1,a2,an，及集合上的关系R= (ai,aj) | ai,ajA, ij，其中(ai,aj)表示ai与aj间存在冲突关系。要求将A划分成互不相交的子集A1,A2,Ak,(kn)，使任何子集中的元素均无冲突关系，同时要求分子集个数尽可能少,例 A=1,2,3,4,5,6,7,8,9 R= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) 可行的子
13、集划分为： A1= 1,3,4,8 A2= 2,7 A3= 5 A4= 6,9 ,算法思想：利用循环筛选。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组 所用数据结构 冲突关系矩阵 rij=1, i,j有冲突 rij=0, i,j无冲突 循环队列cqn 数组resultn存放每个元素分组号 工作数组newrn,工作过程 初始状态：A中元素放于cq中，result和newr数组清零，组号group=1 第一个元素出队，将r矩阵中第一行“1”拷入newr中对应位置，这样，凡与第一个元素有冲突的元素在newr中对应位置处均为“1”,下一个元素出队 若其在newr中对应位置为“1”，有冲突，重新插入cq队尾，参加下一次分组 若其在newr中对应位置为“0”, 无冲突，可划归本组；再将r矩阵中该元素对应行中的“1”拷入newr中 如此反复，直到9个元素依次出队，由newr中为“0”的单元对应的元素构成第1组,将组号group值“1”写入result对应单元中 令group=2,newr清零，对cq中元素重复上述操作，直到cq中front=rear,即队空，运算结束,
