《数据结构的应用(栈——基础知识)ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构的应用(栈——基础知识)ppt课件.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确栈栈基础知识基础知识基础知识基础知识在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确栈的定义在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确一摞书籍、一叠盘子一摞书籍、一叠盘子一摞书籍、一叠盘子一摞书籍、一叠盘子往手电筒里放电池往手电筒里放电池往手电筒里放电池往手电筒里放电池,取电池取电池取电池取电池.最先放的是最后被取最先放的是最后被取最先放的是最后被取最先放的是最后
2、被取出出出出铁路调度中用到停车栈铁路调度中用到停车栈铁路调度中用到停车栈铁路调度中用到停车栈 生活中栈的实例生活中栈的实例在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确栈的插入和删除操作分别称栈的插入和删除操作分别称为为进栈进栈和和出栈出栈。进栈是将一。进栈是将一个数据元素存放在栈顶，出个数据元素存放在栈顶，出栈是将栈顶元素取出。图中栈是将栈顶元素取出。图中 a a1 1称为栈底元素，称为栈底元素，a an n为栈顶为栈顶元素。元素。定义：栈定义：栈(stack)是限定仅在表尾的一端进行插入或是限定仅在表尾的一端进行插入或删除操作的
3、线性表。允许进行插入或删除操作的一端删除操作的线性表。允许进行插入或删除操作的一端称为栈顶称为栈顶(top)，而另一端称为栈底，而另一端称为栈底(bottom)。不含。不含元素的栈称为空栈。元素的栈称为空栈。栈的定义及基本运算栈的定义及基本运算 a1 a2 an-1 an 栈顶栈顶(top)栈底栈底(bottom)出栈出栈 进栈进栈 栈底元素栈底元素 栈顶元素栈顶元素栈顶元素栈顶元素 在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确栈的栈的“上溢上溢”和和“下溢下溢”当栈满时再做进栈运算必定产生空间溢出，简称当栈满时再做进栈运算必定产
4、生空间溢出，简称当栈满时再做进栈运算必定产生空间溢出，简称当栈满时再做进栈运算必定产生空间溢出，简称“上溢上溢上溢上溢”;当栈空时再做退栈运算也将产生溢出，当栈空时再做退栈运算也将产生溢出，当栈空时再做退栈运算也将产生溢出，当栈空时再做退栈运算也将产生溢出，简称简称简称简称“下溢下溢下溢下溢”。上溢是一种出错状态，应该设法。上溢是一种出错状态，应该设法。上溢是一种出错状态，应该设法。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序避免之；下溢则可能是正常现象，因为栈在程序避免之；下溢则可能是正常现象，因为栈在程序避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或
5、终态都是空栈，所以下溢常中使用时，其初态或终态都是空栈，所以下溢常中使用时，其初态或终态都是空栈，所以下溢常中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。常用来作为程序控制转移的条件。常用来作为程序控制转移的条件。常用来作为程序控制转移的条件。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确Init()Destroy(S)Clear(S)Push(S,e)Pop(S,e)IsEmpty(S)Size(S)GetTop(S,e)栈的主要操作栈的主要操作在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设
6、置具有一定的梯度，由浅入深，所提出的问题也很明确顺序栈的操作实现在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确typedef structtypedef struct DataType dataMaxSize;DataType dataMaxSize;int top;/top int top;/top 指示栈顶元指示栈顶元指示栈顶元指示栈顶元/素在顺序栈中的位置素在顺序栈中的位置素在顺序栈中的位置素在顺序栈中的位置(下标下标下标下标)SeqStackSeqStack a1 a2 an-1 an top 栈底栈底(bottom)栈底元
7、素栈底元素 栈顶元素栈顶元素栈顶元素栈顶元素 栈的顺序存储定义栈的顺序存储定义在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确AEs.top43210s.top=-1(a)空栈空栈43210s.tops.top=0(b)进栈进栈s.top43210ABCDs.top=4(c)栈满栈满s.top43210s.top=2(d)出栈出栈ABCAE在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 置空栈：首先建立栈空间，然后初始化栈置空栈：首先建立栈空间，然后初始化栈置空栈：首先建立
8、栈空间，然后初始化栈置空栈：首先建立栈空间，然后初始化栈顶指针。顶指针。顶指针。顶指针。SeqStack *Init()SeqStack *Init()SeqStack *s;SeqStack *s;s=new SeqStack;s=new SeqStack;s-top=-1;s-top=-1;return s;return s;顺序栈的基本操作顺序栈的基本操作在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 判空栈判空栈判空栈判空栈 bool IsEmpty(SeqStack*s)bool IsEmpty(SeqStack*s)if
9、(s-top=-1)if(s-top=-1)return true;return true;else else return false;return false;顺序栈的基本操作顺序栈的基本操作在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 入栈入栈入栈入栈int Push(SeqStack*s,DataType x)int Push(SeqStack*s,DataType x)if(s-top=MaxSize-1)if(s-top=MaxSize-1)return ERROR;/return ERROR;/栈满不能入栈栈满不能入
10、栈栈满不能入栈栈满不能入栈 else else s-top+;s-top+;s-datas-top=x;s-datas-top=x;return OK;return OK;顺序栈的基本操作顺序栈的基本操作在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 出栈出栈出栈出栈 int Pop(SeqStack*s,DataType*x)int Pop(SeqStack*s,DataType*x)if(IsEmpty(s)if(IsEmpty(s)return ERROR;/return ERROR;/栈空栈空栈空栈空 else else *
11、x=s-datas-top;/*x=s-datas-top;/栈顶元素存入栈顶元素存入栈顶元素存入栈顶元素存入*x x s-top-;s-top-;return OK;return OK;顺序栈的基本操作顺序栈的基本操作在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 取栈顶元素取栈顶元素取栈顶元素取栈顶元素DataType GetTop(SeqStack*s)DataType GetTop(SeqStack*s)if(IsEmpty(s)if(IsEmpty(s)return ERROR;/return ERROR;/栈空栈空栈空栈
12、空 returnreturn s-datas-top;s-datas-top;顺序栈的基本操作顺序栈的基本操作在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确链栈的操作实现在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确a1a2a3栈底栈顶.an若是栈中元素的数目变化范若是栈中元素的数目变化范围较大或不清楚栈元素的数围较大或不清楚栈元素的数目，就应该考虑使用链式存目，就应该考虑使用链式存储结构。人们将用链式存储储结构。人们将用链式存储结构表示的栈称作结构表示的栈称作“链栈链栈
13、”。由于栈的插入删除操作只由于栈的插入删除操作只能在一端进行，而对于单链能在一端进行，而对于单链表来说，在首端插入删除结表来说，在首端插入删除结点要比尾端相对地容易一些。点要比尾端相对地容易一些。链栈的示意链栈的示意top在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确typedef struct Nodetypedef struct Node DataType data;DataType data;Node*next;Node*next;StackNode,*LinkStack;StackNode,*LinkStack;栈的链式存储
14、定义栈的链式存储定义在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 置空栈置空栈置空栈置空栈 void Init(void Init(LinkStack topLinkStack top)top=NULL;top=NULL;链栈的基本操作链栈的基本操作在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 判栈空判栈空判栈空判栈空bool IsEmpty(LinkStack top)bool IsEmpty(LinkStack top)return top=NULL;return
15、 top=NULL;链栈的基本操作链栈的基本操作在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 入栈入栈入栈入栈 int Push(LinkStack top,DataType x)int Push(LinkStack top,DataType x)/*/*将数据元素将数据元素将数据元素将数据元素x x压入栈压入栈压入栈压入栈headhead中中中中*/StackNode*temp=new StackNode;StackNode*temp=new StackNode;if(temp=NULL)if(temp=NULL)return
16、ERROR;/*return ERROR;/*申请空间失败申请空间失败申请空间失败申请空间失败*/temp-data=x;temp-data=x;temp-next=top;temp-next=top;top=temp;/*top=temp;/*修改当前栈顶指针修改当前栈顶指针修改当前栈顶指针修改当前栈顶指针*/return OK;return OK;链栈的基本操作链栈的基本操作在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 出栈出栈出栈出栈int Pop(LinkStack top,DataType*x)int Pop(LinkS
17、tack top,DataType*x)/*/*将栈将栈将栈将栈headhead的栈顶元素弹出，放到的栈顶元素弹出，放到的栈顶元素弹出，放到的栈顶元素弹出，放到x x所指的存储空间中所指的存储空间中所指的存储空间中所指的存储空间中*/if(top=NULL)/*if(top=NULL)/*栈为空栈为空栈为空栈为空*/return ERROR;return ERROR;*x=top-data;*x=top-data;LinkStack p=top;LinkStack p=top;top=top-next;top=top-next;delete p;/*delete p;/*释放存储空间释放存储空
18、间释放存储空间释放存储空间*/return TRUE;return TRUE;链栈的基本操作链栈的基本操作在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确问题：当程序中同时使用几个栈时，如何防止栈的问题：当程序中同时使用几个栈时，如何防止栈的上溢上溢？方法一：将栈的容量加到足够大，但这种方法由于事方法一：将栈的容量加到足够大，但这种方法由于事先难以估计容量，有可能浪费空间。先难以估计容量，有可能浪费空间。方法二：使用两个（或多个）栈方法二：使用两个（或多个）栈共享共享存储空间办法。存储空间办法。两栈的栈底分别设在给定存储空间的两端，然
19、后各自两栈的栈底分别设在给定存储空间的两端，然后各自向中间伸延，向中间伸延，当两栈的栈顶相遇时才可能发生溢出。当两栈的栈顶相遇时才可能发生溢出。S1.buttom0 1 2 3 m-4 m-3 m-2 m-1 S2.buttoma1 a2 a3b1b2b3b4S2.topS1.topS1进栈方向在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确栈的一些应用在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确栈的应用栈的应用数制转换数制转换 十进制十进制十进制十进制NN和其它进制数的
20、转换是计算机实现计算和其它进制数的转换是计算机实现计算和其它进制数的转换是计算机实现计算和其它进制数的转换是计算机实现计算的基本问题的基本问题的基本问题的基本问题,其解决方法很多其解决方法很多其解决方法很多其解决方法很多,其中一个简单算法基其中一个简单算法基其中一个简单算法基其中一个简单算法基于下列原理于下列原理于下列原理于下列原理:N=(n div d)*d+n mod dN=(n div d)*d+n mod d (其中其中其中其中:div:div为整除运算为整除运算为整除运算为整除运算,mod,mod为求余运算为求余运算为求余运算为求余运算)例如例如例如例如 (1348)1348)101
21、0=(2504)=(2504)8 8，其运算过程如下：其运算过程如下：其运算过程如下：其运算过程如下：在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 n n div 8 n mod 8 n n div 8 n mod 8 1348 168 4 1348 168 4 168 21 0 168 21 0 21 2 5 21 2 5 2 0 2 2 0 2在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确我我我我们们们们看看看看到到到到所所所所转转转转换换换换的的的的8 8进进进进
22、制制制制数数数数按按按按底底底底位位位位到到到到高高高高位位位位的的的的顺顺顺顺序序序序产产产产生生生生的的的的，而而而而通通通通常常常常的的的的输输输输出出出出是是是是从从从从高高高高位位位位到到到到低低低低位位位位的的的的，恰恰恰恰好好好好与与与与计计计计算算算算过过过过程程程程相相相相反反反反，因因因因此此此此转转转转换换换换过过过过程程程程中中中中每每每每得得得得到到到到一一一一位位位位8 8进进进进制制制制数数数数则则则则进进进进栈栈栈栈保保保保存存存存，转转转转换换换换完完完完毕毕毕毕后后后后依依依依次次次次出出出出栈栈栈栈则则则则正正正正好好好好是是是是转转转转换换换换结结结结果
23、。果。果。果。算法思想如下：当算法思想如下：当算法思想如下：当算法思想如下：当N0N0时重复时重复时重复时重复1 1，2 2 1 1若若若若 N0N0，则则则则将将将将N N%r r 压压压压入入入入栈栈栈栈s s中中中中 ，执执执执 行行行行2;2;若若若若N=0N=0，将栈，将栈，将栈，将栈s s的内容依次出栈，算的内容依次出栈，算的内容依次出栈，算的内容依次出栈，算 法结束。法结束。法结束。法结束。2 2修改修改修改修改N(N(用用用用N/r N/r 代替代替代替代替 N)N)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确#d
24、efine L 10#define L 10void Conversion(int N,int r)void Conversion(int N,int r)int sL,top;/*int sL,top;/*定义一个顺序栈定义一个顺序栈定义一个顺序栈定义一个顺序栈*/int x;int x;top=-1;/*top=-1;/*初始化栈初始化栈初始化栈初始化栈*/cout10Nr:;cout10Nr:;while(N)while(N)s+top=N%r;/*s+top=N%r;/*余数入栈余数入栈余数入栈余数入栈*/N=N/r;/*N=N/r;/*商作为被除数继续商作为被除数继续商作为被除数继续
25、商作为被除数继续*/在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确while(top!=-1)while(top!=-1)x=stop-;x=stop-;coutx;cout1时，需要利用塔座时，需要利用塔座 b 做辅助塔座，做辅助塔座，（1）将压在编号为）将压在编号为n的圆盘上的的圆盘上的 n-1个圆盘从个圆盘从 a 移到移到b上；上；(借助于塔座借助于塔座c)（2）将编号为）将编号为 n 的圆盘移到塔座的圆盘移到塔座c上；上；（3）再将）再将n-1个圆盘移到个圆盘移到c上。上。而将而将n-1个圆盘移到个圆盘移到c上的问题和原问题具有相同的特上的问题和原问题具有相同的特征属性。由此可以得到征属性。由此可以得到 n 阶阶Hanoi塔问题的递归函数。塔问题的递归函数。栈的应用栈的应用HanoiHanoi塔问题塔问题