《数据结构与算法》ppt课件

《《数据结构与算法》ppt课件》由会员分享，可在线阅读，更多相关《《数据结构与算法》ppt课件（31页珍藏版）》请在金锄头文库上搜索。

1、数据结构与算法（Java版）,2019年1月29日,数据结构是计算机及相关专业中一门重要的专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用专业中具有举足轻重的作用。,2019年1月29日,课程任务 在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。 学业基础 本课程的先修课程

2、为离散数学和高级语言程序设计。学习本课程必须具备高级语言程序设计(C语言)的基础知识与基本技能。它的后续课程有操作系统和数据库原理等。,2019年1月29日,教学内容： (1)数据结构的概念； (2)抽象数据类型； (3)算法和算法分析。 教学目的： (1)领会数据、数据元素和数据项的概念及其相互间的关系； (2)清楚数据结构的逻辑结构、存储结构的联系与区别； (3)理解抽象数据类型的概念； (4)掌握进行简单算法分析的方法。,第1章 数据结构与算法,2019年1月29日,教学重点： 数据、数据项、数据元素、数据结构的概念； 逻辑结构和数据结构在概念上的联系与区别； 抽象数据类型和数据抽象；

3、评价算法优劣的标准及方法。 教学难点： 区别算法与程序； 逻辑结构、存储结构的联系与区别； 抽象数据类型与数据抽象； 算法的时间复杂度分析。,2019年1月29日,1.1.1 为什么要学习数据结构,在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须重视数据结构。 随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。解决这类问题的关键是要设计出合适的数据结构，才能有

4、效地解决问题。,1.1 引言,2019年1月29日,【例1-1】成绩检索系统。要求成绩检索系统提供自动查询的功能，如查找某个学生的单科成绩或平均成绩，查询某门课程的最高分等等。,【例1-2】棋盘布局问题。要求将4个棋子布在4行4列的棋盘上，使得任两个棋子既不在同一行或同一列，也不在同一对角线上。,2019年1月29日,【例1-3】教学计划编排问题一个教学计划包含许多课程，在教学计划包含的许多课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构来表示，如图所示。有向图中的每个顶点

5、表示一门课程，如果从顶点vi到vj之间存在有向边， 则表示课程i必须先于课程j进行。,2019年1月29日,由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。,2019年1月29日,1、数据结构课程的发展 数据结构作为一门独立的课程在国外是从1968年才开始的，但在此之前其有关内容已散见于编译原理及操作系统之中。 从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越

6、重视数据结构。 从70年代中期到80年代，各版本的数据结构著作相继出现。,1.1.2 数据结构课程的内容,2019年1月29日,数据结构课程集中讨论软件开发过程中的设计阶段、同时涉及编码和分析阶段的若干基本问题。此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。因此，数据结构的内容包括三个层次的五个“要素”。,2、数据结构课程的内容,2019年1月29日,1.2.1 有关概念和术语,1、数据 数据是信息的载体，是所有能够被计算机识别、存储和加工处理的符号的总称。 2、数据项 数据项（Data Item）是具有独立含义的标识单位，是数据不可分割的最小单位。 3、数据元素

7、 数据元素（Data Element）是数据的基本单位。 4、数据对象 数据对象（Data Object）或数据元素类（Data Element Class）是具有相同性质的数据元素的集合。,1.2 数据结构的概念,2019年1月29日,4、数据结构 数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。 根据数据元素间关系的不同特性，通常有下列四类基本的结构： 集合结构。线性结构。树结构。图结构。,2019年1月29日,下图为表示上述四类基本结构的

8、示意图。,2019年1月29日,(1)逻辑层次的数据结构有两个要素。 一个是数据元素的集合，另一个是关系的集合。 形式上，数据结构可以采用一个二元组来表示： Data_Structure （D，R） 其中，D是数据元素的有限集，R是D上关系的有限集。 (2) 应用层次的数据结构包括数据的逻辑结构和数据的物理结构。 数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，它与数据的存储无关。 数据结构在计算机中的标识称为数据的物理结构，或称存储结构。,2019年1月29日,1.2.2 抽象数据类型,1、数据类型 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 2、抽象数据类型 抽象数据

9、类型（Abstruct Data Type，简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。,2019年1月29日,1.3.1 数据结构的C语言描述,根据数据结构的概念，在计算机中表示用户自定义的数据结构，实现数据结构上的操作及应用，需要描述三方面的内容：数据对象的类型、数据对象的关系和对数据对象的操作。 C语言不是面向对象的程序设计语言，因此不具有将数据结构三方面的内容封装的功能，必须分别描述。,1.3 数据结构的描述方法,2019年

10、1月29日,数据对象的联系 数据对象的关系体现了数据的逻辑结构，可以采用顺序存储表示，也可以采用链式存储表示。一般顺序存储采用数组类型表示，链式存储采用指针类型表示。 数据对象的操作 数据对象的操作在C语言中被描述为独立的函数。,2019年1月29日,1.3.2 数据结构的C+描述,C是对C语言的改进和扩充，以C为基础，包含了整个C，具备C的全部特性、属性和优点，同时添加了对面向对象编程的完全支持。因此采用C描述数据结构，可以仍采用和C描述一样的方式，也可以采用面向对象的方式描述。 数据对象的联系 对数据对象的关系和数据对象的操作的描述也是通过定义类的形式，将对数据对象关系的存储与对数据对象操

11、作的定义封装到一个类中，数据对象的关系通过类的私有数据描述体现。 数据对象的操作被描述成类的成员函数，较好地保证了数据结构的抽象和独立,2019年1月29日,1.3.3 数据结构的Java描述,Java语言的数据类型分为两大类： 基本数据类型和引用数据类型。其中，基本数据类型有八种，即四种整型类型、两种浮点类型、一种字符类型和一种布尔类型。没有前面在C语言、C中描述数据结构时用到的结构体类型和指针类型。在Java语言中类似C，仍然采用类定义数据对象，并将对数据对象的关系的存储描述与数据对象的操作封装到类的定义中，主要不同的是使用引用类型代替指针类型。不用指针类型描述数据结构，使得数据结构的描述

12、中没有了与地址相关的运算*和&，更易于对数据结构的理解。,2019年1月29日,数据对象的类型 class DataType public: 数据成员列表 数据对象的联系，数据对象的关系体现了数据的逻辑结构，可以采用顺序存储表示，也可以采用链式存储表示。一般顺序存储采用数组类型表示，链式存储采用指针类型表示。 例如，顺序存放a1,a2,an的存储定义为： class SeqList private DataType data; private int last; 成员函数 ,2019年1月29日,1.4.1 算法及其特性,算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序

13、列。其中每一条指令表示一个或多个操作。 一个算法应该具有下列特性： 有穷性。 确定性。 可行性。 输入。 输出。,1.4 算法,2019年1月29日,算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。 要设计一个好的算法通常要考虑以下的要求。 正确。 可读。 健壮。 高效。,2019年1月29日,1.4.2 算法描述,算法可以使用各种不同的方法来描述。 自然语言: 程序流程图、N-S图等算法描述工具： 直接使用某种程序设计语言： 用伪码语言的描述方法：,2019年1月29日,1.4.

14、3 算法的性能分析,时间复杂度、空间复杂度：也成为时间性能和空间性能，是对某个算法的时间效率和空间效率的度量。 时间复杂度 将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素： 硬件的速度。 书写程序的语言。 编译程序所生成目标代码的质量。 问题的规模。,2019年1月29日,时间复杂度 ： 一个算法的时间复杂度（Time Complexity）就是指算法的时间耗费，这里用T(n)表示。 一个算法执行所耗费的时间，是算法中所有语句执行时间之和，而每条语句的执行时间是该语句执行一次所用时间与该语句重复执行次数的乘积。一个语句重复执行的次数称为语句的频度（Frequency

15、Count）。 算法的时间复杂度T(n)表示为： 其中ti表示语句i执行一次的时间，ci表示语句i的频度。 假设每条语句执行一次的时间均为一个单位时间，那么算法的时间耗费可简单表示为各语句的频度之和：,2019年1月29日,【例1-5】下面的程序段用来求两个n阶方阵A和B的乘积C。 for(i=0;in;i+) /* n+1*/ for(j=0;jn;j+) /* n(n+1) */ Cij=0; /* n2*/ for(k=0;kn;k+) /* n2(n+1) */ Cij+=Aik*Bkj; /* n3*/ 右边列出了各语句的频度，因而算法的时间复杂度T(n)为： T (n) (n+1)

16、n(n+1)+ n2+ n2(n+1) + n3 =2n3+3n2+2n+1 可见，T(n)是矩阵阶数n的函数。,2019年1月29日,【例1-6】冒泡排序。 void BublleSort(int a , int n) for (i=0; iaj+1) ajaj+1; swap=1; 选择交换相邻的两个元素“ajaj+1;”作为基本操作。 而n个元素组成的输入集可能有n!中排列情况，若各种情况等概率，则冒泡排序的平均时间复杂度T(n)=(n2)。,2019年1月29日,空间复杂度： 一个算法的空间复杂度（Space complexity）是指算法运行从开始到结束所需的存储量。 算法的一次运行是针对所求解的问题的某一特定实例而言的。例如，