数据结构(绪论)第章课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,2021/3/18,*,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,2021/3/18,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,2021/3/18,*,Click to edit Master title style,20XX年复习资料,大学复习资料,专 业：,班 级：,科目老师：,日 期：,数 据 结 构,第,1,章 绪论,2,2021/3/18,一、基本概念,利用计算机处理的问题类型,数值计算问题，主要用不同的,数学方程,来描述,例,1,利用有限元计算方法进行结构静力分析计算,例,2,利用环流模式方程进行天气预报计算,非数值计算问题，主要用不同的,数据结构,来描述,例,1,图书馆书目检索,例,2,计算机和人对奕问题,例,3,交通灯的控制系统,3,2021/3/18,基本概念,数据、数据对象等,数据（,data,）,是对客观事物的符号化表示，是信息、概念与知识的载体,数据项（,data item,）,是构成数据的相对独立的分项，它反映客观事物的某种特性,数据元素（,data element,）,是构成数据的,具有相同性质的基本单元,数据对象（,data object,）,是性质相同的数据元素的集合。,是数据的一个子集。是一种运行时的概念。,4,2021/3/18,基本概念,数据结构,数据结构（,data structure,）,是相互之间存在一种或多种特定关系的数据元素的集合,数据结构的二元组表示：,Data_Structure,=(,D,S,),其中：,D,是数据元素的有限集，,S,是,D,上关系的有限集,5,2021/3/18,基本概念,数据结构,例如一维数组是一种数据结构,Array=,数据元素的集合是,D,=,a,1,a,2,a,n,数据元素关系的集合是,S,=R,R=,|,1,i,n,其中,为序偶,6,2021/3/18,基本概念,数据结构,按照软件系统开发过程中的数据层次模型，数据之间存在两种结构关系,数据的,逻辑结构,（位于逻辑层），反映数据元素之间的逻辑关系，由抽象数据类型来表达,数据的,物理结构,（位于实现层），也称,存储结构,，考虑的是数据在计算机中是如何存储和组织的,7,2021/3/18,基本概念,数据结构,数据元素之间的逻辑关系通常可分为,4,类基本的逻辑结构,1.,集合,结构中的数据元素之中同属一个集合,2.,线性结构,结构中的元素之间存在一个对一个的关系,3.,树型结构,结构中的数据元素之间存在一个对多个的关系,4.,图状结构或网状结构,结构中的数据元素之间存在多个对多个的关系,8,2021/3/18,逻辑结构例,学生选课问题,该问题可以用三张数据表来表示，每张表中每条记录为数据元素,如表中数据元素是无序的，则数据表构成集合结构,如表中数据元素是有序的，则数据表构成线性结构,学生表,课程表,选课表,学号,姓名,课程号,课程名称,学号,课程号,成绩,S0001,张三,C0001,数据结构,S0001,C0001,85,S0002,李四,C0002,操作系统,S0001,C0003,76,S0005,王五,C0003,编译原理,S0002,C0001,90,C0004,数据库原理,S0002,C0004,83,S0003,C0002,92,9,2021/3/18,逻辑结构例,三维实体造型问题,左图的机械零件可以分解成三个基本的实体模型通过布尔运算,+,和,-,操作得到,右图构成了一个树型的数据结构，每一个节点为一个基本实体模型或通过布尔运算得到的复合实体模型,10,2021/3/18,逻辑结构例,地图表示问题,左图的地图经抽象可以得到右图的结构,右图构成了图状的数据结构,11,2021/3/18,数据的物理结构,数据的存储结构 逻辑结构在存储器中的映象,“数据元素”如何映象？,“关系”如何映象？,12,2021/3/18,数据的物理结构,数据元素在计算机内部实际存储时，根据各数据元素之间相对的存储位置及相互之间的关系，存在着两种存储结构,顺序存储结构,在存储器中，数据元素是依次存放的，数据元素在物理存储器上的位置关系体现了它们在逻辑上的顺序关系,链式存储结构,在存储器中，数据元素是分散存放的，在一个数据元素中，必须有一个或若干专门的数据项来指示其他相关联的数据元素在存储器中的位置,13,2021/3/18,数据的物理结构,分别用顺序结构和链式结构来存储数列“10,20,30,40”,数列的顺序存储结构,数列的链式存储结构,14,2021/3/18,数据的物理结构,链式映象需要用一个附加信息指示下一元素的存储位置,15,2021/3/18,基本概念,数据类型,数据类型,在用高级程序语言编写的程序中，必须对程序,中出现的每个变量、常量或表达式，明确说明,它们所属的数据类型,。,16,2021/3/18,基本概念,数据类型,（,C+,为例,）,基本数据类型,字符（,char,）、整数（,int,）、浮点数（,float/double,）、指针（,*,）、引用（,&,）,复杂数据类型,数组（,）、结构（,struct,）、枚举（,enum,）、类（,class,）、联合（,union,）,不同类型的变量，其所能取的值的范围不同，,所能进行的操作不同。,17,2021/3/18,基本概念,数据类型,数据类型,是一个 值的集合和定义在此集合上,的一组操作的总称。,18,2021/3/18,基本概念,抽象数据类型,在软件系统开发的全过程中，对客观现实中存在的事物，存在三个观察层面,应用层是用户通过物理观察得到的客观事物的视图，是可以用,自然语言,描述的，或用图形、图像、音频、视频等,物理量,表达的在概念层次上的数据。,逻辑层（抽象层）是从应用层次抽象出来的数据视图，利用,抽象数据类型,进行形式化描述。,实现层明确地表示出了,数据的组织与存储结构,，并用某种具体的程序设计语言进行代码实现。,19,2021/3/18,基本概念,抽象数据类型,抽象数据类型（,ADT,，,Abstract Data Type,）,是与具体计算机内部表示和实现方式无关的数据类型,是由一个逻辑上的,数学模型,以及定义在该模型上的一组,操作,构成,可以用三元组定义,(,D,S,P,),D,是数据对象,S,是,D,上的关系集,P,是对,D,的基本操作集,抽象数据类型和数据类型实际上是一个概念,20,2021/3/18,基本概念,抽象数据类型,ADT 有两个重要特征:,一、数据抽象,用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。,二、数据封装,将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。,21,2021/3/18,抽象数据类型例,ADT Set/,集合的抽象数据类型,数据对象：,D,ai|aiElemType,i=1,2,.,n,n 0,数据关系：,R=aiaj|ai,ajD,基本操作：,Init(),操作结果：构造一个空的集合。,Destroy(),操作结果：销毁集合。,IsEmpty(),操作结果：判断集合是否为空，如为空，则返回,TRUE,；,否则返回,FALSE,。,Insert(e),操作结果：在集合中加入一个元素。如元素已存在，,返回,FALSE,；否则返回,TRUE,。,Remove(e),操作结果：在集合中移除一个元素。如元素存在，,则返回,TRUE,；否则返回,FALSE,。,IsMember(e),操作结果：判断在集合中是否存在元素。,FindFirst(&e),操作结果：找到集合中的第一个元素。,如成功，返回,TRUE,；如果集合为空，返回,FALSE,22,2021/3/18,抽象数据类型例,FindFirst(&e),操作结果：找到集合中的第一个元素。,如成功，返回,TRUE,；如果集合为空，返回,FALSE,FindNext(&e),初始条件：已经执行过,FindFirst,或,FindNext,操作,操作结果：在上一次查找的前提下，找到集合中的下,一个元素；如成功，返回,TRUE,；如上次查找已到最后,一个元素，返回,FALSE,。,Union(s),操作结果：与另一个集合,s,做并运算，返回并集。,Intersection(s),操作结果：与另一个集合,s,做交运算，返回交集。,Difference(s),操作结果：与另一个集合,s,做差运算，返回差集。,23,2021/3/18,二、算法与算法分析,程序,为计算机处理问题编制一组指令集,算法,处理问题的策略,数据结构,问题的数学模型,Algorithm+Data Structures=Programs,算法,+,数据结构,=,程序,-,Niklaus Wirth,24,2021/3/18,算法,算法（,algorithm,）,解决某一特定问题的具体步骤的描述，是指令的有限序列,算法的五个重要特征,有穷性,确定性,可行性,输入,输出,25,2021/3/18,算法,1,有穷性,对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。,2,确定性,对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。,26,2021/3/18,算法,3,可行性,算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。,4,有输入,作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。,5,有输出,它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。,27,2021/3/18,算法,算法设计的原则,设计算法时，通常应考虑达到以下目标：,1正确性,2.可读性,3健壮性,4高效率与低存储量需求,28,2021/3/18,算法的性能分析与度量,算法性能的度量方法,事后测试,可采用一些程序运行性能跟踪与测量工具（如,Profiler,）,预先评做,不考虑算法的实现语言、编译器、运行的硬件平台，只考虑在一定问题规模下算法运行的,时间复杂度,和,空间复杂度,性能度量,时间复杂度,按某种算法设计的程序在计算机上执行时花费的,CPU,时间的度量,空间复杂度,按某种算法设计的程序在计算机上执行时需要使用的存储空间的度量,29,2021/3/18,算法的性能分析与度量,和算法执行时间相关的因素：,1,算法选用的策略,2,问题的规模,3,编写程序的语言,4,编译程序产生的机器代码的质量,5,计算机执行指令的速度,30,2021/3/18,算法的性能分析与度量,一个特定算法的“运行工作量”,的大小，只依赖于问题的规模（通常用整数量,n,表示），或者说，它是问题规模的函数。,31,2021/3/18,算法的性能分析与度量,算法,=,控制结构,+,原操作,（固有数据类型的操作）,算法的执行时间,=,原操作,(i),的执行次数,原操作,(i),的执行时间,32,2021/3/18,算法的性能分析与度量,时间的复杂度,从算法中选取对于所处理问题来说是关键步骤的程序语句作为基本操作，该基本操作,重复执行的次数,作为算法的时间量度。,基本操