数据结构 教学课件 ppt 作者 宗大华 陈吉人 01数据结构概述

《数据结构 教学课件 ppt 作者 宗大华 陈吉人 01数据结构概述》由会员分享，可在线阅读，更多相关《数据结构 教学课件 ppt 作者 宗大华 陈吉人 01数据结构概述（51页珍藏版）》请在金锄头文库上搜索。

1、,第1章 数据结构概述,数据的逻辑结构； 数据的存储结构； 数据处理算法的描述与分析。,“数据结构”是计算机专业的一门重要基础课程，它研究的问题是从实际需要中抽象出来的，是计算机科学各领域以及系统软件都会用到的知识。 本章是全书的基础，主要介绍以下几个方面的内容：,1.1 数据的逻辑结构,人们要让计算机做事情，都必须涉及三个问题：一，确定所要加工处理的数据间的关系，以便进行处理时，能够知道一个数据的后面是哪一个数据，这是数据的逻辑结构问题；二，确定要对数据做哪些处理，这是算法描述问题；三，确定以何种方式把数据存放到计算机的内存，并反映出它们间的邻接关系，这是数据的存储结构问题。,1.1.1 数

2、据及数据间的邻接关系,“数据”是信息的载体，是人们用符号来表示客观事物的一种集合。现在把“数据”定义为：所有能够输入到计算机中被计算机加工、处理的符号的集合。 通常，数据由“数据元素”（简称“元素”）集合而成的。数据元素也常被称作“结点”、“顶点”、“记录”。每个数据元素都具有完整、确定的实际意义，是数据加工处理的对象。,一个数据元素又可以细分成由若干个“数据项”组成。数据项也常称作“字段”、“域”，它是数据元素中不可再分割的最小标识单位，通常不具备完整、确定的实际意义，只是反映数据元素某一方面的属性。 数据结构关心的是从一个数据能够找到另一个数据的那种“关系”，人们根据那种关系来组织和存储数

3、据，以便顺利、有效地实现对数据的各种处理要求。,如果两个数据结点间有着某种逻辑上的联系，就称这两个结点是“邻接的”。若用圆圈代表结点，用结点间的一条连线代表它们之间存在的逻辑关系，那么，就用图1-1来表示结点A和B是“邻接的”。,图1-1 结点的邻接,常见的数据间的邻接关系有三种：线性关系、树型关系以及图状关系。数据间的邻接关系，就是数据的“逻辑结构”。,1.1.2 数据的逻辑结构,所谓数据间具有“线性”关系，是指数据一个接一个地排列成一行。如果所要处理的数据间呈线性关系，那么就说它的逻辑结构是线性的。 在线性关系中，排在第1个位置的结点称为起始结点，排在最后一个位置的结点称为终端结点，其余的

4、结点称为中间结点，如图1-2所示。,1线性关系,图1-2 线性关系中的各种结点,线性关系的特点是：除起始结点和终端结点外，每个结点的前面和后面，都有且只有一个结点与它邻接，起始结点的前面没有邻接的结点，终端结点的后面没有邻接的结点。简单地说，线性关系的特点是：有头有尾，顺序排列。,所谓数据间具有“树型”关系，是指在数据之间具有分支、层次的逻辑关系。如果所要处理的数据之间呈树型关系，那么就说它的逻辑结构是树型的。 文件目录间的逻辑结构就是树型的。图1-3所示为一个树型目录图例。,2树型关系,图1-3 文件目录间的树型关系,树型关系的特点是：第1层只有一个结点，它是树型关系的起点；除第1层结点和分

5、支末端结点外，位于中间各层的结点的前面只有一个结点与它相邻接，每个结点的后面可以有多个结点与它相邻接；第1层结点的前面没有结点与之邻接，每个分支末端结点的后面没有结点与之邻接。,如果数据中的任何两个元素间都可能有邻接关系，那么就说它们之间的关系是图状的。如果所要处理的数据之间呈图状关系，那么就说它的逻辑结构是图状的。图状关系是数据间最复杂的关系。 图1-4所示为一张航空网络图。在图状关系中，找不到谁是起点，谁是终点，各个结点的地位可以说都是相同的。,3图状关系,图1-4 航空网络,图状关系的特点是：每个结点都可能与多个结点有邻接关系。数据间的线性关系和树型关系，都可以视为是图状关系的一个特例。

6、,1.2 数据的存储结构,在计算机里存放数据时，既要存储数据本身，也要存储数据间的邻接关系。这样，在对数据进行加工处理时，才能够方便、正确地从一个数据找到与之邻接的另一个数据。 数据的“存储结构”，就是研究数据在内存中的存储方式，也就是在内存中有哪些存放数据的方法。数据的存储结构也称为数据的“物理结构”。,在把数据存储到存储器时，是以数据元素（即数据结点）为单位进行的。分配给一个数据结点的存储区域，称为一个“存储结点”。在一个存储结点里，除了要有数据本身的内容外，还要有体现数据间邻接关系的内容。,所谓数据的“顺序式存储”结构，即是为一组数据分配一个连续的存储区，然后按照数据间的邻接关系，相继存

7、放每个数据。这种存储结构，是借助存储结点间的位置关系，来体现数据元素间的邻接关系的。,1.2.1 顺序式存储结构,比如，图1-5左侧为一个数据元素所需要的存储尺寸：size字节，图1-5右侧所示为在内存里开辟了一个连续的存储区，用来依次存放数据的若干个存储结点。,图1-5 顺序存储结构,所谓数据的“链式存储”结构，即是存储每个数据的存储结点都由两个部分组成，一部分用来存放数据元素本身的信息，另一部分用来存放与本数据元素邻接的数据元素存储结点的位置，即存储指向与之邻接的存储结点的指针（起始地址），通过这些指针反映出数据间的逻辑关系。 图1-6给出的是一个链式存储结构。,1.2.2 链式存储结构,

8、图1-6 链式存储结构,在链式存储结构中，存储结点里的指针并不局限于只能是一个，而应根据问题的需要安排为一个或多个。如果采用链式存储结构时，存储结点里只有一个指针，则称是单链式结构；如果存储结点里有两个指针，则称是双链式结构；如此等等。,1.3 算法及算法分析,实现数据的加工处理时，如果问题较大、较复杂，就应该先通过分析列出与加工处理相关的各个步骤，然后再去用某种计算机程序设计语言编写出程序在计算机上运行。第一步就是所谓的算法描述，第二步就是所谓的程序实现。,1算法和程序的区别,1.3.1 算法及算法的描述,算法和计算机程序是两个不同的概念。 所谓“算法”，是指解决问题的一种方法步骤或者一个过

9、程。对于一个问题，可以用多种算法来解决；而一个给定的算法，则只解决一个特定的问题。 一个算法应该具有以下几个重要的特征。,（1）输入：一个算法应该有n（n0）个初始的输入数据。 （2）输出：一个算法可以没有或有一个或多个输出信息，它们与输入数据之间会有着某种特定的关系。,（3）确定性：算法中的每一个步骤都必须具有确切的含义，不能有二义性。 （4）可行性：算法中描述的每一个操作步骤都必须是可以执行的，也就是说，都可以通过计算机实现。 （5）有穷性：一个算法必须在经历有限个步骤之后正常结束，不能形成死循环。,例1-1 判断下面用文字描述的计数过程是否构成一个算法。 （1）开始； （2）n=0； /

10、* 变量n赋初值0 */ （3）n=n+1； /* 变量n增1 */ （4）重复执行（3）； /* 循环执行增1操作 */ （5）结束。,例1-2 编写一个算法，按照从小到大的顺序排列两个数值变量x、y的内容，即要求最终有xy。 解：用文字描述解决这个问题的算法如下： （1）输入变量x、y的数值； （2）把两个数值中的小者存放到x里； （3）把两个数值中的大者存放到y里； （4）输出x、y的值。 可以看出，上面的描述符合算法的5个特征。,所谓“程序（Program）”，是指使用某种计算机程序设计语言对一个算法的具体实现。比如，例1-2的算法，可以用如下的C语言程序来实现。 算法侧重于对解决问题

11、的方法描述，即要做些什么；而程序是算法在计算机程序设计语言中的实现，即具体要怎样去做。,#include “stdio“ main() int x, y, temp; scanf (“%d%d“, /* 打印输出 */ ,算法是可以用不同方法来描述的，下面给出几种常见的方法。,2算法的描述, 算法描述方法1：使用人们习惯的自然语言来描述算法。 算法描述方法2：使用人们熟悉的流程图（即框图）来描述算法。,例1-4 用流程图描述输出整数1、2、3、9、10的过程。 解：用流程图描述输出整数1、2、3、9、10的过程的算法如图1-8所示。,图1-7 流程图的各种图形名称和作用,图1-8 用流程图描述

12、算法, 算法描述方法3：用“类C语言”来描述算法。 本书将采用类C语言来描述算法。 算法描述方法4：直接采用C语言来描述算法。,例1-5 分别用C语言和类C语言来描述输出整数1、2、3、9、10的过程。 解：（1）用C语言描述输出整数1、2、3、9、10的过程的算法如下。 void num () int i; i=1; while (i= 10) printf (“i = %dn“, i ); i = i +1; ,（2）用类C语言描述输出整数1、2、3、9、10的过程的算法如下。 void num () i=1; while (i= 10) printf (“i = %dn“, i ); i

13、 = i +1; ,对同一个问题可以设计出不同的算法，它们之间当然有好差之分。判定算法质量时应遵循下面的几条原则：,1.3.2 算法分析, 算法是否易读，易于人们理解； 算法的结构是否简明、清晰； 算法的执行效率是否高； 算法的存储利用率是否高； 算法的可移植性是否好。,在算法分析中，人们最看重的是执行效率（时间）和存储利用率（空间）这两个问题。在数据结构里，对一个算法执行效率的度量，称为“时间复杂度”；对一个算法在执行过程中所需占用存储空间的度量，称为“空间复杂度”。,例1-6 变量a、b、c、d中各存一个整数，求a、b、c中的最大者与d的乘积的算法。,void max1 (a, b, c,

14、 d) a = a*d; b = b*d; c = c*d; if (ab) x = a; else x = b; if (cx) x = c; printf (“%dn“, x); ,图1-9 max1的流程,算法2为： void max2 (a, b, c, d) if (ab) x = a; else x = b; if (cx) x = c; x = x*d; printf (“%dn“, x); ,图1-10 max2的流程,“基本操作”是指算法中那些所需时间与操作数的具体取值无关的操作。赋值、两个数相加或两个数比较大小等，都可以作为基本操作，这些操作的执行时间与具体操作数是无关的。

15、,例1-7 分析下面所给算法段中基本操作的执行次数。 for (i = 1; i n; i+) y = y +1; for (j = 0; j= (2*n); j+) x+; ,例1-8 分析下面所给算法段的时间复杂度。 x = 0; y = 1; for (j=1; j=n; j+) s = x + y; y = x; x = s; ,常见的时间复杂度数量级有如下几种。 常量阶 记为O(1)。具有这种时间复杂度的算法，其执行所花费的时间是一个常量，表明该算法与问题的规模无关。, 线性阶 记为O(n)。具有这种时间复杂度的算法，其执行所花费的时间与问题的规模成正比，呈现出一种线性关系。 平方阶 记为O(n2)。具有这种时间复杂度的算法，其执行所花费的时间按问题规模的平方倍增长。比如，问题的规模n加倍时，算法的时间复杂度就增长4倍；当问题规模增加4倍时，算法的时间复杂度将增长16倍。, 立方阶 记为O(n3)。具有这种时间复杂度的算法，其执行所花费的时间按问题规模的立方倍增长。比如，问题的规模n加倍时，算法的时间复杂度就增长8倍。 对数阶 O(log2n)或O(nlog2n)都表示时间复杂度是对数阶的算法。与O(n2)或O(n3)比，具有对数阶的时间复杂度的算法，其时间的增长速度相对会缓慢一些。,