堆栈知识详解(简单易懂)ppt课件.ppt





《堆栈知识详解(简单易懂)ppt课件.ppt》由会员分享,可在线阅读,更多相关《堆栈知识详解(简单易懂)ppt课件.ppt(75页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第第5 5章章 堆栈堆栈-后进先出:一种操作受限的线性表后进先出:一种操作受限的线性表信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能主要内容主要内容堆栈的定义堆栈的定义堆栈的描述堆栈的描述公式化描述公式化描述链表描述链表描述堆栈的应用堆栈的应用括号匹配、汉诺塔、火车车厢重排括号匹配、汉诺塔、火车车厢重排迷宫、开关盒布线、离线等价类迷宫、开关盒布线、离线等价类2信息技术科学学院为深入学习习近平
2、新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能堆栈定义堆栈定义DCBA栈顶EpushABCDE栈顶ABCDE栈顶ExtopABCDE栈顶popExtopABCD栈顶栈底堆栈堆栈(stackstack)是一个)是一个线性表线性表,其其插入插入和和删除删除操作都在表的操作都在表的同一端同一端进行,这进行,这端被称为端被称为栈顶栈顶(toptop),),另一端被称为另一端被称为栈底栈底(bottombottom)LIFOLIFOLast in,First outLast in,First out信息技术科学学院为深入学习习近平新时代中国特色社会主义思想
3、和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能抽象数据类型抽象数据类型抽象数据类型抽象数据类型StackStack 实例实例元素线性表,栈底,栈顶元素线性表,栈底,栈顶操作操作CreateCreate()():创建一个空的堆栈:创建一个空的堆栈IsEmptyIsEmpty()():如果堆栈为空,则返回:如果堆栈为空,则返回
4、truetrue,否则返回,否则返回falsefalseIsFullIsFull()():如果堆栈满,则返回:如果堆栈满,则返回truetrue,否则返回,否则返回falsefalseTopTop()():返回栈顶元素:返回栈顶元素PushPush(x x):向堆栈中添加元素:向堆栈中添加元素x xPopPop(x x):删除栈顶元素,并将它传递给:删除栈顶元素,并将它传递给x x 信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能主要内容主要内容堆栈的定义堆栈的定义堆栈的描述堆栈的描述公式化描述公式化描述链表描述链表
5、描述堆栈的应用堆栈的应用括号匹配、汉诺塔、火车车厢重排括号匹配、汉诺塔、火车车厢重排迷宫、开关盒布线、离线等价类迷宫、开关盒布线、离线等价类7信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能公式化描述:继承线性表公式化描述:继承线性表templateclass Stack:private LinearList /LIFO objects public:Stack(int MaxStackSize=10):LinearList(MaxStackSize)bool IsEmpty()const return Linear
6、List:IsEmpty();bool IsFull()const return(Length()=GetMaxSize();线性表尾部作为栈顶信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能公式化描述(续)公式化描述(续)T Top()const if(IsEmpty()throw OutOfBounds();T x;Find(Length(),x);return x;Stack&Push(const T&x)Insert(Length(),x);return*this;Stack&Pop(T&x)Delete(L
7、ength(),x);return*this;取栈顶提取最后一个元素压栈添加到表尾出栈提取最后一个元素信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能实现方法分析实现方法分析IsFullIsFull需要获取数组大小需要获取数组大小方法一方法一将类将类LinearListLinearList的成员的成员MaxSizeMaxSize变为变为protectedprotected类型类型方法二:方法二:LinearListLinearList类增加函数类增加函数protected:int GetMaxSize()const
8、return MaxSize;LinearListLinearList类的变化不会影响类的变化不会影响StackStack类,更好!类,更好!信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能实现方法分析实现方法分析继承方式为什么是继承方式为什么是privateprivate?privateprivate继承会把基类的所有成员变为派生类的私有继承会把基类的所有成员变为派生类的私有成员成员栈虽可看作线性表的特例,但毕竟不是栈虽可看作线性表的特例,但毕竟不是用户使用用户使用StackStack类,我们希望他们使用类,我们希
9、望他们使用PushPush、PopPop,而不是,而不是InsertInsert、DeleteDelete而而privateprivate继承恰好可使继承恰好可使InsertInsert、DeleteDelete成为成为StackStack的私有成员,用户无法看到的私有成员,用户无法看到信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能StackStack的效率的效率构造函数、析构函数与构造函数、析构函数与LinearListLinearList相同相同T T:基本类型,:基本类型,(1)(1)T T:用户自定义类,:
10、用户自定义类,(MaxStackSize)(MaxStackSize)其他函数:其他函数:(1)(1)信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能H1.H1.自定义的自定义的StackStack类类templateclass Stack public:Stack(int MaxStackSize=10);Stack()delete stack;bool IsEmpty()const return top=-1;bool IsFull()const return top=MaxTop;T Top()const;St
11、ack&Push(const T&x);Stack&Pop(T&x);private:int top;/current top of stack int MaxTop;/max value for top T*stack;/element array;信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能构造函数构造函数templateStack:Stack(int MaxStackSize)/Stack constructor.MaxTop=MaxStackSize-1;stack=new TMaxStackSize;t
12、op=-1;空栈信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能TopTop函数函数templateT Stack:Top()const/Return top element.if(IsEmpty()throw OutOfBounds();return stacktop;信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能PushPush函数函数templateStack&Stack:Push(const T&x)/Push x to stac
13、k.if(IsFull()throw NoMem();/Push fails stack+top=x;return*this;信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能PopPop函数函数templateStack&Stack:Pop(T&x)/Delete top element and put in x.if(IsEmpty()throw OutOfBounds();x=stacktop-;return*this;信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精
14、神,充分发挥中小学图书室育人功能数组描述缺陷数组描述缺陷与线性表数组描述类似,空间利用率低与线性表数组描述类似,空间利用率低两个堆栈特例,空间利用率较高两个堆栈特例,空间利用率较高PushPush最坏情况(数组满)仍为最坏情况(数组满)仍为(ArraySize)(ArraySize)Pop Pop(1)(1)信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能主要内容主要内容堆栈的定义堆栈的定义堆栈的描述堆栈的描述公式化描述公式化描述链表描述链表描述堆栈的应用堆栈的应用括号匹配、汉诺塔、火车车厢重排括号匹配、汉诺塔、火车
15、车厢重排迷宫、开关盒布线、离线等价类迷宫、开关盒布线、离线等价类19信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能链表描述链表描述栈顶在链表哪一端?栈顶在链表哪一端?尾节点尾节点Push(x)Insert(n,x)Push(x)Insert(n,x):(n)(n)Pop(x)Delete(n,x)Pop(x)Delete(n,x):(n)(n)首节点首节点Push(x)Insert(0,x)Push(x)Insert(0,x):(1)(1)Pop(x)Delete(1,x)Pop(x)Delete(1,x):(1)
16、(1)信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能LinkedStackLinkedStack类类templateclass LinkedStack:private Chain public:bool IsEmpty()const return Chain:IsEmpty();bool IsFull()const;T Top()const if(IsEmpty()throw OutOfBounds();T x;Find(1,x);return x;信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十
17、九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能LinkedStackLinkedStack类类 LinkedStack&Push(const T&x)Insert(0,x);return*this;LinkedStack&Pop(T&x)Delete(1,x);return*this;信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能IsFullIsFull函数函数templatebool LinkedStack:IsFull()const/Is stack full?try ChainNode*p=ne
18、w ChainNode;delete p;return false;catch(NoMem)return true;笨拙!笨拙!信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能H2.H2.自定义的链表实现自定义的链表实现template class Node friend LinkedStack;private:T data;Node*link;信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能自定义的链表实现(续)自定义的链表实现(续)te
19、mplateclass LinkedStack public:LinkedStack()top=0;LinkedStack();bool IsEmpty()const return top=0;bool IsFull()const;T Top()const;LinkedStack&Push(const T&x);LinkedStack&Pop(T&x);private:Node*top;/pointer to top node;信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能析构函数析构函数templateLinke
20、dStack:LinkedStack()/Stack destructor.Node*next;while(top)next=top-link;delete top;top=next;信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能IsFullIsFull函数函数templatebool LinkedStack:IsFull()const/Is the stack full?try Node*p=new Node;delete p;return false;catch(NoMem)return true;信息技术科学
21、学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能TopTop函数函数templateT LinkedStack:Top()const/Return top element.if(IsEmpty()throw OutOfBounds();return top-data;信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能PushPushtemplateLinkedStack&LinkedStack:Push(const T&x)/Push x to stac
22、k.Node*p=new Node;p-data=x;p-link=top;top=p;return*this;信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能PopPoptemplateLinkedStack&LinkedStack:Pop(T&x)/Delete top element and put it in x.if(IsEmpty()throw OutOfBounds();x=top-data;Node*p=top;top=top-link;delete p;return*this;信息技术科学学院为深入
23、学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能H1-2H1-2小结小结堆栈的两种实现方式堆栈的两种实现方式公式化公式化链表链表Create()(1)/(MaxSize)(1)/(MaxSize)(1)(1)Destroy()(1)/(MaxSize)(1)/(MaxSize)(n)(n)IsEmpty()(1)(1)(1)(1)IsFull()(1)(1)(1)(1)Top()(1)(1)(1)(1)Push()(1)(1)(1)(1)Pop()(1)(1)(1)(1)31信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的
24、十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能主要内容主要内容堆栈的定义堆栈的定义堆栈的描述堆栈的描述公式化描述公式化描述链表描述链表描述堆栈的应用堆栈的应用括号匹配、汉诺塔、火车车厢重排括号匹配、汉诺塔、火车车厢重排迷宫、开关盒布线、离线等价类迷宫、开关盒布线、离线等价类32信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能括号匹配括号匹配(a*(b+c)+d)+(e-b)(a*(b+c)+d)+(e-b)符合语法符合语法(a+b)(a+b)(不符合语法不符合语法寻找匹配括号对寻找匹配括号对正确处理正
25、确处理和未匹配括号和未匹配括号错误报告错误报告括号匹配是一个基础问题,可以引申到括号匹配是一个基础问题,可以引申到C+C+编译器编译器数学公式自动求解数学公式自动求解信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能34信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能35信息技术科学学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能算法设计思路算法设计思路(a*(b+c(a*(b
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 堆栈 知识 详解 简单 易懂 ppt 课件

限制150内