清华大学出版社 《数据结构与算法》赵玉兰 等编著第3章.ppt

1、1,数据结构与算法DATA STRUCTURE AND ARITHMETIC,计算机专业本科主干基础课,2,第三章 栈、队列与广义表 3.1 栈 3.2 队列 3.3 栈与队列的应用 3.4 广义表,3,3.1 栈 ( Stack ),只允许在表的一端进行插入和删除的线性表。 允许插入和删除 的一端称为栈顶(top)， 另一端称为栈底(bottom) 不含元素的栈称为空栈 特点 后进先出 (LIFO) 或先进后出 (FILO),4,栈的抽象数据类型 ADT Stack Data 数据元素表 top: 栈顶位置 Operations Constructor Process: 创建一个空栈 IsE

2、mpty Process: 判断栈是否为空 Output: 如果栈为空，则返回true，否则返回false GetTop Process: 取栈顶元素 Output: 返回栈顶元素,3.1.1 ADT栈,5,栈的抽象数据类型,Length Process: 求栈中元素个数 Output: 返回栈中元素的个数 Push / 入栈 Input: 要添加的数据元素 Process: 向栈中添加元素x Pop / 出栈 Process: 删除栈顶元素 Output: 返回栈顶元素 Clear Process: 删除栈中所有元素并置新的栈顶 /Stack,6,一、顺序栈 const int MaxSta

3、ckSize=50; /栈中能容纳最大元素个数 class SeqStack DataType StackListMaxStackSize; int top; public: SeqStack(); /构造函数，初始化top bool IsEmpty(); /判断栈的状态是否为空 bool IsFull(); DataType GetTop(); /取栈顶元素 void Push(const DataType x); /入栈 DataType Pop(); /出栈 void Clear(); /栈清空 ;/ SeqStack,3.1.2 栈的实现,7,顺序栈的基本操作的实现:,SeqStack

4、( ) /构造函数，初始化一个空栈 StackList = new DataTypeMaxStackSize; top=-1; / Stack bool IsEmpty ( ) /判断栈是否为空 if(top=-1) return true; else return false; / IsEmpty,8,bool IsFull( ) /判断栈是否已满 if(top=MaxStackSize-1) return true; else return false; / IsFull,9,DataType GetTop( ) /取栈顶元素 i f (IsEmpty( ) cout”栈空！”endl;

5、return nulldata; return StackListtop; ,10,栈顶指针top, 指向栈底位置,入栈,A,出栈,栈满,B,C,D,E,F,top=-1,栈空，此时出栈，则下溢（underflow) top= MaxStackSize-1,栈满，此时入栈，则上溢（overflow),栈空,顺序栈的入栈与出栈,11,void Push(DataType x) /入栈 if (IsFull( ) cout”栈满！”endl; else StackList+top = x; / Push,12,DataType Pop( ) /出栈 if (IsEmpty( ) cout”栈空！”

6、endl; return nulldata; return StackListtop-; /Pop,13,算法分析： 以上栈的操作与表中元素个数无关。它们的时间复杂度均为O(1)。 定义顺序栈时，应该知道所需的最大栈长度。如果事先无法预知栈的最大长度，可以采用链式栈。,14,2链式栈栈的链式存储称为链栈。用单链表来实现链栈。因此其结点结构与单链表的结构相同。,链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头,a0,an-1,a1,15,class StackNode DataType data; /结点数据 StackNode *next; /结点链指针 public

7、: friend class LinkStack； StackNode ( DataType d=nulldata ) data=d; next=NULL; ;/ StackNode,链式栈 (LinkedStack)类的定义,16,class LinkStack StackNode *top; /栈顶指针 public: LinkStack ( ) top=new StackNode();top-next=NULL; /创建头结点 void Push (DataType data); /入栈 DataType Pop ( ); /出栈 DataType GetTop ( ); / 读栈顶元素

8、 void Clear ( ) top-next=NULL; /清栈空,实现错 bool IsEmpty ( ) return top -next= = NULL; /判栈空 ;/ LinkStack,链式栈 (LinkedStack)类的定义,17,类中操作算法描述如下： void Push (DataType item ) /入栈操作 p=new StackNode ( item); p-next=top-next; top-next=p; /Push,18,DataType LinkStack :pop ( ) /出栈操作 if ( top-next!=NULL ) p = top-ne

9、xt; retvalue = p-data; /暂存栈顶数据 top -next= p-next; /修改栈顶指针 delete p; return retvalue; /释放,返回数据 else /栈空的情况 cout”the stack is empty!”endl; return nulldata; /Pop,类中操作算法描述如下：,19,DataType GetTop ( ) /取栈顶元素操作 if (top-next!=NULL) return top-next-data; else /栈空的情况 cout”the stack is empty!”endl; return nulld

10、ata; /GetTop,类中操作算法描述如下：,20,双栈共享一个栈空间,21,void main() f1(); r ,void f2() f3(); t ,void f1() f2(); s ,一、函数的嵌套调用,void f3() ,3.1.3 栈与递归,22,一、函数的嵌套调用,r,f2();,s,3.1.3 栈与递归,f3(),23,1递归的概念,1) 什么是递归 函数直接或间接的调用自身的过程.,2) 递归三要素 (1) 定义出口 (2) 把一个大的问题划分成同类型的子问题 (3) 解的合成,2. 递归函数和运行时栈,3.1.3 栈与递归,24,很多问题都是用递归的方法定义的，例

11、如我们普遍熟悉阶乘函数，Fibonacci数列,Fib(n)=,0 (n=0),1 (n=1),Fib(n-1)+Fib(n-2) (n1),3.1.3 栈与递归,25,3递归算法的设计方法,在设计递归算法时，应该遵循下面的规则： （1）定义一个最小规模的问题，并给出其解； （2）把复杂的问题划分为同类型的若干规模较小的子问 题，并分别解决子问题； （3）把各子问题的解组合起来，即可得到原问题的解。,3.1.3 栈与递归,26,例1 递归的执行情况分析-n!,int fact (int n) if ( n=0) fact= 1; else fact=n* fact ( n-1); ,void

12、main( ) int f; f=fact(3); coutf; ,3.1.3 栈与递归,27,top,递归调用执行情况如下：,系统栈,int fact (int n) 1 if ( n=0) 2 fact= 1; 3 else 4 fact=n* fact( n-1); ,3.1.3 栈与递归,28,int fact (int n) 1if ( n=0) 2 fact= 1; 3else 4 fact=n* fact( n-1); ,3,n*fact(2);,top,n,递归调用执行情况如下：,系统栈,29,3,n*fact(2);,n,2,n*fact(1);,top,n,递归调用执行情况

13、如下：,系统栈,int fact (int n) 1if ( n=0) 2 fact= 1; 3else 4fact=n* fact( n-1); ,30,1,n*fact(0);,top,n,3,n*fact(2);,n,2,n*fact(1);,n,递归调用执行情况如下：,系统栈,int fact (int n) 1if ( n=0) 2 fact= 1; 3else 4fact=n* fact( n-1); ,31,1,n*fact(0);,top,n,3,n*fact(2);,n,2,n*fact(1);,n,递归调用执行情况如下：,系统栈,int fact (int n) 1if (

14、 n=0) 2 fact= 1; 3else 4fact=n* fact( n-1); ,32,3,n*fact(2);,n,2,n*fact(1);,n,1,n*fact(0);,n,top,fact(1)=1,递归调用执行情况如下：,系统栈,int fact (int n) 1if ( n=0) 2 fact= 1; 3else 4fact=n* fact( n-1); ,33,3,n*fact(2);,n,2,n*fact(1);,n,1,n*fact(0);,n,fact(1)=1,top,fact(2)=2,递归调用执行情况如下：,系统栈,int fact (int n) 1if (

15、 n=0) 2 fact= 1; 3else 4fact=n* fact( n-1); ,34,3,n*fact(2);,n,2,n*fact(1);,n,1,n*fact(0);,n,fact(1)=1,fact(2)=2,top,fact(3)=6,递归调用执行情况如下：,系统栈,int fact (int n) 1if ( n=0) 2 fact= 1; 3else 4fact=n* fact( n-1); ,35,计算斐波那契数列的函数Fib(n)的定义,求解斐波那契数列的递归算法 long Fib ( int n ) if ( n = 0|n=1 ) return n; else r

16、eturn Fib (n-1) + Fib (n-2); ,36,Fib(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，建立如下一个调用层次树,37,非递归实现Fibonacci函数如下： long Fib(int n) long oneback=0 , twoback=1 , current; if(n=0|n=1) return n; else for(i=2;in;i+) current =oneback+twoback;

17、 oneback=twoback; twoback=current; return current; / Fib,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,再将n-

18、1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题.,n=1时，直接把圆盘从A移到C,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); (8) (9)

19、,41,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) ,42,main() int n; coutn; cout”Steps:n“ disks”; hanoi(n,A,B,C); (0) void hanoi(int n

20、,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) ,43,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,

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

22、IFO, First In First Out),46,3.2.1 ADT 队列 队列的抽象数据类型定义 ADT Queue Data 数据项列表 front: 队列中第一个元素的位置 rear: 队列中最后一个元素的位置 Operations Constructor Process: 初始化队首和队尾,47,IsEmpty Process: 判断是否为空队列 Output: 若队列空，返回true，否则返回false Length Process: 求队列中元素个数 Output: 返回队列的元素个数 Front Process: 取出队头元素 Output: 返回队头元素,队列的抽象数据类

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

24、void Enter(DataType item); /入队 DataType Leave(); /出队 void Clear(); /清队空 DataType Front(); / 取队头元素 int Length(); / 求队长 bool IsEmpty(); / 判断队是否为空 bool IsFull(); /判断队是否为满 ;/ SeqQueue,51,图3.10 头尾指针和队列中元素的变化,rear,5,4,3,2,1,0,5,4,3,2,1,0,d,1,d,2,d,3,5,4,3,2,1,0,d,1,d,2,d,3,d,4,d,5,d,6,front,front,rear,rea

25、r,5,4,3,2,1,0,d,5,d,6,rear,front,(,a,),空队列,(,b,),d,1,d,2,d,3,入队,(,c,),d,4,d,5,d,6,入队,(,d,),d,1,d,2,d,3,d,4,出队,front,假溢出,真溢出,52,存在问题 当front=0,rear=M时，再有元素入队发生溢出真溢出 当front0,rear=M时，再有元素入队发生溢出假溢出 解决方案 队首固定，每次出队后剩余元素向下移动浪费时间 循环队列 基本思想：把队列设想成环形，让QueueList 0接在QueueList M-1之后，若rear=M, 则令rear=0;,0,M-1,1,fro

26、nt,rear,.,.,循环队列,53,队满：front=rear,A4,A5,A6,0,1,2,3,4,5,rear,front,初始状态,队空：front=rear,循环队列,54,其一是给队列设一个标志位以区别队列是空还是满； 其二是给队列增加一个统计元素个数的变量count，当count=MaxQSize时队满；count=0时队空； 其三是比前两种方法少用一个变量，约定队尾指针加1等于对头指针（从后面赶上队头指针）为队满的情况。这种情况下队满的条件是： (rear+1) % MaxQSize=front， 也能和空队区别开。此时队列中有一个空单元。,在循环队列中解决队空和队满的三种处

27、理方法：,55,SeqQueue() /构造函数，初始化一个空队列 front=rear=0; / SeqQueue void Enter(DataType item) /入队操作 if(rear+1)%MaxQSize=front) /判断是否队满 cout”队列已满，不能入队！”endl; else QueueListrear+=item; / Enter,循环队列类的操作算法描述如下：,56,DataType Leave() /出队操作 if(front=rear) /判断是否队空 cout”队列已空，不能出队”endl; return nulldata; return(QueueLis

28、t+front); / Leave,循环队列类的操作算法描述如下：,void ClearQueue() rear=front; / ClearQueue,57,循环队列类的操作算法描述如下：,bool IsEmpty() /判断队列是否为空 if(rear=front) return true; else return false; / IsEmpty bool IsFull() /判断队列是否已满 if(rear+1)%MaxQSize=front) return true; else return false; / IsFull,58,二、链队列 链式存储的队称为链队列。和链栈类似，用单链

29、表来实现链队列，根据队列的FIFO原则，为了操作上的方便，我们分别需要一个头指针和尾指针，如图所示。队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。,59,链队列描述如下：,class QNode /链队结点的类 DataType data; QNode *next; public: QNode(DataType item=nulldata) data= item; next=NULL; ; / QNode,60,链队列描述如下：,class LinkQueue QNnode *front, *rear; public: LinkQueue()rear =front=new

30、QNode(); void Enter (DataType item ); /入队 DataType Leave();/出队 DataType Front();/读队头元素 void Clear()front-next = rear-next = NULL; bool IsEmpty() return front next= NULL; ; / LinkQueue,61,链队列的操作算法描述如下：,void Enter( DataType item ) /入队操作 /将新元素item插入到队列的队尾 rear-next = new QNode ( item); rear=rear-next;

31、/Enter,62,链队列的操作算法描述如下：,DataType Leave( ) /出队操作, 删去队头结点，并返回队头元素的值 if (!IsEmpty ( ) )/判队不空 p = front-next; DataType retvalue = p-data;/保存队头的值 front-next = p-next; delete p; if(front-next=NULL) /删除队列中唯一结点后，重新设置rear rear=front; return retvalue; else cout” 队列空!”endl; return nulldata; /Leave,63,链队列的操作算法描

32、述如下：,DataType Front( ) /取队头元素 if(!IsEmpty ( ) ) return front-next-data; else cout”队列空，无队头元素！”endl; return nulldata; /Front,64,void Clear() /清队空 p=front-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=

33、8为例转换方法如下： 我们看到所转换的8进制数按低位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。,66,N N / 8 (整除) N % 8(求余) 3467 433 3 低 433 54 1 54 6 6 6 0 6 高 所以：(3467)10 =(6613)8,67,算法思想如下： 当N0时重复（1），（2） （1）若N0，则将N % r 压入栈s中，执行（2）； 若N=0，将栈s的内容依次出栈，算法结束。 （2）用N / r 代替 N,68,算法描述如下： void conversi

34、on(int N，int r) SeqStack s; int x; while( N ) s.Push (N % r ); N=N / r ; while (! s.IsEmpty ( ) x=s.Pop ( ) ; coutx ; /while /conversion,69,应用2：表达式求值,(1) 中缀表达式的计算 算术四则运算的规则： a. 根据运算符优先级由高到低的顺序进行运算。 b. 有括号出现时先算括号内的，后算括号外的，多层括号，由 内向外进行； c. 乘方连续出现时先算最右面的。,70,运算符间的优先关系(1和2相继出现的运算符),(1) 中缀表达式的计算,71,算法思想：

35、 设定两栈：操作数栈 OPND，操作符栈 OPTR 栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底 元素为表达式起始符 #； 依次读入字符：是操作数则入OPND栈，是操作符则要判断： if 栈顶元素(1)操作符(2) ，则退栈、计算，结果压入 OPND栈；,(1) 中缀表达式的计算,72,计算中缀表达式：3*2(4+2*1)-5#的值,73,计算中缀表达式：3*2(4+2*1)-5#的值,74,void EvaluateExpression( OperandType ,算法3.2 中缀表达式求值,75,else switch(compare( s2. GetTop(),ch)

36、 / 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(); /EvaluateExpression,76,(2) 后缀表达式求值,例如中缀表达式 “a+b*c”的后缀表达式为“abc*+”。 中缀表达式 后缀表达式 a*b+c*d ab*cd*+ a+(b*c+d)/e abc*d+e/+,77,算法思想：,只使用一个栈，当从左向右扫描表达式时

37、，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。,78,void Calcupostfix( OperandType ,79,(3) 中缀表达式转换为后缀表达式,算法思想： 设操作符栈(初始为，记1为栈顶指针) , 依次读入字符， 是操作数则输出，否则(读入的是操作符)，记为2，判断： 若2 1 则2入栈 若21 则输出栈顶元素并退栈 若2=1（ 2(且) ）退栈但不输出 否则 算法结束。 例如：AB*(C-D)-E/F 输出 ABCD-*+EF/-,80,void In-Post() /O

38、P=, *, /, +, -, (, ), #; SeqStack s; s.Push(#); ch=cin.get(); while(ch!=#)|(!s.IsEmpty() if (!In(ch,OP) coutch; ch=cin.get(); ,81,else switch(compare( s. GetTop(),ch) / s. GetTop()为1 ,ch为2 case : op=s.Pop(); coutop; break; /switch /while /In-Post,82,入口,出口,(4) 求迷宫问题,83,class PosType int x,y; class Bl

39、ock /通道块 int ord; /通道块的序号 PosType seat; /通道块在迷宫中的坐标位置 int direction; /从此通道块走向下一通道块的方向 ; class Maze Block e; public: bool MazePath(PosType start, PosType end); ;,84,85,bool Maze:MazePath(PosType start, PosType end) SeqStack s; curpos=start; /当前位置为入口位置 curstep=1; /探索第一步 do if(Pass(curpos) /当前位置可以通过且未走

40、过 footprint(curpos); /留下足印 e=new Block(curstep,curpos,1); s.Push(e); /加入路径 if(curpos=end) return(true); /到达终点 curpos=NextPos(curpos,1); /下一个位置是当前位置的东邻 curstep+; /if,迷宫求解算法,86,else /当前位置不通 if(!s.IsEmpty() e=s.Pop(); while(e.direction=4 / Mazth,87,递归总结 1. 递归是重要的设计和编程工具，使许多算法变得简单，易于设计和实现. 优点 2. 递归使算法的时

41、间复杂度和空间复杂度同时增大，有时会导致效率急剧恶化，或者溢出系统栈。 缺点 3. 使用递归时应该权衡效率和设计的关系。在有足够的空间并且时间要求不高的情况下可以使用递归。,88,3.3.2 队列的应用,舞会在星期五晚举行。舞会开始之前，参加舞会的男士和女士各自排队进入舞厅。舞会开始，从两队中按顺序组成舞伴开始跳舞。一曲结束后，男士和女士分别再进入各自队列。如果男士和女士人数不等，则多出的人只能等到下一舞曲开始。,舞伴,用两个队列来表示男士和女士等待队列，舞会开始前时，按其性别加入不同队列，舞曲开始后，顺序地同时删除两个队列的元素来组成舞伴，直到某一队列为空。,要求用算法来模拟一支舞曲开始后男士和女士组成舞伴的情况，以及多少人在等待的情况。,89,class 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,na