第栈和队列.ppt

《第栈和队列.ppt》由会员分享，可在线阅读，更多相关《第栈和队列.ppt（82页珍藏版）》请在三一办公上搜索。

1、第3章 栈和队列,栈栈与递归 队列 优先级队列,结构,3.1 栈(Stack),只允许在一端插入和删除的线性表。,允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。特点 后进先出(LIFO)。,template class Stack public:Stack(int sz=10);/构造函数 void Push(Type x);/进栈 int Pop(Type/判栈满否,栈的抽象数据类型,栈的两种物理存储方式,栈的数组存储表示 顺序栈栈的链接存储表示 链式栈,template class Stack private:int top;/栈顶指针 Type*elements

2、;/栈元素数组 int maxSize;/栈最大容量 void overflowProcess();/栈的溢出处理,0 1 2 3 4 5 6 7 8 9 maxSize-1,elements,栈的数组存储表示 顺序栈,public:Stack(int sz=10);/构造函数 Stack()delete elements;void Push(Type x);/进栈 int Pop(Type,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 退

3、栈,a,b,a,a 退栈,空栈,top,a,b,d,d 退栈,c,top,a,b,c,top,top,template void SeqStack:overflowProcess()/私有函数：当栈满则执行扩充栈存储空间处理 T*newArray=new E2*maxSize;/创建更大的存储数组 for(int i=0;i=top;i+)newArrayi=elementsi;maxSize+=maxSize;delete elements;elements=newArray;/改变elements指针;,template void SeqStack:Push(T x)/若栈不满,则将元素x

4、插入该栈栈顶,否则溢出处理 if(IsFull()=true)overflowProcess;/栈满 elements+top=x;,注意,template bool SeqStack:Pop(T,template bool Seqstack:getTop(T,注意,算法分析：GetTop()/取栈顶元素Push()/入栈操作Pop()/出栈操作,O(1),双栈共享一个栈空间,初始 t0=b0=-1,t1=b1=？,栈满条件：,maxSize,t0+1=t1,t0=b0或t1=b1,栈空条件：,int push(DualStack&DS,Type x,int i),int Pop(DualSt

5、ack&DS,Type&x,int i),例：多进制输出（将十进制转换成其它进制）,算法：以B进制形式输出1.nB,结果压入栈S中；2.n的剩余部分为n/B,用n/B代替n;3.重复上述过程1和2直到n=0;4.从栈中弹出并打印所有数字。,5310125124023122021,1,0,1,0,1,1,栈的链接存储表示 链式栈,链式栈的栈顶在链头；插入与删除仅在栈顶处执行;链式栈无栈满问题，空间可扩充；适合于多栈操作。,template class Stack;template class StackNode friend class Stack;private:Type data;/结点数据

6、 StackNode*link;/结点链指针public:StackNode(T d=0,StackNode*next=NULL):data(d),link(next);,链式栈(LinkedStack)类的定义,template class LinkedStack:public Stack/链式栈类定义 private:StackNode*top;/栈顶指针 void output(ostream/退栈,bool getTop(E,栈的应用(一):括号匹配,字符串:(a*(b+c)-d),目的:输入字符串,输出匹配的括号和没有匹配的括号,算法基本思想:从左到右扫描,把遇到的左括号存放在栈中;

7、每当在后续的扫描过程中遇到一个右括号时,就将它与栈顶的左括号相匹配,并在栈顶删除该左括号。,#include#include#include#include“stack.h”const int maxLength=100;void PrintMatchedPairs(char*expression)stack s(maxLength);int j,length=strlen(expression);for(int i=1;ilength;i+)if(expressioni-1=()s.Push(i);/左括号,位置进栈 else if(expressioni-1=)/右括号 if(s.Pop(

8、j)=true)/栈不空,退栈成功 coutj“与”i“匹配”endl;else cout“没有与第”i”个右括号匹配的左括号!”endl;while(s.IsEmpty()=false)s.Pop(j);cout.endl;,?,栈的应用(二)：表达式计算,一个表达式由操作数(亦称运算对象)、操作符(亦称运算符)和分界符组成。算术表达式有三种表示：中缀(infix)表示，如 A+B；前缀(prefix)表示，如+AB；后缀(postfix)表示，如 AB+；,一般表达式的操作符有4种类型：算术操作符 如双目操作符（+、-、*、/和%）以及单目操作符（-）;关系操作符 包括=、。这些操作符主要

9、用于比较;逻辑操作符 如与(括号(和)它们的作用是改变运算顺序。,表达式中相邻两个操作符的计算次序为：优先级高的先计算；优先级相同的自左向右计算；当使用括号时从最内层括号开始计算;,如：中缀表达式 a+b*(c-d)-e/f,从左向右顺序地扫描表达式，并用一个栈暂存扫描到的操作数或计算结果。在后缀表达式的计算顺序中已隐含了加括号的优先次序，括号在后缀表达式中不出现。,应用后缀表示计算表达式的值,通过后缀表示计算表达式值的过程,顺序扫描表达式的每一项，根据它的类型做如下相应操作：若该项是操作数，则将其压栈；若该项是操作符，则连续从栈中退出两个操作数Y和X，形成运算指令XY，并将计算结果重新压栈。

10、当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。,后缀表达式：ABCD-*+EF G/-,void Calculator:Run()char ch;double newoperand;while(cin ch,void DoOperator(char op)/从栈S中取两个操作数，形成运算指令并计算进栈 double left,right;int succ=S.GetTop(right);S.Pop();if(succ)succ=S.GetTop(left);S.Pop();if(!succ)return;/退出两个操作数 switch(op)case+:S.Push(left

11、+right);break;/加 case-:S.Push(left-right);break;/减 case*:S.Push(left*right);break;/乘 case/:if(right!=0.0)S.Push(left/right);/除 else cout“除数为0!n”);exit(1);,中缀表达式转换为后缀表达式,中缀表达式转化为后缀表达式,a+b*(c-d)-e/f,a+b*(c-d)-e/f,a+b*(c-d)-e/f,a+b*(c-d)-e/f,a+b*cd-e/f,a+bcd-*-e/f,a+b*(c-d)-e/f,a+bcd-*-ef/,abcd-*+-ef/,

12、a+b*(c-d)-e/f,abcd-*+ef/-,3.2 栈与递归,3.2.1 递归的概念,幂函数：xnS(n)=i=1+2+3+n,如果已经求得xn或S(n),计算xn+1或S(n+1)时？,定义是递归的,求解阶乘函数的递归算法long Factorial(long n)if(n=0)return 1;else return n*Factorial(n-1);,例如，阶乘函数,主程序 main:fact(4),参数 4 计算 4*fact(3),参数 3 计算 3*fact(2),参数 2 计算 2*fact(1),参数 1 计算 1*fact(0),参数 0 直接定值=1,参数传递,结果

13、返回,递归调用,回归求值,求解阶乘 n!的过程,递归的定义:若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。,以下三种情况常常用到递归方法:定义是递归的 数据结构是递归的 问题的解法是递归的,数据结构是递归的,一个结点，它的指针域为NULL，是一个单链表;一个结点，它的指针域指向单链表，仍是一个单链表。,例如，单链表结构,f,f,例1：搜索链表最后一个结点并打印其数值,template void Print(ListNode*f)if(f-link=NULL)cout data link);,template

14、void Print(ListNode*f,Type,例2:在链表中寻找等于给定值的结点并打印其数值,递归,定义是递归的 数据结构是递归的 问题的解法是递归的,问题的解法是递归的,汉诺塔(Tower of Hanoi)问题：,设A柱上最初的盘子总数为n,hanoi(n,A,B,C)如果 n=1，则将这一个盘子直接从 A 柱移到 C 柱上。,将 A 柱上最后一个盘子直接移到 C 柱上；,用 A 柱做过渡，将 B 柱上的(n-1)个盘子移到 C 柱上。,否则，执行以下三步：用 C 柱做过渡，将 A 柱上的(n-1)个盘子移到 B 柱上；,移动时需要注意的事项每次移动时必须保证从塔底到塔顶碟子的大小

15、是从大到小的。,#include#include strclass.h”void Hanoi(int n,String A,String B,String C)/解决汉诺塔问题的算法 if(n=1)cout move A to C endl;else Hanoi(n-1,A,C,B);cout move A to C endl;Hanoi(n-1,B,A,C);,构成递归的条件,不能无限制地调用本身，必须有一个出口，化简为非递归状况直接处理。Procedure()if()return(initial value);else return(parameter exchange);,3.2.2 递

16、归过程与递归工作栈,递归过程在实现时，需要自己调用自己。,如：n!long Factorial(long n)if(n=0)return 1;else return n*Factorial(n-1);,求解阶乘 n!的过程,主程序 main:fact(4),参数 4 计算 4*fact(3),参数 3 计算 3*fact(2),参数 2 计算 2*fact(1),参数 1 计算 1*fact(0),参数 0 直接定值=1,参数传递,结果返回,递归调用,回归求值,但是，递归并不是一种高效的方法,调用次数 NumCall(k)=？,斐波那契数列的递归调用树,Fib(1),Fib(0),Fib(1)

17、,Fib(2),Fib(3),Fib(4),Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(1),Fib(2),Fib(3),Fib(5),2*Fib(k+1)-1,算法的时间复杂度：,O(2n),如何降低算法复杂度,采用动态规划（Dynamic Programming）通过辅助数组避免重复计算,用循环实现斐波那契数列,long FibIter(long n)if(n=1)return n;long twoback=0,oneback=1,Current;for(int i=2;i=n;i+)Current=twoback+oneback;twoback=oneb

18、ack;oneback=Current;return Current;,算法的时间复杂度：O(n),递归过程改为非递归过程,方法：单向递归和尾递归：直接用迭代实现 其他情形：借助栈 实现,单向递归和尾递归：用迭代法实现,单向递归：斐波那契数列long Fib(long n)if(n=1)return n;else return Fib(n-1)+Fib(n-2);,long FibIter(long n)if(n=1)return n;long twoback=0,oneback=1,Current;for(int i=2;i=n;i+)Current=twoback+oneback;twob

19、ack=oneback;oneback=Current;return Current;,尾递归：,void sterfunc(int A,int n)/消除了尾递归的非递归函数 while(n=0)cout value An endl;n-;,3.3 队列,定义队列是只允许在一端删除，在另一端插入的线性表。允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性 先进先出(FIFO,First In First Out),template class Queue public:Queue(int=10);/构造函数 void EnQueue(Type x);/进队 int

20、 DeQueue(Type/判队列满否,队列的抽象数据类型,队列的顺序存储表示,#include template class Queue private:int rear,front;/队尾,队头指针 Type*elements;/队列元素数组 int maxSize;/最大元素个数public:Queue(int sz=10);Queue()delete elements;void EnQueue(Type x);/进队,队列的进队和出队,队列的进队和出队,初始化：front=rear=-1 进队时：rear=rear+1，再将新元素按 rear 指示位置加入；队尾指针指示实际队尾位置。出

21、队时：front=front+1，队头指针指示实际队头的前一位置，再将下标为 front 的元素取。队满时：rear=maxsize 1;再进队将溢出（假溢出）；队空时:front=rear;再出队将队空处理。,队列的顺序存储表示循环队列（Circular Queue）,队列存放数组被当作首尾相接的表处理。当队头、队尾指针加1进到maxsize 1 后，再前进一个位置就自动到0，可用取模(余数)运算实现。队头指针进1:front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;队列初始化：front=rear=0;队空条件：front=rear;队

22、满条件：(rear+1)%maxSize=front,循环队列(Circular Queue),0,1,2,3,4,5,6,7,front,C,rear,D,E,F,G,H,(rear+1)%maxSize=front,A,int DeQueue(Type,循环队列其他操作的定义,(rear-front+maxSize)%maxSize,template int Queue:DeQueue(Type,队列的链接存储表示 链式队列,队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为 front=NULL。,front,rear,template class Queue;

23、template class QueueNode friend class Queue;private:Type data;/队列结点数据 QueueNode*link;/结点链指针public:QueueNode(Type d=0,QueueNode*next=NULL):data(d),link(next);,链式队列类的定义,template class Queue private:QueueNode*front,*rear;/队头、队尾指针指针public:Queue():rear(NULL),front(NULL)Queue();void EnQueue(Type x);int De

24、Queue(Type/实现与Queue()同,int IsEmpty()const return front=NULL;template Queue:Queue()/队列的析构函数 QueueNode*p;while(front!=NULL)/逐个结点释放 p=front;front=front-link;delete p;,template void Queue:EnQueue(Type item)/将新元素item插入到队列的队尾 if(front=NULL)/创建第一个结点front=rear=new QueueNode(item,NULL);else/队列不空,插入 rear-link

25、=new QueueNode(item,NULL);rear=rear-link;,template Type Queue:DeQueue()if(IsEmpty()return 0;/判队空 QueueNode*p=front;Type x=front-data;front=front-link;delete p;return x;template Type Queue:GetFront()if(IsEmpty()return 0;Type x=front-data;return x;,算法分析：入队：出队：,O(1)O(1),队列的应用,银行的排队系统,每个元素都有一个优先级。每次从队列中

26、取出的是具有最高优先级的元素。优先级的含义依赖于具体的应用。例如：操作系统中的进程调度,3.4 优先级队列(Priority Queue),优先级队列的类定义,#include#include$include const int maxPQSize=50;/缺省元素个数template class PQueue public:PQueue();PQueue()delete pqelements;void PQInsert(const Type,void makeEmpty()count=0;int IsEmpty()const return count=0;int IsFull()const

27、return count=maxPQSize;int Length()const return count;private:Type*pqelements;/优先级队列数组 int count;/队列元素计数,优先级队列部分成员函数的实现template PQueue:PQueue():count(0)pqelements=new TypemaxPQSize;assert(pqelements!=0);/分配断言template void PQueue:PQInsert(const Type count+；,template Type PQueue:PQRemove()assert(!IsEmpty();/判队空断言 Type min=pqelements0;int minindex=0;for(int i=1;icount;i+)/寻找最小元素 if(pqelementsi min)/存于min min=pqelementsi;minindex=i;pqelementsminindex=pqelementscount-1;count-;/删除 return min;,算法分析：PQInsert:PQRemove:,O(1)O(n),如果按优先级从大到小的顺序将队列组成一个链表,