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

数据结构实用幻灯片-绪论

26页
  • 卖家[上传人]:F****n
  • 文档编号:88148704
  • 上传时间:2019-04-20
  • 文档格式:PPT
  • 文档大小:204KB
  • / 26 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1、第1章 绪论, 1.1 数据结构 1.2 基本概念和术语 1.3 抽象数据类型 1.4 算法和算法分析,引 论,对于一个课题,在计算机领域,一般遵循下面的解决原则: 需求分析 总体设计 模块分割 建立数学模型 解数学模型的算法 程序编制 调试 结果 数据结构涉及到:数学模型的建立和对该模型具体实现的对应的算法。 数据结构的地位:数学、硬件、软件之间。核心专业基础课.,1.1数据结构的基本概念和术语,1. 基本术语 (1)数据:描述客观事物的数字、字符以及所有能 输入到计算机中并被计算机程序处理的符号的 集合。(数字、字符、声音、图形、图像等等) (2)数据元素:数据的基本单位,在计算机程序中 常常作为一个整体进行考虑和处理,如纪录/结 构。 (3)数据项:数据的不可分割的最小单位,如结构 中的域。 (4)数据对象:性质相同的数据元素的集合,是数 据的一个子集。,2. 数据结构 (1)定义:是相互之间存在一种或多种特定关系的 数据元素的集合。 数据之间不是相互独立的,他们之间有某种特定的关系,这种数据元素之间的关系,称为“结构” 结构=关系+实体 另一种定义:按照逻辑关系组织起来的一批数

      2、据, 按一定的存储方法把它存储在计算机中, 并在这些数据上定义了一个运算的集合。 形式定义:二元组 (D,S) 其中D是数据元素的有限集,S是D上关系的有限集,(2)四种基本结构(逻辑结构) p5 集合:元素仅属于同一个集体,没有其他关系。 线性结构:存在一对一 关系,序列相邻,次序关系。 树型结构:存在一对多关系,层次关系。 图状结构(网状结构) :存在多对多关系,任意性 存储器模型:一个存储器M是一系列固定大小的存储单元,每个单元U有一个唯一的地址A(U),该地址被连续地编码。每个单元U有一个唯一的后继单元U=succ(U) 物理结构就是逻辑结构到存储器的一个映射。 四种存储结构:顺序存储、链接存储、索引存储、散列存储,(3)实例:P1-P3 例1-1 例1-3 表:计算机系人事表,3. 数据结构的划分,(1)按数据结构的性质划分 数据的逻辑结构数据元素之间的逻辑关系 (设计算法 数学模型) 数据的物理结构数据结构在计算机中的 映像 (存储结构,算法的实现),3. 数据结构的划分,(2)按数据结构在计算机内的存储方式来划分 顺序存储结构借助元素在存储器的相 对位置来表示数据元素之间

      3、的逻辑关系。 链式存储结构借助指示元素存储地址 的指针表示数据元素之间的逻辑关系。,3. 数据结构的划分,(2)按数据结构在计算机内的存储方式来划分 索引存储方法:在存储结点的同时,还建立附加 的索引表,索引表中的每一项称为索引项,形式为:关键字,地址。 散列存储方法:根据结点的关键字直接计算出该结点的存储地址。 说明:四种存储方法可结合起来对数据结构进 行存储映像。,3. 数据结构的划分,(3)按数据结构的操作来划分 静态结构经过操作后,数据的结构特征保持不变(如数组)。 半静态结构经过操作后,数据的结构特性只允许很小变迁(如栈、队列)。 动态结构经过操作后,数据的结构特性变化比较灵活,可随机地重新组织结构(如指针)。,1.2 抽象数据类型 ADT,定义:是指基于一个逻辑类型的数据模型以及定义在该模型上的一组操作。每一个操作由它的输入和输出定义。 抽象的与具体的相对应 示例: int a,b; 则 a和b可以进行+、-、*、/的运算 2和6则是具体的int数据,1.3 算法和算法分析,1. 算法 p13 定义:指一系列确定的而且是在有限步骤内 能完成的操作。,算法的重要特性 P13,

      4、(1) 有穷性 :能执行结束 (2) 确定性 :对于相同的输入执行相同的路径 (3) 0至多个输入 (4) 1至多个输出 (5) 有效性(可行性) (用于描述算法的操作都是 足够基本的) 问题:程序是不是算法? 如操作系统,只要系统不遭破坏,它就永远不会停止,即使没有作业要处理,仍处于一个等待循环中,等待新作业的进入。因此操作系统程序不是一个算法。,2. 算法与数据结构的关系,计算机科学家沃斯(N.Wirth)提出的: “算法+数据结构=程序” 揭示了程序设计的本质:对实际问题选择一种好的数据结构,加上设计一个好的算法,而好的算法很大程度上取决于描述实际问题的数据结构。算法与数据结构是互相依赖、互相联系的。 一个算法总是建立在一定数据结构上的;反之,算法不确定,就无法决定如何构造数据。 p6图1.6上面2行,算法与数据结构关系举例,例1:编写程序查询某城市某人的电话号码 建立一张登记表,存放2个数据项: 姓名+Tel 好的算法取决于这张表的结构及存储方式: 将表中结点按照姓名顺序地存储在计算机中,依次查找,可能遍历整个表都找不到。 建立一张姓氏索引表:姓+表中的起始地址 则不需查找其他

      5、姓氏,查找效率得到提高。,算法与数据结构关系举例,例2: 设计一个考试日程安排表,使在尽可能短的时间内安排完考试,要求同一个学生选修的几门课程不能安排在同一个时间内。,算法与数据结构关系举例,解决该问题,首先选择一个合适的数据结构。用无向图表示,图中的顶点表示课程,不能同时考试的课程之间连上一条边。则该问题就抽象成对该无向图进行“着色”操作,即用尽可能少的颜色去给图中每个顶点着色,使得任意两个相邻的顶点着不同的颜色。同一种颜色表示一个考试 时间。 答案:1:A,C 2:B,D 3:E 4: F 解决问题的关键步骤是先选取合适的数据结构表示问题,才能写出有效的算法。,3. 算法设计的要求 p13p14,(1)正确性 四层含义 p14 a,b,c,d (2)可读性 首先是给人读,然后才是机器执行 (3)健壮性 容错性 (4)效率与低存储量需求,算法的效率,定义:一个算法如果能在所要求的资源限制内将问题解决好,则称这个算法是有效率的。 例如,一个资源限制是:可用来存储数据的全部空间可能是分离的内存空间限制和磁盘空间限制以及允许执行每一个子任务所需要的时间。,4 . 算法的分析 算法性能的评价

      6、,评价标准: 1)算法所需的计算时间 2)算法所需的存储空间 3)算法的简单性 度量算法执行时间的两种方法 p14 1)事后统计法 此方法有两个缺陷 p14 2)事前分析估算法 此方法取决于多个因素:a,b,c,d,e p14,5 . 时间复杂度,(1)引例 (a) +x; s=0; +x 的频度为1 (b) for (i=1; i=n; +i) +x; s+=x; +x的频度为n (c) for (j=1;j=n;+j) for (k=1;k=n;+k) +x; s+=x; +x的频度为n2,5 . 时间复杂度,(2)定义: 一般情况下,算法中基本操作重复执行的时间是问题规模n的某个函数f(n),算法的时间量度记作 T(n) = O(f(n) 它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称时间复杂度。 语句的频度:该语句重复执行的次数。频度统计法,结论,(1)当f(n)为对数函数、幂函数、或它们的乘积时,算法的运行时间是可以接受的,称这些算法是有效算法;当f(n)为指数函数或阶乘函数时,算法的运行时间是不可接受的,称这些算法是无效的算法。 (2)随着n值的增大,增长速度各不相同,n足够大时,存在下列关系: 对数函数幂函数指数函数,常见函数的增长率,O(1) 常量阶,与n无关 O(log n) log n阶 O(n) n阶 O(n log n) n log n阶 O(n2) 平方阶 O(n3) 立方阶 O(2n) 指数阶 增长率由慢到快 图示见p16图1-7 尽量少用指数阶的算法 说明:教材p17第2行 除特别指明外,均指最坏情况下的时间复杂度,6. 空间复杂度,(1)存储算法本身所占用的空间 (2)算法的输入/输出数据占用的空间 (3)算法在运行过程中临时占用的辅助空间 原地工作:若辅助空间相对于输入数据量是常数,则称此算法是原地工作。 若所占空间量依赖于特定的输入,按最坏情况来分析。,

      《数据结构实用幻灯片-绪论》由会员F****n分享,可在线阅读,更多相关《数据结构实用幻灯片-绪论》请在金锄头文库上搜索。

      点击阅读更多内容
    最新标签
    发车时刻表 长途客运 入党志愿书填写模板精品 庆祝建党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.