资源描述
第一章,绪 论,基本概念和术语,1、数据：对客观事物的符号表示，信息的载体，能被计算机识别、存储和加工处理。 2、数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。 3、数据结构：相互之间存在一种或多种特定关系的数据元素的集合。 形式定义为： Data_Structure = (D, S) 其中D是数据元素的有限集，S是关系的有限集。,基本概念和术语,数据结构包括以下内容： （1）数据的逻辑结构。从逻辑关系上描述数据，与数据存储无关，独立于计算机。它包括以下四类基本结构： 集合：同属一个集合 线性结构：一对一 树形结构：一对多 图状结构或网状结构：多对多,基本概念和术语,（2）数据的物理结构，数据结构在计算机存储器中的表示，又称存储结构。它包括两种存储结构： 顺序存储结构：借助数据元素在存储器中相对位置表示逻辑关系 链式存储结构：依靠数据元素中的指针表示元素之间的逻辑关系,基本概念和术语,（3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。 4、数据类型：一个值的集合及在值上定义的一组操作的总称。 分为：原子类型和结构类型。 5、抽象数据类型（ADT）：抽象数据的组织和与之相关的操作。 优点：将数据和操作封装在一起实现了信息隐藏。,基本概念和术语,（1）分类 原子类型。变量的值不可分解 固定聚合类型。变量的值由确定数目的成分按某种结构组成 可变聚合类型。变量的值的成分的数目不确定 （2）形式定义 三元组表示法：（D, S, P）,基本概念和术语,（3）定义格式 抽象数据类型的定义格式 ADT 抽象数据类型名 数据对象： 数据关系： 基本操作： ADT 抽象数据类型名,基本概念和术语,基本操作的定义格式 基本操作名（参数表） 初始条件： 操作结果：,抽象数据类型的表示和实现,本书采用类C语言作为描述数据结构及其算法的工具，类C语言使用方法与C语言相近，但函数中使用的变量可不作声明，增加使用C+中的引用在函数调用中传递参数。 类C语言简要说明请参见教材P10-11,算法和算法分析,1、算法 算法是对特定问题求解步骤的一种描述，是指令的集合。 算法的特性：有穷性、确定性、可行性、输入、输出 2、算法设计的要求 正确性 可读性 健壮性 效率与存储量需求,算法和算法分析,3、算法分析 算法分析就是对算法质量优劣的评价，通常分为事后统计和事前分析两种方法。 算法分析应从两个角度： 依据算法编写的程序在计算机中运行时间的多少的度量，即时间复杂度。 依据算法编写的程序在计算机中占存储空间的多少的度量，即空间复杂度。 注：时间复杂度和空间复杂度合称算法的复杂度。,算法和算法分析,4、算法的时间复杂度 是算法执行的时间耗费，是求解问题规模n的函数。记为：T(n)=O(f(n)。 (1)时间复杂度的计算方法频度统计法 例： for(i=1; i=n; +i) for(j=1; j=n; +j) cij = 0; for(k=1; k=n; +k) cij += aik * bkj; 算法的频度=n+1 + n(n+1) + n2 + n2(n+1) + n3 = 2n3 + 3n2 + 2n + 1 则算法的时间复杂度为O(n3),算法和算法分析,(2)有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。此时，一种办法是讨论平均时间复杂度，一种办法是讨论最坏的情况下的时间复杂度。 (3)常见的时间复杂度按数量级递增排列依次为： 常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)。 5、算法的空间复杂度 是算法的空间耗费，也是求解问题规模n的函数。记为：S(n)=O(f(n)。,本章小结,数据结构研究的是数据的逻辑结构和存储结构以及其算法； 本课程从抽象数据类型角度讨论各种类型的数据结构及其应用； 本课程使用类C语言作为算法的描述工具； 算法的五大特性：有穷性、确定性、可行性、输入、输出； 一个“好”的算法应满足正确性、可读性、健壮性以及效率与低存储量的需求； 算法的分析主要考察算法的时间复杂度和空间复杂度。,作业,1. 算法的时间复杂度取决于（ ） A问题的规模 B. 待处理数据的初态 C. A和B 2.计算机算法指的是（1），它必须具备（2） 这三个特性。 (1) A计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 3一个算法应该是（ ）。 A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C. 4从逻辑上可以把数据结构分为（ ）两大类。 A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构,作业,5数据结构中评价算法的两个重要指标是 时间复杂度 和 空间复杂度 。 6. 下面程序段的时间复杂度为 O(n) 。(n1) sum=1； for (i=0;sum=i;j-) s;,
展开阅读全文