《数据结构概述》PPT课件.ppt

书山有路勤为径,学海无涯苦作舟,讲解人：杨文贤,数据结构,第一章概述,前期课程,数据结构,计算机基础C语言离散数学,后期课程,操作系统编译原理数据库原理软件工程,承上启下,计算机科学课程体系（偏软）,C/C+语言数据结构软件工程,掌握基本编程方法,掌握数据组织和数据处理的方法,掌握大型软件开发方法,学习识字,学习写作文,学习写小说,基本要求,课程关系,与语文学习过程类比,动手能力（上机）,1.1什么是数据结构？,随着计算机技术的发展，计算机应用的范围更广，所处理的数据更复杂。如果要提高数据处理的效率，就必须研究数据本身的特性、数据之间的关系，以及如何有效地将数据组织存储在计算机内。通过对数据结构的学习,你将掌握非数值计算程序设计中用的基本方法和技巧。,问题1：图书检索自动化数据：各类书籍，更确切地说是每本书的信息，如：书名，作者，分类号，出版单位，出版时间，作者简介，内容简介等等。操作：检索，排序，等等数据之间的关系：线性关系操作：书目入库，借书，还书等,1.1什么是数据结构？,1.1什么是数据结构？,书目文件,线性表,1.1什么是数据结构？,问题2：人机对弈数据：各种棋局状态，确切地说是描述棋盘格局的信息操作：走棋，即选择一种策略使棋局状态发生变化（由一个格局派生出另一个格局）数据的逻辑结构：表示棋局之间的演化关系：树型结构,树,问题：多叉路口交通灯的管理（即在多叉路口应设置几种颜色的交通灯，以保证交通流畅）,数据：路口各条路的信息操作：设置信号灯（求出各个可同时通行的路的集合）,1.1什么是数据结构？,共13条路：A-B,B-A,A-CB-C,A-D,B-D,D-A,E-AD-B,E-B,D-C,E-C,E-D,图,AB,AC,AD,BA,DC,ED,BC,BD,DA,DB,EA,EB,EC,可以用四种颜色着色，因此需要设置四种信号灯,数据结构课程的主要任务,研究和解决非数值数据的组织和处理描述非数值计算问题的数学模型，不再是数学方程例如：前述的三个例子：数据的线性结构，树型结构，图主要研究：数据元素之间固有的逻辑关系数据逻辑结构数据元素及关系在计算机内的表示数据存储结构对数据结构的操作算法,基本术语数据：被计算机加工处理的对象。数据元素：是数据的基本单位。在计算机程序中通常作为一个整体考虑和处理。数据项：是数据不可分割的最小单位。一个数据元素可由若干个数据项组成。,1.2基本概念和术语,1.2基本概念和术语,数据对象:是性质相同的数据元素的集合。,数据元素,整个表是学生成绩数据对象,数据项,数据结构:相互之间存在一种或多种特定关系的数据元素的集合它包括数据元素的逻辑结构、存储结构和相适应的运算。特点是：数据元素集合相同，而其上的关系不同，则构成的数据结构不同。,数据结构的形式定义：数据结构是一个二元组DS=(D,R)其中：D是数据元素的有限集，R是D上关系的有限集。关系的表示序偶：有序对。例如：前驱：序偶中第一元素为第二元素的前驱后继：序偶中第二元素为第一元素的后继例：设有数据结构B=(D,R)其中：D=d1,d2,d3,d4,d5,d6R=r，r=,，试画出其逻辑结构图。,(1)集合结构数据元素除了“属于同一集合”的联系之外，没有其它的关系。(2)线性结构数据元素之间存在一对一的关系。(3)树型结构数据元素之间存在一对多的关系。(4)图状结构或网状结构数据元素之间存在多对多的关系。,数据的逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。数据的逻辑结构可看作是从具体问题抽象出来的数学模型。,线性结构：各个数据成员依次排列在一个线性序列中。非线形结构：各个数据成员不再保持在一个线性序列中，每个数据成员可能与零个或多个其他数据成员发生关系。,数据的存储结构数据元素及其关系在计算机内的表示。数据元素的映象用二进制位(bit)的位串表示数据元素。每个数据元素的映象称为结点每个数据项的映象称为数据域逻辑结构可以映射为以下四种存储结构：顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：借助指针表达数据元素间的逻辑关系。不要求逻辑上相邻的数据元素在物理位置上也相邻。索引存储结构：在存储数据元素的同时，还建立附加的索引表。通过索引表，可以找到存储数据元素的节点。散列存储结构：根据散列函数和处理冲突的方法确定数据元素的存储位置。用高级程序语言编程时，直接用其提供的数据类型描述！,数据的操作在数据逻辑结构上定义的一组数据被使用的方式，其具体实现要在存储结构上进行。,这三个方面的关系：数据的逻辑结构独立于计算机，是数据本身所固有的。存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必须依赖于存贮结构。,数据结构的三个方面,数据结构的三个方面,1数据的逻辑结构,3数据的运算：检索、排序、插入、删除、修改等,2数据的存储结构(亦称物理结构),非线性结构,线性结构,线性表,栈,队列,串,树形结构,图形结构,集合结构,顺序存储,链式存储,1.3抽象数据类型,抽象数据类型ADT（AbstractDataType）：数据元素集合以及定义在该集合上的一组操作“抽象”指与具体实现无关，仅考虑能做什么，而不考虑如何做。形式描述：ADT=(D，R，P)标准定义格式？其中：D是数据对象，R是D上的关系集，P是D的基本操作集。作用：抽象数据类型可以使我们更容易描述实际问题。例：用线性表描述学生成绩表，用树或图描述遗传关系。好处：可提高软件的复用程度。使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。,数据类型：是一个值的集合和定义在这个值集上一组操作总称。分类：(按值的不同特性)原子类型：每一个对象仅由单值构成的类型；结构类型：每一个对象可由若干成分按某种结构构成的类型。,抽象数据类型重要特性数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。抽象数据类型的实现面向对象类面向过程结构体,例：复数数据类型的抽象描述分析：定义实部i虚部实部和虚部的取值范围实数复数的操作、ADT复数的数据类型抽象数据对象：D=e1,e2|实数数据关系：R1=|e1是复数的实部，e2是复数的虚部用两个实数来表示复数，将复数定义为两个实数的有序对，并约定实部是前驱，虚部是后继。,基本操作：InitComplex(Add(r1,r2,例：矩形数据类型抽象描述分析：定义长、宽长和宽的取值范围实数矩形的操作初始化(构造)矩形、计算矩形的周长和面积ADTRECtangleis数据对象：D=e1,e2|实数数据关系：R1=|e1是长，e2是宽基本操作:InitRectangle(r,len,width);操作结果：初始化矩形长和宽Circumference(r);操作结果：计算矩形周长Area(r);操作结果：计算矩形面积EndRECtangle,1.4算法分析,算法就是求解问题的一系列步骤的集合。通常把具体存储结构上的操作实现步骤或过程称为算法使用最适当的【数据结构】，才能够设计出最有效率的【算法】，进而转换成为有效率的【程序】。例：求n个整数中的最大值。1.将第1个数赋值给max；2.初始化计数器变量i为1；3.当imax，则将ai赋值max；(2)i自增1；4.返回max的值。,程序数据结构算法,算法的5个特性（性质）有穷性：对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。确定性：每条指令必须有确切的含义，不能有二义性。可行性：算法中描述的操作都是用已经实现的基本运算组成。输入：可以有0、1、或多个输入量。输出：它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。,算法和程序的关系两者相似而又有区别。程序不一定满足有穷性（死循环）；程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。,考虑下列两段描述：(1)描述一voidexam1()n2;while(n%20)nn+2;coutnendl;,华中科大考研题,(2)描述二voidexam2()y=0;x=5/y;coutx,yendl;这两段描述均不能满足算法的特征,试问它们违反了哪些特征？,解：(1)算法是一个死循环,违反了算法的有穷性特征。(2)算法包含除零错误,违反了算法的可行性特征。,算法的评价（设计准则）正确性除了应该满足算法说明中写明的“功能”之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。健壮性算法应对非法输入的数据作出恰当反映或进行相应处理，一般情况下，应向调用它的函数返回一个表示错误或错误性质的值。可读性易于理解、实现和调试。高效性执行时间短（时间效率）、占用存储空间少（空间效率）,时间复杂度一般用算法中基本语句被执行的次数来表示算法的时间效率（算法的时间复杂度）。,例：分析下面程序段的时间复杂度。(1)inti,sum=0;(2)for(i=0;in;i+)(3)sum=sum+i;(4)returnsum;T(n)=2n+3，且T(n)是n数量级的。渐进时间复杂度：忽略次要语句的执行次数，只对重要的语句（原操作）和执行最频繁的语句进行计数，同时对计算结果只取其最高次幂，且略去系数不写。渐近时间复杂度常简称为时间复杂度，用“大o”表示。T(n)=2n+3=O(n),（1次）,（n+1次）,（n次）,（1次）,也就是只求出T(n)的最高阶,忽略其低阶项和常系数,这样既可简化T(n)的计算,又能比较客观地反映出当n很大时,算法的时间性能。例如,T(n)=3n2-5n+10000=O(n2),本质上讲，是一种最高数量级的比较,一个没有循环的算法的基本运算次数与问题规模n无关,记作O(1),也称作常数阶。一个只有一重循环的算法的基本运算次数与问题规模n的增长呈线性增大关系,记作O(n),也称线性阶。其余常用的还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。各种不同数量级对应的值存在