数据结构（一）.ppt

数据结构（一）,基本概念,数据 可以被计算机识别、存储和加工处理的符号的集合。 是计算机操作的对象的总称。 是信息的载体。 例子 数值计算程序（实数或整数） 编译程序（源程序） 图像处理程序（图像）,基本概念,数据元素 组成数据的基本单位。 是数据中的一个“个体”。 又称元素、记录、结点或者顶点。 数据项 数据元素由数据项组成。 是数据结构中讨论的最小单位。 又称域、字段。,基本概念,数据结构 相互之间存在着某种关系的数据元素的集合。 逻辑结构 数据元素之间的逻辑关系。 存储结构 逻辑结构在存储器中的映象。,基本概念,数据的逻辑结构，可形式表示为二元组： L = ( N, R ) 其中 N 是结点的有限集合 R 是 N 上的关系集合 例子 L = ( N, R ) N = a0, a1, a2 R = r r = ( a0, a1 ), ( a0, a2 ) ,基本概念,设L=( N, R )是一个逻辑结构，R= r ， 若a, bN，且关系( a, b )r， 则： 称 a 是 b 的 前趋结点， 称 b 是 a 的 后继结点， 称 a 和 b 是 相邻结点， 如果不存在aN，使( a, b )r ，则称b为始结点， 如果不存在bN，使( a, b )r，则称a为终结点， 既非始结点又非终结点的结点被称为内结点。,基本概念,数据的逻辑结构 线性结构 树形结构 图状结构 集合结构,基本概念,线性结构 结构中有且仅有一个始结点和一个终结点，每个内结点有且仅有一个前趋结点和一个后继结点。 非线性结构 结构中的结点可能有多个前趋结点和多个后继结点。,基本概念,一行表示一个结点（元素），每个结点由学号、姓名、性别等九个域（数据项）组成。 表的第一行是始结点；最后一行是终结点；中间的行都是内结点。 表的逻辑结构是线性结构。,基本概念,数据的存储结构 “数据元素”的映象 “关系”的映象 数据元素的映象方法 用二进制位(bit)的位串表示数据元素 (321)10 = (101000001)2 A = (001000001)2,基本概念,关系的映象方法 顺序映象 以相对的存储位置表示后继关系 链式映象 以附加信息(指针)表示后继关系,x y,存储结构只含数据元素本身 的信息，无附加信息,链式映象中，存储结构除数据元素本身信息外，需要附加信息指示存储位置,基本概念,算法 是能够解决某类问题的由若干指令组成的有限序列。 一个算法可以用自然语言、程序设计语言或专门设计的伪语言描述。 算法必须满足五个特性： （1）有限性 （2）确定性 （3）输入 （4）输出 （5）可行性,基本概念,有限性：任何一条指令都只能执行有限次，换句话说，算法必须在执行有限步后结束。 确定性：算法中每条指令的含义必须明确，不允许有二义性，对于相同的输入只能得出相同的输出。 输入：一个算法可以有零个或多个输入数据，这些输入数据取自确定的对象集合。 输出：算法有一个或多个输出，这些输出是同输入有某个特定关系的量。 可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。,基本概念,算法的设计原则： 正确性 可读性 坚固性(健壮性) 高效率与低存储量需求,基本概念,正确性:说一个算法是正确的，是指对于一切合法的输入数据，该算法经过有限时间（算法意义上的有限）的执行都能产生正确（或者说满足规格说明要求）的结果。 可读性: 可读性好的算法有助于设计者和他人阅读、理解、修改和重用。晦涩难读的程序易于隐藏较多错误。 坚固性: 当输入数据非法时，算法能适当地作出合适的反应。 高效率与低存储量需求:通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。,基本概念,目前不存在证明算法正确性的形式化方法 算法正确性的四个层次 程序中不含语法错误； 程序对于几组输入数据能够得出满足要求的结果； 程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果； 程序对于一切合法的输入数据都能得出满足要求的结果；,基本概念,算法效率的衡量方法和准则 两种方法 事后统计法 必须执行程序 其它因素掩盖算法本质 事前分析估算法,基本概念,和算法执行时间相关的因素： 算法选用的策略 问题的规模 编写程序的语言 编译程序产生的机器代码的质量 计算机执行指令的速度 用绝对的时间单位衡量算法效率不合适,基本概念,撇开影响算法效率的软硬件因素，一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f (n) 的增长率相同，则可记作： T (n) = O( f (n) ) 称T (n) 为算法的(渐近)时间复杂度。,基本概念,算法 = 控制结构 + 基本运算 为了比较同一问题的不同算法，通常的做法是，从算法中选取一些基本运算，以基本运算的重复执行次数作为算法的时间量度。,void mult(int an, int bn, int( /for /mult,O(n3),基本概念,例子： (a) x=x+1; O(1) (b) for(i=0; in; i+) x=x+1; O(n) (c) for(i=0; in; i+) O(n2) for( j=0; jn; j+) x=x+1; 算法分类： 常量阶 O(c) 对数阶 O(log2n) 线性阶 O(n) 多项式阶 O(nm) 指数阶 O(2n),基本概念,类似于算法的时间复杂度，空间复杂度度量算法所需存储空间，记做： S = O( f (n) ) 算法所需存储空间包括： 输入数据所占空间 程序本身所占空间 辅助变量所占空间,基本概念,若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。,基本概念,数据类型 在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。 不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。 数据类型是一个值的集合和定义在此集合上的 一组操作的总称。,基本概念,抽象数据类型 是指一个数学模型以及定义在此数学模型上的一组操作。 抽象数据类型的特征 数据抽象 用抽象数据类型描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口。 数据封装 将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。 抽象数据类型和类,基本概念,抽象数据类型的描述,ADT Name is Data 构成该抽象类型所必须的基本数据项 Operations 构造函数（声明一个该类型的对象时，对基本数据项进行初始化） Initial Values： 赋给基本数据项的值 Process： 初始化对象 操作1 Input： 操作1要求用户输入的值 Preconditions： 系统执行操作1前数据所需的状态 Process： 对数据执行操作1 Output： 操作1结束后返回的数据 Postconditions：执行操作1后数据的状态 操作2 . 操作n . end ADT Name,