资源描述
数据结构 信息与电气工程学院 计算机技术教研室 主要授课内容 第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 串 第五章 数组和广义表 主要授课内容 第六章 树和二叉树 第七章 图 第八章 查找 第九章 内部排序 第一章 绪论 1.1 基本概念和术语 1.2 算法和算法分析 1.1基本概念和术语 1. 数据 (data)的形式定义 是对客观事物的符号表示 ， 在计算机科学中是指 所有能输入到计算机中并被计算机程序处理的符 号的总称 常用的几种数据形式： 数值数据：是用 0到 9十个数字的组合描述一个实 体。 符号数据 ： 是用公认的一些符号的组合描述一个 实体。这种数据具有广泛性、模糊性。 1.1基本概念和术语 图像（图形）数据是用图像、图形描述一个实 体。 这种数据能直观的表现实体各部分之间的 关系，便于我们了解分实体的本质。虽然处理 复杂，但是，我们仍然要使用它。 语音数据 ： 是用自然语言描述一个实体。 总之 ， 在计算机科学领域 ， 凡是计算机能 识别与处理的数字 、 符号 、 图像 、 图形 、 语言 以及它们的汇集通称数据 。 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基本概念和术语 四类基本结构： 集合：结构中的数据元素之间除了“同属于一 个集合”的关系外，别无其它关系。 线性结构：结构中的数据元素之间存在一个对 一个的关系。 树形结构：结构中的数据元素之间存在一个对 多个的关系。 图状结构（网状结构）：结构中的数据元素之 间存在多个对多个的关系。 1.1基本概念和术语 4. 逻辑结构：描述数据元素之间逻辑关系的结构 5. 物理结构：数据结构在计算机中的表示，又称 为存储结构。 6. 数据元素之间的关系的两种表示方法： 顺序存储：把数据存储到地址连续的区间，借 助元素在存储器中的相对位置来表示数据元素 之间的逻辑关系。 链式存储：把数据存储到任意的地址区间，借 助指示元素存储地址的指针表示数据元素之间 的逻辑关系。 返回 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) 算法的空间复杂性 （ space complexity) 算法的空间相当于程序所需空间中的可变 空间部分 SP。 所以 ， 算法所需空间的量度记 作： S (n)=O(f(n) 其中 N 为问题特征 。 表示除输入和程序之 外所需的额外空间 。 1.2 算法和算法分析 5. 算法的描述方式 （ 1） 自然语言描述 （ 2） 流程框图描述 （ 3） 形式语言描述 ， 本课采用 C语言来 描述算法； 返回
展开阅读全文