《数据结构完整版课件全套ppt教学教程汇总最新最全》由会员分享，可在线阅读，更多相关《数据结构完整版课件全套ppt教学教程汇总最新最全（385页珍藏版）》请在金锄头文库上搜索。
1、数据结构（第四版）数据结构（第四版）第第1章章 绪绪 论论数据结构（第四版）数据结构（第四版）第第1章章 绪绪 论论学习目的要求:1.理解和熟悉数据结构中的基本概念。2.理解和掌握线性结构、树形结构和图形结构的概念和二元组的表示方法。3.熟悉算法评价的一般规则，算法时间复杂度、空间复杂度的概念和数量级的表示方法。数据结构（第四版）数据结构（第四版）第第1章章 绪绪 论论1.1 1.1 什么是数据结构什么是数据结构1.2 1.2 数据的逻辑结构数据的逻辑结构1.3 1.3 算法的描述算法的描述数据结构（第四版）数据结构（第四版）例1.1 电话号码自动查找问题。我们称这种数据结构为线性表。1.1
2、1.1 什么是数据结构什么是数据结构序号用户名电话号码地址01赵一12345671青年路1-1号02钱二12345672青年路1-2号03孙三12345673青年路1-3号04李四12345674青年路1-4号05周五12345675青年路1-5号06吴六12345676青年路1-6号07郑七12345677青年路1-7号08王九12345678青年路1-8号数据结构（第四版）数据结构（第四版）例1.2 计算机磁盘中文件的目录结构。文件目录结构示意图在磁盘目录中，包含一个根目录和若干个一级子目录或文件，在一级子目录中又包含若干个子目录或文件。我们称这种数据结构为树形结构。1.1 1.1 什么是
3、数据结构什么是数据结构数据结构（第四版）数据结构（第四版）网络结构示意图统。它是由各个 网站和终端用户所组成，利用网线或电话线连接到一起的。例1.3 Internet网络系统。我们称这种数据结构为图形结构。1.1 1.1 什么是数据结构什么是数据结构数据结构（第四版）数据结构（第四版）1.2 1.2 数据的逻辑结构数据的逻辑结构1.2.1 基本术语1.数据（Data）数据是指能够输入到计算机中，并能被计算机处理的一切对象。对计算机科学而言，数据的含义极为广泛，如整数、实数、字符、文字、图形、图像和声音等都是数据。数据结构（第四版）数据结构（第四版）2.数据元素（Data Element）数据元
4、素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。但它还可以分割成若干个具有不同属性的项（字段）。数据元素一般由一个或多个数据项组成。1.2 1.2 数据的逻辑结构数据的逻辑结构1.2.1 基本术语数据结构（第四版）数据结构（第四版）3.数据项（Data Item）数据项是具有独立意义的最小数据单位，是对数据元素属性的描述。1.2 1.2 数据的逻辑结构数据的逻辑结构1.2.1 基本术语数据结构（第四版）数据结构（第四版）4.数据类型（Data Type）数据类型是一组性质相同的值的集合以及定义于这个值的集合上的一组操作的总称。每个数据项属于某一确定的基本数据类型。1.2 1.
5、2 数据的逻辑结构数据的逻辑结构1.2.1 基本术语数据结构（第四版）数据结构（第四版）5.数据对象（Data Object）数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象的集合是0，1，2，;字母字符数据对象的集合是A，B，C，Z;电话号码查找系统中，数据对象就是全体电话用户。1.2 1.2 数据的逻辑结构数据的逻辑结构1.2.1 基本术语数据结构（第四版）数据结构（第四版）6.数据结构（Data Structure）数据结构的基本含义是指数据元素之间的关系，它是按照某种关系组织起来的一批数据，以一定的存储方式把它们存储到计算机存储器中，并在这些数据上定义了一个运算
6、的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，数据元素之间的这种相互关系就称为结构，带有结构的数据对象称为数据结构。1.2 1.2 数据的逻辑结构数据的逻辑结构1.2.1 基本术语数据结构（第四版）数据结构（第四版）1.2.2 数据的逻辑结构集合：结构中各数据元素之间不存在任何关系。线性结构：在该数据结构中的数据元素存在着一对一的关系。树形结构：在该数据结构中的数据元素存在着一对多的关系。图形或网状结构：在该数据结构中的数据元素存在着多对多的关系。1.2 1.2 数据的逻辑结构数据的逻辑结构数据结构（第四版）数据结构（第四版）（a）集合结构示意图（b）线性结构示
7、意图（c）树形结构示意图（d）图形结构示意图数据的逻辑结构的基本分类:1.2 1.2 数据的逻辑结构数据的逻辑结构数据结构（第四版）数据结构（第四版）数据结构可用二元组S=（D，R）的形式来描述。其中，D表示数据元素的集合，R表示D上关系的集合。关于二元组S=（D，R）中前驱和后继的关系，可以描述如下，假设a1，a2是D中的两个元素，则在二元组中，a1是a2的直接前驱，a2是a1的直接后继。数据逻辑结构的数学定义方法:1.2 1.2 数据的逻辑结构数据的逻辑结构数据结构（第四版）数据结构（第四版）例1.4 用上面的数学方法给出一周七天的数据逻辑结构。设a1、a2、a3、a4、a5、a6、a7分
8、别表示星期一至星期日，这是线性结构。图中圆框表示一个结点，圆框内的符号是该结点的值，带箭头的线段表示前驱与后继的关系。1.2 1.2 数据的逻辑结构数据的逻辑结构数据结构（第四版）数据结构（第四版）例1.5 设一个数据结构的抽象描述为 S=D，R，其中:D=1，2，3，4，5，6，7，8R=，1.2 1.2 数据的逻辑结构数据的逻辑结构数据结构（第四版）数据结构（第四版）1.3 1.3 算法的描述算法的描述1.3.1 算法算法是对某一特定问题求解步骤的一种描述。在计算机系统中，算法是由若干条指令组成的有穷序列，其中每一条指令表示计算机的一个或多个操作。数据结构（第四版）数据结构（第四版）算法满
9、足以下5个性质:1.输入:一个算法可以有0个或多个输入量，在算法执行之前提供给算法。2.输出:一个算法的执行结果要有一个或多个输出量，它是算法对输入数据处理的结果。3.有穷性:一个算法必须在执行有穷步骤之后结束，并且每一步骤也都必须在有限的时间之内完成。4.确定性:算法中的每一步骤都有明确的含义，没有二义性。5.可行性:算法中描述的每一个操作，都可以通过已经实现的基本运算，执行有限次后来完成。1.3 1.3 算法的描述算法的描述数据结构（第四版）数据结构（第四版）1.3.2 算法的设计要求一般来说，算法必须具有以下几个方面的基本特征:（1）正确性 正确性是设计一个算法的首要条件，所设计的算法要
10、满足具体问题的要求。在给算法输入合理的数据后，能在有限的时间内得出正确的结果。1.3 1.3 算法的描述算法的描述数据结构（第四版）数据结构（第四版）（2）可读性 算法是对特定问题求解步骤的一种描述，它要转变成计算机可执行的程序，同时必须可以供他人使用。为了阅读与交流，所设计的算法要让他人能看懂，在算法或程序中可以增加一些注释来提高可读性。1.3 1.3 算法的描述算法的描述1.3.2 算法的设计要求数据结构（第四版）数据结构（第四版）（3）健壮性 当输入的数据不符合要求时，算法应能判断出数据的非法性，并能进行适当的处理。比如，暂停或终止程序的执行，显示错误信息等。不允许产生不可预料的结果。1
11、.3 1.3 算法的描述算法的描述1.3.2 算法的设计要求数据结构（第四版）数据结构（第四版）（4）高效性 算法的效率是指算法执行的时间和占用的存储空间。如果对于同一个问题有多个算法可供选择，应尽可能选择执行时间短、占用空间少的算法。1.3 1.3 算法的描述算法的描述1.3.2 算法的设计要求数据结构（第四版）数据结构（第四版）1.3.3 算法的评价一个好的算法首先要具备正确性，然后是可读性和健壮性。在具备了这三个条件后，就应考虑算法的效率问题，即算法的时间效率和空间效率两个方面。1.3 1.3 算法的描述算法的描述数据结构（第四版）数据结构（第四版）（1）时间效率 时间效率就是考虑一个算
12、法运行时所需时间的多少。一个算法运行所需要的时间与算法中语句执行的次数成正比，如果算法中语句重复执行的次数越多，所需要的时间也就越多。时间复杂度一般不是算法的精确执行次数，而是结算的数量级。它着重体现的是随着问题规模的增大，算法执行时间增长的变化趋势。1.3.3 算法的评价1.3 1.3 算法的描述算法的描述数据结构（第四版）数据结构（第四版）例1.6 求下列4个程序段的语句频度。1.3 1.3 算法的描述算法的描述（a）i+;x=0;（b）for（i=1;i=n;i+）x=x+1;（c）for（i=1;i=n;i+）for（j=1;j=n;j+）x=x+1;（d）for（i=1;i=n;i+
13、）for（j=1;j=n;j+）for（k=1;k=n;k+）x=x+1;数据结构（第四版）数据结构（第四版）（a）是一个没有循环算法的基本操作，它的语句频度与问题规模没有关系，记作 T（n）=O（1），也称为常量阶。（b）是一个一重循环的算法，它的语句频度随问题规模 n的增大而呈线性增大，这种线性关系记作 T（n）=O（n），也称线性阶。（c）是一个二重循环的算法，它的语句频度为 n2，记作T（n）=O（n2），称为平方阶。（d）是一个三重循环的算法，它的语句频度为 n3，记作T（n）=O（n3），称为立方阶。1.3 1.3 算法的描述算法的描述常见的时间复杂度还有对数阶 O（log 2n）
14、、O（n log 2n），指数阶O（2n）等。数据结构（第四版）数据结构（第四版）（2）空间效率 一个算法在执行过程中所占用的存储空间大小，称为空间效率或空间频度。与时间复杂度类似，空间复杂度是指算法在计算机内执行时临时占用的存储空间大小。算法的空间复杂度一般以数量级形式给出。1.3 1.3 算法的描述算法的描述数据结构（第四版）数据结构（第四版）1.数据结构研究的是数据的表示形式和数据之间的相互关系。数据的逻辑结构有四种:集合、线性结构、树形结构和图形结构。2.集合的数据元素之间不存在任何关系;线性结构的数据元素之间存在一对一的线性关系;树形结构的数据元素之间存在一对多的非线性关系;图形结构
15、的数据元素之间存在多对多的非线性关系。3.算法的评价指标主要为正确性、可读性、健壮性和高效性四个方面。在高效性中又包括算法执行的时间效率和所占用的空间效率。4.通常用数量级的形式来表示算法的时间复杂度和空间复杂度。数量级的形式有常量阶、线性阶、平方阶、立方阶、对数阶和指数阶等。一个算法的时间复杂度和空间复杂 度越低，算法的执行效率就会越高。本章小结本章小结数据结构（第四版）数据结构（第四版）谢谢观看！谢谢观看！谢谢观看！谢谢观看！数据结构（第四版）数据结构（第四版）第第2章章 线性表线性表数据结构（第四版）数据结构（第四版）第2章 线性表学习目的要求:1.线性表的定义和线性表的特征。2.线性表
16、的顺序存储结构及其算法的实现。3.线性链表的描述及其算法的实现。循环链表和双向循环链表的描述。数组的顺序存储和矩阵的压缩存储的描述。数据结构（第四版）数据结构（第四版）2.1 线性表的基本概念2.2 线性表的顺序存储结构及其算法2.3 线性表的链式存储结构及其运算2.4 算法应用举例2.5 数组第2章 线性表数据结构（第四版）数据结构（第四版）2.1.1 线性表的定义2.1 线性表的基本概念线性表（linear list）是由 n个数据元素组成的有限序列。线性表可以用一个标识符来命名，如果用A来表示线性表，则:A=（a1 ，a2 ，ai ，an ）线性表是一种非常典型的线性结构，用二元组可以表示成:S=（D，R）D=a1，a2，ai，an R=，数据结构（第四版）数据结构（第四版）2.1.2 线性表的基本操作（1）InitList（List）:初始化操作，建立一个空的线性表List;（2）ListLength（List）:求线性表的长度;（3）GetElement（List，i）:取线性表中的第 i 个元素（1 i n，n为线性表长度）;（4）PriorElement（List，x）:
