电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源03栈和队列

44页
  • 卖家[上传人]:E****
  • 文档编号:89116127
  • 上传时间:2019-05-18
  • 文档格式:PPTX
  • 文档大小:1.62MB
  • / 44 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1、栈和队列,栈的定义和基本运算/ 顺序栈/ 链栈/ 队列的定义和基本运算/顺序队列/链式队列/实训,唐懿芳,数据结构与算法,目录,CONTENTS,栈的定义和基本运算,1、栈的定义 2、栈的基本运算,01,数据结构与算法,第一节:栈的定义和基本运算,数据结构与运算,生活中的栈与队列 栈和队列是特殊的线性表 栈与队列的特征 LIFO(Last In First Out) FIFO(First In First Out),栈的定义,堆栈简称为栈,是限定只能在表的一端进行插入和删除操作的线性表。 在表中,允许插入和删除的一端称作“栈顶”,另一端称作“栈底”。通常将元素插入栈顶的操称作为“入栈”(进栈或压栈),称删除栈顶元素的操作为“出栈”,栈底,栈顶,入栈,出栈,图3.1 堆栈,a1,a2,an,第一节:栈的定义和基本运算,栈的基本运算,堆栈的基本运算如下。 (1) StackInit()初始化堆栈。 (2) StackEmpty(s) 判定栈s是否为空。 (3) StackLength(s) 求堆栈s的长度。 (4) GetTop(s) 获取栈顶元素的值。 (5) Push(s, e) 将元

      2、素e进栈。 (6) Pop(s),出栈(删除栈顶元素)。,数据结构与运算,第一节:栈的定义和基本运算,栈的存储结构,两种存储结构: (1) 顺序栈采用顺序结构存储 (2) 链栈采用链式结构存储,数据结构与运算,顺序栈,1、顺序栈的存储结构 3、顺序栈的案例 2、顺序栈的基本运算,02,数据结构与算法,第二节:顺序栈,顺序栈的存储结构,MaxSize-1,#define MaxSize 堆栈可能达到的最大长度 typedef struct ElementType elemMaxSize; int top; /*栈顶位置*/ SeqStack;,栈底,栈顶,a0,a1,an-1,备 用 空 间,栈满和栈空的条件是什么?,栈满:top=Maxsize-1 栈空:top=-1,数据结构与运算,SeqStack StackInit() SeqStack s; s.top=-1; return(s); ,顺序栈的基本运算,初始化堆栈 StackInit(),int StackEmpty(SeqStack s) return(s.top=-1); ,判定栈s是否为空StackEmpty(s),int

      3、 StackLength(SeqStack s) return(s.top+1); ,求堆栈s的长度StackLength(s),ElementType GetTop(SeqStack s) if (StackEmpty(s) /*空栈*/ return(nil); return(s.elems.top); ,获取栈顶元素的值GetTop(s),void Push(SeqStack *s, ElementType e) if (s-top= MaxSize-1) /*栈满*/ printf(“Full”); else s-top+; s-elems-top=e ; ,进栈Push(s, e),ElementType Pop(SeqStack *s) if (s-top= -1) /*栈空*/ return(nil); /* 返回空值*/ else e=s-elems-top; s-top-; return (e); ,出栈Pop(s),第二节:顺序栈,数据结构与运算,顺序栈案例1,【例1】假设有两个栈共享一个一维数组空间0,MaxSize1,其中一个栈用数组的第0单元(元素)作为栈底,

      4、另一栈用数组的第MaxSize1号单元(元素)作为栈底(即两个堆栈从两端向中间延伸),其对应的类型描述如下: #define MaxSize 堆栈可能达到的最大长度 typedef struct ElementType elemMaxSize; int top1, top2; /*栈顶位置*/ ShareStack;,第二节:顺序栈,数据结构与运算,顺序栈案例2,则栈1的栈顶表示为:s-top1,栈2的栈顶表示为:s-top2; 栈1的进栈操作使得栈顶1右(后)移,即s-top1+,栈2进 栈操作使得栈顶2左(前)移,即s-top1-; 栈满时两个栈顶相邻,即s-top1+1s-top2。,图3.2 共享堆栈,栈1,栈顶2,a1,an,b1,bm,栈2,栈底1,栈底2,0,MaxSize-1,栈顶1,第二节:顺序栈,数据结构与运算,顺序栈案例3 进栈,void Push(ShareStack *s, ElementType e, int i) /*将元素e压入栈i(i=1,2)*/ if (s-top1+1=s-top2) /*栈满*/ printf(“Full”); else if

      5、(i=1) s-top1+; s-elems-top1=e ; else s-top2-; s-elems-top2=e ; ,第二节:顺序栈,数据结构与运算,顺序栈案例4出栈,ElementType Pop(ShareStack *s, int i) /*栈i(i=1,2)出栈*/ if (i=1) if (s-top1=-1) /*栈1空*/ return(nil); else e=s-elems-top1; s-top1-; return(e); if (i=2) if (s-top2= MaxSize) /*栈2空*/ return(nil); else e=s-elems-top2; s-top2+; return(e); ,第二节:顺序栈,数据结构与运算,链栈,1、栈的链式存储结构 2、链栈的基本运算,03,数据结构与算法,第三节:链栈,链栈的存储结构,#define MAX_SIZE 100 /设置最大元素个数 typedef int Elemtype; typedef struct snode ElementType data; struct snode *next;

      6、StackNode; typedef StackNode *LinkStack; / * LinkStack为指向StackNode 的指针类型* /,.,图3.6 链栈,栈顶,a1,an,an-1,栈底,data,next,s,数据结构与运算,第三节:链栈,链栈的基本操作,1栈初始化 栈的初始化实现比较简单,算法如下: LinkStack StackInit() LinkStack s=(LinkStack)malloc(sizeof(StackNode); s-next=0; return (s); /* StackInit */ 2判断栈是否为空 在判断栈是否为空时,只需将栈顶指针s-next值与null相比即可,算法实现如下: int StackEmpty(LinkStack s) return(s-next=NULL); /* StackEmpty */,数据结构与运算,第三节:链栈,链栈的基本操作,3求栈的长度 int StackLength(LinkStack s) LinkStack p=s-next; int length=0; while (p) length+;

      7、p=p-next; return(length); /* StackLength */ 4进栈操作 /插入元素e为新的栈顶元素 void Push(LinkStack s, int e) LinkStack p=(StackNode *)malloc(sizeof(StackNode); p-data=e; p-next=s-next; /如图把当前的栈顶元素赋值给新结点的直接后继 s-next =p; /如图将新的结点p赋值给栈顶指针 /* Push*/,数据结构与运算,第三节:链栈,链栈的基本操作,5出栈操作 /若栈不空,则删除栈顶元素,用e返回值 int Pop(LinkStack s) if (StackEmpty(s) /*栈空*/ return(nil); /* 返回空值*/ else LinkStack p=s-next; /*如图将栈顶结点赋值给p*/ int e=0; s-next= p-next; /*如图使得栈顶指针下移1位,指向后一结点*/ e=p-data; free(p); /*释放结点p*/ return(e); /* Pop*/,数据结构与运算,第三节:

      8、链栈,链栈的基本操作,6获取栈顶元素 根据栈顶指针s,可以直接获取最后入栈的元素。应该注意的是,在进行读取之前,也要进行栈空检查。 相关的算法实现如下: int GetTop(LinkStack s) if (StackEmpty(s) return(nil); return(s-next-data); /* GetTop*/,数据结构与运算,队列,1、队列的定义 3、队列的存储结构 2、队列的基本运算,04,数据结构与算法,第4节:队列,队列的定义,队列简称为队,是限定只能在表的一端作插入运算、在另一端作删除运算的线性表; 在表中,允许插入的一端称作“队尾”,允许删除的另一端称作“队首”(或“队头”); 通常将元素插入队尾的操作称作为入队列(或入队),称删除队首元素的操作为出队列(或出队)。,数据结构与运算,第4节:队列,队列的基本运算,数据结构与运算,队列的基本运算如下。 (1) InitQueue() 初始化队列。 (2) QueueEmpty(q) 判定队列q是否为空。 (3) QueueLength(q) 求队列q的长度。 GetHead(q) 获取队列q队首元素的值。 (5) AddQueue (q, e) 将元素e入队。 (6) DeleteQueue (q) 删除队首元素。,第4节:队列,队列的存储结构,两种结构: (1) 顺序队列采用顺序结构存储 (2) 链式队列采用链式结构存储,数据结构与运算,顺序队列,1、队列的顺序存储结构 2、顺序队列的基本运算,05,数据结构与算法,第5节:顺序队列,队列的顺序存储结构 1,#define MaxSize n 队列可能达到的最大长度n typedef struct ElementType elemMaxSize; int front, rear; /*队首、队尾指示器*/ Queue;,数据结构与运算,第5节:顺序队列,队列的顺序存储结构 2,数据结构与运算,图3.12 队列操作,a,b,c,e,rear=4,d,front=-1,b,c,e,rear=4,d,front=0,front=rear=4,front=rear=-1,

      《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源03栈和队列》由会员E****分享,可在线阅读,更多相关《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源03栈和队列》请在金锄头文库上搜索。

      点击阅读更多内容
    新上传的PPT文档
    2024年度北京市昌平区北七家镇平西府卫生院合同制护理人员招聘考前冲刺模拟试卷B卷含答案 2024年度河北省承德市承德县中医院合同制护理人员招聘基础试题库和答案要点 2024年度浙江省温州市乐清市妇幼保健院合同制护理人员招聘综合练习试卷A卷附答案 2024年度北京市房山区崇各庄乡卫生院合同制护理人员招聘考前冲刺试卷A卷含答案 2024年度浙江省温岭市骨伤科医院合同制护理人员招聘题库练习试卷B卷附答案 2024年度浙江省遂昌县中医院合同制护理人员招聘模拟题库及答案 2024年度浙江省温州市明乐眼科医院合同制护理人员招聘考前冲刺试卷A卷含答案 2024年度浙江省武义县武义东风莹石公司职工医院合同制护理人员招聘提升训练试卷B卷附答案 2024年度北京市昌平区北七家镇医院合同制护理人员招聘通关题库(附带答案) 2024年度浙江省新昌县新康医院合同制护理人员招聘题库综合试卷B卷附答案 2024年度浙江省温岭市精神康复医院合同制护理人员招聘通关题库(附带答案) 2024年度河北省崇礼县妇幼保健站合同制护理人员招聘自我提分评估(附答案) 2024年度浙江省温州市妇幼保健所合同制护理人员招聘典型题汇编及答案 2024年度浙江省温州市鹿城区人民医院合同制护理人员招聘考前练习题及答案 2024年度河北省平泉县妇幼保健院合同制护理人员招聘考前冲刺试卷B卷含答案
    最新标签
    发车时刻表 长途客运 入党志愿书填写模板精品 庆祝建党101周年多体裁诗歌朗诵素材汇编10篇唯一微庆祝 智能家居系统本科论文 心得感悟 雁楠中学 20230513224122 2022 公安主题党日 部编版四年级第三单元综合性学习课件 机关事务中心2022年全面依法治区工作总结及来年工作安排 入党积极分子自我推荐 世界水日ppt 关于构建更高水平的全民健身公共服务体系的意见 空气单元分析 哈里德课件 2022年乡村振兴驻村工作计划 空气教材分析 五年级下册科学教材分析 退役军人事务局季度工作总结 集装箱房合同 2021年财务报表 2022年继续教育公需课 2022年公需课 2022年日历每月一张 名词性从句在写作中的应用 局域网技术与局域网组建 施工网格 薪资体系 运维实施方案 硫酸安全技术 柔韧训练 既有居住建筑节能改造技术规程 建筑工地疫情防控 大型工程技术风险 磷酸二氢钾 2022年小学三年级语文下册教学总结例文 少儿美术-小花 2022年环保倡议书模板六篇 2022年监理辞职报告精选 2022年畅想未来记叙文精品 企业信息化建设与管理课程实验指导书范本 草房子读后感-第1篇 小数乘整数教学PPT课件人教版五年级数学上册 2022年教师个人工作计划范本-工作计划 国学小名士经典诵读电视大赛观后感诵读经典传承美德 医疗质量管理制度 2 2022年小学体育教师学期工作总结 2022年家长会心得体会集合15篇
    关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
    手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
    ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.