《0绪论数据结构PPT课件》由会员分享，可在线阅读，更多相关《0绪论数据结构PPT课件（22页珍藏版）》请在金锄头文库上搜索。
1、 第一章 绪 论众所周知，人们在学习计算机语言课程的时侯，众所周知，人们在学习计算机语言课程的时侯，使用计算机来解决实际问题，大致需要以下三个使用计算机来解决实际问题，大致需要以下三个步骤：步骤： 1 1、分析实际问题，抽象出一个适当的数学模型；、分析实际问题，抽象出一个适当的数学模型；2 2、设计一个解决该数学模型的算法；、设计一个解决该数学模型的算法；3 3、编程、调试、测试、修改直至问题最终解答。、编程、调试、测试、修改直至问题最终解答。 为了设计出执行效率高、省空间的程序，就形成为了设计出执行效率高、省空间的程序，就形成了了“数据结构数据结构(Data Structure)”(Data
2、 Structure)”这门学科。这门学科。 1 1 1 什么是数据结构 众所周知，计算机的程序是对信息进行加众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。构关系，这就是数据结构的内容。2 2 那么，什么是数据结构呢？先看以下的例子。那么，什么是数据结构呢？先看以下的例子。 例如电话号码查询系统例如电话号码查询系统设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了N N个人的名字和其相个人的名字和其相应的电话号
3、码。假定电话号码薄按如下形式安排：应的电话号码。假定电话号码薄按如下形式安排： (Name(Name1 1，TnoTno1 1)(Name)(Name2 2，TnoTno2 2)(Name)(Namen n，TnoTnon n) ) 其中其中:Name:Namei i和和TnoTnoi i(i=1(i=1，2n) 2n) 分别表示某人的名字分别表示某人的名字和对应的电话号码。和对应的电话号码。要求设计一个算法，当给定任何一个人的名字时，要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法
4、也能够报告没有这中根本就没有这个人，则该算法也能够报告没有这个人的标志。个人的标志。 3 3 算法的设计，依赖于计算机如何存储人的名算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电字和对应的电话号码，或者说依赖于名字和其电话号码的结构。话号码的结构。 数据的结构，直接影响算法的选择和效率。数据的结构，直接影响算法的选择和效率。 上述的问题是一种数据结构问题。可将名字上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、和对应的电话号码设计成：二维数组、表结构、向量。向量。 假定我们把名字和其电话号码逻辑上已安排假定我们把名字和其电话号码
5、逻辑上已安排成成N N元向量的形式，它的每个元素是一个数对元向量的形式，它的每个元素是一个数对(Name(Namei i，TnoTnoi i) )， 1in 1in 数据结构还要提供每种结构类型所定义的各数据结构还要提供每种结构类型所定义的各种运算的算法。种运算的算法。4 4 通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。5 5 2 基本概念和术语数据数据(Data(Data):):是对信息的一种符号表示。在计算机是对信息的一种符号表示。在计算机科学中是指所有能输入
6、到计算机中并被计算机程序科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。处理的符号的总称。数据元素数据元素(Data Element(Data Element):):是数据的基本单位，在是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项一个数据元素可由若干个数据项(Data Item)(Data Item)组成。组成。数据项是数据的不可分割的最小单位。数据项是数据的不可分割的最小单位。数据对象数据对象(Data Object)(Data Object)：是性质相同的数据元素：是性质相同的数据元
7、素的集合。是数据的一个子集。的集合。是数据的一个子集。6 6数据结构数据结构(Data Structure)(Data Structure)：数据结构是研究数数据结构是研究数据与数据之间关系的一门学科，主要描述数据的据与数据之间关系的一门学科，主要描述数据的组织形式、存储结构以及操作的实现算法。组织形式、存储结构以及操作的实现算法。它包它包括三个方面的内容：括三个方面的内容： 1 1、结构中数据元素之间的逻辑关系描述，称为、结构中数据元素之间的逻辑关系描述，称为数据的数据的逻辑结构逻辑结构逻辑结构逻辑结构(Logic Structure)(Logic Structure)。即数据元素。即数据元
8、素之间的抽象关系。之间的抽象关系。 2 2、结构中的数据在计算机中的表示方式，称为、结构中的数据在计算机中的表示方式，称为数据的数据的存储结构存储结构存储结构存储结构(Storage Structure)(Storage Structure)。即数据结。即数据结构在计算机中的映象，包括数据元素的映象和关构在计算机中的映象，包括数据元素的映象和关系的映象。系的映象。 3 3、结构中的数据所要进行的运算，称之为数据的、结构中的数据所要进行的运算，称之为数据的运算运算运算运算(Operating)(Operating)，或称为，或称为操作操作操作操作。7 7通常数据的逻辑结构分为四类基本结构：通常数
9、据的逻辑结构分为四类基本结构：一、一、集合集合(set)(set)结构中的数据元素除了同属于一种结构中的数据元素除了同属于一种类型外，别无其它关系。类型外，别无其它关系。二、二、线性结构线性结构(Linear)(Linear)结构中的数据元素之间存结构中的数据元素之间存在一对一的关系。在一对一的关系。三、三、树型结构树型结构 (Tree)(Tree)结构中的数据元素之间存在结构中的数据元素之间存在一对多的关系。一对多的关系。四、四、图状结构或网状结构图状结构或网状结构(Graph or Net)(Graph or Net)结构中结构中的数据元素之间存在多对多的关系。的数据元素之间存在多对多的关
10、系。8 8通常数据的存储结构分为四类基本结构：通常数据的存储结构分为四类基本结构：1 1、顺序存储结构顺序存储结构( (SequentialSequentialSequentialSequential) )把每个数据元素，把每个数据元素，按某种顺序存放在一段连续的存储单元中。按某种顺序存放在一段连续的存储单元中。2 2、链式存储结构链式存储结构(Linked)(Linked)把每个结点的数据，零把每个结点的数据，零散地存放在存储单元中。散地存放在存储单元中。3 3、索引存储结构索引存储结构 (Index)(Index)把每个结点的数据按一把每个结点的数据按一定规律顺序或链式存放在存储单元中。定
11、规律顺序或链式存放在存储单元中。4 4、HashHash存储结构存储结构(Hash)(Hash)把每个结点的数据通过一把每个结点的数据通过一个预设的个预设的HashHash函数，来决定该结点的存储单元。函数，来决定该结点的存储单元。9 9数据结构的形式定义为：数据结构是一个二元组：数据结构的形式定义为：数据结构是一个二元组： data-Structure=(Ddata-Structure=(D，R) R) 其中：其中：D D是数据元素的有限集，是数据元素的有限集， R R是是D D上关系的有限集。上关系的有限集。例例 复数的数据结构定义为复数的数据结构定义为： Complex=Complex=
12、(C(C，R) R) 其中：其中：C C是含两个实数的集合是含两个实数的集合C C1 1，C C2 2，分别表示复数的分别表示复数的实部和虚部。实部和虚部。R=PR=P，P P是定义在集合上的一种关是定义在集合上的一种关系系 C C1 1，C C2 2 。10103 算法和算法分析算法算法(Algorithm)(Algorithm)：是对特定问题求解步骤的一种：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一描述，是指令的有限序列，其中每一条指令表示一个或多个操作。个或多个操作。算法具有以下五个特性：算法具有以下五个特性：（1 1）有穷性有穷性 一个算法必须总是在执行有穷
13、步之一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。后结束，且每一步都在有穷时间内完成。（2 2）确定性确定性 算法中每一条指令必须有确切的含算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出义。不存在二义性。且算法只有一个入口和一个出口。口。1111（3 3）可行性可行性 一个算法是可行的。即算法描一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执述的操作都是可以通过已经实现的基本运算执行有限次来实现的。行有限次来实现的。4 4）输入输入 一个算法有零个或多个输入，这些一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。输入取
14、自于某个特定的对象集合。5 5）输出输出 一个算法有一个或多个输出，这些一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。输出是同输入有着某些特定关系的量。1212算法设计的要求评价一个好的算法有以下几个标准评价一个好的算法有以下几个标准: :(1)(1)、正确性正确性(Correctness )(Correctness )算法应满足具体问算法应满足具体问题的需求。题的需求。(2)(2)、可读性可读性(Readability)(Readability)算法应该好读。以算法应该好读。以有利于阅读者对程序的理解。有利于阅读者对程序的理解。、健状性、健状性(Robustness)(Ro
15、bustness) 算法应具有容错处理。算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。不是产年莫名其妙的输出结果。(4)(4)、效率与存储量需求效率与存储量需求 效率指的是算法执效率指的是算法执行的时间；存储量需求指算法执行过程中所需行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规要的最大存储空间。一般，这两者与问题的规模有关。模有关。1313算法效率的度量 对一个算法要作出全面的分析，可分成两个对一个算法要作出全面的分析，可分成两个阶段进行，即阶段进行，即事先分析阶段事先分析阶段
16、和和事后测试阶段。事后测试阶段。事先分析：事先分析：求出该算法的一个时间界限函数求出该算法的一个时间界限函数事后测试：事后测试：收集此算法的执行时间和实际占用收集此算法的执行时间和实际占用空间的统计资料。空间的统计资料。定义：如果存在两个正常数定义：如果存在两个正常数c c和和n n0 0，对于所有的，对于所有的nnnn0 0，有，有f(n) f(n) ccg(n) g(n) 则记作则记作 f(n)=O(g(n) f(n)=O(g(n)1414 一般情况下，算法中基本操作重复执行的次一般情况下，算法中基本操作重复执行的次数是问题规模数是问题规模 n n 的某个函数，算法的时间量度记的某个函数，
17、算法的时间量度记作：作：T(n)=O(f(n)T(n)=O(f(n)，称作算法的，称作算法的渐近时间复杂度渐近时间复杂度。例、例、for(i = 1for(i = 1；i = n; +i)i = n; +i) for(j = 1; j = n; +j) for(j = 1; j = n; +j) cij = 0; cij = 0; for(k = 1; k = n; +k) for(k = 1; k = n; +k) cij+=aik*bkj; cij+=aik*bkj; 1515由于是一个三重循环，每个循环从由于是一个三重循环，每个循环从1 1到到n n，则总次数，则总次数为为: nnn =
18、 n: nnn = n3 3时间复杂度为时间复杂度为T(n)=O(nT(n)=O(n3 3) )。频度：是指该语句重复执行的次数：是指该语句重复执行的次数例例 +x;s=0; +x;s=0;将将x x自增看成是基本操作，则语句频度为，即时自增看成是基本操作，则语句频度为，即时间复杂度为间复杂度为(1)(1)。如果将如果将s=0s=0也看成是基本操作，则语句频度为，也看成是基本操作，则语句频度为，其时间复杂度仍为其时间复杂度仍为(2)(2)，即常量阶。，即常量阶。例、例、for(i = 1; i = n; +i)+x; s+=x;for(i = 1; i = n; +i)+x; s+=x; 语句
19、频度为：语句频度为：2n2n，其时间复杂度为：，其时间复杂度为：O(n)O(n)。即。即时间复杂度为线性阶。时间复杂度为线性阶。1616例、例、for(i = 1; i = n; +i)for(i = 1; i = n; +i)for(j = 1; j = n; +j)for(j = 1; j = n; +j) +x;s+=x; +x;s+=x;语句频度为：语句频度为：2n2n2 2，其时间复杂度为：，其时间复杂度为：O(nO(n2 2) )，即时间复杂度为平方阶。即时间复杂度为平方阶。1717以下六种计算算法时间的多项式是最常用的。其关系以下六种计算算法时间的多项式是最常用的。其关系为：为：
20、O(1)O(logn)O(n)O(nlogn)O(nO(1)O(logn)O(n)O(nlogn)O(n2 2) O(n) O(n3 3) )指数时间的关系为：指数时间的关系为：O(2O(2n n) O(n!) O(n) O(n!) O(nn n) ) 当当n n取得很大时，指数时间算法和多项式时间算法取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。那就取得了一个伟大的成就。1818算法的存
21、储空间需求算法的存储空间需求空间复杂度空间复杂度: :算法所需存储空间的度量，记作算法所需存储空间的度量，记作: : S(n)=O(f(n) S(n)=O(f(n) 其中其中n n为问题的规模为问题的规模( (或大小或大小) )程序所用的存储空间包括两个部分：程序所用的存储空间包括两个部分： 固定部分和可变部分。固定部分和可变部分。19191 1、固定部分：、固定部分：这部分空间的大小与输入输出的个数多少、数值这部分空间的大小与输入输出的个数多少、数值大小无关。主要包括存放程序指令代码的空间，大小无关。主要包括存放程序指令代码的空间，常数、简单变量、定长成分（如数组元素、结构常数、简单变量、定
22、长成分（如数组元素、结构成分、对象的数据成员等）变量所占的空间等。成分、对象的数据成员等）变量所占的空间等。这部分属于静态空间，只要作简单的统计就可估这部分属于静态空间，只要作简单的统计就可估算。算。2 2、可变部分：、可变部分：这部分空间主要包括其尺寸与实例特征有关的成这部分空间主要包括其尺寸与实例特征有关的成分变量所占空间、引用变量所占空间、以及递归分变量所占空间、引用变量所占空间、以及递归栈所用的空间，还有算法运行时动态命令使用的栈所用的空间，还有算法运行时动态命令使用的空间。空间。2020算法的设计要求算法的设计要求1 1、避免二义性文法产生；、避免二义性文法产生； 2 2、避免使用转移语句；、避免使用转移语句； 3 3、书写格式要规范；、书写格式要规范； 4 4、注意语言中字母的大小写是敏感问题。、注意语言中字母的大小写是敏感问题。 2121
