• / 61
  • 下载费用:10 金币  

数据结构第三章课件.ppt

关 键 词:
数据结构第三章课件.ppt
资源描述:
栈的概念 栈的存储结构 栈的操作算法 栈的应用 队列的概念 队列的存储结构与操作算法 队列的操作算法 队列的应用,第三章 栈和队列,3.1 栈 ( Stack )的概念,只允许在一端插入和删除的表 允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom) 特点后进先出 (LIFO),进栈示例,,出栈示例,,例: 假定有4个元素A,B,C,D,按所列次序进栈,试写出所有可能的出栈序列。注意,每一个元素进栈后都允许出栈,如ACDB就是一种出栈序列。 解:可能的出栈序列有ABCD,ABDC,ACBD,ACDB,ADCB,BACD,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA。,栈的基本操作,1、初始化 2、进栈PUSH 3、出栈POP 4、取栈顶元素GetTop 5、判栈是否非空,3.2 栈的存储结构,,顺序存储------顺序栈 链式存储-------链栈,,template class SeqStack {T data[MaxSize]; //存放栈元素int top; //栈顶指针 public:SeqStack( ) ; //构造函数void Push(T x); //入栈T Pop( ); //出栈T Top( ); //取栈顶元素bool Empty( ); //判断栈是否为空 };,链式栈的存储,链式栈无栈满问题,空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头,,template class LinkStack {Node *top; //栈顶指针 public:LinkStack( ); //构造函数~LinkStack( ); //析构函数void Push(T x); //入栈T Pop( ); //出栈T Top( ); //取栈顶元素bool Empty( ); //判断链栈是否为空栈 };,3.3 栈的操作算法,1. 顺序栈的操作算法 2. 链式栈的操作算法,1 顺序栈的操作算法,顺序栈的初始化 template SeqStack::SeqStack( ) {top=-1; },(2) 顺序栈的入栈操作,template void SeqStack::Push(T x) {if (top== MaxSize-1) {cerr“上溢“; exit(1);}top++;data[top]=x; },(3) 顺序栈的出栈操作,template T SeqStack::Pop( ) { if (top==-1) {cerr“下溢“; exit(1);}x=data[top];top--;return x; },(4) 取栈顶元素操作,template T SeqStack::Top( ) {if (top==-1) {cerr“下溢“; exit(1);}return data[top]; },(5) 判断顺序栈是否为空,template bool SeqStack::Empty( ) {return top==-1; },2 链栈的操作算法,(6) 链栈初始化 template LinkStack::LinkStack( ) {top=NULL; },链栈入栈操作 template void LinkStack::Push( T x){s=new Node;s-data=x;s-next=top;top=s;},(8) 链栈出栈操作 template T LinkStack::Pop( ) { if (top==NULL) {cerrdata; p=top; top=top-next; delete p;return x; },(9) 取栈顶元素操作,template T LinkStack::Top( ) {if (top==NULL) {cerrdata; },(10) 判断链栈是否为空,template bool LinkStack::Empty( ) {return top==NULL; },(11) 链栈的析构函数 template LinkStack::~LinkStack( ) { p=top;while (p){ q=p;p=p-next;delete q;}top=NULL; },思考:两个栈共享同一段内容空间,为了使得空间利用率最高,应如何分配栈空间? --------两个堆栈共享空间,,,,,,,,0,maxsize-1,lefttop,righttop,,,3.4 栈的应用举例 1. 栈的应用之一: 递归调用 例: Hanoi塔问
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:数据结构第三章课件.ppt
链接地址:https://www.weizhuannet.com/p-9819131.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开