c++栈和队列PPT

1、栈 栈的应用 队列 队列的应用,第三章 栈和队列,1,栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS 3.1 栈（stack） 1. 栈的定义和特点 定义： 限定仅在表尾进行插入或删除操作的线性表，通常称插入、删除的这一端，即表尾为栈顶 (Top)，另一端表头为栈底 (Base) ，不含元素的空表称空栈。 特点： 先进后出（FILO）或后进先出（LIFO）,2,2. 栈的存储结构 (1) 顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，可用数组来实现顺序栈。 因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点

2、；栈顶位置是随着进栈和退栈操作而变化的，故需用一个变量top来指示当前栈顶的位置，通常称top为栈顶指针。,3,栈顶指针top,指向实际栈顶后的空位置,进栈,A,出栈,栈满,B,C,D,E,F,栈空,设栈的初始容量为Stacksize top=base,栈空，此时出栈则下溢（underflow) top-base= Stacksize,栈满，此时入栈则上溢（overflow),顺序栈的存储,4,顺序存储栈的结点类型的定义： #define STACK_INIT_SIZE 100; /存储空间初始分配量 #define STACKINCREMENT 10; /存储空间分配增量 typedef s

3、truct SElemType *base; /栈底指针 SElemType *top; /栈顶指针 int stacksize； /当前已分配的存储空间 sqStack;,5,顺序栈入栈算法,Push( sqStack ,6,在一个程序中同时使用两个栈,顺序栈出栈算法 Status Pop(sqStack ,7,例1： 多进制输出：,8,例1的解法： n n div 8 n mod 8 159 19 7 19 2 3 2 0 2,9,void conversion( ) /教材48页 initstack(s); /构造空栈，见教材47页 scanf (“%”,n); while(n) pus

4、h(s,n%8); /入栈 n=n/8; while(! Stackempty(s) /判断是否为空栈，见教材46页 pop(s,e); /出栈,e为出栈元素 printf(“%d”,e); ,10,例2： 假设以I和O分别表示入栈和出栈，栈的初态和终栈均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，下列所示的序列中，不合法的是 ( ) A. IOIIOIOO B. IOOIOIIO C. IIOOIOIO D. IIIOOIOO,B,11,例3: 一个栈的入栈序列为a，b，c，d，e，则出栈的不可能序列为（ ）。 A、e d c b a B、d e c b a C、d c e a

5、b D、a b c d e,C,12,例4: 设有一顺序栈S，元素s1、s2、s3、s4、s5、s6依次入栈，如果6个元素出栈的顺序是s2、s4、s3、s6、s5、s1，则栈的容量至少应该是（ ） A、2 B、3 C、5 D、6,B,13,2. 栈的存储结构 (2) 链栈,链栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链栈的栈顶在链头 适合于多栈操作,结点定义： typedef int datatype; typedef struct node datatype data; struct node *link; JD;,14,入栈算法,出栈算法,15,回文游戏：顺读与逆读字符串一样（不

6、含空格）,1.读入字符串 2.去掉空格（原串） 3.压入栈 4.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文,字符串：“madam im adam”,3. 栈的应用,16,表达式求值（前提规则见教材52、53页）,读一个字符，如为操作数，直接入到操作数栈；否则即为运算符，需判断： 1、如当前运算符高于栈顶运算符，入到运算符栈； 2、如当前运算符低于栈顶运算符，栈顶运算符出栈，同时操作数栈出栈两个数与运算符计算，并将结果入栈； 并输出到队列，当前运算符再与栈顶运算符比较； 3、如当前运算符等于栈顶运算符，且栈顶运算符为 “（”，当前运算符为“）”，则脱去括号继续读下一字符；

7、 4、如当前运算符等于栈顶运算符，且栈顶运算符为 “#”，当前运算符也为“#”，则表达式求值完毕。,表达式求值的处理规则,17,运算符的优先级,当前运算符,栈顶运算符,18,设两个栈：操作数栈OPND和运算符栈OPTR,例: 计算 2+4-3*6 ,参考书54页例 3*（7-2）,19,过程的嵌套调用,4. 栈的递归和嵌套应用,20,递归过程及其实现 递归：函数直接或间接的调用自身叫 实现：建立递归工作栈,补充： 递归的种类 1、直接递归(direct recursion)：在子程序中直接调用本身，就称为直接递归。 2、间接递归：在子程序中调用了另外的子程序，再从另外子程序中调用原来的子程序，

8、则称为间接递归。,补充：递归程序和非递归程序的比较,21,例 递归的执行情况分析,void write( int w) int i; if ( w!=0) write( w-1); for(i=1;i1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题 算法：,执行情况： 递归工作栈保存内容：形参n,x,y,z和返回地址 返回地址用行编号表示,25,/*Hanoi.txt*/ main() int m; printf(Input the n

9、umber of disks:); scanf(%d, ,void hanoi(int n,char x,char y,char z) if (n =1) move(1,x,z); /将第1号盘子从A移到C上 else hanoi(n-1,x,z,y); /将n-1个盘子从A移到B上，借助于C move(n,x,z); /将第n号盘子从A移到C上 hanoi(n-1,y,x,z); /将剩下的n-1个盘子从B移到C上，借助于A ,void move(int h,char c,char f) printf(%d:%c%cn, h,c,f); ,26,3.2 队列 队列的定义及特点 定义：队列是限

10、定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)允许插入的一端 队头(front)允许删除的一端 队列特点：先进先出(FIFO),27,链队列 结点定义,typedef struct node int data; struct node *link; JD;,设队首、队尾指针front和rear, front指向头结点，rear指向队尾,28,29,入队算法,出队算法,30,队列的顺序存储结构 实现：用一维数组实现sqM,J1,J2,J3,设两个指针front,rear, 约定： rear指示队尾元素的下一个位置； front指示队头元素； 初值front=rear=0

11、,空队列条件：front= =rear 入队列：sqrear+=x; 出队列：x=sqfront+;,31,存在问题 设数组维数为M，则： 当front=0,rear=M时，再有元素入队发生溢出真溢出 当front0,rear=M时，再有元素入队发生溢出假溢出 解决方案 队首固定，每次出队剩余元素向下移动浪费时间 循环队列 基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;,实现：利用“模”运算 入队： sq rear =x; rear=(rear+1)%M; 出队： x=sq front ; front=(front+1)%M; 队满、队空判定条件

12、,32,队空：front=rear 队满：front=rear,解决方案： 1.另外设一个标志以区别队空、队满 2.队列中留一个空位： 队空：front= =rear 队满：(rear+1)% M = =front,33,入队算法： void en_cycque(int sq,int front,int rear,int x) if(rear+1)% M)= =front) /对满 printf(overflow); else sqrear=x; rear=(rear+1)% M; /尾指针后移 ,34,出队算法： int dl_cycque(int sq,int front,int rear

13、,int *q) if(front=rear) /对空 return(0); /返回出队失败标志 else *q=sqfront; /存储出队元素 front=(front+1)% M; /头指针后移一位 return(1); /返回出队成功标志 ,35,例5: 在具有n个单元的循环队列中，队满时共有 _个元素。,n-1,例6: 若用单链表来表示队列，则应该选用( ) 带尾指针的循环链表 带头指针的循环链表 C. 带尾指针的非循环链表 D. 带头指针的非循环链表,A,36,队列应用举例 划分子集问题 问题描述：已知集合A=a1,a2,an，及集合上的关系R= (ai,aj) | ai,ajA,

14、 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) 可行的子集划分为： A1= 1,3,4,8 A2= 2,7 A3= 5 A4= 6,9 ,37,算法思想：利用循环筛选。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互

15、不冲突的划归第二组；直到所有元素进组 所用数据结构 冲突关系矩阵 rij=1, i,j有冲突 rij=0, i,j无冲突 循环队列cqn 数组resultn存放每个元素分组号 工作数组newrn,38,工作过程 初始状态：A中元素放于cq中，result和newr数组清零，组号group=1 第一个元素出队，将r矩阵中第一行“1”拷入newr中对应位置，这样，凡与第一个元素有冲突的元素在newr中对应位置处均为“1”,下一个元素出队 若其在newr中对应位置为“1”，有冲突，重新插入cq队尾，参加下一次分组 若其在newr中对应位置为“0”, 无冲突，可划归本组；再将r矩阵中该元素对应行中的“

16、1”拷入newr中 如此反复，直到9个元素依次出队，由newr中为“0”的单元对应的元素构成第1组,将组号group值“1”写入result对应单元中 令group=2,newr清零，对cq中元素重复上述操作，直到cq中front=rear,即队空，运算结束,39,算法描述,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) ,40,算法描述,cq,R= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6)

17、, (5,4), (7,5), (7,6), (3,7), (6,3) ,41,算法描述,cq,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) ,42,算法描述,cq,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) ,43,算法描述,cq,R= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2

18、), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) ,44,算法描述,cq,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) ,45,算法描述,cq,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) ,46,算法描述,cq,R= (2,8), (9,4), (2,9), (2,

19、1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) ,47,算法描述,cq,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) ,48,算法描述,cq,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) ,49,算法描述,cq,R= (2,8), (9

20、,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) ,50,算法描述,cq,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) ,51,算法描述,cq,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) ,52,算法描述,cq,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) ,53,算法描述,cq,R= (2,8), (9,4), (2,9),