欢迎来到天天文库
浏览记录
ID:59265693
大小:388.50 KB
页数:48页
时间:2020-09-22
《数据结构与算法分析(第3章 栈与队列)ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、数据结构与算法廊坊师范学院数学与信息科学学院授课教师:崔业勤第三章栈与队列本章重点难点重点:栈和队列的逻辑结构定义以及在两种(顺序,链式)存储结构上如何实现栈和队列的基本运算.难点:循环队列的边界处理.3.1栈●栈:是一种特殊的线性结构,只能在一端进行插入和删除的线性表。●栈的相关概念:(1)栈顶:线性表中进行插入删除的一端(2)栈底:与栈顶对应的一端(3)入栈:插入元素(push,压栈)(4)出栈:删除元素(pop,弹出)123栈的结构模拟特点:后进先出栈顶栈底3.1.1栈的基本运算入栈出栈读取栈顶元素栈是否为空等栈的抽象数据
2、类型定义TempateClassStack{boolPush(constTvalue);boolPop(T&value);boolTop(T&value);boolEmpty();..};3.1.2栈的物理实现—顺序栈●相关变量:(1)栈的最大长度:intmaxsize(2)栈顶的位置:inttop(3)栈的指针变量:T*sttemplateclassarrStack{private:intmaxsize;//栈的最大长度inttop;//栈顶下标T*st;//指向栈的指针public:arrSt
3、ack(intsize){maxsize=size;top=-1;st=newT[maxsize];}arrStack(){top=-1;}~arrStack(){delete[]st;}voidClear(){//清空栈的内容top=-1;}//显示栈元素栈的顺序实现boolPush(constTitem){//入栈if(top==maxsize-1){cout<<"stackisfull!"<4、ntrue;}}//出栈boolPop(T&item){if(top==-1){cout<<"thestackisempty,can'tpop!"<Topp{if(top==-1){cout<<"thestackise5、mpty,can'tread!"<*top(2)栈中元素的个数:intsize注意:栈的结构中top了代替头指针4321top栈顶栈底templateclassLink{public:Tdata;//结点的数据域Link*next;//结点的指针域Link(Tinfo,Link*nextValue=NULL)//具有两个参数的6、List构造函数{data=info;next=nextValue;}Link(Link*nextValue=NULL)//具有一个参数的List构造函数{next=nextValue;}};栈的链式实现#include"link.h"templateclasslinkstack{private:Link*top;//指向栈顶的指针intsize;//存放元素的个数public:linkstack(){top=NULL;size=0;}~linkstack(){clear();}voidclear()7、{while(top!=NULL){Link*tmp=top;top=top->next;deletetmp;}size=0;}//入栈boolpush(constTitem){Link*tmp=newLink(item,top);top=tmp;size++;returntrue;}//出栈boolpop(T&item){Link*tmp;if(size==0){cout<<"thestackisempty,can'tpop!"<data;tmp8、=top->next;deletetop;top=tmp;size--;returnfalse;}//取栈顶元素booltopp(T&item){if(size==0){cout<<"thestackisempty,can'tread!"<
4、ntrue;}}//出栈boolPop(T&item){if(top==-1){cout<<"thestackisempty,can'tpop!"<Topp{if(top==-1){cout<<"thestackise
5、mpty,can'tread!"<*top(2)栈中元素的个数:intsize注意:栈的结构中top了代替头指针4321top栈顶栈底templateclassLink{public:Tdata;//结点的数据域Link*next;//结点的指针域Link(Tinfo,Link*nextValue=NULL)//具有两个参数的
6、List构造函数{data=info;next=nextValue;}Link(Link*nextValue=NULL)//具有一个参数的List构造函数{next=nextValue;}};栈的链式实现#include"link.h"templateclasslinkstack{private:Link*top;//指向栈顶的指针intsize;//存放元素的个数public:linkstack(){top=NULL;size=0;}~linkstack(){clear();}voidclear()
7、{while(top!=NULL){Link*tmp=top;top=top->next;deletetmp;}size=0;}//入栈boolpush(constTitem){Link*tmp=newLink(item,top);top=tmp;size++;returntrue;}//出栈boolpop(T&item){Link*tmp;if(size==0){cout<<"thestackisempty,can'tpop!"<data;tmp
8、=top->next;deletetop;top=tmp;size--;returnfalse;}//取栈顶元素booltopp(T&item){if(size==0){cout<<"thestackisempty,can'tread!"<
此文档下载收益归作者所有