《第2章 数据结构概述优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第2章 数据结构概述优秀PPT.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第2章 数据结构概述现在学习的是第1页，共30页2.1 什么是数据结构 一、数据结构的定义一、数据结构的定义 “数据结构数据结构”是研究是研究非数值计算非数值计算的程序设计问的程序设计问题中计算机的操作对象以及它们之间的关系和运算的题中计算机的操作对象以及它们之间的关系和运算的一门一门学科学科。程序中往往要处理大量的数据，这些数据采用什程序中往往要处理大量的数据，这些数据采用什么样的方式来组织、存放才能最大限度地方便应用处么样的方式来组织、存放才能最大限度地方便应用处理，提高程序效率。理，提高程序效率。现在学习的是第2页，共30页二、数据结构的研究内容二、数据结构的研究内容研究内容：三种数据结
2、构两种基本算法研究内容：三种数据结构两种基本算法 线性结构线性结构 树形结构树形结构 图形结构图形结构 查找查找 排序排序 逻辑结构逻辑结构存储结构存储结构以及操作对象之间的运算以及操作对象之间的运算2.1 什么是数据结构 数据结构研究数据的组织形式，包括数据的逻辑数据结构研究数据的组织形式，包括数据的逻辑结构，物理结构以及在该数据结构上所施加的运算。结构，物理结构以及在该数据结构上所施加的运算。现在学习的是第3页，共30页2.2 基本概念和术语数据数据数据元素数据元素数据对象数据对象数据结构数据结构逻辑结构逻辑结构存储结构存储结构数据类型数据类型抽象数据类型抽象数据类型现在学习的是第4页，共
3、30页2.2 基本概念和术语 定义：对客观事物的符号表示，在计算机科定义：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。处理的符号的总称。数据包含整型、实型、布尔型、字符、表格、图数据包含整型、实型、布尔型、字符、表格、图象、声音等象、声音等 例如，一个图书管理程序所要处理的数据可例如，一个图书管理程序所要处理的数据可能是一张如表能是一张如表1-11-1所示的表格。所示的表格。数据数据现在学习的是第5页，共30页 2.2 基本概念和术语表表 1-1 1-1 数据举例图书信息表数据举例图书信息表现在学习的是第
4、6页，共30页2.2 基本概念和术语 定义：它是组成数据的基本单位。在程序定义：它是组成数据的基本单位。在程序中通常把数据元素作为一个整体进行考虑和处中通常把数据元素作为一个整体进行考虑和处理。理。有时，一个数据元素中含有若干个子项（叫数据有时，一个数据元素中含有若干个子项（叫数据项）组成。项）组成。数据项是构成数据的最小单位。数据项是构成数据的最小单位。数据元素数据元素数据对象数据对象性质（类型）相同的一组数据元素组成的集合。性质（类型）相同的一组数据元素组成的集合。现在学习的是第7页，共30页 数据结构指的是数据之间的相互关系，即数据数据结构指的是数据之间的相互关系，即数据的组织形式。一般
5、包括以下三方面的内容：的组织形式。一般包括以下三方面的内容：数据元素之间的逻辑关系，也称为数据的数据元素之间的逻辑关系，也称为数据的逻辑结构逻辑结构；数据元素及其关系在计算机存储器内的表示，数据元素及其关系在计算机存储器内的表示，称为数据的称为数据的存储结构存储结构，又称，又称物理结构物理结构；数据的运算，即对数据施加的操作。数据的运算，即对数据施加的操作。以上三方面称为数据结构的三要素。以上三方面称为数据结构的三要素。根据数据元素之间关系的不同特性通常有下列根据数据元素之间关系的不同特性通常有下列四种常用的数据结构：四种常用的数据结构：2.2 基本概念和术语数据结构数据结构现在学习的是第8页
6、，共30页2.2 基本概念和术语集合集合：结构中的数据：结构中的数据元素之间除了元素之间除了 同属于同属于一个集合一个集合 的关系外，的关系外，别无其他关系；别无其他关系；线性结构线性结构：结构中的数：结构中的数据元素之间存在一对一据元素之间存在一对一的线性关系；的线性关系；四种基本的数据结构四种基本的数据结构现在学习的是第9页，共30页2.2 基本概念和术语树形结构树形结构：结构中的数结构中的数据元素之间存在着一对据元素之间存在着一对多的关系；多的关系；图状结构图状结构：结构中的数结构中的数据元素之间存在着多对据元素之间存在着多对多的关系；多的关系；v1v6v2v3v5v4301020505
7、1010060四种基本的数据结构四种基本的数据结构ABCDEFG现在学习的是第10页，共30页2.2 基本概念和术语 上述四种数据结构的统一形式定义为：数据结构是上述四种数据结构的统一形式定义为：数据结构是一个二元组一个二元组 Data_Structure=(D,S)Data_Structure=(D,S)其中其中:D:D是数据元素的有限集是数据元素的有限集 S S是是D D上关系的有限集。上关系的有限集。上述数据结构均有以下两种存储结构：上述数据结构均有以下两种存储结构：顺序存储结构：顺序存储结构：申请一块连续的内存空间依次存储申请一块连续的内存空间依次存储每一个数据元素。它的特点是借助数据
8、元素在内存中的每一个数据元素。它的特点是借助数据元素在内存中的相对位置反映数据元素之间的逻辑关系。相对位置反映数据元素之间的逻辑关系。链式存储结构：链式存储结构：特点是借助指示元素存储地址的指针特点是借助指示元素存储地址的指针来表示数据元素之间的逻辑关系。来表示数据元素之间的逻辑关系。现在学习的是第11页，共30页2.2 基本概念和术语数据类型数据类型 数据类型数据类型 是指一个是指一个 值的集合和定义在此集合上的值的集合和定义在此集合上的一组操作的总称。一组操作的总称。抽象数据类型是指一个数学模型以及定义在该抽象数据类型是指一个数学模型以及定义在该模型上的模型上的 一组操作的总称。一组操作的
9、总称。抽象数据类型抽象数据类型现在学习的是第12页，共30页2.3 算法和算法分析算法和算法分析 算法的算法的5个重要特性：个重要特性：1.有穷性有穷性2.确定性确定性3.可行性可行性4.输入输入5.输出输出注意：算法和程序的区别。注意：算法和程序的区别。一、算法的定义一、算法的定义 算法，简单地说就是解决特定问题的方法，是对特算法，简单地说就是解决特定问题的方法，是对特定问题求解步骤的一种描述，对计算机而言，它是指令定问题求解步骤的一种描述，对计算机而言，它是指令的有限序列。的有限序列。现在学习的是第13页，共30页二、算法设计的要求二、算法设计的要求设计一个好的算法应考虑以下几个方面设计一
10、个好的算法应考虑以下几个方面1.1.正确性正确性 程序对于精心选择的典型、苛刻而带有刁难性的几组数程序对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果据能够得出满足规格说明要求的结果.2.可读性可读性3.健壮性健壮性4.高效率和低存储量高效率和低存储量 效率指的是算法执行时间。效率指的是算法执行时间。存储量指的是算法执行过程中所需要的最大存储空存储量指的是算法执行过程中所需要的最大存储空间。间。2.3 算法和算法分析算法和算法分析现在学习的是第14页，共30页三、三、算法效率的度量算法效率的度量 一个问题可以有多种解题方法，那么就有多个对应一个问题可以有多种解题方法
11、，那么就有多个对应的算法。算法的优劣由算法的时间复杂度和空间复杂度的算法。算法的优劣由算法的时间复杂度和空间复杂度来衡量。来衡量。算法执行时间需依据该算法编制的程序在计算机上算法执行时间需依据该算法编制的程序在计算机上运行时所消耗的时间来度量。运行时所消耗的时间来度量。度量一个程序的执行时间通常有两种方法：度量一个程序的执行时间通常有两种方法：1.1.事后统计：统计算法的实际执行时间。但这种方法事后统计：统计算法的实际执行时间。但这种方法受以下因素的影响，容易掩盖算法本身的优劣。受以下因素的影响，容易掩盖算法本身的优劣。a.a.机器执行速度机器执行速度 b.b.算法采用的语言及相应的编译系统算
12、法采用的语言及相应的编译系统 c.c.编译程序所产生的机器代码质量编译程序所产生的机器代码质量2.3 算法和算法分析算法和算法分析现在学习的是第15页，共30页2.2.事前分析估计事前分析估计 算法算法=控制结构（顺序、分支、循环）控制结构（顺序、分支、循环）+原操作原操作 算法时间则取决于两者的综合效果。算法时间则取决于两者的综合效果。为了比较同一问题的不同算法，通常的做法是：从算法为了比较同一问题的不同算法，通常的做法是：从算法中的诸多原操作中，选取对于所研究的问题来说是有中的诸多原操作中，选取对于所研究的问题来说是有代表性代表性的原操作的原操作作为作为基本操作基本操作，以该基本操作在算法
13、中重复执行的以该基本操作在算法中重复执行的次数次数(也称频度也称频度)作为算法运行时间的衡量准则。作为算法运行时间的衡量准则。2.3 算法和算法分析算法和算法分析现在学习的是第16页，共30页 它指的是在给定的问题规模它指的是在给定的问题规模n n下，算法中的基本操作重下，算法中的基本操作重复执行次数的复执行次数的数量级数量级。通常记作：。通常记作：T(n)=O(f(n)T(n)=O(f(n)称称T(n)T(n)为算法的为算法的(渐近渐近)时间复杂度时间复杂度,简称简称时时间复杂度。间复杂度。其中，其中，n n是问题规模，即所要处理问题的数量。是问题规模，即所要处理问题的数量。f(n)f(n)
14、：指基本操作重复执行次数，是：指基本操作重复执行次数，是n n的函数。的函数。字符字符“O O”代表代表T(n)T(n)与与f(n)f(n)是同一数量级，即随着是同一数量级，即随着n n的增大，的增大，算法执行时间的增长率与算法执行时间的增长率与f(n)f(n)的增长率相同。的增长率相同。算法的时间复杂度算法的时间复杂度2.3 算法和算法分析算法和算法分析现在学习的是第17页，共30页 上述的上述的数学符号数学符号“O O”，它的严格定义是，它的严格定义是“若若T(n)T(n)和和f(n)f(n)是定义在正整数集合上的两个函数，则是定义在正整数集合上的两个函数，则T(n)=O(f(n)T(n)
15、=O(f(n)表示存在正的常数表示存在正的常数C C和和n0,n0,使得当使得当nn0nn0时都满足时都满足0T(n)C0T(n)Cf(n)f(n)。”也即：这两个函数当整型自变量也即：这两个函数当整型自变量n n趋向于无穷大趋向于无穷大时，两者的比值是一个不等于时，两者的比值是一个不等于0 0的常数。的常数。2.3 算法和算法分析算法和算法分析现在学习的是第18页，共30页举例：两个举例：两个NN的矩阵相乘的算法的矩阵相乘的算法void mult(int a,int b,int c)/以二维数组存储矩阵元素，以二维数组存储矩阵元素，c 为为 a 和和 b 的乘积的乘积 for(i=1;i=n
16、;+i)n+1 for(j=1;j=n;+j)n(n+1)cij=0;n2 for(k=1;k0;i-)for(j=0;j0;i-)x+;for(j=0;j0;i-)x+;for(j=0;jn;j+)y+；(4)for(i=0;in;i+)x+;for(j=0;jm;j+)y+；算法的时间复杂度算法的时间复杂度2.3 算法和算法分析算法和算法分析现在学习的是第20页，共30页(5)for(i=0;in;i+)for(j=0;jm;j+)y+；(6)for(i=0;in;i+)for(j=0;jn-i;j+)y+；f(n)=n(n-1)/2 T(n)=O(?)算法的时间复杂度算法的时间复杂度(7
17、)for(i=0;i10;i+)x+；(8)for(i=0;i1000;i+)x+；无问题规模，算法时间复无问题规模，算法时间复杂度是常数阶杂度是常数阶O(1)2.3 算法和算法分析算法和算法分析现在学习的是第21页，共30页(9)i=1;j=0;while(2*ib?max=amax=b输出max结束yesyesNoNo现在学习的是第28页，共30页三、类三、类C语言语言 用一种类似于用一种类似于C语言语法规则的程序语言来描述算法，语言语法规则的程序语言来描述算法，无需考虑是否合乎语法约束，能看懂就行。无需考虑是否合乎语法约束，能看懂就行。void maxab()scanf(&a,&b);i
18、f(ab)max=a;else max=b;print(max);2.4 2.4 算法的描述方法算法的描述方法现在学习的是第29页，共30页四、高级语言四、高级语言 用严谨的某一高级语言的语法和函数来描述算法。用严谨的某一高级语言的语法和函数来描述算法。void maxab()int a,b,max;printf(“please input two numbers to a and b:”);scanf(“%d,%d”,&a,&b);if(ab)max=a;else max=b;printf(“The max is:%d”,max);2.4 2.4 算法的描述方法算法的描述方法现在学习的是第30页，共30页