1-数据结构-清华大学严蔚敏PPT-绪论重点优秀PPT.ppt

《1-数据结构-清华大学严蔚敏PPT-绪论重点优秀PPT.ppt》由会员分享，可在线阅读，更多相关《1-数据结构-清华大学严蔚敏PPT-绪论重点优秀PPT.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、。夏克俭 编著。国防编著。国防工业出版社。工业出版社。第1章 绪 论 目前，计算机已深化到社会生活的各个领域，其应用已不再仅仅局限于科学计算，而更多的是用于限制，管理及数据处理等非数值计算领域。计算机是一门探讨用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示，信息的处理。信息的表示和组织又干脆关系到处理信息的程序的效率。随着应用问题的不断困难，导致信息量剧增与信息范围的拓宽，使很多系统程序和应用程序的规模很大，结构又相当困难。因此，必需分析待处理问题中的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要探讨的问题。编写解决实际问题的程序的一般过程：编写解决实际问题的程

3、序的一般过程：如何用数据形式描述问题如何用数据形式描述问题?即由问题抽象出一即由问题抽象出一个适当的数学模型个适当的数学模型;问题所涉及的数据量大小及数据之间的关系问题所涉及的数据量大小及数据之间的关系;如何在计算机中存储数据及体现数据之间的关如何在计算机中存储数据及体现数据之间的关系系?处理问题时须要对数据作何种运算处理问题时须要对数据作何种运算?所编写的程序的性能是否良好所编写的程序的性能是否良好?上面所列举的问题基本上由数据结构这门课程来上面所列举的问题基本上由数据结构这门课程来回答。回答。计算机求解问题的一般步骤计算机求解问题的一般步骤1.1 数据结构及其概念数据结构及其概念 算法与数

4、据结构算法与数据结构是计算机科学中的一门综合性专是计算机科学中的一门综合性专业基础课。是介于数学、计算机硬件、计算机软件三者业基础课。是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，而之间的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。他系统程序和大型应用程序的重要基础。数据结构的例子数据结构的例子姓名姓名电话号码电话号码陈海陈海1361234558813612345588李四锋李四锋1305611234513056112345。例

5、例1：电话号码查询系统：电话号码查询系统 设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了N个人的名字个人的名字和其相应的电话号码，假定按如下形式支配：和其相应的电话号码，假定按如下形式支配：(a1,b1)，(a2,b2)，(an,bn)，其中，其中ai,bi(i=1，2n)分别表示某人的名字和电话号码。分别表示某人的名字和电话号码。本问本问题是一种典型的表格问题。如表题是一种典型的表格问题。如表1-1，数据与数，数据与数据成简洁的一对一的线性关系。据成简洁的一对一的线性关系。表表1-1 线性表结构线性表结构例例2 2：磁盘书目文件系统：磁盘书目文件系统 磁盘根书目下有很多子磁盘根书目

6、下有很多子书目及文件，每个子书目里书目及文件，每个子书目里又可以包含多个子书目及文又可以包含多个子书目及文件，但每个子书目只有一个件，但每个子书目只有一个父书目，依此类推：父书目，依此类推：本问题是一种典型的树本问题是一种典型的树型结构问题，如图型结构问题，如图1-1 1-1，数，数据与数据成一对多的关系，据与数据成一对多的关系，是一种典型的非线性关系结是一种典型的非线性关系结构构树形结构。树形结构。图图图图1-11-1 树形树形结构结构结构结构例例3 3：交通网络图：交通网络图 从一个地方到另外一个地方可以有多条路径。本问从一个地方到另外一个地方可以有多条路径。本问题是一种典型的题是一种典型

7、的网状结构网状结构问题，数据与数据成多对多的问题，数据与数据成多对多的关系，是一种非线性关系结构。关系，是一种非线性关系结构。佛山惠州广州中山东莞深圳珠海图图1-2 网状结构网状结构 数据(Data)：是客观事物的符号表示。在计算机科学中指的是全部能输入到计算机中并被计算机程序处理的符号的总称。数据元素(Data Element)：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不行分割的最小单位。数据项是对客观事物某一方面特性的数据描述。数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一

8、个子集。如字符集合C=A,B,C,。基本概念和术语基本概念和术语 数据结构数据结构(Data Structure)：是指相互之间具：是指相互之间具有有(存在存在)确定联系确定联系(关系关系)的数据元素的集合。元的数据元素的集合。元素之间的相互联系素之间的相互联系(关系关系)称为逻辑结构。数据元称为逻辑结构。数据元素之间的逻辑结构有四种基本类型，如图素之间的逻辑结构有四种基本类型，如图1-3所所示。示。集合：结构中的数据元素除了集合：结构中的数据元素除了“同属于一个集同属于一个集合合”外，没有其它关系。外，没有其它关系。线性结构：结构中的数据元素之间存在一对线性结构：结构中的数据元素之间存在一对

9、一的关系。一的关系。树型结构：结构中的数据元素之间存在一对树型结构：结构中的数据元素之间存在一对多的关系。多的关系。图状结构或网状结构：结构中的数据元素之图状结构或网状结构：结构中的数据元素之间存在多对多的关系。间存在多对多的关系。数据结构的形式定义是一个二元组：数据结构的形式定义是一个二元组：Data-Structure=(DData-Structure=(D，S)S)其中：其中：D D是数据元素的有限集，是数据元素的有限集，S S是是D D上关系的有限集。上关系的有限集。例例2 2：设数据逻辑结构：设数据逻辑结构B=B=（K K，R R）K=kK=k1 1,k,k2 2,k,k9 9 R=

10、k R=，k，k，k，k，k，k，k，k，k，k 画出这逻辑结构的图示，并确定那些是起点，那些是终点画出这逻辑结构的图示，并确定那些是起点，那些是终点 数据结构的形式定义数据结构的形式定义图图1-3 四类基本四类基本结构图结构图结构图结构图 数据结构的存储方式数据结构的存储方式 数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题便利而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。元素之间的关系在计算机中有两种不同的表示方法：依次表示和非依次表示。由此得

11、出两种不同的存储结构：依次存储结构和链式存储结构。依次存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。链式存储结构：在每一个数据元素中增加一个存放链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针另一个元素地址的指针(pointer)(pointer)，用该指针来表示，用该指针来表示数据元素之间的逻辑结构数据元素之间的逻辑结构(关系关系)。例：设有数据集合例：设有数据集合A=3.0,2.3,5.0,-8.5,11.0 A=3.0,2.3,5.0,-8.5,11.0，两，两种不同的存储结构。种不同的存储结构。依次结构：数据元素存放的地址是连续的；依次结

12、构：数据元素存放的地址是连续的；链式结构：数据元素存放的地址是否连续没有要链式结构：数据元素存放的地址是否连续没有要求。求。数据的逻辑结构和物理结构是密不行分的两个数据的逻辑结构和物理结构是密不行分的两个方面，一个算法的设计取决于所选定的逻辑结构，方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依靠于所接受的存储结构。而算法的实现依靠于所接受的存储结构。在在C C语言中，用一维数组表示依次存储结构；语言中，用一维数组表示依次存储结构；用结构体类型表示链式存储结构。用结构体类型表示链式存储结构。数据结构的三个组成部分：数据结构的三个组成部分：逻辑结构：逻辑结构：数据元素之间逻辑关系的描述

13、数据元素之间逻辑关系的描述 D_S=（D，S）存储结构：存储结构：数据元素在计算机中的存储及其逻辑数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。关系的表现称为数据的存储结构或物理结构。数据操作：数据操作：对数据要进行的运算。对数据要进行的运算。本课程中将要探讨的三种逻辑结构及其接受本课程中将要探讨的三种逻辑结构及其接受的存储结构如图的存储结构如图1-4所示。所示。数据的逻辑结构数据的逻辑结构非线性结构非线性结构集合图状结构有向图无向图树形结构一般树二叉树线性结构线性结构一般线性表线性表推广广义表数组串受限线性表栈和队列图1-5 数据逻辑结构层次关系图数据逻辑结构层次关

14、系图图图1-4 逻辑结构与所采用的存储结构逻辑结构与所采用的存储结构线性表线性表树树图图顺序存储结构顺序存储结构链式存储结构链式存储结构复合存储结构复合存储结构逻辑结构逻辑结构物理结构物理结构 数据类型数据类型(Data Type)(Data Type)：指的是一个值的集合和定：指的是一个值的集合和定义在该值集上的一组操作的总称。义在该值集上的一组操作的总称。数据类型是和数据结构亲密相关的一个概念。数据类型是和数据结构亲密相关的一个概念。在在C C语言中数据类型有：基本类型和构造类型。语言中数据类型有：基本类型和构造类型。数据结构不同于数据类型，也不同于数据对象，它数据结构不同于数据类型，也不

15、同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。各元素之间的相互关系。数据类型数据类型 数据结构的主要运算包括：数据结构的主要运算包括：建立建立(Create)(Create)一个数据结构；一个数据结构；消退消退(Destroy)(Destroy)一个数据结构；一个数据结构；从一个数据结构中删除从一个数据结构中删除(Delete)(Delete)一个数据元素；一个数据元素；把一个数据元素插入把一个数据元素插入(Insert)(Insert)到一个数据结构中；到一个数据结构中；对一个数据结构进行访问对一个数据结

16、构进行访问(Access)(Access)；对一个数据结构对一个数据结构(中的数据元素中的数据元素)进行修改进行修改(Modify)(Modify)；对一个数据结构进行排序对一个数据结构进行排序(Sort)(Sort)；对一个数据结构进行查找对一个数据结构进行查找(Search)(Search)。数据结构的运算数据结构的运算 抽象数据类型抽象数据类型(Abstract Data Type(Abstract Data Type，简称，简称ADT)ADT)：是指一个数学模型以及定义在该模型上：是指一个数学模型以及定义在该模型上的一组操作。的一组操作。ADT ADT的定义仅是一组逻辑特性描述，的定义

17、仅是一组逻辑特性描述，与其与其在计算机内的表示和实现无关。因此，不论在计算机内的表示和实现无关。因此，不论ADTADT的内部结构如何变更，只要其数学特性不变，都的内部结构如何变更，只要其数学特性不变，都不影响其外部运用。不影响其外部运用。ADT ADT的形式化定义是三元组：的形式化定义是三元组：ADT=(DADT=(D，S S，P)P)其中：其中：D D是数据对象，是数据对象，S S是是D D上的关系集，上的关系集，P P是对是对D D的基本操作集。的基本操作集。1.2 抽象数据类型抽象数据类型ADTADT的一般定义形式是：的一般定义形式是：ADT ADT 数据对象：数据对象：数据关系：数据关

18、系：基本操作：基本操作：ADT ADT 其中数据对象和数据关系的定义用伪码描述。其中数据对象和数据关系的定义用伪码描述。基本操作的定义是：基本操作的定义是：()初始条件：初始条件：操作结果：操作结果：初始条件：描述操作执行之前数据结构和参数应初始条件：描述操作执行之前数据结构和参数应满足的条件满足的条件;若不满足，则操作失败，返回相应的出若不满足，则操作失败，返回相应的出错信息。错信息。操作结果：描述操作正常完成之后，数据结构的操作结果：描述操作正常完成之后，数据结构的变更状况和变更状况和 应返回的结果。应返回的结果。1.3.1 1.3.1 算法算法算法算法(Algorithm)(Algori

19、thm)：是：是对对特定特定问题问题求求解方法解方法(步步骤骤)的一种描述，是指令的的一种描述，是指令的有限序列，其中每一条指令表示一有限序列，其中每一条指令表示一个或多个操作。个或多个操作。算法具有以下五个特性算法具有以下五个特性 有有穷穷性：性：一个算法必需一个算法必需总总是在是在执执行有行有穷穷步之后步之后结结束，且每一步都在束，且每一步都在有有穷时间穷时间内完成。内完成。确定性：算法中每一条指令必需确定性：算法中每一条指令必需有精确的含有精确的含义义。不存在二。不存在二义义性。且性。且算法只有一个入口和一个出口。算法只有一个入口和一个出口。可行性：可行性：一个算法是能行的。即一个算法是

20、能行的。即算法描述的操作都可以通算法描述的操作都可以通过过已已经实经实现现的基本运算的基本运算执执行有限次来行有限次来实现实现。1.3 算法分析初步算法分析初步 输入：输入：一个算法有零个或多个输入，这些输入一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。取自于某个特定的对象集合。输出：输出：一个算法有一个或多个输出，这些输出一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。是同输入有着某些特定关系的量。一个算法可以用多种方法描述，主要有：一个算法可以用多种方法描述，主要有：运用自然语言描述；运用形式语言描述；运用计算运用自然语言描述；运用形式语言描述；运用计算机程序

21、设计语言描述。机程序设计语言描述。算法和程序是两个不同的概念。一个计算机算法和程序是两个不同的概念。一个计算机程序是对一个算法运用某种程序设计语言的具体实程序是对一个算法运用某种程序设计语言的具体实现。算法必需可终止意味着不是全部的计算机程序现。算法必需可终止意味着不是全部的计算机程序都是算法。都是算法。在本门课程的学习、作业练习、上机实践在本门课程的学习、作业练习、上机实践等环节，算法都用等环节，算法都用C C语言来描述。在上机实践时，为语言来描述。在上机实践时，为了检查算法是否正确，应编写成完整的了检查算法是否正确，应编写成完整的C C语言程序。语言程序。评价一个好的算法有以下几个标准评价

22、一个好的算法有以下几个标准 正确性正确性(Correctness)(Correctness)：算法应满足具体问题的需算法应满足具体问题的需求。求。可读性可读性(Readability)(Readability)：算法应简洁供人阅读和沟通。算法应简洁供人阅读和沟通。可读性好的算法有助于对算法的理解和修改。可读性好的算法有助于对算法的理解和修改。健壮性健壮性(Robustness)(Robustness)：算法应具有容错处理。当输算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生稀里糊涂的输出结果。处理，而不会产

23、生稀里糊涂的输出结果。通用性通用性(Generality)(Generality)：算法应具有一般性算法应具有一般性 ，即算法，即算法的处理结果对于一般的数据集合都成立。的处理结果对于一般的数据集合都成立。算法设计的要求算法设计的要求 算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种：事后统计：计算机内部进行执行时间和实际占用空间的统计。问题：必需先运行依据算法编制的程序；依靠软硬件环境，简洁掩盖算法本身的优劣；没有实际价值。事前分析：求出该算法的一个时间界限函数。1.3.3 算法效率的度量算法效率的度量 效率与存储量需求：效率与存储量需求：效率指的是算

24、法执行的时效率指的是算法执行的时间；存储量需求指算法执行过程中所须要的最大存间；存储量需求指算法执行过程中所须要的最大存储空间。一般地，这两者与问题的规模有关。储空间。一般地，这两者与问题的规模有关。与此相关的因素有：与此相关的因素有：依据算法选用何种策略；依据算法选用何种策略；问题的规模；问题的规模；程序设计的语言；程序设计的语言；编译程序所产生的机器代码的质量；编译程序所产生的机器代码的质量；机器执行指令的速度；机器执行指令的速度；撇开软硬件等有关部门因素，可以认为一个特定算撇开软硬件等有关部门因素，可以认为一个特定算法法“运行工作量运行工作量”的大小，只依靠于问题的规模（通常的大小，只依

25、靠于问题的规模（通常用用n n表示），或者说，它是问题规模的函数。表示），或者说，它是问题规模的函数。算法分析应用举例算法分析应用举例 算法中基本操作重复执行的次数是问题规模算法中基本操作重复执行的次数是问题规模n n的某的某个函数，其时间量度记作个函数，其时间量度记作 T(n)=O(f(n)T(n)=O(f(n)，称作算法的，称作算法的渐近时间困难度渐近时间困难度(Asymptotic Time complexity)(Asymptotic Time complexity)，简，简称时间困难度。称时间困难度。一般地，常用最深层循环内的语句中的原操作的执一般地，常用最深层循环内的语句中的原操作

26、的执行频度行频度(重复执行的次数重复执行的次数)来表示。来表示。“O”“O”的定义：的定义：若若f(n)f(n)是正整数是正整数n n的一个函数，则的一个函数，则 O(f(n)O(f(n)表示表示 M0 M0，使得当，使得当n n0n n0时，时，|f(n)|M|f(n0)|f(n)|M|f(n0)|。表示时间困难度的阶有：表示时间困难度的阶有：O(1)O(1)：常量时间阶：常量时间阶 O(n)O(n)：线性时间阶：线性时间阶 O(O(n)n)：对数时间阶：对数时间阶 O(n O(nn)n)：线性对数时间阶：线性对数时间阶 O(nk)：k2，k次方时间阶例 两个n阶方阵的乘法 for(i=1，

27、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=0s=0也看成是基本操作，则语句频度为，其时也看成是基本操作，则语句频度为，其时间困难度仍为间困难度仍为(1)(1)，即常量阶。，即常量阶。例例 for(i=1;i=n;+i)for(i=1;i=n;+i)+x;s+=x;+x;s+=x;语句频度为：语句频度为：2n2n，其时间困难度为：，其时间困难

28、度为：O(n)O(n)，即为线性，即为线性阶。阶。例例 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;语句频度为：语句频度为：2n2 2n2，其时间困难度为：，其时间困难度为：O(n2)O(n2)，即为，即为平方阶。平方阶。定理：若定理：若A(n)=a m n m+a m-1 n m-1 A(n)=a m n m+a m-1 n m-1+a1n+a0+a1n+a0是一个是一个mm次多项式，则次多项式，则A(n)=O(n A(n)=O(n m)m)例例 for(i=2;i=n;+i)for(

29、i=2;i=n;+i)for(j=2;j=i-1;+j)for(j=2;j=i-1;+j)+x;ai,j=x;+x;ai,j=x;语句频度为：语句频度为：1+2+3+n-2=(1+n-2)(n-1+2+3+n-2=(1+n-2)(n-2)/22)/2 =(n-1)(n-2)/2 =(n-1)(n-2)/2=n2-3n+2=n2-3n+2 时间困难度为时间困难度为O(n2)O(n2)，即此算法的时间困难度，即此算法的时间困难度为平方阶。为平方阶。一个算法时间为一个算法时间为O(1)O(1)的算法，它的基本运算执的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数行的次数是固定的。因此

30、，总的时间由一个常数（即零次多项式）来限界。而一个时间为（即零次多项式）来限界。而一个时间为O(n2)O(n2)的算法则由一个二次多项式来限界。的算法则由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其关以下六种计算算法时间的多项式是最常用的。其关系为：系为：O(1)O(O(1)O(n)O(n)O(nn)O(n)O(nn)O(n2)O(n3)n)O(n2)O(n3)指数时间的关系为：指数时间的关系为：O(2n)O(n!)O(nn)O(2n)O(n!)O(nn)当当n n取得很大时，指数时间算法和多项式时间算法取得很大时，指数时间算法和多项式时间算法在所需时间上特殊悬殊。因此，只

31、要有人能将现有指数在所需时间上特殊悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个宏大的成就。就取得了一个宏大的成就。有的状况下，算法中基本操作重复执行的次数还随问有的状况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。题的输入数据集不同而不同。例例1 1：素数的推断算法。：素数的推断算法。Void prime(int n)Void prime(int n)/*n/*n是一个正整数是一个正整数 */*/int i=2;int i=2;while(n%i)!=0&i*1.0 sqrt(n)

32、i+;while(n%i)!=0&i*1.0sqrt(n)if(i*1.0sqrt(n)printf(“&d printf(“&d 是一个素数是一个素数n”,n);n”,n);elseelseprintf(“&d printf(“&d 不是一个素数不是一个素数n”,n);n”,n);嵌套的最深层语句是嵌套的最深层语句是i+i+；其频度由条件；其频度由条件(n%i)!=0&i*1.0 sqrt(n)(n%i)!=0&i*1.0 sqrt(n)确定，明显确定，明显i*1.0 i*1.01&change;-for(i=n-1;change=TURE;i1&change;-i)i)for(j=0;ji

33、;+j)for(j=0;jaj+1)if(ajaj+1)aj aj aj+1;change=TURE;aj+1;change=TURE;最好状况：最好状况：0 0次次 最坏状况：最坏状况：1+2+3+1+2+3+n-1=n(n-1)/2+n-1=n(n-1)/2 平均时间困难度为：平均时间困难度为：O(n2)O(n2)算法的空间分析算法的空间分析 空间困难度空间困难度(Space complexity)(Space complexity)：是指算法编写：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度成程序后，在计算机中运行时所需存储空间大小的度量。记作：量。记作：S(n)=O(f(

34、n)S(n)=O(f(n)其中：其中：n n为问题的规模为问题的规模(或大小或大小)该存储空间一般包括三个方面：该存储空间一般包括三个方面：指令常数变量所占用的存储空间指令常数变量所占用的存储空间;输入数据所占用的存储空间输入数据所占用的存储空间;帮助帮助(存储存储)空间。空间。一般地，算法的空间困难度指的是帮助空间。一般地，算法的空间困难度指的是帮助空间。一维数组一维数组anan：空间困难度空间困难度 O(n)O(n)二维数组二维数组anmanm：空间困难度空间困难度 O(n*m)O(n*m)习习 题题 一一1 1 简要回答术语：数据，数据元素，数据结构，数据简要回答术语：数据，数据元素，数

35、据结构，数据类型。类型。2 2 数据的逻辑结构？数据的物理结构？逻辑结构与物数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区分和联系是什么？理结构的区分和联系是什么？3 3 数据结构的主要运算包括哪些？数据结构的主要运算包括哪些？4 4 算法分析的目的是什么？算法分析的主要方面是什算法分析的目的是什么？算法分析的主要方面是什么？么？5 5 分析以下程序段的时间困难度，请说明分析的理由分析以下程序段的时间困难度，请说明分析的理由或缘由。或缘由。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(n=1)return(1);else return(n*fact(n-1);