0绪论-数据结构.ppt

第一章绪论§1什么是数据结构众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下的例子。例如电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码。假定电话号码薄按如下形式安排：(Name1，Tno1)(Name2，Tno2)…(Namen，Tnon)其中:Namei和Tnoi(i=1，2…n)分别表示某人的名字和对应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据的结构，直接影响算法的选择和效率。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定我们把名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(Namei，Tnoi)，1≤i≤n数据结构还要提供每种结构类型所定义的各种运算的算法。§2基本概念和术语数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项(DataItem)组成。数据项是数据的不可分割的最小单位。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(DataStructure)：数据结构是研究数据与数据之间关系的一门学科，主要描述数据的组织形式、存储结构以及操作的实现算法。它包括三个方面的内容：1、结构中数据元素之间的逻辑关系描述，称为数据的逻辑结构(LogicStructure)。即数据元素之间的抽象关系。2、结构中的数据在计算机中的表示方式，称为数据的存储结构(StorageStructure)。即数据结构在计算机中的映象，包括数据元素的映象和关系的映象。3、结构中的数据所要进行的运算，称之为数据的运算(Operating)，或称为操作。通常数据的逻辑结构分为四类基本结构：一、集合(set)结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构(Linear)结构中的数据元素之间存在一对一的关系。三、树型结构(Tree)结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构(GraphorNet)结构中的数据元素之间存在多对多的关系。通常数据的存储结构分为四类基本结构：1、顺序存储结构(Sequential)把每个数据元素，按某种顺序存放在一段连续的存储单元中。2、链式存储结构(Linked)把每个结点的数据，零散地存放在存储单元中。3、索引存储结构(Index)把每个结点的数据按一定规律顺序或链式存放在存储单元中。4、Hash存储结构(Hash)把每个结点的数据通过一个预设的Hash函数，来决定该结点的存储单元。数据结构的形式定义为：数据结构是一个二元组：data-Structure=(D，R)其中：D是数据元素的有限集，R是D上关系的有限集。例复数的数据结构定义为：Complex=(C，R)其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。§3算法和算法分析算法(Algorithm)：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：（1）有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。（3）可行性一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。4）输入一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。5）输出一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。算法设计的要求评价一个好的算法有以下几个标准:(1)、正确性(Correctness)算法应满足具体问题的需求。(2)、可读性(Readability)算法应该好读。以有利于阅读者对程序的理解。⑶、健状性(Robustness)算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。(4)、效率与存储量需求效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。算法效率的度量对一个算法要作出全面的分析，可分成两个阶段进行，即事先