数据结构第三章-栈与队列(00002)课件.ppt
《数据结构第三章-栈与队列(00002)课件.ppt》由会员分享,可在线阅读,更多相关《数据结构第三章-栈与队列(00002)课件.ppt(41页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第三章 栈与队列数据结构本章主要内容l栈的定义与基本运算l栈的顺序存储和链式存储l队列的定义与基本运算l队列的线性存储和链式存储1、栈的定义与基本运算栈(Stack)在生活中非常常见,例如洗干净的盘子总是逐个往上叠放在已经洗好的盘子上面,而用的时候我们必须从上往下逐个取用,即后洗好的盘子反而要比先洗好的盘子更提前被使用到。这便是栈的典型特征:后进先出(last in first out)。例如:如果进栈顺序是a1,a2,则出栈顺序是:a1,a2或者a2,a1。出栈顺序的不唯一是因为可能够有如下两种情况:(1)a1入栈后马上出栈,然后a2入栈再出栈,因此出栈顺序是a1,a2。(2)在a1,a2都
2、入栈后a2在栈顶要先出栈,然后是a1出栈。1、栈的定义与基本运算规定:an为栈顶,a1为栈底(1).初始化操作:Init_Stack(s);(2).判断栈是否为空:Empty_Stack(s);(3).入栈:Push_Stack(s,x);(4).出栈:Pop_Stack(s);(5).读取栈顶元素:GetTop_Stack(s);(6).销毁栈:Destroy_Stack(s);(7).显示栈内所有数据:Traverse_Stack(s);2、栈的顺序存储和链式存储用C语言的一维数组来定义动态顺序存储的类型:#define StackInitSize 100 /栈存储空间的初始分配量#def
3、ine StackIncrementSize 10 /栈存储空间的分配增量typedefstructSelemType*base;/栈底指针SelemType*top;/栈顶指针intstacksize;/当前分配的栈可使用最大存储容量 Seqstack;2、栈的顺序存储和链式存储如右图所示,top指向栈顶元素的下一位置,top=0表示空栈。top=StackSize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出,简称“上溢”;当栈空时再做退栈运算也将产生溢出,简称“下溢”。上溢是一种出错状态,应该设法避免之。下溢一般是正常现象,常常用来作为程序控制转移的条件。2、栈的顺序存储和链式存储(
4、1)构造一个空栈SvoidInit_Stack(SeqStack*S)S.base=(SelemType*)malloc(StackInitSize*sizeof(Selemtype);if(!S.base)printf(“存储空间分配失败”);S.top=S.base;S.stacksize=STACK_INIT_SIZE;printf(“存储空间分配成功”);2、栈的顺序存储和链式存储(3)入栈操作void Push(SeqStack*S,SelemType e)if(S.top-S.base=S.stacksize)/栈满,追加存储空间S.base=(SelemType*)realloc
5、(S.base,(S.stacksize+StackIncrementSize)*sizeof(Selemtype);if(!S.base)printf(“存储空间分配失败”);S.top=S.base+S.stacksize;S.stacksize+=StackIncrementSize;*S.top+=e;printf(“存储空间分配成功”);2、栈的顺序存储和链式存储(4)出栈操作,退出一个栈内节点并得到栈顶数据元素的值。首先判断栈是否为空栈,若不空则取得栈顶元素并且栈高度-1void Pop_Stack(SeqStack*S,SelemType*e)if(S.top=S.base)pr
6、intf(“当前栈空,出栈失败”);e=*S.top-;printf(“出栈成功”);2、栈的顺序存储和链式存储栈除了顺序存储方式外还有链式存式存储,栈用链式存储结构实现简称链栈。链栈的节点结构和链表的节点结构相同,值得注意的是,链栈中指针的方向是从栈顶指向栈底链栈中指针的方向是从栈顶指向栈底链栈中指针的方向是从栈顶指向栈底链栈中指针的方向是从栈顶指向栈底。2、栈的顺序存储和链式存储下面我们简单介绍的一些链栈的基本操作。(1)建立一个空栈只要利用已经定义的链表的节点指针类型声明一个栈顶指针,并将其置为空即可。建立一个空栈的代码语句如下:NODEPTR top;top=NULL;2、栈的顺序存储
7、和链式存储(2)进栈操作,让一个数据元素e进入链栈在链式存储结构下,不需要判断栈未满,只需建立一个新节点并为其分内存空间,之后挂载到链头位置即可。void Push_Stack(NODEPTR*top,elemtype e)NODEPTR p;p=(NODEPTR)malloc(LEN);if(p=NULL)printf(“系统分配空间失败!”);return;p-data=e;/存入新节点元素值p-next=(*top);/新节点与原栈顶相连接(*top)=p;/新节点作为新栈顶3、队列的定义与基本运算队列(Queue)是限定只能在一端进行插入,在另外一端进行删除的线性表。在队列中,允许插入
8、的一端被称为队尾(rear),允许删除的一端被称为队头(front)。例如:a1是队头元素,an是队尾元素。通过看下图我们可以知道队列中的元素是以a1,a2,a3an的顺序入队的,则退出时肯定也是以a1,a2,a3an的顺序出队的。即a1是第一个出队列的元素,只有在a1,a2,an-1都离开了队列之后,an才能出队列。队列的修改是依据“先进先出”的原则进行,因此队列又称FIFO(First In First Out)表。3、队列的定义与基本运算规定:a1为队头,an为队尾(1).初始化操作:Init_Queue(q);(2).入队操作:In_Queue(q,x);(3).出队操作:Out_Qu
9、eue(q,x);(4).读队头元素:Front_Queue(q);(5).判断队列是否为空:Empty_Queue(q);(6).求队列长度:Len_Queue(q);(7).销毁队列:Destroy_Queue(q);4、队列的顺序存储和链式存储队列是线性表性表的一种特殊情况,所以队列也和一般的线性表一样,有两种存储结构:顺序队列和链式队列。采用顺序结构存储的队列被称为顺序队列顺序队列顺序队列顺序队列,队列是在队头和队尾进行各种操作的,它们的位置都有可能发生变化,因此为了操作方便,除了队列的数据区外还设置了队头、队尾两个指针。队列的数据区域为sq-data0,sq-dataMAXSIZE-
10、1,队头指针为队头指针为队头指针为队头指针为sq-frontsq-front,队尾指针为队尾指针为队尾指针为队尾指针为sq-rearsq-rear。4、队列的顺序存储和链式存储顺序队的定义代码如下:#define MAXSIZE 100/定义顺序队列的最大容量typedef structdatatype dataMAXSIZE;/定义队列元素的存储空间int front,rear;/定义队头和队尾指针SeqQueue定义指向队列的指针变量SeqQueue*sq;申请顺序队的存储空间sq=malloc(sizeof(SeqQueue);4、队列的顺序存储和链式存储一般情况下,设队头指针指向队头元
11、素的前一个位置,即队头指针位置+1才是队列的第一个元素所在存储地址,队尾指针指向队列的最后一个元素。在不考虑队列的溢出问题的前提下,入队操作可以分为两步来进行,首先将队尾指针rear+指向新的队尾位置,其次将插入元素放进队尾指针指向空间,完成入队操作即可。具体代码实现如下:sq-rear+;sq-datasq-rear=a;/将新元素a进行入队4、队列的顺序存储和链式存储顺序队列的“假溢出假溢出假溢出假溢出”现象:下页图是顺序队各种操作示意,从图中可以看到不管是入队操作还是出队操作,整个队列都会随着操作的进展向数组中下标较大的位置方向移动,因为从上述相关操作可以看到,都会执行“+”这一步,于是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第三 队列 00002 课件
限制150内