数据结构：第一章 绪论.ppt

数据（Data） 定义: 数据元素（Data Element） 定义： 数据元素是组成数据的基本单位 ，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。例如： 数据结构（Data Structure） 定义： 数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。 集合结构 定义： 结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。 线性结构 定义： 结构中的数据元素之间存在着一对一的线性关系。 树型结构 定义： 结构中的数据元素之间存在着一对多的层次关系。 图状结构或网状结构 定义： 结构中的数据元素之间存在着多对多的任意关系。 逻辑结构 定义： 数据的逻辑结构是指数据元素之间逻辑关系描述。 存储结构 定义： 存储结构（又称物理结构）是逻辑结构在计算机中存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。 1.2数据抽象与抽象数据类型 数据的抽象 汇编语言中十进制表示的数据98.65、9.6E3等, 它们是二进制数据的抽象; 抽象数据类型(Abstract Data Type) 定义： 抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。 ADT的表示与实现 ADT的定义： 1.3 算法 算法（Algorithm）定义 定义： Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. 算法是规则的有限集合，是为解决特定问题而规定的一系列操作。 算法的特性 算法设计的要求 算法的正确性 算法描述的工具 设计实现算法过程步骤 1. 找出与求解有关的数据元素之间的关系 对算法作性能评价 评价算法的标准： 评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。 性能评价 定义： 对问题规模N与该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。 关于算法执行时间 定义： 一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。 语句频度 定义： 语句频度是指该语句在一个算法中重复执行的次数。 算法的时间复杂度 算法的时间复杂度，即是算法的时间量度记做： T(n)=O(f(n)) 常用的时间复杂度频率计数 数据结构中常用的时间复杂度频率计数有7个: 常用的时间复杂度频率计数 常用的时间复杂度频率表： 最坏时间复杂度 定义： 讨论算法在最坏情况下的时间复杂度，即分析最坏情况下以估计出算法执行时间的上界。 算法的空间复杂度 定义： 说明 关于本书内容编写说明 本书基本结构 第一部分：数据结构的基本概念（第1章） 第二部分：基本的数据结构 包括：线性结构—线性表、栈和队列、串、数组与广义表 （第2—5章） 非线性结构—树、图（第6、7章） 第三部分：基本技术 包括：查找技术与排序技术（第8、9、10章） O(1) 常数型 O(n)线性型 O(n2)平方型 O(n3)立方型 O(2n)指数型 O(log2n)对数型 O(nlog2n)二维型 按时间复杂度由小到大排列的频率表： 2147483648 32768 1024 160 32 5 65536 5096 256 64 16 4 256 512 64 24 8 3 16 64 16 8 4 2 4 8 4 2 2 1 2 1 1 0 1 0 一般讲：前3种可实现，后3种虽理论上是可实现的，实际上只有对N限制在很小范围才有意义，当N较大时，不可能实现。 2n n3 n2 nlog2n n log2n 例如冒泡排序算法 void bubble(int a[], int length) {将a中整数数组重新排序，达到递增有序} int i=0, j, temp; int change ; do{ change=false ; for(j=1;jlength-i;j++) if( a[j]a[j+1]) {temp= a[j];