(严蔚敏)绪论.pptVIP

课程的地位 《数据结构》作为一门独立课程在国外最早是从1968年开始设立的。（美国唐·欧克·努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷较系统地阐述了数据的逻辑结构、存储结构和相应操作/算法的著作。） 《数据结构》是计算机专业的必修课程，核心课程。 其他相关专业主要选修课程。 数据对象（data object）：性质相同的数据元素的集合，是数据的一个子集。如例1-1中的书目文件。 数据结构（data structure)：是相互之间存在一种或多种特定关系的数据元素的集合。（即数据元素和数据元素关系的集合。） ●任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。 ● 通常有下列4类基本结构： 集合： 结构中的数据元素除了同属于一种类型外，别无其它关系。 线性结构：结构中的数据元素之间存在一对一的关系。 树型结构：结构中的数据元素之间存在一对多的关系。 图状结构或网状结构： 结构中的数据元素之间存在多对多的关系。 例 1-4 复数的数据结构定义为 Complex=(C，R) C是含两个实数的集合﹛c1，c2﹜; R = {P}，P是定义在集合C上的一种关系{ c1，c2 }，c1表示实部，c2表示虚部。 抽象数据类型(Abstract Data Type, ADT)指一个数学模型以及定义在该模型上的一组操作。 抽象数据类型的定义仅取决于它的数学(逻辑)特性，而与在计算机内部的实现没有关系；即不论其内部结构如何变化，只要它的数学特性不变，都不影响其对外接口。 抽象数据类型和数据类型实质上是一个概念，只不过“抽象”的意义在于数据类型与在计算机内部的实现没有关系。 一个含有抽象数据类型的软件模块通常应包含定义、表示和实现三个部分。 ●抽象数据类型的形式化用以下三元组定义： ●本书定义抽象数据类型的格式： ADT抽象数据类型名{ 数据对象： 数据关系： 基本操作： } ADT抽象数据类型名 1.4.2 算法设计的要求 ●衡量算法优劣的标准 (1) 正确性(correctness)： 1.不含语法错误 2.对于几组输入数据能够得出满足规格说明要求的结果 3.对于精心选择的典型、苛刻而带有刁难性的数据能够得出满足规格说明要求的结果 4.对于一切合法的输入数据都能产生满足规格说明要求的结果 (2)可读性(readability)：人的阅读与交流 (3)健壮性(robustness)：当输入非法数据时，算法能够适当的做出反应或进行处理，不会产生莫名其妙的结果 (4)效率与低存储量：算法的执行时间和所需的最大存储空间 【例】两个n×n 阶矩阵相乘(C=A×B) for (i=1; i=n; i++) for (j=1; j=n; j++){ c[i][j] = 0; for (k=1; k=n; k++) c[i][j] += a[i][k]*b[k][j] ; } 【例】 (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; } 时间复杂度为: (a) O(1) — 常量阶 (b) O(n) — 线性阶 (c) O(n2) — 平方阶 原则: (1)尽可能选用多项式阶O(nk)的算法，而不希望用指数阶O(2n)的算法。 (2)算法的时间复杂度在难以精确计算基本操作执行次数的情况下，只需求出它关于n的增长率或阶即可。 最好情况：0次 最坏情况：1+2+3+…+n-1 = n(n-1)/2 平均时间复杂度为: O(n2) 在本书以后各章节中讨论的时间复杂度，除特别指明外，均指最坏情况下的时间复杂度。 1.4.4 算法的存储空间需求 算法的存储量指的是算法执行过程中所需的最大存储空间。 算法执行期间所需要的存储量应该包括以下三部分：(1)输入数据所占空间；(2)程序本身所占空间；(3)辅助变量所占空间。 程序代码本身所占空间对不同算法通常不会有数量级之差别，因此在比较算法时可以不加考虑；算法的输入数据量和问题规模有关，若输入数据所占空间只取决于问题本身，和算法无关，则在比较算法时也可以不加考虑；由此只需要分析除输入和程序之外的额外空间。 类似于算法的时间复杂度，本书中以空间复杂度作为算法所需存储空间的量度，记作: S(n)