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

数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第一章 绪论

19页
  • 卖家[上传人]:E****
  • 文档编号:89184373
  • 上传时间:2019-05-20
  • 文档格式:PPT
  • 文档大小:120KB
  • / 19 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1、数据结构,第一章 绪论,第一章 绪论,第一章 绪论,知 识 点 数据结构中常用的基本概念和术语 算法描述和分析方法 难 点 算法复杂性的分析方法 要 求 了解数据的逻辑结构和物理结构,算法的基本概念,它们对于程序设计的重要性以及相互关系 掌握算法复杂性的概念及分析方法,第一章 绪论,第一章目录,1.1 基本概念 1.2 算法的描述 1.3 算法的评价 1.4 应用举例及分析 小 结 习题与练习,第一章 绪论,1.1 基本概念(1),数据(Data):一切能够由计算机接受和处理的对象。 数据元素(Data element):是数据的基本单位,在程序中作为一个整体加以考虑和处理。 数据项(Data item):是数据的不可分割的最小单位,在有些场合下,数据项又称为字段或域。,第一章 绪论,1.1 基本概念(2),数据结构(Data structure):数据之间的相互关系,即数据的组织形式。 研究数据结构,是指研究数据的逻辑结构和物理结构 数据的逻辑结构:数据元素之间的逻辑关系 数据的物理结构:数据元素在计算机存储器中是如何存储的 定义一组有关数据元素的运算,第一章 绪论,1.1 基本概念

      2、(3),算法(Algorithm):对特定问题求解步骤的一种描述。 算法是一个有穷的规则序列,这些规则决定了解决某一特定问题的一系列运算。 由此问题相关的一定输入,计算机依照这些规则进行计算和处理,经过有限的计算步骤后能得到一定的输出。,返回,第一章 绪论,1.2 算法的描述,本书将采用类C语言描述算法 类C语言是标准C语言的简化 ,与标准C语言的主要区别如下: 1. 所有算法都以如下所示的函数形式表示: 函数类型 函数名(参数表) 语句序列 类C语言的形参书写比标准C语言简单,如,int xyz(int a,int b,int c)可以简单写成int xyz (int a,b,c),第一章 绪论,类C与标准C的主要区别(续),2. 局部量的说明可以省略,必要时对其作用给予注释 。 3. 不含go to语句,增加一个出错处理语句error(字符串),其功能是终止算法的执行并给出表示出错信息的字符串。 4. 输入/输出语句有: 输入语句 scanf(格式串),变量1,变量N); 输出语句 printf(格式串),变量1,变量N); 通常省略格式串 。,返回,第一章 绪论,1.3.1 评价

      3、算法的一般原则,正确性:算法应能正确地实现处理要求 。 易读性:有助于对算法的理解,便于纠正和扩充 。 简单性:使证明其正确性比较容易,对算法进行修改也比较方便。 高效率:达到所需的时、空性能。,第一章 绪论,1.3.2 算法复杂性的分析,算法的复杂性包括时间复杂性(所需运算时间)和空间复杂性(所占存储空间),重点是时间复杂性 。 一个算法所需的运算时间通常与所解决问题的规模大小有关。 用n 表示问题规模的量 ,把算法运行所需的时间T表示为n的函数,记为T(n)。 不同的T(n)算法,当n增长时,运算时间增长的快慢很不相同。,第一章 绪论,一个算法所需的执行时间就是该算法中所有语句执行次数之和。 渐进时间复杂性:当n逐渐增大时T(n)的极限情况,一般简称为时间复杂性。 时间复杂性常用数量级的形式来表示,记作T(n)=O(f(n)。 其中,大写字母O为Order(数量级)的字头,f(n)为函数形式,如T(n)=O(n2)。,第一章 绪论,当T(n)为多项式时,可只取其最高次幂项,且它的系数也可略去不写。 一般地,对于足够大的n,常用的时间复杂性存在以下顺序: O(1) O(logn) O

      4、(n) O(n*logn) O(n2) O(n3)O(2n)O(3n)O(n!) 其中,O(1)为常数数量级,即算法的时间复杂性与输入规模n无关。,第一章 绪论,算法的运行时间往往还与具体输入的数据有关,通常用以下两种方法来确定一个算法的运算时间: 1. 平均时间复杂性:研究同样的n值时各种可能的输入,取它们运算时间的平均值。 2. 最坏时间复杂性:研究各种输入中运算最慢的一种情况下的运算时间。,返回,第一章 绪论,例1.1,计算下面交换i和j内容程序段的时间复杂性。 temp=i; i=j; j=temp; 解:以上三条单个语句均执行1次,该程序段的执行时间是一个与问题n无关的常数,因此,算法的时间复杂度为常数阶,记作T(n)=O(1).,第一章 绪论,例1.2,计算下面求二个矩阵相乘的时间复杂性 (1) for(i=0;in;i+) (n+1次) (2) for(j=0;j=n;j+) (n(n+1)次 ) (3)cij=0; (n2) (4)for(k=0;kn;k+) (n2(n+)次 ) (5) cij+=aik*bkj; (n3次) 解:T(n)=2n3+3n2+2n+1,返回,第一章 绪论,小 结,本章介绍了贯穿全书的基本概念和基本思想。 数据 数据结构 逻辑结构 物理结构 算法 算法的时间复杂性,返回,第一章 绪论,习题与练习,一、名词解释 数据 数据元素 数据类型 数据结构 数据逻辑结构 数据物理结构 算法 算法的时间复杂性 二、简答 1. 怎么样来评析一个算法的好坏? 2. 什么是算法的最坏和平均时间复杂性?,第一章 绪论,三、分析下列算法的时间复杂性: 1void f1(int n) int i,k; i=1;k=100; while(in) k=k+1;i+=2; 2i=1; while(i=n) i=i*10;,第一章 绪论,3sum=0; for(i=0;in;i+) for(j=0;jn;j+) sum=sum+Arrayij;,返回,

      《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第一章 绪论》由会员E****分享,可在线阅读,更多相关《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第一章 绪论》请在金锄头文库上搜索。

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