内蒙古大学《算法与数据结构》课件第3章栈、队列与广义表

1、第三章 栈、队列与广义表 3.1 栈 3.2 队列 3.3 栈与队列的应用 3.4 广义表13.1 栈 ( Stack )只允许在表的一端进行插入和删除的线性表。允许插入和删除 的一端称为栈顶(top)， 另一端称为栈底(bottom) 不含元素的栈称为空栈 特点 后进先出 (LIFO) 或先进后出 (FILO)2栈的抽象数据类型ADT Stack Data 数据元素表 top: 栈顶位置 Operations Constructor Process: 创建一个空栈 IsEmpty Process: 判断栈是否为空 Output: 如果栈为空，则返回true，否则返回false GetTop

2、Process: 取栈顶元素 Output: 返回栈顶元素 3.1.1 ADT栈3栈的抽象数据类型 Length Process: 求栈中元素个数 Output: 返回栈中元素的个数 Push / 入栈 Input: 要添加的数据元素 Process: 向栈中添加元素x Pop / 出栈 Process: 删除栈顶元素 Output: 返回栈顶元素 Clear Process: 删除栈中所有元素并置新的栈顶 /Stack4一、顺序栈const int MaxStackSize=50; /栈中能容纳最大元素个数class SeqStack DataType StackListMaxStackSi

3、ze; int top; public: SeqStack(); /构造函数，初始化top bool IsEmpty(); /判断栈的状态是否为空 bool IsFull(); DataType GetTop(); /取栈顶元素 void Push(const DataType x); /入栈 DataType Pop(); /出栈 void Clear(); /栈清空;/ SeqStack3.1.2 栈的实现5顺序栈的基本操作的实现: SeqStack( ) /构造函数，初始化一个空栈 StackList = new DataTypeMaxStackSize; top=-1; / SeqSt

4、ack bool SeqStack : IsEmpty ( ) /判断栈是否为空 if(top=-1) return true; else return false;/ IsEmpty6bool SeqStack :IsFull( ) /判断栈是否已满 if(top=MaxStackSize-1) return true; else return false;/ IsFull7DataType SeqStack : GetTop( ) /取栈顶元素 i f (IsEmpty( ) cout”栈空！”endl; return nulldata; return StackListtop;8栈顶指针

5、top,指向栈底位置top入栈Atop出栈栈满BCDEFtop=-1,栈空，此时出栈，则下溢（underflow)top= MaxStackSize-1,栈满，此时入栈，则上溢（overflow)toptoptoptoptoptoptoptoptoptoptop栈空top123450栈空123450ABCDEF123450顺序栈的入栈与出栈9void SeqStack : Push(DataType x) /入栈 if (IsFull( ) cout”栈满！”endl; else StackList+top = x;/ Push10DataType SeqStack : Pop( ) /出栈

6、if (IsEmpty( ) cout”栈空！”next=NULL; /创建头结点 void Push (DataType data); /入栈 DataType Pop ( ); /出栈 DataType GetTop ( ); / 读栈顶元素 void Clear ( ) top-next=NULL; /清栈空,实现错 bool IsEmpty ( ) return top -next= = NULL; /判栈空;/ LinkStack链式栈 (LinkedStack)类的定义16类中操作算法描述如下：void LinkStack : Push (DataType item ) /入栈操作

7、 p=new StackNode ( item); p-next=top-next; top-next=p;/Push17DataType LinkStack :pop ( ) /出栈操作 if ( top-next!=NULL ) p = top-next; retvalue = p-data; /暂存栈顶数据 top -next= p-next; /修改栈顶指针 delete p; return retvalue; /释放,返回数据 else /栈空的情况 cout”the stack is empty!”next!=NULL) return top-next-data; else /栈空

8、的情况 cout”the stack is empty!”0Fact(n)=1 若n=0Fib(n)=0 (n=0)1 (n=1)Fib(n-1)+Fib(n-2) (n1)3.1.3 栈与递归233递归算法的设计方法在设计递归算法时，应该遵循下面的规则：（1）定义一个最小规模的问题，并给出其解；（2）把复杂的问题划分为同类型的若干规模较小的子问 题，并分别解决子问题；（3）把各子问题的解组合起来，即可得到原问题的解。 3.1.3 栈与递归24例1 递归的执行情况分析-n! int fact (int n) if ( n=0) fact= 1; else fact=n* fact ( n-1)

9、; void main( ) int f; f=fact(3); coutf; 3.1.3 栈与递归25地址 ntop递归调用执行情况如下：系统栈 int fact (int n) 1 if ( n=0) 2 fact= 1; 3 else 4 fact=n* fact( n-1);3.1.3 栈与递归26 int fact (int n) 1if ( n=0) 2 fact= 1; 3else 4 fact=n* fact( n-1);地址 n3n*fact(2); 4 n=3 topn递归调用执行情况如下：系统栈273n*fact(2);n2n*fact(1);4 n=2 4 n=3 to

10、pn地址 n递归调用执行情况如下：系统栈 int fact (int n) 1if ( n=0) 2 fact= 1; 3else 4fact=n* fact( n-1);281n*fact(0);4 n=1 4 n=2 4 n=3 topn3n*fact(2);n2n*fact(1);n地址 n递归调用执行情况如下：系统栈 int fact (int n) 1if ( n=0) 2 fact= 1; 3else 4fact=n* fact( n-1);291n*fact(n-1);4 n=1 4 n=2 4 n=3 topn3n*fact(2);n2n*fact(1);n0n地址 nfact

11、(0)=1递归调用执行情况如下：系统栈 int fact (int n) 1if ( n=0) 2 fact= 1; 3else 4fact=n* fact( n-1);303n*fact(n-1);n2n*fact(n-1);n0nfact(0)=11n*fact(n-1);n4 n=2 4 n=3 topfact(1)=1地址 n递归调用执行情况如下：系统栈 int fact (int n) 1if ( n=0) 2 fact= 1; 3else 4fact=n* fact( n-1);313n*fact(n-1);n2n*fact(n-1);n0nfact(0)=11n*fact(n-1

12、);nfact(1)=14 n=3 topfact(2)=2地址 n递归调用执行情况如下：系统栈 int fact (int n) 1if ( n=0) 2 fact= 1; 3else 4fact=n* fact( n-1);323n*fact(n-1);n2n*fact(n-1);n0nfact(0)=11n*fact(n-1);nfact(1)=1fact(2)=2topfact(3)=6地址 n递归调用执行情况如下：系统栈 int fact (int n) 1if ( n=0) 2 fact= 1; 3else 4fact=n* fact( n-1);33计算斐波那契数列的函数Fib(

13、n)的定义求解斐波那契数列的递归算法long Fib ( int n ) if ( n = 0|n=1 ) return n; else return Fib (n-1) + Fib (n-2);34Fib(5)Fib(4)Fib(3)Fib(1)Fib(2)Fib(0)Fib(3)Fib(2)Fib(1)Fib(1)Fib(0)Fib(1)Fib(2)Fib(1)Fib(0)考虑n=5，建立如下一个调用层次树35非递归实现Fibonacci函数如下： long Fib(int n) long oneback=0 , twoback=1 , current; if(n=0|n=1) retur

14、n n; else for(i=2;itemp) return An-1; else return temp; （2）求数组A中的最大整数。38例：Tower of Hanoi问题问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则：每次只能移一个圆盘圆盘可在三个塔座上 任意移动任何时刻，每个塔座上 不能将大盘压到小盘上39执行情况递归工作栈保存内容：实参n,x,y,z和返回地址返回地址用行编号表示汉诺塔解决方法n1时，先把A上的n-1个圆盘移到B,然后将n号盘从A移到C,再将

15、n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题.n=1时，直接把圆盘从A移到C n x y z 返回地址 系统栈40 main() int m; coutn; coutSteps:n disks; hanoi(n,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z)

16、;(8) (9) ABC1233 A B C 03 A B C 02 A C B 63 A B C 02 A C B 61 A B C 6ABC3 A B C 02 A C B 641 main() int n; coutn; cout”Steps:n“ disks”; hanoi(n,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) AB

17、C3 A B C 02 A C B 61 C A B 8ABC3 A B C 02 A C B 63 A B C 03 A B C 02 A C B 642 main() int n; coutn; cout”Steps:n“ disks”; hanoi(n,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B

18、A C 83 A B C 02 B A C 81 B C A 6ABC3 A B C 02 B A C 83 A B C 043 main() int n; coutn; cout”Steps:n“ disks”; hanoi(n,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 81 A B C 8

19、ABC3 A B C 02 B A C 83 A B C 0栈空3 A B C 02 B A C 844递归总结1. 递归是重要的设计和编程工具，使许多算法变得简单，易于设计和实现. 优点2. 递归使算法的时间复杂度和空间复杂度同时增大，有时会导致效率急剧恶化，或者溢出系统栈。 缺点3. 使用递归时应该权衡效率和设计的关系。在有足够的空间并且时间要求不高的情况下可以使用递归。转453.3 队列 ( Queue )定义队列是只允许在表的一端进行删除，而在另一端进行插入的线性表。允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特点先进先出(FIFO, First In F

20、irst Out)463.2.1 ADT 队列 队列的抽象数据类型定义ADT Queue Data 数据项列表 front: 队列中第一个元素的位置 rear: 队列中最后一个元素的位置 Operations Constructor Process: 初始化队首和队尾 47IsEmpty /判队空函数 Process: 判断是否为空队列 Output: 若队列空，返回true，否则返回falseLength /求队长 Process: 求队列中元素个数 Output: 返回队列的元素个数Front /去队头元素 Process: 取出队头元素 Output: 返回队头元素队列的抽象数据类型定义

21、48队列的抽象数据类型Enter /入队 Input: 要进入队列的元素 Process: 在队尾插入新的元素Leave /出队 Process: 删除队头元素 Output: 返回队头元素ClearQueue /清队空 Process: 删除队列中所有元素并设置初始状态/Queue493.2.2 队列的实现一、顺序队列顺序队列定义如下：const int MaxQSize=50;class SeqQueue int front, rear; DataType QueueListMaxQSize;public: SeqQueue();/构造函数,初始化数据成员 50顺序队列定义如下：void

22、Enter(DataType item); /入队DataType Leave(); /出队void Clear(); /清队空DataType Front(); / 取队头元素int Length(); / 求队长bool IsEmpty(); / 判断队是否为空bool IsFull(); /判断队是否为满;/ SeqQueue51图3.10 头尾指针和队列中元素的变化rear543210543210d1d2d3543210d1d2d3d4d5d6frontfrontrearrear543210d5d6rearfront(a) 空队列(b) d1,d2,d3入队(c) d4,d5,d6入队

23、(d) d1,d2,d3,d4出队front假溢出真溢出52存在问题当front=0,rear=M时，再有元素入队发生溢出真溢出当front0,rear=M时，再有元素入队发生溢出假溢出解决方案队首固定，每次出队后剩余元素向下移动浪费时间循环队列基本思想：把队列设想成环形，让QueueList 0接在QueueList M-1之后，若rear=M, 则令rear=0;0M-11frontrear.循环队列53队满：front=rear012345rearfrontA5A6A7012345rearfrontA4A9A8A4A5A6012345rearfront初始状态A4,A5,A6出队A7,A

24、8,A9入队队空：front=rear循环队列54其一是给队列设一个标志位以区别队列是空还是满；其二是给队列增加一个统计元素个数的变量count，当count=MaxQSize时队满；count=0时队空；其三是比前两种方法少用一个变量，约定队尾指针加1等于对头指针（从后面赶上队头指针）为队满的情况。这种情况下队满的条件是： (rear+1) % MaxQSize=front， 也能和空队区别开。此时队列中有一个空单元。在循环队列中解决队空和队满的三种处理方法：55SeqQueue() /构造函数，初始化一个空队列 front=rear=0;/ SeqQueuevoid Enter(DataT

25、ype item) /入队操作 if(rear+1)%MaxQSize=front) /判断是否队满 cout”队列已满，不能入队！”endl; else QueueListrear+=item;/ Enter循环队列类的操作算法描述如下：56DataType Leave() /出队操作if(front=rear) /判断是否队空 cout”队列已空，不能出队”next = rear-next = NULL; bool IsEmpty() return front next= NULL; ; / LinkQueue 61链队列的操作算法描述如下：void Enter( DataType ite

26、m ) /入队操作 /将新元素item插入到队列的队尾 rear-next = new QNode ( item); rear=rear-next;/Enter62链队列的操作算法描述如下：DataType Leave( ) /出队操作, 删去队头结点，并返回队头元素的值 if (!IsEmpty ( ) )/判队不空 p = front-next; DataType retvalue = p-data;/保存队头的值 front-next = p-next; delete p; if(front-next=NULL) /删除队列中唯一结点后，重新设置rear rear=front; retu

27、rn retvalue; else cout” 队列空!”next-data; else cout”队列空，无队头元素！”next; while(p) front-next=p-next; delete p; p=front-next; rear=front; 转65 3.3 栈与队列的应用 3.3.1 栈的应用应用1：数制转换问题将十进制数N转换为r进制的数，其转换方法利用辗转相除法：以N=3467，r=8为例转换方法如下：我们看到所转换的8进制数按低位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是

28、转换结果。 66N N / 8 (整除) N % 8(求余)3467 433 3 低 433 54 1 54 6 6 6 0 6 高所以：(3467)10 =(6613)867算法思想如下：当N0时重复（1），（2）（1）若N0，则将N % r 压入栈s中，执行（2）； 若N=0，将栈s的内容依次出栈，算法结束。（2）用N / r 代替 N68算法描述如下：void conversion(int N，int r) SeqStack s; int x; while( N ) s.Push (N % r ); N=N / r ; while (! s.IsEmpty ( ) x=s.Pop ( )

29、 ; coutx ; /while/conversion69应用2：表达式求值(1) 中缀表达式的计算 算术四则运算的规则： a. 根据运算符优先级由高到低的顺序进行运算。 b. 有括号出现时先算括号内的，后算括号外的，多层括号，由 内向外进行； c. 乘方连续出现时先算最右面的。 70 2 1 * / + ( ) # * / + （ ） # = =运算符间的优先关系(1和2相继出现的运算符)(1) 中缀表达式的计算71 算法思想：设定两栈：操作数栈 OPND，操作符栈 OPTR 栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底 元素为表达式起始符 #；依次读入字符：是操作数则

30、入OPND栈，是操作符则要判断： if 栈顶元素(1)操作符(2) ，则退栈、计算，结果压入 OPND栈； (1) 中缀表达式的计算72 读字符 操作数栈s1 运算符栈s2 说明33#3入栈S1*3#*入栈s223，2#*2入栈s13，2#*入栈s2(3，2#*(入栈s243，2，4#*(4入栈s1+3，2，4#*(+入栈s223，2，4，2#*(+2入栈s1*3，2，4，2#*(+*入栈s2计算中缀表达式：3*2(4+2*1)-5#的值7313，2，4，2，1#*(+*1入栈s1)3，2，4，2#*(+做2*1=2，结果2入栈s1)3，2，6#*(做4+2=6，结果6入栈s2)3，2，6 #

31、*( 出栈-3，64#*做26，结果64入栈s1-192#做3*64，结果192入栈s1 -192#-入栈s25192，5#-5入栈s1#187#做192-5, 结果187入栈s1计算中缀表达式：3*2(4+2*1)-5#的值74void EvaluateExpression( OperandType &result) /s1为操作对象栈，s2为操作符栈，OP为运算符集合 /OP=, *, /, +, -, (, ), #; SeqStack s1,s2; s2.Push(#); ch=cin.get(); while(ch!=#)|(s2.GetTop()!=#) if (!In(ch,OP

32、) s1.Push(ch); ch=cin.get(); 算法3.2 中缀表达式求值75else switch(compare( s2. GetTop(),ch) / s2. GetTop()为1 ,ch为2 case : temat=s2.Pop(); b=s1.Pop();a=s1.Pop(); result= Operate(a,temat,b); s1.Push(result); break; /switch /while result=s1.GetTop(); /EvaluateExpression76 (2) 后缀表达式求值 例如中缀表达式 “a+b*c”的后缀表达式为“abc*+

33、”。中缀表达式 后缀表达式a*b+c*d ab*cd*+a+(b*c+d)/e abc*d+e/+77算法思想：只使用一个栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。 78void Calcupostfix( OperandType &result) /OP=, *, /, +, -, (, ), #; SeqStack s; ch=cin.get(); while(ch!=#) if (!In(ch,OP) s.Push(ch); else b=s.Pop()

34、; a=s.Pop(); result= Operate(a,ch,b); s.Push(result); ch=cin.get(); return result; 79 (3) 中缀表达式转换为后缀表达式 算法思想：设操作符栈(初始为，记1为栈顶指针) , 依次读入字符，是操作数则输出，否则(读入的是操作符)，记为2，判断：若2 1 则2入栈若21 则输出栈顶元素并退栈若2=1（ 2(且) ）退栈但不输出 否则 算法结束。例如：AB*(C-D)-E/F 输出 ABCD-*+EF/-80void In-Post() /OP=, *, /, +, -, (, ), #; SeqStack s;

35、s.Push(#); ch=cin.get(); while(ch!=#)|(!s.IsEmpty() if (!In(ch,OP) coutch; ch=cin.get(); 81else switch(compare( s. GetTop(),ch) / s. GetTop()为1 ,ch为2 case : op=s.Pop(); coutop; break; /switch /while /In-Post82 入口出口(4) 求迷宫问题南北西东83class PosType /迷宫中的坐标位置 int x,y;class Block /通道块 int ord; /通道块的序号 PosTy

36、pe seat; /通道块在迷宫中的坐标位置 int direction; /从此通道块走向下一通道块的方向 ;class Maze Block e; public: bool MazePath(PosType start, PosType end); ;84N(北)i-1, jW(西)i, j-1i, jE(东)i, j+1S(南) i+1, j85bool Maze:MazePath(PosType start, PosType end) SeqStack s; curpos=start; /当前位置为入口位置 curstep=1; /探索第一步do if(Pass(curpos) /当前

37、位置可以通过且未走过 footprint(curpos); /留下足印 e=new Block(curstep,curpos,1); s.Push(e); /加入路径 if(curpos=end) return(true); /到达终点 curpos=NextPos(curpos,1); /下一个位置是当前位置的东邻 curstep+; /if迷宫求解非递归算法86else /当前位置不通 if(!s.IsEmpty() e=s.Pop(); while(e.direction=4 & !s.IsEmpty() MarkPrint(e.seat); e=s.Pop(); /留下不能通过的标记并

38、后退 / while if(e.direction4) e.direction+; s.Push(e); /换下一个方向探索 curpos=NextPos(e.seat, e.direction); /新位置是旧位置的相邻块 /end if /if / elsewhile(!s.IsEmpty(); return(false);/ Mazth 转873.3.2 队列的应用 舞会在星期五晚举行。舞会开始之前，参加舞会的男士和女士各自排队进入舞厅。舞会开始，从两队中按顺序组成舞伴开始跳舞。一曲结束后，男士和女士分别再进入各自队列。如果男士和女士人数不等，则多出的人只能等到下一舞曲开始。舞伴 用两个

39、队列来表示男士和女士等待队列，舞会开始前时，按其性别加入不同队列，舞曲开始后，顺序地同时删除两个队列的元素来组成舞伴，直到某一队列为空。 要求用算法来模拟一支舞曲开始后男士和女士组成舞伴的情况，以及多少人在等待的情况。88class Person /Person为跳舞人的类 char *name; char sex; /”F”为男，”M”为女 ; void Dance_parnter() SeqQueue M_Dancer, F_Dancer; / M_Dancer为男士队列，F_Dancer为女士队列 Person p; /Person为跳舞人的类 Person_arrive(p,name,sex); /有人到达舞会,将其姓名和性别赋给p /建立男士队列和女士队列 =name; p.sex=sex;3.3.2 队列的应用89while（strcmp(,”#”)0） /将男士和女士分别入各自队列 if (p.sex= =F) M_Dancer.Enter(p); else F_Dancer.Enter(p); Person_arrive(p,name,sex); /while 90while(!M_Dancer.IsEmpty() & !F_Dancer.IsEmpty()/顺序地同时从两个队列中删除 p=M_D