数据结构教案第1章绪论.ppt

数据结构 信息与电气工程学院 计算机技术教研室 主要授课内容 第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 串 第五章 数组和广义表 主要授课内容 第六章 树和二叉树 第七章 图 第八章 查找 第九章 内部排序 第一章 绪论 1.1 基本概念和术语 1.2 算法和算法分析 1.1基本概念和术语 1. 数据(data)的形式定义 是对客观事物的符号表示，在计算机科学中是指 所有能输入到计算机中并被计算机程序处理的符号 的总称 常用的几种数据形式： n 数值数据：是用0到9十个数字的组合描述一个实 体。 n符号数据 ：是用公认的一些符号的组合描述一个 实体。这种数据具有广泛性、模糊性。 1.1基本概念和术语 n图像（图形）数据是用图像、图形描述一个实 体。 这种数据能直观的表现实体各部分之间的关 系，便于我们了解分实体的本质。虽然处理复杂 ，但是，我们仍然要使用它。 n语音数据：是用自然语言描述一个实体。 总之，在计算机科学领域，凡是计算机能 识别与处理的数字、符号、图像、图形、语言以 及它们的汇集通称数据。 1.1基本概念和术语 2. 数据元素 数据元素(data element) 是系统中数据的 基本单位（即在内存中具有可访问地址号的最 小数据单位）。在实际应用中一个数据元素往 往是有几部分组成，其中每一部分称为一个数 据项（数据项是数据处理时不可再分割的最小 数据单元）。每一个数据项都有一个值，习惯 上称这个值为关键字。应用时，关键字又分主 关键字与次关键字。主关键字是指它能唯一的 标识一个数据元素。 1.1基本概念和术语 下表为一张学生登记表，在表中每一个学 生为一个数据元素 学号姓名性别 年龄班级 99001李明男19计1 99002王华女20计2 99003赵立男18计1 1.1基本概念和术语 3. 数据对象（data object) 是性质相同的数据元素的集合，是数据的一个 子集。 例：字母字符数据对象是集合 C=A，B，Z 4. 数据结构(data structure) 是相互之间存在一种或多种特定关系的数据元 素的集合。 数据结构的形式定义为：数据结构是一个二元组 Data_Structure=(D,S) 1.1基本概念和术语 四类基本结构： n集合：结构中的数据元素之间除了“同属于一 个集合”的关系外，别无其它关系。 n线性结构：结构中的数据元素之间存在一个对 一个的关系。 n树形结构：结构中的数据元素之间存在一个对 多个的关系。 n图状结构（网状结构）：结构中的数据元素之 间存在多个对多个的关系。 1.1基本概念和术语 4. 逻辑结构：描述数据元素之间逻辑关系的结构 5. 物理结构：数据结构在计算机中的表示，又称 为存储结构。 6. 数据元素之间的关系的两种表示方法： n顺序存储：把数据存储到地址连续的区间，借 助元素在存储器中的相对位置来表示数据元素之 间的逻辑关系。 n链式存储：把数据存储到任意的地址区间，借 助指示元素存储地址的指针表示数据元素之间的 逻辑关系。 返回 1.2 算法和算法分析 1.算法的定义 算法是对某类特定问题求 解步骤的描述。它应满足下列特性： （1）有穷性 （2）确定性 （3）可行性 （4）输入 （5）输出 1.2 算法和算法分析 2. 算法设计的要求 （1）正确性 （2）可读性 （3）健壮性 （4）效率与低存储量需求 1.2 算法和算法分析 3.对程序性能的分析 为了对算法性能有个深刻的了解，我们首先分 析程序的性能。（程序的空间复杂性与程序的时 间复杂性） （1）程序的性能（program performance) 是指运行一个程序所需要的内存大小和时间多 少。一般使用两种方法来确定一个程序的性能： 一个是分析法；一个是实验法法。在对程序进行 性能分析（performance analysis)时，采用分 析法，而在对程序进行性能测量(performance measurement)时，借助实验法。 1.2 算法和算法分析 程序的空间复杂性(space complexity) 是指运行完一个程序所需要的内存大小。 讨论程序的空间复杂性的主要原因如下： 如果程序将要运行在一个多用户计算机 系统中，可能需要指明分配给该程序的内存 大小。 对任何一个计算机系统想提前知道是否 有足够可用的内存来运行该程序。 1.2 算法和算法分析 一个问题可能有若干个内存需求各不相 同的解决方案。 可以利用空间复杂性来估算一个程序 所能解决的问题的最大规模 程序的时间复杂性（time complexity) 是指运行完该程序所需要的时间。 讨论程序的时间复杂性的主要原因如下 ： 1.2 算法和算法分析 有些计算机需要用户提供程序运行时 间的上限， 一旦达到这个上限程序将被强 制结束。 正在开发的程序可能需要提供一个满 意的实时响应。 如果有多种可选的方案来解决一个问 题，那么具体决定采用哪一个主要基于这 些方案之间的性能差异。 1.2 算法和算法分析 (2)程序空间复杂性的计算 程序所需的空间主要由指令空间、环境栈空间两部 分构成。 指令空间（instruction space)是指用来存储经过 编译之后的程序指令所需的空间。 指令空间有两部分组成： 存储常量和简单变量所需的空间。 存储复合变量所需的空间。包裹数据结构所需的空 间及动态分配的空间。 1.2 算法和算法分析 环境栈空间 (environment stack space) 环境栈用 来保存函数调用返回时，恢复运行所需要的 信息。 总上所述，一个程序所需的空间由两部分组成： 固定部分：包含指令、简单变量空间，定长复 合变量所需的空间及常量所需的空间。 可变部分：包含复合变量所需的空间、 动态分配 所需的空间以及递归栈所需的空间。 1.2 算法和算法分析 任意程序P所需的空间S（P）可以表示为： S（P）=C+SP 其中C是一个常量表示固定部分所需的空间， SP表示可变部分所需的空间。在应用中大都用SP作 程序空间复杂性。 （3）程序时间复杂性的计算 一个程序P所占用的时间T（P）=编译时间+ 运行时间。编译时间与程序的特征无关。因此主要 讨论程序的运行时间， 运行时间通常用TP表示。 1.2 算法和算法分析 令n代表程序的特征，那么， TP的计算公 式为： TP（n） =c1ADD(n)+c2SUB(n)+c3MUL(n)+c4DIV(n)+ 其中c1、c2、c3、c4分别表示一个加、减 、乘、 除操作所需的时间。函数ADD、SUB、 MUL、DIV分别表示程序P中所使用的加、减、 乘、除操作的次数。在应用中大都是估算运行 时间。往往用最多的操作次数为程序时间复杂 性 1.2 算法和算法分析 4.对算法性能的分析 虽然， 算法不是程序不能上机运行，但是对 算法性能的分析，完全可以用对程序性能的分析 方法进行. (1) 算法的时间复杂性（time complexity） 算法的时间相当于程序时间中的运行时间部分 。同样，关键操作的次数对时间复杂性的影响最 大。假设, 算法中关键操作执行的次数是问题特 征（规模）n 的某个函数f（n）。那么，算法的 时间量度(复杂性)记作： T (n) = O(f(n) 1.2 算法和算法分析 它表示随问题特征n的增大，算法中关键操作 执行时间的增长率和f（n） 的增长率相同，所 以称f（n）为算法的时间复杂性。在多数情况下 , 算法中关键操作执行的次数和包含它的语句的 频度相同。 语句的频度（frequency count)指 的是该语句重复执行的次数。所以，在实际应用 时，用算法中语句的最大频度作为算法的时间复 杂性。 1.2 算法和算法分析 例如：在下面的三个程序段中 (a)+x;s=0; (b)for(i=1;i=n;+i)+x;s+=x; (c)for (j=1;j=n;+j) for (k=1;k=n;+k) +x;s+=x; 关键操作+x的语句的频度分别为1，n ，n， 则这三个程序段的时间复杂性分别为O（1）， O（n），O（n ）分别称为常数阶，线性阶，平 方阶。 1.2 算法和算法分析 (2)算法的空间