【2018年必威体育精装版整理】数据结构第一章绪论.ppt

第1章 绪 论 1.6 ?关于学习数据结构的学习 1.1 什么是数据结构（定义） 数据结构的相关名词： 数据（Data） 数据元素（Data Element） 数据对象（Data Object） 数据结构（Data Structure） 数据类型(Data Type) 数据抽象与抽象数据类型 数据（Data） 定义： 数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。 数据包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。 数据元素（Data Element） 定义： 数据元素是组成数据的基本单位 ，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。例如： 数据对象（Data Object） 定义： 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据 数据特点 数据结构 数据结构（Data Structure） 定义： 数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。 例如表结构： 数据结构（Data Structure） 数据类型(Data Type) 定义： 数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。 数据类型(Data Type) 高级语言中的数据类型分为两大类： 数据抽象与抽象数据类型 数据的抽象 抽象数据类型(Abstract Data Type) 抽象数据类型实现 ADT的表示与实现 面向对象的概念 结构化的开发方法与面向对象开发方法不同点 数据的抽象 汇编语言中十进制表示的数据98.65、9.6E3等, 它们是二进制数据的抽象; 抽象数据类型(Abstract Data Type) 定义： 抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。 抽象数据类型(Abstract Data Type) 线性表的抽象数据类型的描述： 抽象数据类型实现 传统的面向过程的程序设计 ADT的表示与实现 ADT的定义： 面向对象的概念 面向对象的概念： 结构化与面向对象开发方法的不同点 结构化的开发方法： 是面向过程的开发方法，首先着眼于系统要实现的功能。 1.2 数据结构的内容 逻辑结构 存储结构 运算集合 逻辑结构 定义： 数据的逻辑结构是指数据元素之间逻辑关系描述。 集合结构 定义： 结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。 线性结构 定义： 结构中的数据元素之间存在着一对一的线性关系。 树型结构 定义： 结构中的数据元素之间存在着一对多的层次关系。 图状结构或网状结构 定义： 结构中的数据元素之间存在着多对多的任意关系。 存储结构 定义： 存储结构（又称物理结构）是逻辑结构在计算机中存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。 运算集合 例如工资表： 1.3 算法 算法（Algorithm）定义 算法的特性 算法设计的要求 算法（Algorithm）定义 定义： Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. 算法是规则的有限集合，是为解决特定问题而规定的一系列操作。 算法的特性 算法设计的要求 算法的正确性 1.4 算法描述的工具 概述： 算法+数据结构=程序 算法、语言、程序的关系 设计实现算法过程步骤 类描述算法的语言选择 算法、语言、程序的关系 1. 算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存贮关系描述）。 设计实现算法过程步骤 1. 找出与求解有关的数据元素之间的关系 类描述算法的语言选择 类语言： 1.5 对算法作性能评价 评价算法的标准： 评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。 性能评价 有关数量关系计算 性能评价 定义： 对问题规模与该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。 有关数量关系计算 数量关系评价体现在时间——算法在机器中所耗费时间。 数量关系评价体现在空间——算法在机器中所占存储量。 关于算法执行时间 语句频度 算法的时间复杂度 数据结构中常用