数据结构二版51.ppt

数据结构;数据结构目录;第1章 绪论;(a1，b1)(a2，b2)…(an，bn) 其中ai，bi(i=1，2…n) 分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。;;通过以上几例可以直接地认为：数据结构 就是研究数据的逻辑结构和物理结构以及它们 之间相互关系，并对这种结构定义相应的运算， 而且确保经过这些运算后所得到的新结构仍然 是原来的结构类型。;;1.2 基本概念和术语;数据结构主要指逻辑结构和物理结构, 数据之间的相互关系称为逻辑结构。通常分为四类基本结构： 一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。 二、线性结构 结构中的数据元素之间存在一对一的关系。 三、树型结构 结构中的数据元素之间存在一对多的关系。 四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 ; 数据对象可以是有限的，也可以是无限的。 　数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。 抽象数据类型：一个数学模型以及定义在该模型上的一组操作。 　　抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。 　　;数据类型：在一种程序设计语言中，变量所具有的数据种类。 例1、 在FORTRAN语言中，变量的数据类型有整型、实型、和复数型 例2、在C语言中 数据类型：基本类型和构造类型 基本类型：整型、浮点型、字符型 构造类型：数组、结构、联合、指针、枚举型、自定义 数据对象：某种数据类型元素的集合。 例3、整数的数据对象是{…-3，-2，-1，0，1，2，3，…} 英文字符类型的数据对象是{A，B，C，D，E，F，…} ;;1.3 算法 算法：是对特定问题求解步骤的一种描述 算法是指令的有限序列，其中每一条指令表示一个或多个操作。 算法具有以下五个特性： （1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间???完成。 （2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。 ;（3）可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 （4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 （5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。;1.3.2 算法设计的要求 评价一个好的算法有以下几个标准: (1) 正确性(Correctness ) 算法应满足具体问题的需求。 (2)可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解。 (3)健状性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。 (4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。;1.4 .1算法效率的度量 空间代价：（空间复杂性）被解决问题的规模由1增至n时，解该问题的算法所占用的空间也以某种单位由f(1)增至f（n）,称f(n)为空间代价。 时间代价：（时间复杂性）被解决问题的规模由1增至n时，解该问题的算法所耗费的时间也以某种单位由g(1)增至g（n）,称g(n)为时间代价。 ;定义：如果存在两个正常数c和n0，对于所有的n≧n0，有 ︱f(n) ︳≦c｜g(n) ︳则记作 f(n)=O(g(n)) 　计算规则： （1）加法规则 设有两个程序段S1和S2,其时间代价分别为T1(n)=O(f1(n))和T2(n)=O(f2(n))，将两个程序段连接在一起得到这段程序总的时间代价为 T(n)=T1(n)+T2(n)= O(f1(n))+O(f2(n))=O(max(f1(n),f2(n)));（2）乘法规则 如果一个程序的时间代价为T1(n)=O(f1(n))，但他的时间代价并不是最基本的，而是以某个子程序的执行代价为单位时间来考虑的，而这个子程序的每次调用时间代价为T2(n)=O(f2(n))，那么这个程序的实际时间代价是 T(n)=T1(n)xT2(n)= O(f1(n))xO(f2(n))=O(f1(n)xf2(n));一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作 T(n)=O(f(n)) 称作算法的渐近时间复杂度。 例１、f