主讲人陈玉华.ppt

《主讲人陈玉华.ppt》由会员分享，可在线阅读，更多相关《主讲人陈玉华.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、主讲人陈玉华 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第1章 绪论oo1.1 数据结构概述数据结构概述oo1.2 基本概念基本概念oo1.3 算法描述及分析算法描述及分析1.1 什么是数据结构什么是数据结构众众所所周周知知，计计算算机机的的程程序序是是对对数数据据进进行行加加工工处处理理。在在大大多多数数情情况况下下，这这些些数数据据并并不不是是无无组组织织的的，数数据据之之间间往往往往具具有有重重要要的的结结构构关关系系，这这就就是是数数据据结结构构的的重

2、重要要内内容容。那那么么，什什么么是是数据结构呢？数据结构呢？oo例例例例 1-1 1-1 一个大学的学生成绩管理。一个大学的学生成绩管理。一个大学的学生成绩管理。一个大学的学生成绩管理。姓名姓名姓名姓名学号学号学号学号性别性别性别性别高数高数高数高数英语英语英语英语物理物理物理物理黄雨黄雨黄雨黄雨98019801女女女女989887877979刘昌刘昌刘昌刘昌98029802男男男男878788886868张云张云张云张云98039803男男男男787865656666马力马力马力马力98049804男男男男777787879090 在在在在这这这这种种种种数数数数据据据据结结结结构构构构中

3、中中中，计计计计算算算算机机机机处处处处理理理理的的的的数数数数据据据据之之之之间间间间存存存存在在在在的的的的是是是是一一一一种种种种 “一个对一个一个对一个一个对一个一个对一个”的简单的简单的简单的简单线性关系，称为线性数据结构。线性关系，称为线性数据结构。线性关系，称为线性数据结构。线性关系，称为线性数据结构。oo例例 1-2 一所大学的部门管理。一所大学的部门管理。计信学院计信学院计信学院计信学院物电学院物电学院物电学院物电学院数学学院数学学院数学学院数学学院计算机系计算机系计算机系计算机系 网络工程网络工程网络工程网络工程 教育技术教育技术教育技术教育技术 教师教师教师教师 学生学生

4、学生学生 教师教师教师教师1 1教师教师教师教师mm 在在在在这这这这种种种种数数数数据据据据结结结结构构构构中中中中，计计计计算算算算机机机机处处处处理理理理的的的的数数数数据据据据之之之之间间间间存存存存在在在在的的的的是是是是一一一一种种种种 “一个对多个一个对多个一个对多个一个对多个”的的的的关系，称为树形数据结构。关系，称为树形数据结构。关系，称为树形数据结构。关系，称为树形数据结构。例例例例 1-3 1-3 在在在在 n n 个个个个城城城城市市市市间间间间建建建建立立立立通通通通信信信信网网网网络络络络，要要要要求求求求在在在在其其其其中中中中任任任任意意意意两两两两个个个个城城

5、城城市市市市间间间间都都都都有有有有直直直直接接接接的的的的或或或或间间间间接接接接的的的的通通通通信信信信线线线线路路路路，在在在在已已已已知知知知某某某某些些些些城城城城市市市市之之之之间间间间直直直直接接接接通通通通信信信信线线线线路路路路预预预预算算算算造造造造价价价价的情况下，使网络的造价最低。的情况下，使网络的造价最低。的情况下，使网络的造价最低。的情况下，使网络的造价最低。A AB BC CD DE EF FG G2 22 21 13 31 12 23 34 44 41 1A AB BC CD DE EF FG G2 22 21 11 12 21 1城市间的通信线路城市间的通信线

6、路城市间的通信线路城市间的通信线路最小造价通信线路最小造价通信线路最小造价通信线路最小造价通信线路 在在在在这这这这种种种种数数数数据据据据结结结结构构构构中中中中，计计计计算算算算机机机机处处处处理理理理的的的的数数数数据据据据之之之之间间间间存存存存在在在在的的的的是是是是一一一一种种种种 “多对多多对多多对多多对多”的的的的关系，称为网状（图状）结构。关系，称为网状（图状）结构。关系，称为网状（图状）结构。关系，称为网状（图状）结构。简简单单地地说说，数数据据结结构构是是研研究究非非数数值值计计算算程程序序设设计计问问题题中中数数据据以以及及它它们们之之间间的的逻逻辑辑关关系系和和对对数

7、数据据操操作作的的一一门门课课程程。重重点点分分析析数数据据之之间间抽抽象象的的相相互互关关系系，而而不不涉涉及及数数据据的的具具体体内容。内容。1.2 基本概念 1.数据数据(data)数据是对客观事物的符号表示，在计算机科学数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程中是指所有能输入到计算机中并被计算机程序处理的符号的总称。序处理的符号的总称。例如，一个利用数值分析方法求解代数方程的程序，例如，一个利用数值分析方法求解代数方程的程序，其处理对象是整数和实数；一个编译程序或文字处其处理对象是整数和实数；一个编译程序或文字处理程序的处理对象是字符串。对计算机科

8、学而言，理程序的处理对象是字符串。对计算机科学而言，数据的含义极为广泛，如图形、图像、色彩、声音数据的含义极为广泛，如图形、图像、色彩、声音等都可以通过编码而归之于数据的范畴。等都可以通过编码而归之于数据的范畴。2.数据元素数据元素(data element)数据元素数据元素 是数据的基本单位，也称为结点，在是数据的基本单位，也称为结点，在计算机程序中通常作为一个整体进行考虑和计算机程序中通常作为一个整体进行考虑和处理。有时，一个数据元素可以由若干个数处理。有时，一个数据元素可以由若干个数据项据项(data item)组成。组成。例例如如，某某程程序序处处理理的的数数据据是是学学生生信信息息表

9、表，每每个个学学生生的的信信息息就就是是一一个个数数据据元元素素，其其中中的的姓姓名名、性性别别、年年龄龄等等是是这这个个数数据据元元素素中中的的数数据据项项。数据项是数据处理中的最小单位。数据项是数据处理中的最小单位。3.数据对象数据对象(data object)数数据据对对象象是是性性质质相相同同的的数数据据元元素素的的集集合合，是是数数据据的的一个子集。一个子集。例如：例如：整数数据对象是集合整数数据对象是集合 N=0，1，2，；字母字符的数据对象是集合字母字符的数据对象是集合 C=A，B，。4.数据的逻辑结构数据的逻辑结构(data logical structure)(data lo

10、gical structure)数据的逻辑结构反映的是数据元素之间的逻辑数据的逻辑结构反映的是数据元素之间的逻辑（数学）关系，并不依赖于计算机。（数学）关系，并不依赖于计算机。(1)集合集合：结构中的数据元素之间除了：结构中的数据元素之间除了“同属同属于一个集合于一个集合”外，别无其他的关系。外，别无其他的关系。(2)线性结构线性结构：结构中的数据元素之间存在着：结构中的数据元素之间存在着一个对一个的关系。一个对一个的关系。(3)树树型型结结构构：结结构构中中的的数数据据元元素素之之间间存存在在着着一个对多个的关系。一个对多个的关系。(4)图状结构或网状结构：图状结构或网状结构：结构中的数据元

11、素结构中的数据元素之间存在着多个对多个的关系。之间存在着多个对多个的关系。5201295 5128135.数据的存储结构数据的存储结构(data memory structure)(data memory structure)数据的存储结构数据的存储结构(或称物理结构或称物理结构)是数据在计是数据在计算机存储器中的表示，包括数据的存储方式算机存储器中的表示，包括数据的存储方式及数据之间的逻辑关系。数据的物理结构是及数据之间的逻辑关系。数据的物理结构是依赖于计算机的。依赖于计算机的。(1)顺序存储结构：顺序存储结构：逻辑上相邻的数据元素在存储器中也相邻。逻辑上相邻的数据元素在存储器中也相邻。(2

12、)链式存储结构：链式存储结构：逻辑上相邻的数据元素在存储器中不一逻辑上相邻的数据元素在存储器中不一定相邻，但存储每个元素时都附加了指针定相邻，但存储每个元素时都附加了指针（地址）字段，通过设置指针使不相邻存储（地址）字段，通过设置指针使不相邻存储的元素有了相邻的逻辑关系的元素有了相邻的逻辑关系 6.数据数据结构结构(data structure)数据结构数据结构是带有结构特性的数据元素集合，研是带有结构特性的数据元素集合，研究的是数据的逻辑结构和数据的存储结构以究的是数据的逻辑结构和数据的存储结构以及它们之间的相互关系，并对这种结构定义及它们之间的相互关系，并对这种结构定义相适应的运算，设计出

13、相应的算法，而且确相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原保经过这些运算后所得到的新结构仍然是原来的结构类型。来的结构类型。1.3 算法算法 描述及分析描述及分析算法算法(algorithm)(algorithm)是对特定问题求解步骤的一种是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指描述，它是指令的有限序列，其中每一条指令表示一个或者多个操作。算法设计依赖于令表示一个或者多个操作。算法设计依赖于数据的存储结构，因此对确定的问题，人们数据的存储结构，因此对确定的问题，人们寻求在适宜的存储结构上设计一种效率较高寻求在适宜的存储结构上设计一种效

14、率较高的算法。的算法。1.算法的重要特性算法的重要特性(1)有穷性：必须总是（对任何合法的输入）在执行有穷有穷性：必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都可以在有穷时间内完成。步之后结束，且每一步都可以在有穷时间内完成。(2)确定性：每一条指令必须有确定的含义，读者理解时确定性：每一条指令必须有确定的含义，读者理解时不会产生二义性，且在任何条件下，只有唯一的执行路不会产生二义性，且在任何条件下，只有唯一的执行路径，即对于相同的输入只能得出相同的输出。径，即对于相同的输入只能得出相同的输出。(3)可可行行性性：算算法法中中描描述述的的操操作作都都是是可可以以通通过过已已实实现

15、现的的基基本运算执行有限次来实现的本运算执行有限次来实现的。(4)有有输输入入：零零个个或或多多个个输输入入，输输入入取取自自于于特特定定对对象象的的集集合。合。(5)有有输输出出：一一个个或或多多个个输输出出，输输出出是是与与输输入入有有特特定定关关系系的量。的量。2.算法的设计要求算法的设计要求(1)正正确确性性(correctness)。算算法法应应满满足足具具体体问问题题需需求求，设设计计或或选选择择的的算法应能正确反映这种需求。算法应能正确反映这种需求。(2)可可读读性性(readability)。算算法法主主要要是是为为了了人人的的阅阅读读及及人人与与人人之之间间的的交交流流，其其

16、次次才才是是机机器器执执行行。可可读读性性好好有有助助于于人人对对算算法法的的理理解解，晦晦涩难懂的程序易于隐藏较多错误难以调试和修改。涩难懂的程序易于隐藏较多错误难以调试和修改。(3)健健壮壮性性(robustness)。当当输输入入数数据据非非法法时时，算算法法也也能能适适当当地地作作出出反应或处理，而不会产生莫名其妙的输出结果。反应或处理，而不会产生莫名其妙的输出结果。(4)高高效效率率与与低低存存储储(high efficiency and low memory)。效效率率指指的的是是算算法法执执行行时时间间。一一个个问问题题若若有有多多个个算算法法可可解解决决，则则执执行行时时间间短

17、短的的算算法法效效率率高高。存存储储量量需需求求指指的的是是算算法法执执行行过过程程中中所所需需的的最最大存储空间。大存储空间。3.算法性能评价算法性能评价(算法效率的度量算法效率的度量)评评价价一一个个程程序序优优劣劣的的重重要要依依据据是是看看这这个个程程序序的的执执行行需需要要占占用用多多少少机机器器资资源源。在在各各种种机机器器资资源源中中，最最重重要要的的是是时时间间资资源源和和空空间间资资源源。因因此此，在在进进行行程程序序分分析析时时，大大家家最最关关心心的的就就是是程程序序所所用用算算法法在在运运行行时时所所要要花花费费的的时时间间代代价价和和程程序序中中使使用用的的数数据据结

18、结构构所所占占有有的的空空间间代代价价。通通常常就就称称之之为为时间复杂度时间复杂度（时间代价）和（时间代价）和空间复杂度空间复杂度（空间代价）。（空间代价）。（1 1）算法的时间复杂度）算法的时间复杂度 一一个个算算法法由由控控制制结结构构（顺顺序序、分分支支和和循循环环）和和原原操操作作（固固有有数数据据类类型型的的操操作作）构构成成，则则算算法法时时间间取取决决于于两两者者的的综综合合效效果果。为为了了便便于于比比较较同同一一问问题题的的不不同同算算法法，通通常常的的做做法法是是，从从算算法法中中选选取取一一种种对对于于所所研研究究的的问问题题（或或算算法法类类型型）来来说说是是“基基本

19、本操操作作”的的原原操操作作，以该以该“基本操作基本操作”重复执行的次数作为算法运行时间的度量。重复执行的次数作为算法运行时间的度量。在在在在一一一一般般般般情情情情况况况况下下下下，算算算算法法法法中中中中 “基基基基本本本本操操操操作作作作”重重重重复复复复执执执执行行行行的的的的次次次次数数数数是是是是问问问问题题题题规规规规模模模模 n n 的某个函数的某个函数的某个函数的某个函数 f f(n n)，算法的时间度量记作：，算法的时间度量记作：，算法的时间度量记作：，算法的时间度量记作：T T(n n)=)=O O(f f(n n)此此此此式式式式表表表表示示示示随随随随着着着着时时时时

20、间间间间规规规规模模模模 n n 的的的的增增增增大大大大，算算算算法法法法执执执执行行行行时时时时间间间间的的的的增增增增长长长长率率率率和和和和 f f(n n)的增长率相同，所以的增长率相同，所以的增长率相同，所以的增长率相同，所以 T T(n n)称作算法的时间复杂度称作算法的时间复杂度称作算法的时间复杂度称作算法的时间复杂度(time complexity)(time complexity)。由由由由于于于于算算算算法法法法时时时时间间间间复复复复杂杂杂杂度度度度分分分分析析析析只只只只考考考考虑虑虑虑相相相相对对对对于于于于问问问问题题题题规规规规模模模模 n n 的的的的增增增增

21、长长长长率率率率，因因因因而而而而在在在在难难难难以以以以精精精精确确确确计计计计算算算算基基基基本本本本操操操操作作作作执执执执行行行行次次次次数数数数的的的的情情情情况况况况下下下下，只只只只要要要要求求求求出出出出它它它它关关关关于于于于 n n 的的的的增增增增长长长长率率率率即即即即可可可可。我我我我们们们们可可可可以以以以在在在在计计计计算算算算任任任任何何何何算算算算法法法法运运运运行行行行时时时时间间间间代代代代价价价价的的的的时时时时候候候候，忽忽忽忽略略略略所所所所有的常数和低次项，用大有的常数和低次项，用大有的常数和低次项，用大有的常数和低次项，用大 O O 表示法来表示

22、算法的时间复杂度。表示法来表示算法的时间复杂度。表示法来表示算法的时间复杂度。表示法来表示算法的时间复杂度。3.3.算法效率的度量算法效率的度量算法效率的度量算法效率的度量例如：在下列三个程序段中例如：在下列三个程序段中例如：在下列三个程序段中例如：在下列三个程序段中 +x;s=0;+x;s=0;for(i=1;i=n;+i)for(i=1;i=n;+i)+x;+x;s+=x;s+=x;for(j=1;j=n;+j)for(j=1;j=n;+j)for(k=1;k=n;+k)for(k=1;k=n;+k)+x;+x;s+=x;s+=x;含含基基本本操操作作“x 增增 1”的的语语句句的的重重复

23、复次次数数分分别别为为 1、n 和和 n2，则则这这三个程序段的时间复杂度分别为三个程序段的时间复杂度分别为 O(1)、O(n)和和 O(n2)。通常有如下的函数关系排序：通常有如下的函数关系排序：c log2 n n n log2n n2 n3 2n 其中，其中，c是与是与n无关的任意常数。上述函数排序与数无关的任意常数。上述函数排序与数学中对无穷大的分级完全一致，因为考虑的也是学中对无穷大的分级完全一致，因为考虑的也是n值变值变化过程中的趋势。化过程中的趋势。按数量级将常见的时间复杂度递增排序，依次为：按数量级将常见的时间复杂度递增排序，依次为：常数阶常数阶O(1)、对数阶、对数阶O(log2n)、线性阶、线性阶O(n)、线、线性对数阶性对数阶O(nlog2n)、平方阶、平方阶O(n2)、立方阶、立方阶O(n3)、指数阶、指数阶(2n)等。参见下图。等。参见下图。