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