《数据结构和算法》PPT课件.ppt

数据结构（Java语言版）,软件技术专业,第1讲数据结构和算法,主讲:段春梅Qq:365159341Tel:18927043195,目的：勾勒数据结构课程的轮廓。要求：掌握数据结构基本概念，理解抽象数据类型概念；熟悉算法设计和分析方法。重点：数据的逻辑结构和存储结构。难点：抽象数据类型，算法分析。,【知识要点】数据结构中的常用术语；线性结构、树形结构（层次结构）和图形结构的认识及结构特点；算法的定义、特性以及描述规则；时间复杂度、空间复杂度的定义以及评价规则。,？,计算机的用途？,早期：主要用于数值计算。,计算机的用途？,后来：处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。,数值计算,数值计算解决问题的一般步骤数学模型选择计算机语言编出程序测试最终解答,比如：y=x2全球天气预报环流模式方程预报人口增长情况微分方程,数值计算的关键是：如何得出数学模型(方程)？分析问题，从中提取操作的对象，根据操作对象间的关系，用数学语言表示。,非数值型数学模型,例1.求一组(n个)整数中的最大值？,例2.人机对弈,数据元素之间的相互关系一般无法用数学方程加以描述。,算法:基本操作是“比较两个数的大小”,算法:每下完一步棋，分析对手可能出现的所有可能性，并找到最佳对策,格局（棋盘状态）,例3田径赛的时间安排问题（无向图的着色问题）设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。,田径赛的时间安排问题解法,（1）设用如下六个不同的代号代表不同的项目：跳高跳远标枪铅球100米200米ABCDEF,(3）某选手比赛的项目必定有边相连（不能同时比赛）,(2)用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。,A,E,B,F,D,C,只需安排四个单位时间进行比赛,B,E,D,F,求解非数值计算的问题：主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？,因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。,什么是程序、软件？,程序算法数据结构程序设计:为计算机处理问题编制一组指令集算法:处理问题的策略数据结构:问题的数学模型,软件程序+文档（软件工程的观点）,为什么要学习数据结构,“数据结构十算法=程序”。软件设计是计算机学科各个领域的核心。软件设计时要考虑的首要问题是数据的表示、组织和处理方法。数据结构设计和算法设计是软件系统设计的核心。,第一节,1.数据结构三种基本结构引入及相关概念例1某大学拟建立校园网络，设计了如图1.1所示的网络拓扑结构图。,图1.1某学校校园网络结构示意图,现对该网络拓扑结构图进行分析，首先通过观察发现，该图中有若个交换机，并且要其性能参数、接口配置、相互之间联系等信息。下面通过对该校园网中交换机基本信息、交换机之间的层次关系、交换机之间的传输距离等问题着手，引入数据结构三种基本结构概念。,1.1线性结构1通过对交换机信息分析，引入线性结构该学校校园网的交换机信息列表如表1.1所示。通过该表可以看出，每个交换机的信息构成了一个整体，而这些交换机信息又构成了一个整体，而单纯从这些信息角度看，它构成一种顺序关系，称其为线性结构。,表1.1某学校校园网中需要交换机信息,【例1.2】图书管理系统。某学校图书信息包括图书编号、书名、数量和价格等方面信息，如表1.2所示，一行表示一条数据记录（简称记录），即表示某种图书的信息，一列代表一个属性，称其为字段，表示该记录中某一方面的属性。每种图书信息的位置有先后次序，他们之间形成一种线性关系，称这种数据结构为线性关系。,表1.2某学校图书信息系统,对上述具有线性结构的信息可以进行的主要操作有查找系统中某个信息、修改系统中某条记录信息、在固定的位置插入和删除相应的数据信息等,即查询、插入、删除、修改等相关操作。,1.2层次结构1通过校园网交换机之间的层次关系，引入层次结构按照交换机的之间的管理和被管理的关系，形成了一种层次结构（也称为树形结构）。每个交换机都称做该结构中的结点，结点之间形成了一对多的树形关系。和图1.2结构类似的还有计算机目录之间关系，公司部门结构关系等等。,图1.2某校园网交换机之间的层次关系示意图,【例1.3】计算机某磁盘（以C盘为例）目录结构如图1.3所示，该磁盘的根目录下有四个子目录（USER、WINDOWS、DOWNLOAD、WMPUB），每个子目录下面又设有两个子目录，他们之间形成了一种层次关系，这就形成一种树形结构（也称为层次结构），每个目录都称作该结构中的结点，结点之间形成了一对多的关系。,图1.3计算机某磁盘目录结构示意图对树形结构可以进行的操作主要有：结点查找、结点信息的修改、结点的插入和删除等。,1.3网状结构如图1.4所示为另一学校网络拓扑结构,图1.4某学校校园网交换机之间位置和距离示意图,由图可看出，各结点之间形成了一种网状结构（也称图形结构），该结构的特点是每个结点之间都可以建立联系，形成了一种多对多的网状关系。与该结构类似的还有交通图、地图、通讯网络图等。,【例1.4】哥尼斯堡七桥问题。在18世纪的东普鲁士的哥尼斯堡城市，有条横贯全城的普雷格尔河和两个岛屿，在河的两岸与岛屿之间架设了7座桥，把它们连接起来（如图1.5(a)所示）。将如图1.5(a)所示的问题抽象成一个数学问题，就是一个如图1.5(b)所示的无向图。,由图1.5(b)可以看出，A、B、C、D四个结点之间都可以产生联系，即多对多的关系，这就是数据结构中的网状结构（也称为图形结构）。在网状结构中可以进行的操作有：检索顶点、查找某顶点到其他顶点之间的路径，求最短距离，求关键路径等等。数据结构既可以描述数值型数据的特点，也可以描述非数值型数据的计算问题。数学模型包括线性表、树、图等数据结构。,数据结构：数据以及数据之间的关系,基本概念和术语,集合线性结构树形结构图状结构,数据的逻辑结构,线性结构：数据元素只有一个前驱数据元素和一个后继数据元素。树结构：每个数据元素只有一个前驱数据元素，可有零个或若干个后继数据元素。图结构：每个数据元素可有零个或若干个前驱数据元素，零个或若干个后继数据元素。,基本概念和术语,数据(Data):所有能被输入到计算机中，且能被计算机处理的符号的集合。它是数据机构最基本的概念。,序号书名作者书名,数据元素,数据元素,数据结构（DataStructure）是指具有某种联系的数据元素以及元素之间所构成的各种关系组成的集合。包括两个方面：一方面是具有某种联系的数据元素；另一方面是数据元素之间具有的各种关系。数据元素不是孤立存在的，正因为在他们之间总存在某种相互关系，才构成了数据元素之间的各种关系，将这些关系称为结构。数据的结构可分为数据的逻辑结构和数据的物理结构。,逻辑结构（LogicalStructure）是指构成数据结构的数据元素相互之间本身具有的逻辑关系。物理结构（或存储结构）是指构成数据结构的数据元素及其关系在计算机中的描述和表示。一种数据结构可对应一种或多种存储结构。,例如：顺序存储结构和链式存储结构,3数据结构的描述数据结构是由两个集合构成的一个二元组。其定义如下：=di|1in,n1/表示构成数据结构的数据元素的集合，其中di表示第i个数据元素，n为D中数据元素的个数。rj|1jm,m1/表示数据元素之间的各种关系，数据元素之间这种固有的关系简单地用前后件关系（或直接前驱与直接后继关系）来描述。rj表示数据元素之间的第j个关系，m为D上的关系个数。,例题1:在计算机中，复数(z=a+ib)可如下定义：复数是一种数据结构Complex=C,R其中，,C=C1,C2R=PP=其中由序偶，表示复数的实部，表示复数的虚部。,课堂思考题：1.假设我们需要编制一个事物管理程序，管理学校科学研究课题小组的各项事物，则首先需要为程序的操作对象-课题小组设计一个数据结构。假设每个小组由一位教师，1至3位研究生及1至6位本科生构成，小组成员之间的关系是：教师指导研究生，研究生指导1至2位本科生。如何定义该数据结构？,答案：,Group=(P,R)其中，P=T,G1,Gn,S11Snm|1n3,1n2R=R1,R2R1=|1in,1n3R2=|1in,1jm,1n3,1m2,复习,1.概念复习数据数据元素数据项（可以举例说明）数据结构2.题目：（1）数据结构被形式地定义为（D,R），其中D是的有限集合，R是D上的有限集合。（2）在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点，其余每个结点的后续结点数可以。,数据元素,关系,前驱,1,后续,任意多个,（3）将下图的逻辑结构图用数据结构的二元组表示。,数据类型,在用高级程序语言编写的程序中，程序中出现的每个变量、常量或表达式，必须事先明确说明它们所属的数据类型。因为类型决定了变量或表达式所有可能取值的范围，以及在这些之上允许进行的操作。,例如Java语言中的整型变量，其取值范围是某区间上的整数，以及，定义在其上的一组操作：加、减、乘、除和取模等算术运算,数据类型是一个值的集合和定义在此集合上的一组操作的总称。,OK,数据类型：原子类型（不可分解，如整形、字符型、布尔型、实型、枚举类型、指针类型）和结构类型（由若干成分按某种结构组成，可分解。例如数组的值由若干个分量构成，每个分量可以是整数，也是可以是数组）。,抽象数据类型,在数据结构中，专门提出抽象数据类型这个概念，用来描述数学模型及相关操作。抽象数据类型（AbstractDataType，简称ADT）是对特定数学模型的数学描述，包括操作的数据，数据之间的关系，以及在该关系上可以实现的操作，即数据类型一般由元素、关系及操作三要素组成。,它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现了信息隐藏。在Java中，可以用类的说明来表示ADT，用类的实现来实现ADT。ADT抽象数据类型名数据对象：（数据对象的定义）；数据关系：（数据关系的定义）；基本操作：（基本操作的定义）；;,数据的操作,初始化。判断是否空状态。求长度：统计元素个数。包含：判断是否包含指定元素。遍历：按某种次序访问所有元素，每个元素只被访问一次。取值：获取指定元素值。置值：设置指定元素值。插入：增加指定元素。删除：移去指定元素。,抽象数据类型可描述如下：,【例1.5】例1.2线性结构对应的抽象数据类型定义如下：ADTbook_list数据元素：每条图书记录xi为一数据元素，i=1，2，.，n(n1)；逻辑结构：所有数据元素xi存在线性关系(xi，xi+1)，x1无前趋，xn无后继；基本操作：Initbook_List(L);/建立空线性表Lengthbook_Llist(L);/求线性表长度GetElement(L,i);/取线性表中第i个元素Searchbook_List(L,x);/确定元素x在线性表L中的位置Insertbook_List(L,I,x);/在线性表中第i个位置插入数据元素xDeletebook_List(L,i);/删除线性表中第i个位置数据元素;,1.算法的概念算法（Algorithm）是指为完成某项任务或者特定问题所设计的一种求解步骤的描述。算法可以理解成指令的有限序列，其中每一条指令可由一个或多个操作组成。说明：算法的含义与程序十分相似，但又有区别。算法是解决问题的步骤分析，而程序是具体实现算法的有效工具。,算法,通过算法解决实际问题的过程如图1.6所示的流程图来描述。,算法的五个重要特性：,1有穷性对于任意合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成；,2确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径,3可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；,4有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；,5有输出它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。,设计算法应考虑达到的目标,1正确性对算法是否“正确”的理解可以有以下四个层次：a程序中不含语法错误；b程序对于几组输入数据能够得出满足要求的结果；c程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果；d程序对于一切合法的输入数据都能得出满足要求的结果通常以第c层意义的正确性作为衡量一个算法是否合格的标准。,2.可读性算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试,设计算法应考虑达到的目标,4高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。,3健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。,一个好的算法通常要达到以下的要求：首先，算法必须是正确的，即其执行结果应当满足预先规定的功能和性能要求；其次，一个可行的算法必须是可以被多个用户读懂的，应当思路清晰、层次分明、简单明了、易读易懂；再次，一个确定的算法每个步骤一定是确实可行的，不能产生二义性；最后，用户设计的算法一定是效率比较高的，对存储空间和时间效率的考虑一定要全面。,算法的评判标准,1.3.2算法表示算法是解决实际问题的有效方法，算法的表示也非常重要，可以使用各种不同的方法和语言进行描述。根据算法描述的不同，可分为如下内容：（1）自然语言自然语言是描述算法最简单的方法，其优点是简单且便于的阅读；缺点是转换成高级语言困难。（2）高级语言高级语言可以准确描述算法，也可以根据相应情况给出问题的解决方案，但是高级语言和人们自然的思维有一定的距离。（3）类语言类语言是介于高级程序设计语言和自然语言之间的一种语言，用其来描述算法可以避免上面两种语言的缺点。（4）流程图流程图是表示算法比较有效的方法之一，它采用框图形式，形象的描述从实际问题到抽象出的数学模型到最后的算法。,常见的流程图样式如图1.7所示：,实际上，许多高级语言都可以对算法进行描述。但是利用Java面向对象程序设计的封装、继承和多态等特性，能够更深入的描述数据结构，因为在数据结构中，数据的逻辑结构、存储结构和对数据的操作是一体的，是相互依存的。,【例1.6】线性结构中的顺序查找。,publicstaticbooleanseqSearch(charkey)/顺序查找方法inti;chardata;for(i=0;i=0)if(n=0|n=1)return1;elseSystem.out.println(n+!=+n+*+(n-1)+!);returnn*fact(n-1);return-1;/n0时n!无定义,时间复杂度,一个算法的时间复杂度（Timecomplexity）是指在计算机上运行该算法（或程序）所需要的时间。实际上，每个程序员都知道，算法执行的时间和很多因素都有关系，例如，机器的性能，算法语言的选取，编译程序的效率，算法的选择，以及问题本身的因素（如问题的复杂程度、问题本身的规模等）。,在针对实际问题时，尤其是考虑规模比较大的问题时，一般使用渐进式表示法来判别算法的时间复杂度。为了使程序员更好的掌握算法本身的特性，通常的做法是：在不考虑不确定情况的前提下，以算法中简单操作重复执行的次数作为算法的时间复杂度的衡量标准，即主要考虑问题的规模，而不考虑某些单个步骤之间的时间差异。因此，一个特定算法的运行时间长短更多地依赖于问题的规模n，或者说它是问题规模n的函数f(n),时间复杂度,随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n)称T(n)为算法的(渐近)时间复杂度如何估算算法的时间复杂度？即如何求f(n),从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则,for(i=0;in;+i)a=0;for(j=0;jn;+j)printf(“hello!”);,T(n)=O(n),算法时间复杂度分析,（2）intn=8,count=0;for(inti=1;i=n;i+)count+;,一个简单语句的时间复杂度为O(1)。,一个循环的时间复杂度为O(n)。,（1）intcount=0;,（3）intn=8,count=0;for(inti=1;i=n;i*=2)count+;,时间复杂度为O(log2n)的循环语句,(4)intn=8,count=0;for(inti=1;i=n;i+)for(intj=1;j=n;j+)count+;,时间复杂度为O(n2)的二重循环,(5)intn=8,count=0;for(inti=1;i=n;i*=2)for(intj=1;j=n;j+)count+;,循环次数为。时间复杂度为O(nlog2n),算法效率的衡量方法和准则,时间复杂度：,和算法执行时间相关的因素：1算法选用的策略2问题的规模3编写程序的语言4编译程序产生的机器代码的质量5计算机执行指令的速度,算法效率的衡量方法和准则,算法的空间复杂度S(n)=O(g(n)表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。算法的存储量包括:1输入数据所占空间;2程序本身所占空间；3辅助变量所占空间。空间复杂度指算法在执行时为解决问题所需要的额外内存空间，不包括输入数据所占用的存储空间。,课后作业：1.已排序数组的顺序查找（用java语言实现）。,本章结束!,