第2章 数据结构概述优秀课件.ppt

《第2章 数据结构概述优秀课件.ppt》由会员分享，可在线阅读，更多相关《第2章 数据结构概述优秀课件.ppt（30页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第2章 数据结构概述第1页，本讲稿共30页2.1 什么是数据结构 一、数据结构的定义一、数据结构的定义 “数据结构数据结构”是研究是研究非数值计算非数值计算的程序设计问的程序设计问题中计算机的操作对象以及它们之间的关系和运算题中计算机的操作对象以及它们之间的关系和运算的一门的一门学科学科。程序中往往要处理大量的数据，这些数据采用什么样的方式来组织、存放才能最大限度地方便应用处理，提高程序效率。第2页，本讲稿共30页二、数据结构的研究内容二、数据结构的研究内容研究内容：三种数据结构两种基本算法研究内容：三种数据结构两种基本算法 线性结构线性结构 树形结构树形结构 图形结构图形结构 查找查找 排序

2、排序 逻辑结构逻辑结构存储结构存储结构以及操作对象之间的运算以及操作对象之间的运算2.1 什么是数据结构 数据结构研究数据的组织形式，包括数据的逻辑结构，数据结构研究数据的组织形式，包括数据的逻辑结构，物理结构以及在该数据结构上所施加的运算。物理结构以及在该数据结构上所施加的运算。第3页，本讲稿共30页2.2 基本概念和术语数据数据数据元素数据元素数据对象数据对象数据结构数据结构逻辑结构逻辑结构存储结构存储结构数据类型数据类型抽象数据类型抽象数据类型第4页，本讲稿共30页2.2 基本概念和术语 定义：对客观事物的符号表示，在计算机科学定义：对客观事物的符号表示，在计算机科学中是指所有能输入到计

3、算机中并被计算机程序处理中是指所有能输入到计算机中并被计算机程序处理的符号的总称。的符号的总称。数据包含整型、实型、布尔型、字符、表格、数据包含整型、实型、布尔型、字符、表格、图象、声音等图象、声音等 例如，一个图书管理程序所要处理的数据可例如，一个图书管理程序所要处理的数据可能是一张如表能是一张如表1-11-1所示的表格。所示的表格。数据数据第5页，本讲稿共30页 2.2 基本概念和术语表 1-1 数据举例图书信息表第6页，本讲稿共30页2.2 基本概念和术语 定义：它是组成数据的基本单位。在程序定义：它是组成数据的基本单位。在程序中通常把数据元素作为一个整体进行考虑和处中通常把数据元素作为

4、一个整体进行考虑和处理。理。有时，一个数据元素中含有若干个子项（叫数据有时，一个数据元素中含有若干个子项（叫数据项）组成。项）组成。数据项是构成数据的最小单位。数据项是构成数据的最小单位。数据元素数据元素数据对象数据对象性质（类型）相同的一组数据元素组成的集合。性质（类型）相同的一组数据元素组成的集合。第7页，本讲稿共30页 数据结构指的是数据之间的相互关系，即数据的组数据结构指的是数据之间的相互关系，即数据的组织形式。一般包括以下三方面的内容：织形式。一般包括以下三方面的内容：数据元素之间的逻辑关系，也称为数据的数据元素之间的逻辑关系，也称为数据的逻辑结逻辑结构构；数据元素及其关系在计算机存

5、储器内的表示，数据元素及其关系在计算机存储器内的表示，称为数据的称为数据的存储结构存储结构，又称，又称物理结构物理结构；数据的运算，即对数据施加的操作。数据的运算，即对数据施加的操作。以上三方面称为数据结构的三要素。以上三方面称为数据结构的三要素。根据数据元素之间关系的不同特性通常有下列四根据数据元素之间关系的不同特性通常有下列四种常用的数据结构：种常用的数据结构：2.2 基本概念和术语数据结构数据结构第8页，本讲稿共30页2.2 基本概念和术语集合集合：结构中的数据：结构中的数据元素之间除了元素之间除了 同属于同属于一个集合一个集合 的关系外，的关系外，别无其他关系；别无其他关系；线性结构线

6、性结构：结构中的：结构中的数据元素之间存在一数据元素之间存在一对一的线性关系；对一的线性关系；四种基本的数据结构四种基本的数据结构第9页，本讲稿共30页2.2 基本概念和术语树形结构树形结构：结构中的数结构中的数据元素之间存在着一据元素之间存在着一对多的关系；对多的关系；图状结构图状结构：结构中的数据结构中的数据元素之间存在着多对多的元素之间存在着多对多的关系；关系；v v1 1v v6 6v v2 2v v3 3v v5 5v v4 430301010202050505 510101001006060四种基本的数据结构四种基本的数据结构ABCDEFG第10页，本讲稿共30页2.2 基本概念和

7、术语 上述四种数据结构的统一形式定义为：数据结构是一上述四种数据结构的统一形式定义为：数据结构是一个二元组个二元组 Data_Structure=(D,S)Data_Structure=(D,S)其中其中:D:D是数据元素的有限集是数据元素的有限集 S S是是D D上关系的有限集。上关系的有限集。上述数据结构均有以下两种存储结构：上述数据结构均有以下两种存储结构：顺序存储结构：顺序存储结构：申请一块连续的内存空间依次存储每申请一块连续的内存空间依次存储每一个数据元素。它的特点是借助数据元素在内存中的相对位一个数据元素。它的特点是借助数据元素在内存中的相对位置反映数据元素之间的逻辑关系。置反映数

8、据元素之间的逻辑关系。链式存储结构：链式存储结构：特点是借助指示元素存储地址的指针特点是借助指示元素存储地址的指针来表示数据元素之间的逻辑关系。来表示数据元素之间的逻辑关系。第11页，本讲稿共30页2.2 基本概念和术语数据类型数据类型 数据类型数据类型 是指一个是指一个 值的集合和定义在此集合上的值的集合和定义在此集合上的一组操作的总称。一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模抽象数据类型是指一个数学模型以及定义在该模型上的型上的 一组操作的总称。一组操作的总称。抽象数据类型抽象数据类型第12页，本讲稿共30页2.3 算法和算法分析算法和算法分析 算法的算法的5个重要特性：

9、个重要特性：1.有穷性有穷性2.确定性确定性3.可行性可行性4.输入输入5.输出输出注意：算法和程序的区别。注意：算法和程序的区别。一、算法的定义 算法，简单地说就是解决特定问题的方法，是对特定问题求解步骤的一种描述，对计算机而言，它是指令的有限序列。第13页，本讲稿共30页二、算法设计的要求二、算法设计的要求设计一个好的算法应考虑以下几个方面设计一个好的算法应考虑以下几个方面1.1.正确性正确性 程序对于精心选择的典型、苛刻而带有刁难性的几程序对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果组数据能够得出满足规格说明要求的结果.2.可读性可读性3.健壮性健壮性4.

10、高效率和低存储量高效率和低存储量 效率指的是算法执行时间。效率指的是算法执行时间。存储量指的是算法执行过程中所需要的最大存储空间。存储量指的是算法执行过程中所需要的最大存储空间。2.3 算法和算法分析第14页，本讲稿共30页三、三、算法效率的度量算法效率的度量 一个问题可以有多种解题方法，那么就有多个对应一个问题可以有多种解题方法，那么就有多个对应的算法。算法的优劣由算法的时间复杂度和空间复杂度的算法。算法的优劣由算法的时间复杂度和空间复杂度来衡量。来衡量。算法执行时间需依据该算法编制的程序在计算机上运行算法执行时间需依据该算法编制的程序在计算机上运行时所消耗的时间来度量。时所消耗的时间来度量

11、。度量一个程序的执行时间通常有两种方法：度量一个程序的执行时间通常有两种方法：1.1.事后统计：统计算法的实际执行时间。但这种方法受以下事后统计：统计算法的实际执行时间。但这种方法受以下因素的影响，容易掩盖算法本身的优劣。因素的影响，容易掩盖算法本身的优劣。a.a.机器执行速度机器执行速度 b.b.算法采用的语言及相应的编译系统算法采用的语言及相应的编译系统 c.c.编译程序所产生的机器代码质量编译程序所产生的机器代码质量2.3 算法和算法分析第15页，本讲稿共30页2.事前分析估计 算法=控制结构（顺序、分支、循环）+原操作 算法时间则取决于两者的综合效果。为了比较同一问题的不同算法，通常的

12、做法是：从算法中的诸多原操作中，选取对于所研究的问题来说是有代表性的原操作作为基本操作，以该基本操作在算法中重复执行的次数(也称频度)作为算法运行时间的衡量准则。2.3 算法和算法分析第16页，本讲稿共30页 它指的是在给定的问题规模它指的是在给定的问题规模n n下，算法中的基本操作下，算法中的基本操作重复执行次数的重复执行次数的数量级数量级。通常记作：。通常记作：T(n)=O(f(n)T(n)=O(f(n)称称T(n)T(n)为算法的为算法的(渐近渐近)时间复杂度时间复杂度,简称简称时间复杂度。时间复杂度。其中，其中，n n是问题规模，即所要处理问题的数量。是问题规模，即所要处理问题的数量。

13、f(n)f(n)：指基本操作重复执行次数，是：指基本操作重复执行次数，是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)=O

14、(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;+i)n+1 for(

15、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)for(i=0;i10;i+)x+；(8)

16、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);if(ab)max=a;else max=b;print(max);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 算法的描述方法第30页，本讲稿共30页