“算法与数据结构”-栈队列.ppt

“算法与数据结构”-栈队列.ppt

ID:56532252

大小:328.50 KB

页数:35页

时间:2020-06-27

“算法与数据结构”-栈队列.ppt_第1页
“算法与数据结构”-栈队列.ppt_第2页
“算法与数据结构”-栈队列.ppt_第3页
“算法与数据结构”-栈队列.ppt_第4页
“算法与数据结构”-栈队列.ppt_第5页
资源描述:

《“算法与数据结构”-栈队列.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、数据结构主讲人:李志芳主讲单位:软件技术教研室时间:2008~2009第二学期逻辑结构----栈1)逻辑结构栈的数据元素的特点及基本操作2)顺序栈的实现及基本操作3)链栈的实现及基本操作4)栈的应用逻辑结构----队列1)逻辑结构队列的数据元素的特点及基本操作2)队列的顺序实现及基本操作*3)队列的链式实现及基本操作*4)队列的应用**逻辑结构----数组(简单介绍)1)逻辑结构数组的数据元素的特点及基本操作2)数组的寻址操作知识点介绍栈的定义和运算栈是特殊的线性表,限定只能在一端进行插入和删除的线性表。栈的特殊概念。能进行插入和删除的一端称为栈顶,另一端称为

2、栈底。(栈只能在栈顶进行插入和删除)栈a1a2……an-1an入栈(压栈)出栈栈顶栈底栈中的数据存储如图所示。则入栈的顺序为:a1,a2,……,an-1,an,则出栈顺序为an,an-1,……,a2,a1。后进先处栈的基本操作栈top1、top=-1栈空。234015ABCD2、A入栈,则top值加1。top3、BCD入栈,则top值为3。top3、DC出栈,则top值为1。top栈的基本操作1)初始化栈:Init_Stack(S)2)判断栈是否为空:IsNull_Stack(S)3)取栈顶元素的值:GetTop_Stack(S)4)压栈:Push_Stack

3、(S,x)5)出栈:Pop_Stack(S)6)判断栈是否为满:IsFull_stack(S)栈顺序栈以顺序存储方式存储的栈叫做顺序栈。一般情况下用数组来表示,结合栈的特性,最好的方法是把数组的尾设置为栈顶,同时为了方便数据的操作,设置top来指示栈顶元素的位置。栈的存储结构a1a2a3a4……an-1an0123……n-1nMax_stack-1ntopSdata#defineMAX_STACK100typedefstruct{data[MAX_STACK];inttop;}Se_Stack;elemtypeint顺序栈的基本操作实现1)初始化栈voidIn

4、it_Stack(Se_Stack*S){s->top=-1;}2)判断栈是否为空intIsNull_Stack(Se_Stack*S){if(s->top==-1)return1;elsereturn0;}3)取栈顶元素的值intGetTop_Stack(Se_Stack*S){if(IsNull_Stack(S))return0;elsereturns->data[s->top];}栈的存储结构顺序栈的基本操作实现4)出栈intPop_Stack(Se_Stack*S,int*x){if(IsNull_Stack(S))return0;else*x=s->

5、data[s->top];s->top--;return1;}5)判断栈是否为满intIsFull_stack(Se_Stack*S){if(s->top==MAX_STACK-1)return1;elsereturn0;}6)压栈intPush_Stack(Se_Stack*S,intx){if(IsFull_stack(S))return0;else{s->top++;s->data[s->top]=x;}return1;}栈的存储结构链栈采用链表存储的栈称为链栈。栈的存储结构a1a2a3an0……top采用链表来存储栈,栈顶选在表头,并设头指针为top,

6、在表头来实现压栈和出栈操作。在这种结构上的操作实际上已经演变为了对链表的基本操作,压栈和出栈操作演变为了在表头进行插入和删除结点的运算。typedefstructnode{intdata;structnode*next;}Stack_Node,*L_Stack;入栈Stack_Node*Push_LStack(Stack_Node*top,intx){Stack_Node*s;s=(Stack_Node*)malloc(sizeof(Stack_Node))if(s==NULL)returnNULL;s->data=x;s->next=top;top=s;re

7、turntop;}栈的存储结构出栈Stack_Node*Pop_LStack(Stack_Node*top,int*x){Stack_Node*p;if(top==NULL)returnNULL;else{*x=top->data;p=top;top=top->next;free(p);returntop;}}栈的存储结构进制之间的转换----例如:十进制转八进制栈的应用135781698521182580251522515进制之间的转换voidconver(intN,intr){Se_Stack*s;intx;Init_Stack(s);while(N){P

8、ush_Stack(s,N%r);N=

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。