数据结构zmz_1绪论课件.pptVIP

数据结构：考试课、 64学时 授课; 48学时 上机训练：16学时 先修课程：离散数学、C语言(或其他语言) 后续课程：面向对象程序设计、操作系统、 数据库系统、人工智能等 表1是5次C语言课程的测验成绩，设计一个小程序计算这5次测验的总分 是一门研究程序设计问题中计算机的操作对象之间的关系和操作等等的学科 Pascal之父：尼古拉斯·沃斯Niklaus Wirth “算法+数据结构=程序” 数据（data)—所有能输入到计算机中去的符号（早期：数值，现在：字符、声音、图像） 数据的存储结构—数据的逻辑结构在计算机存储器中的实现 数据类型—值的集合+一组操作 抽象数据类型—Abstract Data Type,ADT 作业 数据结构依据视点的不同，分为数据逻辑结构和物理结构： 1。逻辑结构：从解决问题的需要出发，为实现必要的功能所建立的数据结构，它属于用户的视图，是面向对象的。 2。物理结构：指数据该如何在计算机中存放，是数据逻辑结构的物理存储方式，是属于具体实现的视图，是面向计算机的。 3。关系：物理结构是逻辑数据的存储映象 一种数据结构包含如下三个方面： 1.逻辑结构：表示数据元素之间的逻辑关系。（元素 之间的抽象关系，与具体实现无关） B=(E,R) 元素取自集合E，元素间有关系R 2.物理结构：数据的逻辑结构在计算机存储器中的映 射（或表示），又称存储结构或存储表示 3.结构的行为特征。作用于数据结构上的各种运算。 例如：检索元素，插入元素，删除元素等 还有具体实现问题：所采用的语言，在该语言里采用 什么具体方式和技术实现数据结构 数据结构依据视点的不同，分为数据逻辑结构和物理结构： 1。逻辑结构：从解决问题的需要出发，为实现必要的功能所建立的数据结构，它属于用户的视图，是面向对象的。 2。物理结构：指数据该如何在计算机中存放，是数据逻辑结构的物理存储方式，是属于具体实现的视图，是面向计算机的。 3。关系：物理结构是逻辑数据的存储映象 一种数据结构包含如下三个方面： 1.逻辑结构：表示数据元素之间的逻辑关系。（元素 之间的抽象关系，与具体实现无关） B=(E,R) 元素取自集合E，元素间有关系R 2.物理结构：数据的逻辑结构在计算机存储器中的映 射（或表示），又称存储结构或存储表示 3.结构的行为特征。作用于数据结构上的各种运算。 例如：检索元素，插入元素，删除元素等 还有具体实现问题：所采用的语言，在该语言里采用 什么具体方式和技术实现数据结构 (3)数据结构和数据类型的关系 “数据结构”是数据类型的抽象； “数据类型”是数据结构在计算机内部的具体表现 算法复杂性高低体现在运行算法时所需计算机资源的多少，计算机资源最重要的是时间和空间资源，所以有算法时间复杂性和空间复杂性。 1。用什么量表示算法复杂性 2。对给定算法，怎样计算其算法复杂性 程序正确性的四个层面： （1）不含语法错误 （2）程序对于n组输入数据能够得出满足规格说明要求的结果。 （3）程序对于精心选择的典型、边界性的n组输入数据能得出满足规格说明要求的结果。 （4）程序对于一切合适的输入数据都能得出满足规格说明要求的结果（穷举）。 用计算机解决问题的步骤： 问题分析：这阶段的任务是弄清所要解的问题是什么； 并且把它用一种语言（自然语言、说明语言或数 学语言）清楚地描述出来。 算法设计：这阶段的任务是建立程序系统的结构，重点 是算法的设计和数据结构的设计。对于大型的复 杂的程序系统，这一阶段往往还包括模块的设计。 程序设计：采用适当的程序设计语言，编写出可执行的 程序。 程序测试和维护：发现和排除在前几个阶段中产生的错 误，经测试通过的程序便可投入运行，在运行过 程中还可能发现隐含的错误和问题，因此还必须 在使用中不断维护和完善。 Criteria: Definiteness: Each instruction is clear and unambiguous Finiteness: The algorithm terminates after finite number of steps Effectiveness: Every instruction must be basic enough to be carried out. It also must be feasible Input: There are zero or more quantities that are externally supplied Output: At least one quantity is produced ADT实现 ADT实现：就是将ADT转换成程序设计语言，加上对应于该