《栈队列和递归》PPT课件.ppt

《《栈队列和递归》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈、队列和递归特殊线性表栈队列串⑴栈的定义⑵操作特性⑶ADT定义⑴队列定义⑵操作特性⑶ADT定义⑴串的定义⑵基本概念⑶ADT定义顺序栈链栈循环队列链队列顺序存储链接存储逻辑结构存储结构逻辑结构逻辑结构存储结构存储结构比较模式匹配比较比较⑴基本操作的实现⑵时间复杂度⑴基本操作的实现⑵时间复杂度3.1栈（Stack）3.2队列（Queue）１.逻辑结构２.存储结构与实现３.应用实例１.逻辑结构２.存储结构与实现３.应用实例３.1栈1、栈的逻辑结构空栈：不含任何数据元素的栈。（a1,a2,……,an）栈：限定仅在一端进行插入和删除操作的线性表。栈顶栈底允许

2、插入和删除的一端称为栈顶，另一端称为栈底。数据元素之间的逻辑关系：一对一。注：栈的运算规则只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。入栈：插入元素到栈顶（即表尾）的操作。出栈：从栈顶（即表尾）删除最后一个元素的操作。问：栈与一般线性表有什么不同？一般线性表（堆）栈逻辑结构：一对一逻辑结构：一对一存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取运算规则：后进先出(LIFO)入栈操作演示出栈操作演示a1a2a3入栈栈底栈顶插入：入栈、进栈、压栈栈顶栈顶入栈的操作示图：栈顶a1a2a3栈底栈顶删除：出栈、弹栈

3、栈顶栈顶出栈的操作示图：栈顶栈的操作特性：后进先出出栈思考题１：一个栈的输入序列为123，若在入栈的过程中允许出栈，且每个元素只允许进一次栈，则可能得到的出栈序列有哪些？答：可以通过穷举所有可能性来求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合计有5种可能性。思考题２：设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）

4、a，c，d，bA、D可以（B、C不行）。讨论：有无通用的判别原则？有。若输入序列i，j，k，则不存在输出序例k、i、j;答：2、栈的存储结构顺序栈、链式栈（１）顺序栈——栈的顺序存储结构(重点)如何改造数组实现栈的顺序存储？012345678a1确定用数组的哪一端表示栈底。附设指针top指示栈顶元素在数组中的位置。topS进栈核心语句：top++;S[top]=a1;栈空：top==-1012345678topa1topa2top进栈的操作步骤如何？012345678a1a2栈满：top==MAX_SIZE-1栈满的如何判断？topa3a4a5a6a7a8

5、a9动态栈类的定义：template//定义模板类DSeqStackclassDSeqStack{public:DSeqStack(intsize);//构造函数，栈的初始化~DSeqStack(){delete[]S;}//析构函数voidPush(consttype&item);//将元素item入栈typePop();//将栈顶元素弹出typeGetTop();//取栈顶元素（并不删除）intEmpty(){returntop==-1;}//判断栈是否为空intfull()const{returntop==MaxSize-1;}

6、//为满则返回1，否则返回0voidclear(){top=-1;}//清空栈private:type*S;//存放栈元素的数组起始地址inttop;//栈顶指针，指示栈顶元素在数组中的下标intMaxSize;//栈最大可容纳元素个数};顺序栈的构造函数算法实现templateDSeqStack::DSeqStack(intsize):top(-1),MaxSize(size){//建立一个最大尺寸为size的空栈S=newtype[MaxSize];//创建存储栈的数组if(S==NULL)//分配不成功{cerr<<

7、"动态存储失败！"<DSeqStack::DSeqStack(intsize);算法实现：顺序栈的入栈操作算法实现templatevoidDSeqStack::Push(consttype&item){if(top==MaxSize-1)throw"栈满！";top++;//栈未满，则入栈S[top]=item;}操作接口：templatevoidDSeqStack::Push(

8、consttype&item)算法实现：时间复杂度？O(1)出栈核