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

《数据结构——用C语言描述(第二版)》-宁正元-电子教案 第1章 绪论

19页
  • 卖家[上传人]:E****
  • 文档编号:89403058
  • 上传时间:2019-05-24
  • 文档格式:PPT
  • 文档大小:313KB
  • / 19 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1、第1章 绪论,1.1 什么是数据结构 1.2 基本概念和术语 1.3 数据类型和抽象数据类型 1.4 算法描述与算法评价,本章将介绍数据结构研究的对象、基本概念和术语、算法的概念及其描述方法(C语言描述)、数据类型以及抽象数据类型,并概述数据结构的发展概况及其在计算机科学中的地位。,第1章 绪 论,随着计算机应用领域的不断扩大,计算机处理的对象更多的是非数值计算问题,它们的数学模型无法用数学方程来进行描述,此时就必须建立相应的数据结构来进行描述,分析问题中所用到的数据是如何组织的,研究数据之间的关系如何,进而为解决这些问题设计出合适的数据结构。,1.1 什么是数据结构,例1 职工信息管理,图1.1 职工花名册表,将每位职工的信息组织成如图1.1所示的花名册。花名册中每个职工的信息由编号、姓名、性别、年龄、月收入等项目组成,占表的一行,表中的结点和结点之间是一种简单的线性关系,这就是上述花名册表的线性逻辑结构。当用计算机对上述花名册表中的数据进行运算时,就要考虑那些结点在计算机中的存储表示,即存储结构。另外,还必须考虑如何进行结点的插入、删除、修改、检索或查找,这就涉及到数据的运算,例2

      2、 旅游交通网络图 如图1.2所示,为一个旅游交通网络咨询系统,可采用一种称之为图的结构来表示实际的交通网络, 此时,这个交通网络图就表示一个数据结构。在这个数据结构中,结点之间的关系可以是任意的,图中任意两个结点之间都可以相关。同样,必须考虑构造后将这张图存放入计算机中,这就要涉及到图的存储结构问题,以及图的运算。 从以上例子可见,要描述诸如此类的非数值计算问题的数学模型,涉及到一些诸如表、图还有树之类的数据结构。 数据结构课程实际上是一门研究非数值计算问题的程序设计中计算机的操作对象以及它们之间的关系和运算操作等的一门学科。在计算机科学中,数据结构不仅是一般程序设计(特别是非数值计算的程序设计)的基础,而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。,数据是指信息的载体,是对客观事物的符号表示,是对有效地输入到计算机中并能被计算机程序处理的符号的总称。如声音、图形、图像。 数据元素是数据的基本单位,数据项是数据的不可分割的最小单位。有时也称之为结点、元素、顶点、记录等。一个数据元素可由若干个数据项组成,如上面职工花名册中的每个人的信息就是一个数据

      3、元素,而每个人的信息包括编号、姓名、性别、年龄、月收入等,这每一个项目就属于数据项。,1.2 基本概念和术语,数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据类型(数据类型)是对在计算机中表示的同一数据对象及其在该数据对象上的一组操作的总称。 数据类型有时还分为原子数据类型和结构数据类型。 数据结构指的是数据及数据之间的相互关系。一般地,数据结构包括以下三个方面的内容: (1)数据元素之间的逻辑关系,有时也称为数据的逻辑结构。 (2)数据元素及其关系在计算机内存中的表示(又称为映象),称之为数据的物理结构,又称为数据的存储结构,它包括数据元素的表示和数据元素之间关系的表示。 (3)数据的运算及实现,即对数据元素可以施加的操作及其这些操作在相应的存储结构上的实现。,数据的逻辑结构是从逻辑关系上描述数据,可以看作是从具体问题抽象出来的数学模型。如上例中的职工花名册表。根据数据元素之间的不同特性,通常有下列四类基本逻辑结构: (1)线性结构:结构中的数据元素存在一个对一个的关系,即所谓的线性关系。 (2)树型结构:结构中的数据元素之间存在一个对多个的关系,是结点之间有分支、并具有

      4、层次关系的结构,它非常类似于自然界中的树。 (3)图或网状结构:该结构中的数据元素之间的关系存在多个对多个的关系,如交通网络图就是一个图状结构。 (4)集合:结构中的数据元素之间除了“同属于一个集合”的相互关系外,别无其它关系。 有时将树形结构、集合和图或网状结构称为非线性结构,此时数据逻辑结构就可分为线性结构和非线性结构两类。,数据的存储结构是指逻辑结构用计算机语言的实现,就是数据元素及其关系如何存放入计算机内存的问题。一般地,数据的存储结构可按以下四种基本存储方法而得到: (1)顺序存储方法:是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中,结点间的逻辑关系由存储单元的相邻关系而体现。由此得到的存储表示称为顺序存储结构,通常可借助计算机语言的数组来描述。 (2)链状存储方式:不要求逻辑上相邻的结点在物理位置上也相邻,数据元素可以存储在任意位置。为了实现数据元素之间逻辑关系的存储,必须通过一些附加的手段来存储这种相互关系,由此得到的存储表示称为链状存储结构。一般可以用指针来实现,通常可借助计算机程序语言的指针类型或者游标来来描述。,(3)索引存储方法:该方法通常是在存储结点信息的

      5、同时,建立附加的索引表。索引表一般有稠密索引和稀疏索引两种。 (4)散列存储方法:该方法是依据结点的关键字直接计算出该结点的存储地址,而后将结点按某种方式存入该地址的一种存储方法。 数据的运算是指定义在数据的逻辑结构上的一组操作的集合。例如,检索(查找)、插入、删除、定位、修改、排序等。要注意的是,这些运算实际上是在逻辑结构上对抽象数据所施加的一系列抽象的操作,运算的实现依赖于所选取的存储结构,是依赖于不同的计算机程序设计语言的。,数据类型是具有相同性质的计算机数据的集合及在这个数据集合上的一组运算。 在高级程序语言中,数据类型可以分为原子类型和结构类型。原子类型即值不可分解的类型,如C语言中的整型、字符型、实型、指针类型等;而结构类型则指的是其值可由若干成分按某种结构组成的类型,是可以分解的,如C语言中提供的结构体。 抽象数据类型(ADT)是指一个数学模型及定义在该数学模型上的一组操作。抽象数据模型的定义取决于它的一组逻辑特性,与其在计算机内部如何表示和实现无关。,1.3 数据类型和抽象数据类型,算法是对特定问题求解方法和步骤的一种描述,它是指令的一组有限序列。一个算法必须具备以下五

      6、个重要特性: (1)输入:一个算法必须具有零个或多个的外界输入。 (2)输出:一个算法必须有一个或多个的输出。 (3)有穷性:一个算法对任何合法的输入值必须总是在执行有穷步之后结束,并且每步都必须在有穷时间内完成。利用这一点,我们可以区别算法与程序。 (4)确定性:算法中每一条指令必须有确切的含义,不会产生二义性。 (5)可行性:算法中描述的操作都必须可以通过已经实现的基本运算有限次执行来实现,而且算法必须在有限时间内完成。 一个算法可以用自然语言、数学语言或约定的符号来描述,也可用计算机高级程序语言来描述,如PASCAl语言、C语言、C、Java或伪代码等。本书选用C语言作为描述算法的工具。,1.4.1 算法描述,1.4 算法描述与算法评价,1.4.2 算法的设计要求,设计一个好的算法可以从以下几个方面考虑: (1)正确性。算法是为了针对解决具体问题而提出的,算法的正确与否必须满足解决实际问题的需要,要经得起一切可能的输入数据的考验。 (2)可读性。算法要让人阅读得懂,程序要尽可能地简单通俗,当然也必须有效。 (3)健壮性。当输入数据非法时,算法应能适当地作出反应或进行处理。 (4)

      7、高效率。要求算法的执行时间要尽可能地短,对于存储空间要尽可能地少,即做到既省时又节省空间。 要设计一个好的算法,必须对这几个方面综合考虑,才可以设计出较好较优的算法。,考虑算法的效率应从下几个方面考虑: (1)时间效率。考虑算法所耗费的运行时间。 (2)空间效率。考虑运行算法需要耗费的存储空间,其中主要考虑算法所需的辅助存储空间。 (3)算法应尽可能地简单,易于理解,易于编码和调试并能得出正确结果。 一个算法的运行时间是指一个算法在计算机上运行所耗费的时间。它可以认为是算法中每条语句的执行时间之和。,1.4.3 算法的评价,例如,两个nn矩阵相乘的算法: for(i=1;i=n;i+) /* n+1次 */ for(j=1;j=n;j+) /* n(n+1)次*/ ci j = 0; /* nn次 */ for(k=1;k=n;k+) /* n2(n+1)次*/ ci j = ci j + i k * b k j;/* n*n*n次*/ 上述算法的时间耗费T(n)为: T(n)= 2n3 + 3n2 + 2n + 1 当n时,T(n)/n32,表示当n充分大时,T(n)与n3是同阶或者

      8、说同数量级,它是矩阵的阶数n的函数。 若引入大“O”记号,则T(n)可记作:T(n)= O(n3) ,此时称T(n)= O(n3)是求解矩阵相乘这个特定问题的渐近时间复杂度。有时将一个算法的渐近时间复杂度O(n)=O(f(n)认为就是时间复杂度。 常见的时间复杂度按数量级递增排列,依次为:常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),指数阶O(2n)等等。,有时,可以依据算法转化为程序时各个语句的特点,利用一些简单的程序分析法则进行简单算法分析: (1)对于一些简单的输入、输出语句或赋值语句,它们执行时,近似认为需要O(1)时间; (2)对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下的“求和法则”进行估计; (3)对于选择结构,如如果语句,它的主要时间耗费是在执行然后子句或别的子句所花费的时间,但须注意检验条件也还需要用O(1)的时间; (4)对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般地可用大O下的“乘法法则”进行估计; (5)对于复杂的算法,可以将它分成几个容易估算的部分,然后利用大O的求和法则和乘法法则计算整个算法的时间复杂度。,衡量一个算法好坏的另一个因素是程序运行时所占用的存贮空间大小。 度量一个算法在运行或执行过程中所占用的存储空间的大小类似于时间复杂度,可以用空间复杂度来度量。算法的空间复杂度一般也以相对于问题规模的数量级的形式给出,如O(1),O(n)等。,

      《《数据结构——用C语言描述(第二版)》-宁正元-电子教案 第1章 绪论》由会员E****分享,可在线阅读,更多相关《《数据结构——用C语言描述(第二版)》-宁正元-电子教案 第1章 绪论》请在金锄头文库上搜索。

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