1第三章第三章 栈、队列与广义表栈、队列与广义表 3.1 栈栈 3.2 队列队列 3.3 栈与队列的应用栈与队列的应用 3.4 广义表广义表23.1 栈栈 ( Stack ) 3栈的抽象数据类型栈的抽象数据类型ADT Stack Data 数据元素表数据元素表 top: 栈顶位置栈顶位置 Operations Constructor Process: 创建一个空栈创建一个空栈 IsEmpty Process: 判断栈是否为空判断栈是否为空 Output: 如果栈为空，则返回如果栈为空，则返回true，否则返回，否则返回false GetTop Process: 取栈顶元素取栈顶元素 Output: 返回栈顶元素返回栈顶元素 3.1.1 ADT栈栈4栈的抽象数据类型栈的抽象数据类型 Length Process: 求栈中元素个数求栈中元素个数 Output: 返回栈中元素的个数返回栈中元素的个数 Push / 入栈入栈 Input: 要添加的数据元素要添加的数据元素 Process: 向栈中添加元素向栈中添加元素x Pop / 出栈出栈 Process: 删除栈顶元素删除栈顶元素 Output: 返回栈顶元素返回栈顶元素 Clear Process: 删除栈中所有元素并置新的栈顶删除栈中所有元素并置新的栈顶 /Stack5一、顺序栈一、顺序栈const int MaxStackSize=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(); /栈清空栈清空;/ SeqStack3.1.2 栈的实现栈的实现6顺序栈的基本操作的实现顺序栈的基本操作的实现: SeqStack( ) /构造函数，初始化一个空栈构造函数，初始化一个空栈 StackList = new DataTypeMaxStackSize; top=-1; / SeqStack bool SeqStack : IsEmpty ( ) /判断栈是否为空判断栈是否为空 if(top=-1) return true; else return false;/ IsEmpty7bool SeqStack :IsFull( ) /判断栈是否已满判断栈是否已满 if(top=MaxStackSize-1) return true; else return false;/ IsFull8DataType SeqStack : GetTop( ) /取栈顶元素取栈顶元素 i f (IsEmpty( ) cout”栈空！栈空！”endl; return nulldata; return StackListtop;9栈顶指针栈顶指针top,指向栈底指向栈底位置位置top入栈入栈Atop出栈出栈栈满栈满BCDEFtop=-1,栈空，此时出栈，则下溢（栈空，此时出栈，则下溢（underflow)top= MaxStackSize-1,栈满，此时入栈，则上溢栈满，此时入栈，则上溢（overflow)toptoptoptoptoptoptoptoptoptoptop栈空栈空top123450栈空栈空123450ABCDEF123450顺序栈的入栈与出栈顺序栈的入栈与出栈10void SeqStack : Push(DataType x) /入栈入栈 if (IsFull( ) cout”栈满！栈满！”endl; else StackList+top = x;/ Push11DataType SeqStack : Pop( ) /出栈出栈 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)类的定义类的定义17类中操作算法描述如下：类中操作算法描述如下：void LinkStack : Push (DataType item ) /入栈操作入栈操作 p=new StackNode ( item); p-next=top-next; top-next=p;/Push18DataType 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 /栈空的情况栈空的情况 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 栈与递归栈与递归243递归算法的设计方法递归算法的设计方法 在设计递归算法时，应该遵循下面的规则在设计递归算法时，应该遵循下面的规则：（1）定义一个最小规模的问题，并给出其解；定义一个最小规模的问题，并给出其解；（2）把复杂的问题划分为同类型的若干规模较小的子问把复杂的问题划分为同类型的若干规模较小的子问 题，并分别解决子问题；题，并分别解决子问题；（3）把各子问题的解组合起来，即可得到原问题的解。把各子问题的解组合起来，即可得到原问题的解。 3.1.3 栈与递归栈与递归25例例1 1 递归的执行情况分析递归的执行情况分析-n!-n! int fact (int n) if ( n=0) fact= 1; else fact=n* fact ( n-1); void main( ) int f; f=fact(3); coutf; 3.1.3 栈与递归栈与递归26地址地址 ntop递归调用执行情况如下：递归调用执行情况如下：系统栈系统栈 int fact (int n) 1 if ( n=0) 2 fact= 1; 3 else 4 fact=n* fact( n-1);3.1.3 栈与递归栈与递归27 int fact (int n) 1if ( n=0) 2 fact= 1; 3else 4 fact=n* fact( n-1);地址地址 n3n*fact(2); 4 n=3 topn递归调用执行情况如下：递归调用执行情况如下：系统栈系统栈283n*fact(2);n2n*fact(1);4 n=2 4 n=3 topn地址地址 n递归调用执行情况如下：递归调用执行情况如下：系统栈系统栈 int fact (int n) 1if ( n=0) 2 fact= 1; 3else 4fact=n* fact( n-1);291n*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);301n*fact(n-1);4 n=1 4 n=2 4 n=3 topn3n*fact(2);n2n*fact(1);n0n地址 nfact(0)=1递归调用执行情况如下：递归调用执行情况如下：系统栈系统栈 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);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);323n*fact(n-1);n2n*fact(n-1);n0nfact(0)=11n*fact(n-1);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);333n*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);34计算斐波那契数列的函数计算斐波那契数列的函数Fib(n)的定义的定义求解斐波那契数列的递归算法求解斐波那契数列的递归算法long Fib ( int n ) if ( n = 0|n=1 ) return n; else return Fib (n-1) + Fib (n-2);2),2() 1(0,1,)(nnFibnFibnnnFib35Fib(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，建立如下一个调用层次树，建立如下一个调用层次树36非递归实现非递归实现Fibonacci函数如下：函数如下： long Fib(int n) long oneback=0 , twoback=1 , current; if(n=0|n=1) return n; else for(i=2;itemp) return An-1; else return temp; （2）求数组）求数组A中的最大整数。中的最大整数。39例：例：Tower of Hanoi问题问题问题描述问题描述：有：有A,B,C三个塔座，三个塔座，A上套有上套有n个直径不个直径不同的圆盘，按直径从小到大叠放，形如宝塔同的圆盘，按直径从小到大叠放，形如宝塔,编号编号1,2,3n。要求将要求将n个圆盘从个圆盘从A移到移到C，叠放顺序叠放顺序不变，移动过程中遵循下列原则：不变，移动过程中遵循下列原则：v每次只能移一个圆盘每次只能移一个圆盘v圆盘可在三个塔座上圆盘可在三个塔座上 任意移动任意移动v任何时刻，每个塔座上任何时刻，每个塔座上 不能将大盘压到小盘上不能将大盘压到小盘上40执行情况执行情况递归工作栈保存内容：实参递归工作栈保存内容：实参n,x,y,z和返回地址和返回地址返回地址用行编号表示返回地址用行编号表示汉诺塔解决方法汉诺塔解决方法n1时，先把时，先把A上上的的n-1个圆盘移到个圆盘移到B,然后将然后将n号盘从号盘从A移到