数据结构课件C++版=.ppt

《数据结构课件C++版=.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈和队列栈栈的应用队列队列的应用优先级队列2021/7/28mayan定义：栈限定只能在表的一端进行插入和删除运算的线性表。递归函数的实现在递归函数的执行中，需多次自己调用自己，递归函数是如何执行的？先看一般函数的调用机制如何实现的。A(){…B();…}C(){……}B(){…C();…}调用调用返回返回函数调用顺序ABC函数返回顺序CBA后调用的函数先返回函数调用机制可通过栈来实现计算机正是利用栈来实现函数的调用和返回的n=3阶乘函数fact(n)的执行过程Main(){intn=3,y;Ly=fact(n);}调用调用调用intfact(n){If（n=1）re

2、turn（1）；ElseL1return（n*fact(n-1)）；}n=3intfact(intn){If（n=1）return（1）；ElseL1return（n*fact(n-1)）；}n=2intfact(intn){If（n=1）return（1）；ElseL1return（n*fact(n-1)）；}//factn=1L3L11L12返回1返回2返回61n*fact(n-1)n*fact(n-1)fact(n)返回地址实参递归调用中栈的变化将十进制整数转换成二至九之间的任一进制数输出将一个十进制数4327转换成八进制数(10347)8：abc3211121312

3、1YXZ2021/7/28mayan第三章栈和队列--栈的定义栈和队列称为运算受限的线性表。栈（stack）是指只允许在表的末端进行插入和删除的线性表。栈又叫做后进先出（LIFO）的线性表。栈的基本概念栈是一种“特殊”的线性表，这种线性表上的插入和删除运算限定在表的某一端进行。栈顶：允许进行插入和删除的这一端。栈底：反之为栈底。栈顶元素：处于栈顶位置的数据元素称为～。栈顶元素的位置由栈顶指针变量记录；空栈:当栈中不含任何数据元素时称为～2021/7/28mayan第三章栈和队列--顺序栈基于数组的存储表示实现的栈称为顺序栈。当前栈顶位置由数组下标指针top指示，即top指示

4、最后加入的元素的存储位置，当top=-1时栈空，当top=maxSize-1时栈满。顺序栈的类定义2021/7/28mayan第三章栈和队列--顺序栈的类定义templateclassSeqStack{//顺序栈类定义private:T*elements;//栈元素存放数组inttop;//栈顶指针intmaxSize;//栈最大容量public:SeqStack(intsz=50);//构造函数~SeqStack(){delete[]elements;}//析构函数2021/7/28mayan第三章栈和队列--顺序栈的类定义voidPush(constT&

5、x);//进栈boolPop(T&x);//出栈boolgetTop(T&x);//取栈顶内容boolIsEmpty()const{returntop=-1;}boolIsFull()const{returntop=maxSize-1;}intgetSize()const{returntop+1;}//返回栈中元素个数voidmakeEmpty(){top=-1}//清空栈的内容};2021/7/28mayan第三章栈和队列--顺序栈的函数实现//顺序栈的构造函数templateSeqStack::SeqStack(intsz):top(-1),max

6、Size(sz){elements=newT[maxSize];}2021/7/28mayan第三章栈和队列--顺序栈的函数实现//若栈不满,则将元素x插入该栈栈顶,否则溢出处理templatevoidSeqStack::Push(constT&x){if(IsFull()==true)printf(“栈满，不能入栈”);return;//栈满elements[++top]=x;//栈顶指针先加1,再进栈}2021/7/28mayan第三章栈和队列--顺序栈的函数实现//函数退出栈顶元素并返回栈顶元素的值templateboolSeqS

7、tack::Pop(T&x){if(IsEmpty()==true)returnfalse;x=elements[top--];//栈顶指针退1returntrue;//退栈成功}2021/7/28mayan第三章栈和队列--顺序栈的函数实现//若栈不空则函数返回该栈栈顶元素templateboolSeqstack::getTop(T&x){if(IsEmpty()==true)returnfalse;x=elements[top];returntrue;}2021/7/28mayan第