DS01数据结构概述讲述.ppt

第1章 数 据 结 构 概 述 第 1 章 1.2 数据结构的有关概念和术语 1、数据：对客观事物的符号表示，信息的载体，能被计算机识别、存储和加工处理。如整数，实数，字符串、图象、声音等都是数据。 2、数据元素：数据的基本单位，又可称为元素、结点、顶点、记录等。 3、数据项: 是数据不可分割的最小单位。如学号、姓名等。 一个数据元素可以由若干个数据项构成。 4、数据对象：性质相同的数据元素的集合。如所有班名相同的记录集合。 5、数据类型：是指一个类型和定义在这个类型上的操作集合。 分为：原子类型和结构类型 6、抽象数据类型：是指一个逻辑概念上的类型和这个类型上的操作集合。优点：将数据和操作封装在一起实现了信息隐藏。 1.2 数据结构的有关概念和术语 抽象数据类型的定义可以由元素、元素之间的关系及操作三部分构成。 抽象数据类型的定义格式 ADT 抽象数据类型名｛ 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ｝ADT 抽象数据类型名 例如：P4 例1-4 1.2 数据结构的有关概念和术语 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。 形式定义为： Data_Structure(D, R) 例如：P5 例1-5 1.2 数据结构的有关概念和术语 数据结构包括以下内容： （1）数据的逻辑结构。从逻辑关系上描述数据，与数据存储无关，独立于计算机。它包括以下四类基本结构： 集合：　同属一个集合 线性结构：　一对一 树形结构：　一对多 图状结构或网状结构：　多对多 （2）数据的物理结构，数据结构在计算机存储器中的表示，又称存储结构。它包括： 顺序存储结构：借助数据元素在存储器中相对位置表示逻辑关系 链式存储结构：依靠数据元素中的指针表示元素之间的逻辑关系 索引 散列 1.3 算法和算法描述 1、算法 算法是对特定问题求解步骤的一种描述，是指令的集合。 算法的特性：有穷性、确定性、可行性、输入、输出 1.3 算法和算法描述 2、算法设计的要求 正确性 可读性 健壮性 高效性 1.3 算法和算法描述 算法描述： 1.文字形式 :用中文或英文这样的文字来描述算法。 2.伪码形式 :用一种仿程序设计语言的语言来描述算法。比如类C语言。 3.程序设计语言形式 :用某种程序设计语言描述算法。其优点是算法不用修改，直接作为程序语句键入计算机，计算机能调用和运行。 1.3 算法和算法描述 算法描述： 类C语言比程序设计语言更容易描述和被理解，比文字描述的自然语言更接近程序设计语言，容易转换成高级语言。 例如：P7 例1-6 算法和程序的区别 1.算法是对特定问题求解步骤的一种描述，是指令的集合。一个问题可以有多种算法。 2.程序是用某种程序设计语言对算法的具体实现。 软件开发生命周期： 需求分析→概要设计→算法设计→程序编码→运行维护 算法和程序的区别 1.程序可以是无穷的，例如：OS； 算法必须是有穷的。 2.程序可以是错误的，算法必须是正确的。 3.程序是用程序设计语言描述，在机器上可以运行；算法也可以用框图，自然语言等方式描述。 1.4 算法时空效率分析方法 算法分析就是对算法质量优劣的评价，通常分为事后统计和事前分析两种方法。 算法分析应从两个角度： 依据算法编写的程序在计算机中运行时间的多少的度量，即时间复杂度。 依据算法编写的程序在计算机中占存储空间的多少的度量，即空间复杂度。 注：时间复杂度和空间复杂度合称算法的复杂度。 1.4 算法时空效率分析方法 1.算法的时间复杂度 程序运行所需要的时间取决于以下因素： (1)机器执行指令的速度 (2)书写算法的程序设计语言 (3)编译产生的机器语言代码质量 (4)算法所选用的策略 (5)问题的规模，即算法的时间效率与算法所处理的数据个数n的函数关系。 1.4 算法时空效率分析方法 算法的时间复杂度 是算法执行的时间耗费，是求解问题规模n的函数。记为：T(n)=O(f(n))。 (1)时间复杂度的计算方法——频度统计法 例1：语句 x=x+1;执行频度为1，时间复杂度记为： T(n)=O(1) 1.4 算法时空效率分析方法 (1)时间复杂度的计算方法——频度统计法 例2： for(i=1; i=n; i++) x=x+1; 算法的频度=n+1 则算法的时间复杂度为O(n) 1.4 算法时空效率分析方法 (1)时间复杂度的计算方法——频度统