数据结构c语言版PPT-.ppt

目前，计算机已深入到社会生活的各个算机已深入到社会生活的各个领域，其域，其应用已不再用已不再仅仅局限于科学局限于科学计算，而更多的是用于控制，管理及数据算，而更多的是用于控制，管理及数据处理等非数理等非数值计算算领域。域。计算机是一算机是一门研究用研究用计算机算机进行信息表示和行信息表示和处理的科学。理的科学。这里面涉及到两个里面涉及到两个问题：信息的：信息的表示表示，信息的，信息的处理理。信息的表示和信息的表示和组织又直接关系到又直接关系到处理信息的程序的效率。随着理信息的程序的效率。随着应用用问题的不断复的不断复杂，导致信息量致信息量剧增与信息范增与信息范围的拓的拓宽，使，使许多系多系统程序和程序和应用程序的用程序的规模很大，模很大，结构又相当复构又相当复杂。因此，必。因此，必须分析待分析待处理理问题中的中的对象的特征及各象的特征及各对象之象之间存在的关系，存在的关系，这就是数据就是数据结构构这门课所要研究的所要研究的问题。无无忧忧PPTPPT整理整理发发布布编写解决写解决实际问题的程序的一般的程序的一般过程程：如何用数据形式描述如何用数据形式描述问题?即由即由问题抽象出一个适抽象出一个适当的数学模型当的数学模型;问题所涉及的数据量大小及数据之所涉及的数据量大小及数据之间的关系的关系;如何在如何在计算机中存算机中存储数据及体数据及体现数据之数据之间的关系的关系?处理理问题时需要需要对数据作何种运算数据作何种运算?所所编写的程序的性能是否良好写的程序的性能是否良好?上面所列上面所列举的的问题基本上由数据基本上由数据结构构这门课程来回答。程来回答。计算机求解算机求解问题的一般步的一般步骤无无忧忧PPTPPT整理整理发发布布1.1 数据数据结构及其概念构及其概念 算法与数据算法与数据结构构是是计算机科学中的一算机科学中的一门综合性合性专业基基础课。是介于数学、。是介于数学、计算机硬件、算机硬件、计算机算机软件三者之件三者之间的一的一门核心核心课程，不程，不仅是一般程序是一般程序设计的基的基础，而，而且是且是设计和和实现编译程序、操作系程序、操作系统、数据、数据库系系统及其他系及其他系统程序和大型程序和大型应用程序用程序的重要基的重要基础。无无忧忧PPTPPT整理整理发发布布1.1.11.1.1 数据数据数据数据结结构的例子构的例子构的例子构的例子姓名姓名电话号码电话号码陈海陈海13612345588李四锋李四锋13056112345。例例1：电话号号码查询系系统 设有一个有一个电话号号码薄，它薄，它记录了了N个人的名字和其相个人的名字和其相应的的电话号号码，假定按如下，假定按如下形式安排：形式安排：(a1,b1)，(a2,b2)，(an,bn)，其中其中ai,bi(i=1，2n)分分别表示某人的表示某人的名字和名字和电话号号码。本本问题是一种典型的表格是一种典型的表格问题。如表如表1-1，数据与数据成，数据与数据成简单的一的一对一的一的线性关系性关系。表表1-1 线性表性表结构构无无忧忧PPTPPT整理整理发发布布例例2 2：磁：磁盘目目录文件系文件系统 磁磁盘根目根目录下有很多子目下有很多子目录及及文件，每个子目文件，每个子目录里又可以包含里又可以包含多个子目多个子目录及文件，但每个子目及文件，但每个子目录只有一个父目只有一个父目录，依此，依此类推推：本本问题是一种典型的是一种典型的树型型结构构问题，如，如图1-11-1 ，数据与数据，数据与数据成一成一对多的关系，是一种典型的多的关系，是一种典型的非非线性关系性关系结构构 树形形结构构。图图1-11-1 树形形结结构构构构无无忧忧PPTPPT整理整理发发布布例例3 3：交通网：交通网络图 从一个地方到另外一个地方可以有多条路径。本从一个地方到另外一个地方可以有多条路径。本问题是一种典型的是一种典型的网状网状结构构问题，数据与数据成多，数据与数据成多对多的多的关系，是一种非关系，是一种非线性关系性关系结构。构。佛山惠州广州中山东莞深圳珠海图1-2 网状网状结构构无无忧忧PPTPPT整理整理发发布布 数据数据(DataData)：是客：是客观事物的符号表示。在事物的符号表示。在计算机科算机科学中指的是所有能学中指的是所有能输入到入到计算机中并被算机中并被计算机程序算机程序处理理的符号的的符号的总称。称。数据元素数据元素(Data ElementData Element)：是数据的基本：是数据的基本单位，在位，在程序中通常程序中通常作作为一个整体一个整体来来进行考行考虑和和处理。理。一个数据元素可由若干个一个数据元素可由若干个数据数据项(Data ItemData Item)组成。成。数据数据项是数据的不可分割的最小是数据的不可分割的最小单位。数据位。数据项是是对客客观事物某一方面特性的数据描述。事物某一方面特性的数据描述。数据数据对象象(Data ObjectData Object)：是性：是性质相同的数据元素的集相同的数据元素的集合，是数据的一个子集。如字符集合合，是数据的一个子集。如字符集合C=A,B,C,C=A,B,C,。1.1.2 基本概念和基本概念和术语无无忧忧PPTPPT整理整理发发布布 数据数据结构构(Data Structure)：是指相互之：是指相互之间具有具有(存在存在)一定一定联系系(关系关系)的数据元素的数据元素的集合。元素之的集合。元素之间的相互的相互联系系(关系关系)称称为逻辑结构构。数据元素之。数据元素之间的的逻辑结构有四种构有四种基本基本类型，如型，如图1-3所示。所示。集合集合：结构中的数据元素除了构中的数据元素除了“同属于一个集合同属于一个集合”外，没有其它关系。外，没有其它关系。线性性结构构：结构中的数据元素之构中的数据元素之间存在一存在一对一的关系。一的关系。树型型结构构：结构中的数据元素之构中的数据元素之间存在一存在一对多的关系。多的关系。图状状结构或网状构或网状结构构：结构中的数据元素之构中的数据元素之间存在多存在多对多的关系。多的关系。无无忧忧PPTPPT整理整理发发布布 数据数据结构的形式定构的形式定义是一个二元是一个二元组：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=k R=，k，k，k，k，k，k，k，k，k，k 画出画出这逻辑结构的构的图示，并确定那些是起点，那些是示，并确定那些是起点，那些是终点点1.1.3 数据数据结构的形式定构的形式定义图1-3 四四类基本基本结结构构构构图图无无忧忧PPTPPT整理整理发发布布1.1.4 数据数据结构的存构的存储方式方式 数据元素之数据元素之间的关系可以是元素之的关系可以是元素之间代表某种含代表某种含义的自然关系，也可以是的自然关系，也可以是为处理理问题方便而人方便而人为定定义的关系，的关系，这种种自然或人自然或人为定定义的的“关系关系”称称为数据元素之数据元素之间的的逻辑关系关系，相，相应的的结构构称称为逻辑结构构。数据数据结构在构在计算机内存中的存算机内存中的存储包括包括数据元素的存数据元素的存储和和元素之元素之间的关系的表示的关系的表示。元素之元素之间的关系在的关系在计算机中有两种不同的表示方法：算机中有两种不同的表示方法：顺序表示和非序表示和非顺序表示序表示。由此得出两种不同的存由此得出两种不同的存储结构：构：顺序存序存储结构构和和链式存式存储结构构。顺序存序存储结构构：用数据元素在存用数据元素在存储器中的相器中的相对位置位置来表示数据元素之来表示数据元素之间的的逻辑结构构(关系关系)。无无忧忧PPTPPT整理整理发发布布 链式存式存储结构构：在每一个数据元素中增加一个存放在每一个数据元素中增加一个存放另一个元素地址的指另一个元素地址的指针(pointer)(pointer)，用，用该指指针来表示来表示数据元素之数据元素之间的的逻辑结构构(关系关系)。例：例：设有数据集合有数据集合A=3.0,2.3,5.0,-8.5,11.0 A=3.0,2.3,5.0,-8.5,11.0，两种不同，两种不同的存的存储结构。构。顺序序结构：数据元素存放的构：数据元素存放的地址是地址是连续的的；链式式结构：数据元素存放的构：数据元素存放的地址是否地址是否连续没有要求没有要求。数据的数据的逻辑结构和物理构和物理结构是密不可分的两个方面，构是密不可分的两个方面，一个一个算法的算法的设计取决于取决于所所选定的定的逻辑结构构，而，而算法的算法的实现依依赖于于所采用的所采用的存存储结构构。在在C C语言中，用言中，用一一维数数组表示表示顺序存序存储结构构；用用结构体构体类型型表示表示链式存式存储结构。构。无无忧忧PPTPPT整理整理发发布布数据数据结构的三个构的三个组成部分：成部分：逻辑结构构：数据元素之数据元素之间逻辑关系的描述关系的描述 D_S=（D，S）存存储结构构：数据元素在数据元素在计算机中的存算机中的存储及其及其逻辑关系的表关系的表现称称为数据的存数据的存储结构或物理构或物理结构。构。数据操作数据操作：对数据要数据要进行的运算。行的运算。本本课程中将要程中将要讨论的三种的三种逻辑结构及其采用的存构及其采用的存储结构如构如图1-4所示。所示。无无忧忧PPTPPT整理整理发发布布数据的数据的逻辑结构构非非线性性结构构集合图状结构有向图无向图树形结构一般树二叉树线性性结构构一般线性表线性表推广广义表数组串受限线性表栈和队列图1-5 数据数据逻辑结构构层次关系次关系图图1-4 逻辑结构与所采用的存构与所采用的存储结构构线性表性表树图顺序存序存储结构构链式存式存储结构构复合存复合存储结构构逻辑结构构物理物理结构构无无忧忧PPTPPT整理整理发发布布 数据数据类型型(Data TypeData Type)：指的是：指的是一个一个值的集合的集合和定和定义在在该值集上的一集上的一组操作操作的的总称。称。数据数据类型是和数据型是和数据结构密切相关的一个概念。构密切相关的一个概念。在在C C语言中数据言中数据类型有：基本型有：基本类型和构造型和构造类型。型。数据数据结构不同于数据构不同于数据类型，也不同于数据型，也不同于数据对象，它象，它不不仅要描述数据要描述数据类型的数据型的数据对象，而且要描述数据象，而且要描述数据对象象各元素之各元素之间的相互关系。的相互关系。1.1.5 数据数据类型型无无忧忧PPTPPT整理整理发发布布 数据数据结构的主要运算包括：构的主要运算包括：建立建立(Create)(Create)一个数据一个数据结构；构；消除消除(Destroy)(Destroy)一个数据一个数据结构；构；从一个数据从一个数据结构中构中删除除(Delete)(Delete)一个数据元素；一个数据元素；把一个数据元素插入把一个数据元素插入(Insert)(Insert)到一个数据到一个数据结构中；构中；对一个数据一个数据结构构进行行访问(Access)(Access)；对一个数据一个数据结构构(中的数据元素中的数据元素)进行修改行修改(Modify)(Modify)；对一个数据一个数据结构构进行排序行排序(Sort)(Sort)；对一个数据一个数据结构构进行行查找找(Search)(Search)。1.1.6 数据数据结构的运算构的运算无无忧忧PPTPPT整理整理发发布布 抽象数据抽象数据类型型(Abstract Data TypeAbstract Data Type ，简称称ADTADT)：是：是指一个数学模型以及定指一个数学模型以及定义在在该模型上的一模型上的一组操作。操作。ADTADT的定的定义仅是一是一组逻辑特性描述，特性描述，与其在与其在计算算机内的表示和机内的表示和实现无关。因此，不无关。因此，不论ADTADT的内部的内部结构如构如何何变化，只要其数学特性不化，只要其数学特性不变，都不影响其外部使用。，都不影响其外部使用。ADTADT的形式化定的形式化定义是三元是三元组：ADT=(DADT=(D，S S，P)P)其中：其中：D D是是数据数据对象象，S S是是D D上的上的关系集关系集，P P是是对D D的的基本基本操作集操作集。1.2 抽象数据抽象数据类型型无无忧忧PPTPPT整理整理发发布布ADTADT的一般定的一般定义形式是：形式是：ADT ADT 数据数据对象：象：数据关系：数据关系：基本操作：基本操作：ADT ADT 其中数据其中数据对象和数据关系的定象和数据关系的定义用用伪码描述。描述。基本操作的定基本操作的定义是：是：()初始条件：初始条件：操作操作结果：果：无无忧忧PPTPPT整理整理发发布布 初始条件：描述操作初始条件：描述操作执行之前数据行之前数据结构和参数构和参数应满足的条件足的条件;若不若不满足，足，则操操作失作失败，返回相，返回相应的出的出错信息。信息。操作操作结果：描述操作正常完成之后，数据果：描述操作正常完成之后，数据结构的构的变化状况和化状况和 应返回的返回的结果。果。无无忧忧PPTPPT整理整理发发布布1.3.11.3.1 算法算法算法算法(AlgorithmAlgorithm)：是：是对特定特定问题求解方法求解方法(步步骤)的一种描的一种描述，是指令的有限序列，其中每一条指令表示一个或多述，是指令的有限序列，其中每一条指令表示一个或多个操作。个操作。算法具有以下五个特性算法具有以下五个特性 有有穷性性：一个算法必一个算法必须总是在是在执行有行有穷步之后步之后结束，且每一步都在有束，且每一步都在有穷时间内完成。内完成。确定性确定性：算法中每一条指令必：算法中每一条指令必须有确切的含有确切的含义。不存在二不存在二义性。且算法只有一个入口和一个出口。性。且算法只有一个入口和一个出口。可行性可行性：一个算法是能行的。即算法描述的操作一个算法是能行的。即算法描述的操作都可以通都可以通过已已经实现的基本运算的基本运算执行有限次来行有限次来实现。1.3 算法分析初步算法分析初步无无忧忧PPTPPT整理整理发发布布 输入入：一个算法有零个或多个一个算法有零个或多个输入，入，这些些输入取入取自于某个特定的自于某个特定的对象集合。象集合。输出出：一个算法有一个或多个一个算法有一个或多个输出，出，这些些输出是出是同同输入有着某些特定关系的量。入有着某些特定关系的量。一个算法可以用多种方法描述，主要有：使用自然一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式言描述；使用形式语言描述；使用言描述；使用计算机程序算机程序设计语言描述。言描述。算法和程序是两个不同的概念算法和程序是两个不同的概念。一个。一个计算机程序是算机程序是对一个算法使用某种程序一个算法使用某种程序设计语言的具体言的具体实现。算法必。算法必须可可终止意味着不是所有的止意味着不是所有的计算机程序都是算法。算机程序都是算法。在本在本门课程的学程的学习、作、作业练习、上机、上机实践等践等环节，算法都用算法都用C C语言来描述。在上机言来描述。在上机实践践时，为了了检查算法算法是否正确，是否正确，应编写成完整的写成完整的C C语言程序。言程序。无无忧忧PPTPPT整理整理发发布布评价一个好的算法有以下几个价一个好的算法有以下几个标准准 正确性正确性(CorrectnessCorrectness )：算法算法应满足具体足具体问题的的需求。需求。可可读性性(ReadabilityReadability)：算法算法应容易供人容易供人阅读和交和交流。可流。可读性好的算法有助于性好的算法有助于对算法的理解和修改。算法的理解和修改。健壮性健壮性(RobustnessRobustness)：算法算法应具有容具有容错处理。当理。当输入非法或入非法或错误数据数据时，算法，算法应能适当地作出反能适当地作出反应或或进行行处理，而不会理，而不会产生莫名其妙的生莫名其妙的输出出结果。果。通用性通用性(GeneralityGenerality)：算法算法应具有一般性具有一般性 ，即算，即算法的法的处理理结果果对于一般的数据集合都成立。于一般的数据集合都成立。1.3.2 算法算法设计的要求的要求无无忧忧PPTPPT整理整理发发布布 算法算法执行行时间需通需通过依据依据该算法算法编制的程序在制的程序在计算算机上运行所消耗的机上运行所消耗的时间来度量。其方法通常有两种：来度量。其方法通常有两种：事后事后统计：计算机内部算机内部进行行执行行时间和和实际占用空占用空间的的统计。问题：必：必须先运行依据算法先运行依据算法编制的程序；依制的程序；依赖软硬硬件件环境，容易掩盖算法本身的境，容易掩盖算法本身的优劣；没有劣；没有实际价价值。事前分析事前分析：求出：求出该算法的一个算法的一个时间界限函数。界限函数。1.3.3 算法效率的度量算法效率的度量 效率与存效率与存储量需求量需求：效率指的是算法效率指的是算法执行的行的时间；存；存储量需求指算法量需求指算法执行行过程中所需要的最大存程中所需要的最大存储空空间。一般地，。一般地，这两者与两者与问题的的规模有关。模有关。无无忧忧PPTPPT整理整理发发布布与此相关的因素有：与此相关的因素有：依据算法依据算法选用何种策略；用何种策略；问题的的规模；模；程序程序设计的的语言；言；编译程序所程序所产生的机器代生的机器代码的的质量；量；机器机器执行指令的速度；行指令的速度；撇开撇开软硬件等有关部硬件等有关部门因素，可以因素，可以认为一个特定算一个特定算法法“运行工作量运行工作量”的大小，只依的大小，只依赖于于问题的的规模（通常用模（通常用n n表示），或者表示），或者说，它，它是是问题规模的函数模的函数。无无忧忧PPTPPT整理整理发发布布算法分析算法分析应用用举例例 算法中算法中基本操作重复基本操作重复执行的次数行的次数是是问题规模模n n的某的某个函数，其个函数，其时间量度量度记作作 T(n)=O(f(n)T(n)=O(f(n)，称作算法的，称作算法的渐近近时间复复杂度度(Asymptotic Time complexityAsymptotic Time complexity)，简称称时间复复杂度度。一般地，常用一般地，常用最深最深层循循环内内的的语句中的原操作的句中的原操作的执行行频度度(重复重复执行的次数行的次数)来表示。来表示。“O”O”的定的定义：若若f(n)f(n)是正整数是正整数n n的一个函数，的一个函数，则 O(f(n)O(f(n)表表示示 MM 0 0，使得当，使得当n n n n0 0时，|f(n)|f(n)|MM|f(n|f(n0 0)|)|。表示表示时间复复杂度度的的阶有：有：O(1)O(1)：常量：常量时间阶 O(n)O(n)：线性性时间阶 O(O(n)n)：对数数时间阶 O(nO(nn)n)：线性性对数数时间阶无无忧忧PPTPPT整理整理发发布布 O(nO(nk k)：k k2 2，k k次方次方时间阶例例 两个两个n 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;由于是一个三重循由于是一个三重循环，每个循，每个循环从从1 1到到n n，则总次数次数为：nnn=nnnn=n3 3时间复复杂度度为T(n)=O(nT(n)=O(n3 3)例例 +x;s=0;+x;s=0;将将x x自增看成是基本操作，自增看成是基本操作，则语句句频度度为，即，即时间复复杂度度为(1)(1)。无无忧忧PPTPPT整理整理发发布布如果将如果将s=0s=0也看成是基本操作，也看成是基本操作，则语句句频度度为，其，其时间复复杂度仍度仍为(1)(1)，即常量，即常量阶。例例 for(i=1;i=n;+i)for(i=1;i=n;+i)+x;s+=x;+x;s+=x;语句句频度度为：2n2n，其，其时间复复杂度度为：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;语句句频度度为：2n2n2 2，其，其时间复复杂度度为：O(nO(n2 2)，即，即为平平方方阶。无无忧忧PPTPPT整理整理发发布布定理定理：若若A(n)=a A(n)=a m m n n m m+a+a m-1m-1 n n m-1m-1+a+a1 1n+an+a0 0是一个是一个mm次多次多项式，式，则A(n)=O(nA(n)=O(n m m)例例 for(i=2;i=n;+i)for(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+1+2+3+n-2=(1+n-2)(n-2)/2+n-2=(1+n-2)(n-2)/2 =(n-1)(n-2)/2=n =(n-1)(n-2)/2=n2 2-3n+2-3n+2 时间复复杂度度为O(nO(n2 2)，即此算法的，即此算法的时间复复杂度度为平方平方阶。一个算法一个算法时间为O(1)O(1)的算法，它的基本运算的算法，它的基本运算执行的行的次数是固定的。因此，次数是固定的。因此，总的的时间由一个常数（即零次由一个常数（即零次多多项式）来限界。而一个式）来限界。而一个时间为O(nO(n2 2)的算法的算法则由一由一个二次多个二次多项式来限界。式来限界。无无忧忧PPTPPT整理整理发发布布 以下六种以下六种计算算法算算法时间的多的多项式是最常用的。其关式是最常用的。其关系系为：O(1)O(O(1)O(n)O(n)O(nn)O(n)O(nn)O(nn)O(n2 2)O(n)O(n3 3)指数指数时间的关系的关系为：O(2O(2n n)O(n!)O(n)O(n!)O(nn n)当当n n取得很大取得很大时，指数，指数时间算法和多算法和多项式式时间算法算法在所需在所需时间上非常上非常悬殊。因此，只要有人能将殊。因此，只要有人能将现有指数有指数时间算法中的任何一个算法化算法中的任何一个算法化简为多多项式式时间算法，那算法，那就取得了一个就取得了一个伟大的成就。大的成就。有的情况下，算法中基本操作重复有的情况下，算法中基本操作重复执行的次数行的次数还随随问题的的输入数据集不同而不同。入数据集不同而不同。无无忧忧PPTPPT整理整理发发布布例例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)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(n%i)!=0&i*1.0 sqrt(n)&i*1.0 sqrt(n)决定，决定，显然然i*1.0 sqrt(n)i*1.01&change;-i)for(i=n-1;change=TURE;i1&;change;-i)for(j=0;ji;+j)for(j=0;jaj+1)if(ajaj+1)aj aj+1;change=TURE;aj 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(nO(n2 2)无无忧忧PPTPPT整理整理发发布布1.3.4 算法的空算法的空间分析分析 空空间复复杂度度(Space complexitySpace complexity)：是指算法：是指算法编写成写成程序后，在程序后，在计算机中运行算机中运行时所需存所需存储空空间大小的度量。大小的度量。记作：作：S(n)=O(f(n)S(n)=O(f(n)其中：其中：n n为问题的的规模模(或大小或大小)该存存储空空间一般包括三个方面：一般包括三个方面：指令常数指令常数变量所占用的存量所占用的存储空空间;输入数据所占用的存入数据所占用的存储空空间;辅助助(存存储)空空间。一般地，算法的一般地，算法的空空间复复杂度度指的是指的是辅助空助空间。一一维数数组anan：空空间复复杂度度 O(n)O(n)二二维数数组anmanm：空空间复复杂度度 O(n*m)O(n*m)无无忧忧PPTPPT整理整理发发布布习习 题题 一一1 1 简要回答要回答术语：数据，数据元素，数据：数据，数据元素，数据结构，数据构，数据类型。型。2 2 数据的数据的逻辑结构？数据的物理构？数据的物理结构？构？逻辑结构与物理构与物理结构的区构的区别和和联系是什么？系是什么？3 3 数据数据结构的主要运算包括哪些？构的主要运算包括哪些？4 4 算法分析的目的是什么？算法分析的主要方面是什么算法分析的目的是什么？算法分析的主要方面是什么？5 5 分析以下程序段的分析以下程序段的时间复复杂度，度，请说明分析的理由或明分析的理由或原因。原因。无无忧忧PPTPPT整理整理发发布布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称称为线性表的性表的最后一个最后一个(尾尾)结点。点。2.1.1 线线性表的定性表的定义义无无忧忧PPTPPT整理整理发发布布a1，a2，ai-1都是都是ai(2 i n)的的前前驱，其中，其中ai-1是是ai的的直接前直接前驱;ai+1，ai+2，an都是都是ai(1 i n-1)的的后后继，其中，其中ai+1是是ai的的直接后直接后继。2.1.22.1.2 线线线线性表的性表的性表的性表的逻辑结逻辑结逻辑结逻辑结构构构构 线性表中的数据元素性表中的数据元素ai所代表的具体含所代表的具体含义随具体随具体应用的不同而不同，在用的不同而不同，在线性表的性表的定定义中，只不中，只不过是一个抽象的表示符号。是一个抽象的表示符号。线性表中的性表中的结点点可以是可以是单值元素元素(每个元素只有一个数据每个元素只有一个数据项)。例例1:26个英文字母个英文字母组成的字母表：成的字母表：(A，B，C、Z）无无忧忧PPTPPT整理整理发发布布例例2 2：某校从某校从19781978年到年到19831983年各种型号的年各种型号的计算机算机拥有量有量的的变化情况：化情况：(6(6，1717，2828，5050，9292，188188）例例3 3：一副扑克的点数一副扑克的点数 (2(2，3 3，4 4，J J，Q Q，K K，A)A)线性表中的性表中的结点点可以是可以是记录型型元素，每个元素含元素，每个元素含有多个数据有多个数据项 ，每个，每个项称称为结点的一个域点的一个域 。每个元。每个元素有一个可以唯一素有一个可以唯一标识每个每个结点的点的数据数据项组，称，称为关关键字字。例例4 4：某校某校20012001级同学的基本情况：同学的基本情况：(2001414101(2001414101，张里里户，男男，06/24/1983)06/24/1983)，(2001414102(2001414102，张化司化司，男男，08/12/1984)08/12/1984)，(2001414102(2001414102，李利辣李利辣，女女，08/12/1984)08/12/1984)若若线性表中的性表中的结点是点是按按值(或按关或按关键字字值)由小到由小到大大(或由大到小或由大到小)排列排列的，称的，称线性表是有序的。性表是有序的。无无忧忧PPTPPT整理整理发发布布2.1.32.1.3 线线线线性表的抽象数据性表的抽象数据性表的抽象数据性表的抽象数据类类类类型定型定型定型定义义义义ADT List数据数据对象：象：D=ai|ai ElemSet,i=1,2,n,n 0 数据关系：数据关系：R=|ai-1,ai D,i=2,3,n 基本操作：基本操作：InitList(&L)操作操作结果：构造一个空的果：构造一个空的线性表性表L；线性表是一种相当灵活的数据性表是一种相当灵活的数据结构，其构，其长度可根据需要增度可根据需要增长或或缩短。短。对线性表的数据元素可以性表的数据元素可以访问、插入和、插入和删除。除。无无忧忧PPTPPT整理整理发发布布ListLength(L)初始条件：初始条件：线性表性表L已存在；已存在；操作操作结果：若果：若L为空表，空表，则返回返回TRUE，否，否则返回返回FALSE；.GetElem(L,i,&e)初始条件：初始条件：线性表性表L已存在，已存在，1 i ListLength(L)；操作操作结果：用果：用e返回返回L中第中第i个数据元素的个数据元素的值；ListInsert(L,i,&e)初始条件：初始条件：线性表性表L已存在，已存在，1 i ListLength(L)；操作操作结果：在果：在线性表性表L中的第中的第i个位置插入元素个位置插入元素e；ADT List无无忧忧PPTPPT整理整理发发布布2.2 线线性表的性表的顺顺序存序存储储 顺序存序存储：把：把线性表的性表的结点点按按逻辑顺序序依次存放在一依次存放在一组地址地址连续的存的存储单元元里。里。用用这种方法存种方法存储的的线性表性表简称称顺序表。序表。顺序存序存储的的线性表的性表的特点特点：线性表的性表的逻辑顺序与物理序与物理顺序一致序一致;数据元素之数据元素之间的关系是以元素在的关系是以元素在计算机内算机内“物理位置相物理位置相邻”来体来体现。设有非空的有非空的线性表：性表：(a1，a2，an)。顺序存序存储如如图2-1所示。所示。2.2.1 线线性表的性表的顺顺序存序存储结储结构构无无忧忧PPTPPT整理整理发发布布 在具体的机器在具体的机器环境下境下：设线性表的每个元素需占用性表的每个元素需占用l l个存个存储单元，以所占的第一个元，以所占的第一个单元的存元的存储地址作地址作为数据数据元素的存元素的存储位置。位置。则线性表中第性表中第i+1i+1个数据元素的存个数据元素的存储位位置置LOC(aLOC(ai+1i+1)和第和第i i个数据元素的存个数据元素的存储位置位置LOC(aLOC(ai i)之之间满足下列关系：足下列关系：LOC(aLOC(ai+1i+1)=LOC(a)=LOC(ai i)+)+l l 线性表的第性表的第i i个数据元素个数据元素a ai i的存的存储位置位置为：LOC(aLOC(ai i)=LOC(a)=LOC(a1 1)+(i-1)*)+(i-1)*l l a1 a2 ai an Loc(a1)Loc(ai)+(i-1)*l 图图2-1 线线性表的性表的顺顺序存序存储储表示表示无无忧忧PPTPPT整理整理发发布布 在高在高级语言言(如如C C语言言)环境下境下：数：数组具有随机存取的具有随机存取的特性特性，因此，借助数，因此，借助数组来描述来描述顺序表。除了用数序表。除了用数组来存来存储线性表的元素之外，性表的元素之外，顺序表序表还应该有表示有表示线性表的性表的长度属性，所以用度属性，所以用结构构类型来定型来定义顺序表序表类型。型。#define OK 1#define OK 1#define ERROR -1#define ERROR -1#define MAX_SIZE 100#define MAX_SIZE 100typedef int Status;typedef int Status;typedef int ElemType;typedef int ElemType;typedef struct sqlisttypedef struct sqlist ElemType Elem_arrayMAX_SIZE;ElemType Elem_arrayMAX_SIZE;int length;int length;SqList;SqList;无无忧忧PPTPPT整理整理发发布布2.2.2 顺顺序表的基本操作序表的基本操作 顺序存序存储结构中，很容易构中，很容易实现线性表的一些操作：性表的一些操作：初始化、初始化、赋值、查找、修改、插入、找、修改、插入、删除、求除、求长度等度等。以下将以下将对几种主要的操作几种主要的操作进行行讨论。1 1 顺序序线性表初始化性表初始化 Status Init_SqList(SqList*L)Status Init_SqList(SqList*L)L-elem_array=(ElemType*)malloc(MAX_SIZE*sizeof L-elem_array=(ElemType*)malloc(MAX_SIZE*sizeof(ElemType);(ElemType);if(!L-elem_array)return ERROR;if(!L-elem_array)return ERROR;else L-length=0;return OK;else L-length=0;return OK;无无忧忧PPTPPT整理整理发发布布2 2 顺序序线性表的插入性表的插入 在在线性表性表 L=(aL=(a1 1，a a i-1i-1，a ai i，a ai+1i+1，a an n)中中的第的第i(1i(1 i i n)n)个位置上插入一个新个位置上插入一个新结点点e e，使其成，使其成为线性表性表：L=(aL=(a1 1，a a i-1i-1，e e，a ai i，