数据结构严蔚敏.ppt

《数据结构严蔚敏.ppt》由会员分享，可在线阅读，更多相关《数据结构严蔚敏.ppt（814页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法与数据结构算法与数据结构教材教材：数据结构数据结构(C语言版语言版)。严蔚敏，吴伟民。严蔚敏，吴伟民 编编 著。清华大学出版社。著。清华大学出版社。参考文献参考文献：1 数据结构数据结构。张选平，雷咏梅。张选平，雷咏梅 编，编，严蔚敏严蔚敏 审。审。机械工业出版社。机械工业出版社。2 数据结构与算法分析数据结构与算法分析。Clifford A.Shaffer著，著，张张 铭，刘晓丹铭，刘晓丹 译。电子工业出版社。译。电子工业出版社。3 数据结构习题与解析数据结构习题与解析(C语实言版语实言版)。李春葆。李春葆。清华大学出版社。清华大学出版社。4 数据结构与算法数据结构与算法。夏克俭。夏克俭

2、 编著。国防工业出编著。国防工业出版社。版社。第1章 绪 论 目前，计算机已深入到社会生活的各个领域，其应目前，计算机已深入到社会生活的各个领域，其应用已不再仅仅局限于科学计算，而更多的是用于控制，用已不再仅仅局限于科学计算，而更多的是用于控制，管理及数据处理等非数值计算领域。计算机是一门研究管理及数据处理等非数值计算领域。计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的个问题：信息的表示表示，信息的，信息的处理处理。信息的表示和组织又直接关系到处理信息的程序的信息的表示和组织又直接关系到处理信息的程序的效率。随着应

3、用问题的不断复杂，导致信息量剧增与信效率。随着应用问题的不断复杂，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，必须分析待处理问题中的对象结构又相当复杂。因此，必须分析待处理问题中的对象的特征及各对象之间存在的关系，这就是数据结构这门的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。课所要研究的问题。编写解决实际问题的程序的一般过程编写解决实际问题的程序的一般过程：如何用数据形式描述问题如何用数据形式描述问题?即由问题抽象出一个即由问题抽象出一个适当的数学模型适当的数学模型;问题所涉及

4、的数据量大小及数据之间的关系问题所涉及的数据量大小及数据之间的关系;如何在计算机中存储数据及体现数据之间的关系如何在计算机中存储数据及体现数据之间的关系?处理问题时需要对数据作何种运算处理问题时需要对数据作何种运算?所编写的程序的性能是否良好所编写的程序的性能是否良好?上面所列举的问题基本上由数据结构这门课程来回答。上面所列举的问题基本上由数据结构这门课程来回答。计算机求解问题的一般步骤计算机求解问题的一般步骤1.1 数据结构及其概念数据结构及其概念 算法与数据结构算法与数据结构是计算机科学中的一门综合性专是计算机科学中的一门综合性专业基础课业基础课。是。是介于数学、计算机硬件、计算机软件三者

5、介于数学、计算机硬件、计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，而之间的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。他系统程序和大型应用程序的重要基础。1.1.1 数据结构的例子数据结构的例子姓名姓名电话号码电话号码陈海陈海13612345588李四锋李四锋13056112345。例例1：电话号码查询系统：电话号码查询系统 设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了N个人的名字和其个人的名字和其相应的电话号码，假定按如下形式安排：相应

6、的电话号码，假定按如下形式安排：(a1,b1)，(a2,b2)，(an,bn)，其中其中ai,bi(i=1，2n)分别表示某人的分别表示某人的名字和电话号码。名字和电话号码。本问题是一种典型的表格问题本问题是一种典型的表格问题。如表如表1-1，数据与数据成简单的一对一的，数据与数据成简单的一对一的线性关系线性关系。表表1-1 线性表结构线性表结构例例2：磁盘目录文件系统：磁盘目录文件系统 磁盘根目录下有很多子目录磁盘根目录下有很多子目录及文件，每个子目录里又可以包及文件，每个子目录里又可以包含多个子目录及文件，但每个子含多个子目录及文件，但每个子目录只有一个父目录，依此类推目录只有一个父目录，

7、依此类推：本问题是一种典型的树型结本问题是一种典型的树型结构问题，如图构问题，如图1-1 ，数据与数据，数据与数据成一对多的关系，是一种典型的成一对多的关系，是一种典型的非线性关系结构非线性关系结构树形结构树形结构。图图图图1-11-1 树形树形结构结构结构结构例例3：交通网络图：交通网络图 从一个地方到另外一个地方可以有多条路径从一个地方到另外一个地方可以有多条路径。本问本问题是一种典型的题是一种典型的网状结构网状结构问题，数据与数据成多对多的问题，数据与数据成多对多的关系，是一种非线性关系结构关系，是一种非线性关系结构。佛山惠州广州中山东莞深圳珠海图图1-2 网状结构网状结构 数据数据(D

8、ata)：是客观事物的符号表示。在计算机科：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。的符号的总称。数据元素数据元素(Data Element)：是数据的基本单位，在程：是数据的基本单位，在程序中通常序中通常作为一个整体作为一个整体来进行考虑和处理。来进行考虑和处理。一个数据元素可由若干个一个数据元素可由若干个数据项数据项(Data Item)组成。组成。数据项是数据的不可分割的最小单位。数据项是对客观数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。事物某一方面特性的

9、数据描述。数据对象数据对象(Data Object)：是性质相同的数据元素的集：是性质相同的数据元素的集合，是数据的一个子集。如字符集合合，是数据的一个子集。如字符集合C=A,B,C,。1.1.2 基本概念和术语基本概念和术语 数据结构数据结构(Data Structure)：是指相互之间具有：是指相互之间具有(存在存在)一定联系一定联系(关系关系)的数据元素的集合。元素之间的相互联的数据元素的集合。元素之间的相互联系系(关系关系)称为称为逻辑结构逻辑结构。数据元素之间的逻辑结构有四。数据元素之间的逻辑结构有四种基本类型，如图种基本类型，如图1-3所示。所示。集合集合：结构中的数据元素除了：结

10、构中的数据元素除了“同属于一个集合同属于一个集合”外，没有其它关系。外，没有其它关系。线性结构线性结构：结构中的数据元素之间存在一对一的：结构中的数据元素之间存在一对一的关系。关系。树型结构树型结构：结构中的数据元素之间存在一对多的：结构中的数据元素之间存在一对多的关系。关系。图状结构或网状结构图状结构或网状结构：结构中的数据元素之间存：结构中的数据元素之间存在多对多的关系。在多对多的关系。数据结构的形式定义是一个二元组：数据结构的形式定义是一个二元组：Data-Structure=(D，S)其中：其中：D是数据元素的有限集，是数据元素的有限集，S是是D上关系的有限集。上关系的有限集。例例2：

11、设数据逻辑结构：设数据逻辑结构B=（K，R）K=k1,k2,k9 R=，画出这逻辑结构的图示，并确定那些是起点，那些是终点画出这逻辑结构的图示，并确定那些是起点，那些是终点1.1.3 数据结构的形式定义数据结构的形式定义图图1-3 四类基本四类基本结构图结构图结构图结构图1.1.4 数据结构的存储方式数据结构的存储方式 数据元素之间的关系可以是元素之间代表某种含义数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关的自然关系，也可以是为处理问题方便而人为定义的关系，这种系，这种自然或人为定义的自然或人为定义的“关系关系”称为数据元素之称为数据元素之间的间

12、的逻辑关系逻辑关系，相应的，相应的结构结构称为称为逻辑结构逻辑结构。数据结构在计算机内存中的存储包括数据结构在计算机内存中的存储包括数据元素的数据元素的存储存储和和元素之间的关系的表示元素之间的关系的表示。元素之间的关系在计算机中有两种不同的表示方法：元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示顺序表示和非顺序表示。由此得出两种不同的存储结构：由此得出两种不同的存储结构：顺序存储结构顺序存储结构和和链式存储结构链式存储结构。顺序存储结构顺序存储结构：用数据元素在存储器中的相对位置用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构来表示数据元素之间的逻辑结构(关系关

13、系)。链式存储结构链式存储结构：在每一个数据元素中增加一个存放在每一个数据元素中增加一个存放另一个元素地址的指针另一个元素地址的指针(pointer)，用该指针来表示，用该指针来表示数据元素之间的逻辑结构数据元素之间的逻辑结构(关系关系)。例例：设有数据集合设有数据集合A=3.0,2.3,5.0,-8.5,11.0，两种不同，两种不同的存储结构。的存储结构。顺序结构：数据元素存放的顺序结构：数据元素存放的地址是连续的地址是连续的；链式结构：数据元素存放的链式结构：数据元素存放的地址是否连续没有要地址是否连续没有要求求。数据的逻辑结构和物理结构是密不可分的两个方面，数据的逻辑结构和物理结构是密不

14、可分的两个方面，一个一个算法的设计取决于算法的设计取决于所选定的所选定的逻辑结构逻辑结构，而，而算法的实算法的实现依赖于现依赖于所采用的所采用的存储结构存储结构。在在C语言中，用语言中，用一维数组一维数组表示顺序存储结构表示顺序存储结构；用用结结构体类型构体类型表示链式存储结构。表示链式存储结构。数据结构的三个组成部分：数据结构的三个组成部分：逻辑结构逻辑结构：数据元素之间逻辑关系的描述数据元素之间逻辑关系的描述 D_S=（D，S）存储结构存储结构：数据元素在计算机中的存储及其逻辑数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构关系的表现称为数据的存储结构或物理结构。数据

15、操作数据操作：对数据要进行的运算对数据要进行的运算。本课程中将要讨论的三种逻辑结构及其采用的存储本课程中将要讨论的三种逻辑结构及其采用的存储结构如图结构如图1-4所示。所示。数据的逻辑结构数据的逻辑结构非线性结构非线性结构集合图状结构有向图无向图树形结构一般树二叉树线性结构线性结构一般线性表线性表推广广义表数组串受限线性表栈和队列图1-5 数据逻辑结构层次关系图数据逻辑结构层次关系图图图1-4 逻辑结构与所采用的存储结构逻辑结构与所采用的存储结构线性表线性表树树图图顺序存储结构顺序存储结构链式存储结构链式存储结构复合存储结构复合存储结构逻辑结构逻辑结构物理结构物理结构 数据类型数据类型(Dat

16、a Type)：指的是：指的是一个值的集合一个值的集合和定义和定义在在该值集上的一组操作该值集上的一组操作的总称。的总称。数据类型是和数据结构密切相关的一个概念。数据类型是和数据结构密切相关的一个概念。在在C语言中数据类型有：基本类型和构造类型。语言中数据类型有：基本类型和构造类型。数据结构不同于数据类型，也不同于数据对象，它数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。各元素之间的相互关系。1.1.5 数据类型数据类型 数据结构的主要运算包括：数据结构的主要运算包括：建立建立(

17、Create)一个数据结构；一个数据结构；消除消除(Destroy)一个数据结构；一个数据结构；从一个数据结构中删除从一个数据结构中删除(Delete)一个数据元素；一个数据元素；把一个数据元素插入把一个数据元素插入(Insert)到一个数据结构中；到一个数据结构中；对一个数据结构进行访问对一个数据结构进行访问(Access)；对一个数据结构对一个数据结构(中的数据元素中的数据元素)进行修改进行修改(Modify)；对一个数据结构进行排序对一个数据结构进行排序(Sort)；对一个数据结构进行查找对一个数据结构进行查找(Search)。1.1.6 数据结构的运算数据结构的运算 抽象数据类型抽象数

18、据类型(Abstract Data Type，简称，简称ADT)：是：是指一个数学模型以及定义在该模型上的一组操作。指一个数学模型以及定义在该模型上的一组操作。ADT的定义仅是一组逻辑特性描述，的定义仅是一组逻辑特性描述，与其在计算与其在计算机内的表示和实现无关。因此，不论机内的表示和实现无关。因此，不论ADT的内部结构如的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。何变化，只要其数学特性不变，都不影响其外部使用。ADT的形式化定义是三元组：的形式化定义是三元组：ADT=(D，S，P)其中：其中：D是是数据对象数据对象，S是是D上的上的关系集关系集，P是对是对D的的基本基本操作集

19、操作集。1.2 抽象数据类型抽象数据类型ADT的一般定义形式是：的一般定义形式是：ADT 数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：ADT 其中数据对象和数据关系的定义用伪码描述。其中数据对象和数据关系的定义用伪码描述。基本操作的定义是：基本操作的定义是：()初始条件：初始条件：操作结果：操作结果：初始条件：描述操作执行之前数据结构和参数应初始条件：描述操作执行之前数据结构和参数应满足的条件满足的条件;若不满足，则操作失败，返回相应的出若不满足，则操作失败，返回相应的出错信息。错信息。操作结果：描述操作正常完成之后，数据结构的操作结果：描述操作正常完成之后，数据结构的变化状况

20、和变化状况和 应返回的结果。应返回的结果。1.3.1 算法算法算法算法(Algorithm)：是对特定问题求解方法：是对特定问题求解方法(步骤步骤)的一种的一种描述，是指令的有限序列，其中每一条指令表示一个或描述，是指令的有限序列，其中每一条指令表示一个或多个操作。多个操作。算法具有以下五个特性算法具有以下五个特性 有穷性有穷性：一个算法必须总是在执行有穷步之后结一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。束，且每一步都在有穷时间内完成。确定性确定性：算法中每一条指令必须有确切的含义。：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。不存在二

21、义性。且算法只有一个入口和一个出口。可行性可行性：一个算法是能行的。即算法描述的操作一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。都可以通过已经实现的基本运算执行有限次来实现。1.3 算法分析初步算法分析初步 输入输入：一个算法有零个或多个输入，这些输入取一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。自于某个特定的对象集合。输出输出：一个算法有一个或多个输出，这些输出是一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。同输入有着某些特定关系的量。一个算法可以用多种方法描述，主要有：使用自然一个算法可以用多种方法描述，主要有：使用自然

22、语言描述；使用形式语言描述；使用计算机程序设计语语言描述；使用形式语言描述；使用计算机程序设计语言描述。言描述。算法和程序是两个不同的概念算法和程序是两个不同的概念。一个计算机程序是。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。须可终止意味着不是所有的计算机程序都是算法。在本门课程的学习、作业练习、上机实践等环节，在本门课程的学习、作业练习、上机实践等环节，算法都用算法都用C语言来描述。在上机实践时，为了检查算法语言来描述。在上机实践时，为了检查算法是否正确，应编写成完整的是否正确，

23、应编写成完整的C语言程序。语言程序。评价一个好的算法有以下几个标准评价一个好的算法有以下几个标准 正确性正确性(Correctness)：算法应满足具体问题的算法应满足具体问题的需求。需求。可读性可读性(Readability)：算法应容易供人阅读和交算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。流。可读性好的算法有助于对算法的理解和修改。健壮性健壮性(Robustness)：算法应具有容错处理。当算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。或进行处理，而不会产生莫名

24、其妙的输出结果。通用性通用性(Generality)：算法应具有一般性算法应具有一般性，即算，即算法的处理结果对于一般的数据集合都成立。法的处理结果对于一般的数据集合都成立。1.3.2 算法设计的要求算法设计的要求 算法执行时间需通过依据该算法编制的程序在计算算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种：机上运行所消耗的时间来度量。其方法通常有两种：事后统计事后统计：计算机内部进行执行时间和实际占用空间的：计算机内部进行执行时间和实际占用空间的统计。统计。问题：必须先运行依据算法编制的程序；依赖软硬问题：必须先运行依据算法编制的程序；依赖软硬件环境，

25、容易掩盖算法本身的优劣；没有实际价值。件环境，容易掩盖算法本身的优劣；没有实际价值。事前分析事前分析：求出该算法的一个时间界限函数。：求出该算法的一个时间界限函数。1.3.3 算法效率的度量算法效率的度量 效率与存储量需求效率与存储量需求：效率指的是算法执行的时间；效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。间。一般地，这两者与问题的规模有关。与此相关的因素有：与此相关的因素有：依据算法选用何种策略；依据算法选用何种策略；问题的规模；问题的规模；程序设计的语言；程序设计的语言；编译程序所产

26、生的机器代码的质量；编译程序所产生的机器代码的质量；机器执行指令的速度；机器执行指令的速度；撇开软硬件等有关部门因素，可以认为一个特定算撇开软硬件等有关部门因素，可以认为一个特定算法法“运行工作量运行工作量”的大小，只依赖于问题的规模（通常的大小，只依赖于问题的规模（通常用用n表示），或者说，它表示），或者说，它是问题规模的函数是问题规模的函数。算法分析应用举例算法分析应用举例 算法中算法中基本操作重复执行的次数基本操作重复执行的次数是问题规模是问题规模n的某的某个函数，其时间量度记作个函数，其时间量度记作 T(n)=O(f(n)，称作算法的渐，称作算法的渐近时间复杂度近时间复杂度(Asymp

27、totic Time complexity)，简称，简称时间时间复杂度复杂度。一般地，常用一般地，常用最深层循环内最深层循环内的语句中的原操作的的语句中的原操作的执执行频度行频度(重复执行的次数重复执行的次数)来表示。来表示。“O”的定义：的定义：若若f(n)是正整数是正整数n的一个函数，则的一个函数，则 O(f(n)表示表示 M0，使得当，使得当n n0时，时，|f(n)|M|f(n0)|。表示表示时间复杂度时间复杂度的阶有：的阶有：O(1)：常量时间阶：常量时间阶 O(n)：线性时间阶：线性时间阶 O(n)：对数时间阶：对数时间阶 O(nn)：线性对数时间阶：线性对数时间阶 O(nk)：k

28、2，k次方时间阶次方时间阶例例 两个两个n阶方阵的乘法阶方阵的乘法 for(i=1，i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;由于是一个三重循环，每个循环从由于是一个三重循环，每个循环从1到到n，则总次数为：，则总次数为：nnn=n3时间复杂度为时间复杂度为T(n)=O(n3)例例 +x;s=0;将将x自增看成是基本操作，则语句频度为，即时自增看成是基本操作，则语句频度为，即时间复杂度为间复杂度为(1)。如果将如果将s=0也看成是基本操作，则语句频度为，其时也看成是基本操作，则语句频度为，其时间复杂度仍为间复杂度仍为(1)，

29、即常量阶。，即常量阶。例例 for(i=1;i=n;+i)+x;s+=x;语句频度为：语句频度为：2n，其时间复杂度为：，其时间复杂度为：O(n)，即为线性，即为线性阶。阶。例例 for(i=1;i=n;+i)for(j=1;j=n;+j)+x;s+=x;语句频度为：语句频度为：2n2，其时间复杂度为：，其时间复杂度为：O(n2)，即为平，即为平方阶。方阶。定理定理：若若A(n)=a m n m+a m-1 n m-1+a1n+a0是一个是一个m次多项式，则次多项式，则A(n)=O(n m)例例 for(i=2;i=n;+i)for(j=2;j=i-1;+j)+x;ai,j=x;语句频度为：语

30、句频度为：1+2+3+n-2=(1+n-2)(n-2)/2 =(n-1)(n-2)/2=n2-3n+2 时间复杂度为时间复杂度为O(n2)，即此算法的时间复杂度为平方，即此算法的时间复杂度为平方阶。阶。一个算法时间为一个算法时间为O(1)的算法，它的基本运算执行的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为零次多项式）来限界。而一个时间为O(n2)的算法则的算法则由一个二次多项式来限界。由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其关以下六种计算算法时间的多项式是最常用的。其关

31、系为：系为：O(1)O(n)O(n)O(nn)O(n2)O(n3)指数时间的关系为：指数时间的关系为：O(2n)O(n!)O(nn)当当n取得很大时，指数时间算法和多项式时间算法取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。就取得了一个伟大的成就。有的情况下，算法中基本操作重复执行的次数还有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。随问题的输入数据集不同而不同

32、。例例1：素数的判断算法。素数的判断算法。Void prime(int n)/*n是一个正整数是一个正整数 */int i=2;while(n%i)!=0&i*1.0sqrt(n)printf(“&d 是一个素数是一个素数n”,n);elseprintf(“&d 不是一个素数不是一个素数n”,n);嵌套的最深层语句是嵌套的最深层语句是i+；其频度由条件；其频度由条件(n%i)!=0&i*1.0 sqrt(n)决定，显然决定，显然i*1.01&change;-i)for(j=0;jaj+1)aj aj+1;change=TURE;最好情况：最好情况：0次次 最坏情况：最坏情况：1+2+3+n-1

33、=n(n-1)/2 平均时间复杂度为：平均时间复杂度为：O(n2)1.3.4 算法的空间分析算法的空间分析 空间复杂度空间复杂度(Space complexity)：是指算法编写成：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。程序后，在计算机中运行时所需存储空间大小的度量。记作：记作：S(n)=O(f(n)其中：其中：n为问题的规模为问题的规模(或大小或大小)该存储空间一般包括三个方面：该存储空间一般包括三个方面：指令常数变量所占用的存储空间指令常数变量所占用的存储空间;输入数据所占用的存储空间输入数据所占用的存储空间;辅助辅助(存储存储)空间。空间。一般地，算法的一般地，算

34、法的空间复杂度空间复杂度指的是指的是辅助空间辅助空间。一维数组一维数组an：空间复杂度空间复杂度 O(n)二维数组二维数组anm：空间复杂度空间复杂度 O(n*m)习习 题题 一一1 简要回答术语：数据，数据元素，数据结构，数据简要回答术语：数据，数据元素，数据结构，数据类型。类型。2 数据的逻辑结构？数据的物理结构？逻辑结构与物数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？理结构的区别和联系是什么？3 数据结构的主要运算包括哪些？数据结构的主要运算包括哪些？4 算法分析的目的是什么？算法分析的主要方面是什算法分析的目的是什么？算法分析的主要方面是什么？么？5 分析以下

35、程序段的时间复杂度，请说明分析的理由分析以下程序段的时间复杂度，请说明分析的理由或原因。或原因。Sum1(int n)int p=1,sum=0,m;for(m=1;m=n;m+)p*=m;sum+=p;return(sum);Sum2(int n)int sum=0,m,t;for(m=1;m=n;m+)p=1;for(t=1;t=m;t+)p*=t;sum+=p;return(sum);递归函数递归函数fact(int n)if(n0时，将非空的线性表记作：时，将非空的线性表记作：(a1，a2，an)a1称为线性表的称为线性表的第一个第一个(首首)结点结点，an称为线性表的称为线性表的最后

36、最后一个一个(尾尾)结点。结点。2.1.1 线性表的定义线性表的定义a1，a2，ai-1都是都是ai(2in)的的前驱前驱，其中，其中ai-1是是ai的的直接直接前驱前驱;ai+1，ai+2，an都是都是ai(1i n-1)的的后继后继，其中其中ai+1是是ai的的直接后继直接后继。2.1.2 线性表的逻辑结构线性表的逻辑结构 线性表中的数据元素线性表中的数据元素ai所所代表的具体含义随具体应代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。象的表示符号。线性表中的线性表中的结点结点可以是可以是单值元素单值元素(

37、每个元素只有一每个元素只有一个数据项个数据项)。例例1:26个英文字母组成的字母表：个英文字母组成的字母表：(A，B，C、Z）例例2：某校从某校从1978年到年到1983年各种型号的计算机拥有量年各种型号的计算机拥有量的变化情况：的变化情况：(6，17，28，50，92，188）例例3：一副扑克的点数一副扑克的点数 (2，3，4，J，Q，K，A)线性表中的线性表中的结点结点可以是可以是记录型记录型元素，每个元素含元素，每个元素含有多个数据项有多个数据项，每个项称为结点的一个域，每个项称为结点的一个域。每个元。每个元素有一个可以唯一标识每个结点的素有一个可以唯一标识每个结点的数据项组数据项组，称

38、为，称为关键字关键字。例例4：某校某校2001级同学的基本情况：级同学的基本情况：(2001414101，张里户张里户，男男，06/24/1983)，(2001414102，张化司张化司，男男，08/12/1984)，(2001414102，李利辣李利辣，女女，08/12/1984)若线性表中的结点是若线性表中的结点是按值按值(或按关键字值或按关键字值)由小到由小到大大(或由大到小或由大到小)排列排列的，称线性表是有序的。的，称线性表是有序的。2.1.3 线性表的抽象数据类型定义线性表的抽象数据类型定义ADT List数据对象：数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据

39、关系：数据关系：R=|ai-1,aiD,i=2,3,n 基本操作：基本操作：InitList(&L)操作结果：构造一个空的线性表操作结果：构造一个空的线性表L；线性表是一种相当灵活的数据结构，其长度可根线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。据需要增长或缩短。对线性表的数据元素可以访问、插入和删除。对线性表的数据元素可以访问、插入和删除。ListLength(L)初始条件：线性表初始条件：线性表L已存在；已存在；操作结果：若操作结果：若L为空表，则返回为空表，则返回TRUE，否则返回否则返回FALSE；.GetElem(L,i,&e)初始条件：线性表初始条件：线性表L已存在

40、，已存在，1iListLength(L)；操作结果：用操作结果：用e返回返回L中第中第i个数据元素的值；个数据元素的值；ListInsert(L,i,&e)初始条件：线性表初始条件：线性表L已存在，已存在，1iListLength(L)；操作结果：在线性表操作结果：在线性表L中的第中的第i个位置插入元素个位置插入元素e；ADT List2.2 线性表的顺序存储线性表的顺序存储 顺序存储顺序存储：把线性表的结点把线性表的结点按逻辑顺序按逻辑顺序依次存放在依次存放在一组地址连续的存储单元一组地址连续的存储单元里。用这种方法存储的线性表里。用这种方法存储的线性表简称顺序表。简称顺序表。顺序存储顺序存

41、储的线性表的的线性表的特点特点：线性表的逻辑顺序与物理顺序一致线性表的逻辑顺序与物理顺序一致;数据元素之间的关系是以元素在计算机内数据元素之间的关系是以元素在计算机内“物理物理位置相邻位置相邻”来体现。来体现。设有非空的线性表：设有非空的线性表：(a1，a2，an)。顺序存储如图顺序存储如图2-1所示所示。2.2.1 线性表的顺序存储结构线性表的顺序存储结构 在具体的机器环境下在具体的机器环境下：设线性表的每个元素需占用：设线性表的每个元素需占用l个存储单元，以所占的第一个单元的存储地址作为数据个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第元素的存储位置。则线性表

42、中第i+1个数据元素的存储位个数据元素的存储位置置LOC(ai+1)和第和第i个数据元素的存储位置个数据元素的存储位置LOC(ai)之间满之间满足下列关系：足下列关系：LOC(ai+1)=LOC(ai)+l 线性表的第线性表的第i个数据元素个数据元素ai的存储位置为：的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l a1 a2 ai an Loc(a1)Loc(ai)+(i-1)*l 图图2-1 线性表的顺序存储表示线性表的顺序存储表示 在高级语言在高级语言(如如C C语言语言)环境下环境下：数组具有随机存取：数组具有随机存取的特性的特性，因此，借助数组来描述顺序表。除了用数组来，

43、因此，借助数组来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。长度属性，所以用结构类型来定义顺序表类型。#define OK 1#define ERROR -1#define MAX_SIZE 100typedef int Status;typedef int ElemType;typedef struct sqlist ElemType Elem_arrayMAX_SIZE;int length;SqList;2.2.2 顺序表的基本操作顺序表的基本操作 顺序存储结构中，很容易

44、实现线性表的一些操作：顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找初始化、赋值、查找、修改、插入、删除、求长度等修改、插入、删除、求长度等。以下将对几种主要的操作进行讨论以下将对几种主要的操作进行讨论。1 顺序线性表初始化顺序线性表初始化 Status Init_SqList(SqList*L)L-elem_array=(ElemType*)malloc(MAX_SIZE*sizeof(ElemType);if(!L-elem_array)return ERROR;else L-length=0;return OK;2 顺序顺序线性表的插入线性表的插入 在线性表在线性表 L=

45、(a1，a i-1，ai，ai+1，an)中中的的第第i(1in)个位置上插入一个新结点个位置上插入一个新结点e，使其成为线性使其成为线性表表：L=(a1，a i-1，e，ai，ai+1，an)实现步骤实现步骤(1)(1)将线性表将线性表L中的中的第第i个至第个至第n个个结点后移一个位置结点后移一个位置。(2)(2)将结点将结点e插入到结点插入到结点ai-1之后之后。(3)(3)线性表长度加线性表长度加1。算法描述算法描述Status Insert_SqList(Sqlist*L，int i，ElemType e)int j;if (iL-length-1)return ERROR;if (L

46、-length=MAX_SIZE)printf(“线性表溢出线性表溢出!n”);return ERROR;for (j=L-length1;j=i-1;-j)L-Elem_arrayj+1=L-Elem_arrayj;/*i-1位置以后的所有结点后移位置以后的所有结点后移 */L-Elem_arrayi-1=e;/*在在i-1位置插入结点位置插入结点 */L-length+;return OK;时间复杂度分析时间复杂度分析 在线性表在线性表L中的中的第第i个个元素之前插入新结点元素之前插入新结点，其时间其时间主要耗费在表中结点的移动操作上，因此主要耗费在表中结点的移动操作上，因此，可用结点的可

47、用结点的移动来估计算法的时间复杂度。移动来估计算法的时间复杂度。设设在线性表在线性表L中的中的第第i个个元素之前插入结点的概率元素之前插入结点的概率为为Pi，不失一般性不失一般性，设各个位置插入是等概率设各个位置插入是等概率，则，则Pi=1/(n+1)，而插入时移动结点的次数为而插入时移动结点的次数为n-i+1。总的平均移动次数：总的平均移动次数：Einsert=pi*(n-i+1)(1in)Einsert=n/2。即即在顺序表上做插入运算，平均要移动表上一半结在顺序表上做插入运算，平均要移动表上一半结点。当表长点。当表长n较大时，算法的效率相当低。因此算法的较大时，算法的效率相当低。因此算法

48、的平均时间复杂度为平均时间复杂度为O(n)。3 顺序线性表的删除顺序线性表的删除 在线性表在线性表 L=(a1，a i-1，ai，ai+1，an)中删除中删除结点结点ai(1in)，使其成为线性表使其成为线性表：L=(a1，ai-1，ai+1，an)实现步骤实现步骤(1)(1)将线性表将线性表L中的中的第第i+1个至第个至第n个结点依此向前移个结点依此向前移动一个位置。动一个位置。(2)(2)线性表长度减线性表长度减1。算法描述算法描述ElemType Delete_SqList(Sqlist*L，int i)int k;ElemType x;if (L-length=0)printf(“线性

49、表线性表L为空为空!n”);return ERROR;else if(iL-length)printf(“要删除的数据元素不存在要删除的数据元素不存在!n”);return ERROR;else x=L-Elem_arrayi-1;/*保存结点的值保存结点的值*/for(k=i;klength;k+)L-Elem_arrayk-1=L-Elem_arrayk;/*i位置以后的所有结点前移位置以后的所有结点前移 */L-length-;return(x);时间复杂度分析时间复杂度分析 删除线性表删除线性表L中的中的第第i个个元素，其时间主要耗费在表元素，其时间主要耗费在表中结点的移动操作上，因此

50、中结点的移动操作上，因此，可用结点的移动来估计算可用结点的移动来估计算法的时间复杂度。法的时间复杂度。设设在线性表在线性表L中中删除第删除第i个个元素的概率为元素的概率为Pi，不失不失一般性一般性，设删除各个位置是等概率设删除各个位置是等概率，则，则Pi=1/n，而删除而删除时移动结点的次数为时移动结点的次数为n-i。则总的平均移动次数：则总的平均移动次数：Edelete=pi*(n-i)(1in)Edelete=(n-1)/2。即即在顺序表上做删除运算，平均要移动表上一半结在顺序表上做删除运算，平均要移动表上一半结点。当表长点。当表长n较大时，算法的效率相当低。因此算法的较大时，算法的效率相