数据结构与算法 (1).pdf

《数据结构与算法 (1).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法 (1).pdf（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法Data Structrue And Algorithms1.1 1.1 什么是数据结构什么是数据结构1.2 1.2 基本概念和术语基本概念和术语1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现1.4 1.4 算法和算法分析算法和算法分析1.4.1 算法1.4.2 算法设计的要求1.4.3 算法效率的度量1.4.4 算法的存储空间的需求第1章绪论什么是数据结构？算法+数据结构=程序设计算法+数据结构=程序设计Pascal之父、结构化程序设计的先驱 Niklaus Wirth 最著名的一本书，书名：算法算法+数据结构数据结构=程序程序尼古拉斯 沃斯（Niklaus

2、Wirth）1934年2月15日瑞士计算机科学家计算机程序设计的艺术洋洋数百万言的多卷本计算机程序设计的艺术堪称计算机科学理论与技术的经典巨著，有评论认为其作用与地位可与数学史上欧几里得的几何学原理相比。本书作者唐纳德克努特(Donald Ervin Knuth)因而荣获1974年度的图灵奖。唐纳德 克努特（Donald Ervin Knuth）1938年1月10日美国计算机科学家The Art of Computer Programming计算机程序设计的艺术The Art of Computer Programming计算机程序设计艺术（包括三卷：基本算法、半数值算法及排序与查找）该书19

3、99年底被American Scientist列为20世纪最佳12部学术专著之一，与狄拉克的量子力学、爱因斯坦的相对论、曼德布罗特的分形论、罗素和怀特海德的数学基础、冯诺意曼和摩根斯坦的博弈论、维纳的控制论、费曼的量子电动力学等科学史上的经典著作并列。计算机程序设计的艺术The Art of Computer Programming目前，计算机已深入到社会生活的各个领目前，计算机已深入到社会生活的各个领域，其应用已不再仅仅局限于科学计算，域，其应用已不再仅仅局限于科学计算，而更而更多的是用于多的是用于生产过程生产过程控制控制，管理及数据处理等，管理及数据处理等非数值计算领域非数值计算领域。数据

4、结构与算法数据结构与算法是一门研究是一门研究用计算机进行信息表示和处理的科学用计算机进行信息表示和处理的科学。这里面。这里面涉及到两个问题：信息的涉及到两个问题：信息的表示表示，信息的，信息的处理处理。第1章绪论信息的表示和组织又直接关系到处理信息信息的表示和组织又直接关系到处理信息的程序的效率。的程序的效率。随着应用问题的随着应用问题的越来越越来越复杂复杂，导致导致信息量剧增与信息范围的拓宽信息量剧增与信息范围的拓宽，使使得得许多许多系统程序和应用程序的规模系统程序和应用程序的规模也越来越也越来越大大，结构结构也越来越也越来越复杂复杂。因此，。因此，必须分析待处理问题中必须分析待处理问题中的

5、对象的特征及对象的对象的特征及对象与对象与对象之间存在的关系之间存在的关系，而而这这正正是数据结构这门课所要研究的问题是数据结构这门课所要研究的问题。第1章绪论 如何用数据形式描述问题如何用数据形式描述问题？即由问题即由问题抽象出一个适当的数学模型抽象出一个适当的数学模型；问题所涉及的数据量大小及数据之间的问题所涉及的数据量大小及数据之间的关系关系；如何在计算机中存储数据及体现数据之如何在计算机中存储数据及体现数据之间的关系间的关系？处理问题时需要对数据作何种运算处理问题时需要对数据作何种运算？所编写的程序的性能是否良好所编写的程序的性能是否良好？上面所列举的问题基本上由数据结构这门上面所列举

6、的问题基本上由数据结构这门课程来回答。课程来回答。计算机求解问题的一般步骤1.11.1 数据结构及其概念数据结构与算法是计算机科学中的一门综合性专业基础课。是介于数学、计算机硬件、计算机软件三者之间的一门核心课程。它不仅是一般程序设计的基础，也是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。1.1.1 数据结构的例子姓名姓名电话号码电话号码陈海陈海1361234558813612345588李四锋李四锋1305611234513056112345。例例1：电话号码查询系统：电话号码查询系统设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了N个人的名字和其

7、个人的名字和其相应的电话号码，假定按如下形式安排：相应的电话号码，假定按如下形式安排：(a1,b1)，(a2,b2)，(an,bn)，其中其中ai,bi(i=1，2n)分别表示某人的分别表示某人的名字和电话号码。名字和电话号码。本问题是一种典型的表格问题本问题是一种典型的表格问题。如如表表1-1，数据与数据成简单的一对一的，数据与数据成简单的一对一的线性关系线性关系。表表1-1线性表结构线性表结构1.1.1 数据结构的例子表表1-2线性表结构线性表结构例例2：学生成绩表：学生成绩表（表表1-2）是一个数据结构是一个数据结构。表1-2 学生成绩表学号学号姓名姓名计算机导论计算机导论高等数学高等数

8、学普通物理普通物理平均成绩平均成绩04081101陈小洁8090858504081102马丽丽7568787404081103林春英8278667504081104王澄娟9085938904081150张吉祥70887578例3：磁盘目录文件系统磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推：本问题是一种典型的树型结构问题，如图1-1，数据与数据成一对多的关系，是一种典型的非线性关系结构树形结构。图图1-1树树形形结结构构例4：交通网络图从一个地方到另外一个地方可以有多条路径。本问题是一种典型的网状结构问题，数据与数据成多对多的关系

9、，是一种非线性关系结构。上海上海天津天津北京北京重庆重庆广州广州深圳深圳成都成都图图1-2网状结构网状结构三个基本的数据结构：小小结结线性结构（一对一：线性）层次结构（一对多：非线性）网状结构（多对多：非线性）数据(Data)：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(Data Element)：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。数据对象(Data Object)：是性质相同的

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

11、中的数据元素除了“同属于一个集合”外，没有其它关系。没有其它关系。线性结构线性结构：结构中的数据元素之间存在一对一的关系。：结构中的数据元素之间存在一对一的关系。树型结构树型结构：结构中的数据元素之间存在一对多的关系。：结构中的数据元素之间存在一对多的关系。集合结构集合结构图图1-3 四类基本结构图四类基本结构图线性结构线性结构树状结构树状结构网状结构网状结构例：设数据逻辑结构B=(K,R)K=k1,k2,k9R=，画出这逻辑结构的图示，并确定哪些是起点，哪些是终点。1.1.3 数据结构的形式定义数据结构的形式定义是一个二元组：Data-StrucTRUE=(D，S)其中：D是数据元素的有限集

12、，S是D上关系的有限集。数据元素之间的关系可以是元素之间代表数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的“关系”称为数据元素之间的逻辑关系逻辑关系，相应，相应的的结构结构称为称为逻辑结构逻辑结构。1.1.4 数据结构的存储方式数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和链式存储结构。链

13、式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointe)，用该指针来表示数据元素之间的逻辑结构(关系)。顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。例：设有数据集合A=3.0,2.3,5.0,-8.5,11.0，两种不同的存储结构。顺序结构：数据元素存放的地址是连续的；链式结构：数据元素存放的地址是否连续没有要求。数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。数据结构的三个组成部分：数据结构的

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

15、列图1-5数据逻辑结构层次关系图数据逻辑结构层次关系图图图1-4逻辑结构与所采用的存储结构逻辑结构与所采用的存储结构线性表线性表树树图图顺序存储结构顺序存储结构链式存储结构链式存储结构复合存储结构复合存储结构逻辑结构逻辑结构物理结构物理结构数据类型(Data Type)：指的是一个值的集合和定义在该值集上的一组操作的总称。数据类型是和数据结构密切相关的一个概念。在C语言中数据类型有：基本类型和构造类型。数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。1.1.5 数据类型数据结构的主要运算包括：建立(Create)一个数据结构；消

16、除(Destroy)一个数据结构；从一个数据结构中删除(Delete)一个数据元素；把一个数据元素插入(Insert)到一个数据结构中；对一个数据结构进行访问(Access)；对一个数据结构(中的数据元素)进行修改(Modify)；对一个数据结构进行排序(Sort)；对一个数据结构进行查找(Search)。1.1.6 数据结构的运算抽象数据类型(Abstract Data Type，简称ADT)：是指一个数学模型以及定义在该模型上的一组操作。ADT的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。ADT的形式

17、化定义是三元组：ADT=(D,S,P)其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。1.2 抽象数据类型ADT的一般定义形式是：ADT 数据对象：数据关系：基本操作：ADT 其中数据对象和数据关系的定义用伪码描述。基本操作的定义是：()初始条件：操作结果：例如：线性表的抽象数据类型定义ADT List数据对象：数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系：数据关系：R=|ai-1,aiD,i=2,3,n 基本操作：基本操作：InitList(&L)ListEmpty(L)GetElem(L,i,&e)ListInsert(L,i,&e)ADT List1

18、.3.1 算法算法(Algorithm)：是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性 有穷性有穷性：一个算法必须总是在执行有穷步之后结束，且每一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。一步都在有穷时间内完成。确定性确定性：算法中每一条指令必须有确切的含义。不存在二算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。义性。且算法只有一个入口和一个出口。可行性可行性：一个算法是能行的。即算法描述的操作都可以通一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次

19、来实现。过已经实现的基本运算执行有限次来实现。1.3 算法分析初步 输入输入：一个算法有零个或多个输入，这些输入取自于某个一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。特定的对象集合。输出输出：一个算法有一个或多个输出，这些输出是同输入有一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。着某些特定关系的量。一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述。算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。在本门课程的学习、作业练习、

20、上机实践等环节，算法都用C语言（类C语言）来描述。在上机实践时，为了检查算法是否正确，应编写成完整的C语言程序。算法+数据结构=程序设计算法算法+数据结构数据结构=程序程序尼古拉斯 沃斯（Niklaus Wirth）1934年2月15日瑞士计算机科学家。Pascal之父、结构化程序设计的先驱Niklaus Wirth最著名的一本书，书名：对比：把数据结构喻为建筑工程中的建筑设计图，那么算法就是工程中的施工流程图。什么是算法？什么是数据结构？什么是程序？什么是算法？什么是数据结构？什么是程序？程序是计算机指令的某种组合，控制计算机的工作流程，完成一定的逻辑功能，以实现某种任务；算法是程序的逻辑抽

21、象，是解决某类客观问题的数学过程；数据结构逻辑结构：客观事物自身所具有的结构特点。物理结构：逻辑结构在计算机中的具体实现。评价一个好的算法有以下几个标准 正确性(Correctness)：算法应满足具体问题的需求。可读性(Readability)：算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。健壮性(Robustness)：算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。通用性(Generality)：算法应具有一般性，即算法的处理结果对于一般的数据集合都成立。1.3.2 算法设计的要求 效率与存储量需求：效率指的

22、是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种：事后统计：计算机内部进行执行时间和实际占用空间的统计。问题：必须先运行依据算法编制的程序；依赖软硬件环境，容易掩盖算法本身的优劣；没有实际价值。1.3.3 算法效率的度量事前分析：求出该算法的一个时间界限函数。与此相关的因素有：依据算法选用何种策略；问题的规模；程序设计的语言；编译程序所产生的机器代码的质量；机器执行指令的速度；撇开软硬件等有关因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模

23、（通常用n表示），或者说，它是问题规模的函数。算法分析应用举例算法中基本操作重复执行的次数是问题规模n的某个函数，其时间量度记作T(n)=O(f(n)，称作算法的渐近时间复杂度(Asymptotic 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)：k2，k次方时间阶例 两个n阶方

24、阵的乘法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)，即常量阶。基本操作（不关心具体操作内容）例 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

25、;语句频度为：2n2，其时间复杂度为：O(n2)，即为平方阶。例 for(i=2;i=n;+i)for(j=2;j=i-1;+j)+x;aij=x;语句频度为：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)的算法则由一个二次多项式来限界。定理：若是一个m次多项式，则()mA nO n 1110mmmmA na nana na以下六种计算算法时间的多项式是最常用的。其关系为：指数时间的关系为：当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。2!nnOO nO n 231()()()OOnO nO nnO nO n