[农学]数据结构 第1章 绪论.ppt

《[农学]数据结构 第1章 绪论.ppt》由会员分享，可在线阅读，更多相关《[农学]数据结构 第1章 绪论.ppt（67页珍藏版）》请在三一文库上搜索。

1、数据结构,主讲：朱付保 邮箱： 电话：13503836121,前言,教学目的为什么学习数据结构？ 教学要求 本课程的主要内容,教学目的,1、掌握常用的基本数据结构的ADT及其应用。 2、学会合理地组织数据，有效的表示数据，有效的处理数据。 3、初步掌握算法时间空间分析的技巧。 4、提高程序设计的质量,考试成绩安排,平时成绩、实验成绩占30 期末卷面成绩占70,学习要求与期望,课堂不允许喧哗，不允许迟到！ 实验课一定要带着提前写好的程序清单，否则取消上机实验资格! 不要放弃任何一个没有调试成功的程序！ 建议大家养成课前预习，课下编写、实现程序的习惯。,本课程的主要内容,第一部分： 数据结构的基本

2、概念 第二部分： 基本的数据结构 线性结构线性表、栈和队列、 串、 数组与广义表； 非线性结构树、 图。 第三部分： 基本技术 查找技术与排序技术。,1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的概念 1.4 算法和算法分析,第一章 绪论,1.1 什么是数据结构,一、为什么要学习数据结构？ 电子计算机的主要用途： 早期： 主要用于数值计算。计算数学 后来： 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。,例1 电话号码查询问题 （1）按顺序存储方式：须遍历表 （2）按姓氏索引方式：索引,非数值计算问题,例1 电话号码查询问题 问题：分别在两种结

3、构上查找“孙十”、“刘八”所需时间 ？ “孙十”：顺序查找，需要8次，折半查找，需要1次； “刘八”：顺序查找，需要6次，折半查找，需要2次； 要写出好的查找算法，取决于这张表的结构及存储方式。 电话号码表的结构和存储方式决定了查找（算法）的效率。,非数值计算问题,例1 电话号码查询问题,非数值计算问题,顺序查找与折半查找 耗时对比,例2 人机对奕问题,例3 田径赛的时间安排问题 设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。(无向图的着色问题),（1）设用如下六个不同的代号代表不同的项目： 跳高 跳远 标枪

4、铅球 100米 200米 A B C D E F （2）用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。 （3）某选手比赛的项目必定有边相连（不能同时比赛）。,-田径赛的时间安排问题解法,A,E,B,F,D,C,只需安排四个单位时间进行比赛,田径赛赛程安排问题图的顶点着色问题,A,C,B,F,D,E,例4 多叉路口交通灯管理问题：单行道，可同时通行的路，不可同时通行的路。,1. 每条路用一个顶点表示,2. 不能同时通行的路中间连一条线,3. 对没有线相连的顶点着色,例5：求两个整数相乘的积 （1）简单情况：用整型变量 c=a*b （2）如果a或b超出最大的整数时该怎么办？此时，如何a

5、与b的积？,解决 (1) 用字符串表示每个大整数 办法 (2) 用整型数组：每个元素表示“大整数”中的一个数字,大整数问题,学习数据结构有什么用？,计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。,程序设计：为计算机处理问题编制一组指令集 算法：处理问题的策略 数据结构：问题的数学模型,同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。,程序=数据结构+算法(尼克劳斯.沃尔斯）,概括什么是数据结构,数据结构描述现实实体的数学模型（非数值计算）及其上的操作在计算机中的表示和实现。,二、数据结构课程的形成和发展： 形成阶段： 60年代初期，“数据结构”

6、有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。,三、数据结构课程所处的地位：,1.2 基本概念和术语 数据: 是指所有能输入到计算机中并被计算机程序处理的符号的总称。是对信息的一种符号表示。,数据元素:,是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项 一个数据元素可由若干个数据项组成。是数据的不可分割的最小单位,例如：学生卡片记录表,数据结构定义- 带结构的数据元素

7、的集合 例1，运动会的比赛结果，按获得名次进行排名： 若三个运动员分别获得1、2、3名， 可用三个字符串表示： s1(zhangsan), s2(lisi), s3(wangwu) 显然这三个名字有“次序”关系，先后顺序不能颠倒 s1(zhangsan), s2(lisi), s3(wangwu) s1(zhangsan), s3(wangwu), s2(lisi),数据结构定义- 带结构的数据元素的集合 例2, 两行三列的二维数组a1, a2, a3, a4, a5, a6,行的次序关系：, , 列的次序关系：, , ,数据结构定义- 带结构的数据元素的集合 例3： 老师、研究生、本科生之间

8、的指导关系： T1指导研究生M1, M2, M1指导本科生S1, S2, S3。 则计算机不仅要存储T1, M1, M2, S1, S2, S3, 还要表示他们之间的关系， , , , , ,数据结构的形式定义为：,数据结构是一个二元组： Data_Structures=(D, S) 其中： D是数据元素的有限集 S是D上关系的有限集,S在计算机中如何存储和实现，是数据结构讨论的重点存储结构,数据结构的主要内容： 具体来说，数据结构包含三个方面的内容，即 数据的逻辑结构 数据的存储结构 对数据所施加的运算（操作）。,这三个方面的关系为： 数据的逻辑结构独立于计算机，是数据本身所固有的。 存储结

9、构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。 运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必须依赖于存贮结构。,逻辑结构-划分方法 一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。 二、线性结构 结构中的数据元素之间存在一对一的关系。 三、树型结构 结构中的数据元素之间存在一对多的关系。,四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。,存储结构（Storge Structure):数据结构在计算机中的表示(或称映象）称为数据的存储结构，又称为物理结构。 四种基本的存储方法： （1）顺序存储方法（顺序存储结构） （2）链接存储方

10、法（链式存储结构） （3）索引存储方法 （4）散列存储方法 同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。,顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。,数据的逻辑结构,数据的存储结构,数据的运算：检索、排序、插入、删除、修改等,线性结构,非线性结构,顺序存储,链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个方面：,散列存储,索引存储,串及数组,例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线

11、性结构。,（1） S=(D, R) D= a, b, c, d, e, f R=(a,e), (b,c), (c,a), (e,f), (f,d),解： 上述表达式可用图形表示为：,b c a e f d,此结构为线性的。,（2） S=(D, R) D=di | 1i5 R=(di , dj ), ij,d1 d5 d2 d4 d3,该结构是非线性的。,解：上述表达式可用图形表示为：,1.3 抽象数据类型概念(ADT),Q1 数据类型与抽象数据类型的区别？ Q2 抽象数据类型如何定义？ Q3 抽象数据类型如何表示和实现？,讨论：,提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的

12、定义、表示和实现，请试阅读。,数据类型：在一种程序设计语言中，变量所具有的数据种类。 例1、 在FORTRAN语言中，变量的数据类型有整型、实型、和复数型 例2、在C语言中 数据类型：基本类型和构造类型 基本类型：整型、浮点型、字符型 构造类型：数组、结构、联合、指针、枚举型、自定义,Q1 数据类型与抽象数据类型的区别？,数据类型：是一个值的集合和定义在该值上 的一组操作的总称。,抽象数据类型：是一个数学模型以及定义在此模型上的一组操作）,它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。,Q2 抽象数据类型如何定义？,抽象数据类型可以用以下的三元组来

13、表示： ADT = （D，S，P） 数据对象 D上的关系集 D上的操作集,ADT抽象数据类型名 数据对象： 数据关系： 基本操作 ： ADT抽象数据类型名,ADT常用定义格式,class Triangle float a, b, c, area; Triangle (float sa, float sb, float sc) a = sa; b = sb; c = sc; float getCircumference() return a + b + c; float getArea() area = /; return area; void modiSideA(float sa) a = s

14、a; float getSideA() return a; ,Q3 抽象数据类型如何表示和实现？,抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。,注1 ：它有些类似C语言中的结构(struct)类型，但增加了相关的服务。 注2 ：教材中用的是类C语言（介于伪码和C语言之间）作为描述工具。其描述语法见P10-11。,但上机时要用具体语言实现，我们用C语言,1.4 算法和算法分析 一、算法的概念和描述： 1、什么是算法？ 是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。,2、 算法描述 算法具有以下五个特性： （1）有穷性 一个算

15、法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 （2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。 （3）可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。,4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。,算法设计的要求 评价一个好的算法有以下几个标准: (1) 正确性(Correctness ) 算法应满足具体问题的需求。 (2)可读性(Readability) 算法应该好读。以有利于阅读者对程序

16、的理解，便于调试和修改。 (3)健状性(Robustness) 算法应具有容错处理。 (4)效率与存储量需求 效率指的是算法执行的时间和存储空间。一般，这两者与问题的规模有关。,注意：算法和程序的关系,算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。,二、算法的描述和实现 描述-可采用自然语言、数学语言或约定的符号语言。 实现-必须借助程序设计语言提供的数据类型及其运算。 本课的描述-采用类C语言。,类C语言,(1) 预定义常量和类型。 本书中用到

17、以下常量符号，如True、False、MAXSIZE等，约定用如下宏定义预先定义： define TRUE 1 define FALSE 0 define MAXSIZE 100 define OK 1 define ERROR 0,(2) 本书中所有的算法都以如下的函数形式加以表示， 其中的结构类型使用前面已有的定义。 数据类型 函数名（形式参数及说明） 内部数据说明； 执行语句组； /*函数名*/ 函数的定义主要由函数名和函数体组成，函数体用花括号“”和“”括起来。 函数中用方括号括起来的部分如“形式参数”为可选项， 函数名之后的圆括号不可省略。,(3) 一些基本的函数， 例如： max函

18、数： 用于求一个或几个表达式中的最大值； min函数： 用于求一个或几个表达式中的最小值； abs函数： 用于求表达式的绝对值； eof函数： 用于判定文件是否结束； eoln函数： 用于判断文本行是否结束。,三、算法分析,1. 性能评价 对问题规模和该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。 问题规模N对不同的问题其含义不同，对矩阵是阶数， 对多项式运算是多项式项数，对图是顶点个数，对集合运算是集合中的元素个数。,2. 有关数量关系的计算 时间算法编程后在机器中所耗费的时间。 空间算法编程后在机器中所占的存储量。 1）关于算法执行时间 一个算法的执行时间大致上等于其所

19、有语句执行时间的总和， 对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。 ,2）语句频度 语句频度是指该语句在一个算法中重复执行的次数。 例1-1 两个nn阶矩阵相乘。,1 for(i=0; in; i+) 2 for(j=0; jn; j+) 3 cij=0; 4 for(k=0; kn; k+) 5 cij =cij + aik * bkj; 6 ,该算法每条语句执行的频度 n n2 n2 n3 n3,3）算法的时间复杂度 原操作是指从算法中选取一种对所研究问题是基本运算的操作，用随着问题规模增加的函数来表征, 以此作为时间量度。 而对于算法分析，我们关心的是算法中语句总

20、的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级（Order of Magnitude）。 在这里， 我们用“O”来表示数量级，这样我们可以给出算法的时间复杂度概念。 所谓算法的时间复杂度， 即是算法的时间量度，记作： T(n)=O(f(n),4） 数据结构中常用的时间复杂度频率计数 数据结构中常用的时间复杂度频率计数有7个： O(1) 常数型 O(n)线性型 O(n2)平方型 O(n3)立方型 O(2n)指数型 O(log2n)对数型 O(nlog2n)二维型 一般情况下，随n的增大，T(n)增长较慢的算法为最优的算法。从中我们应该选择使用多项式

21、阶O(nk)的算法，而避免使用指数阶的算法。,时间复杂度的重要性,举例： 选择排序的基本操作频度：n*(n-1)/2 归并排序的基本操作频度：n*logn-n+1 试比较选择排序和合并排序，设一次比较需要10-6秒（1纳秒） 若规模为n=128 选择排序 所需时间为10-6（128127）/2=0.008秒 归并排序所需时间为10-6（1277-128+1）=0.0008秒,是否令你吃惊？,若规模为n=1M=220 选择排序 所需时间为 10-6（220(220-1)/2=6.4天 归并排序所需时间为 10-6（22020-220+1）=20秒,表1-3 常用的时间复杂度频率表,多种数量级的时

22、间复杂度图示,常见数量级的时间复杂度图示,例如： 下列程序段： for (i=1; i n; i+) for (j=i; j= n; j+) x+; 有一个二重循环， 语句x+的执行频度为 n+(n-1)+(n-2)+3+2+1 =n(n+1)/2 而该语句执行次数关于n的增长率为n2, 即时间复杂度为O(n2)。,5） 最坏时间复杂度 算法中基本操作重复执行的次数还随问题的输入数据集的不同而不同。 例如下面冒泡排序算法：,void bubble(int a , int length) 将a中整数数组重新排序， 达到递增有序 int i=0, j, temp; int change=true;

23、 ,for(i=n-1; i=1 ,此时，算法的评价时间复杂度难以确定。,因此，一种最可行也是最常用的办法是讨论算法在最坏情况下时间复杂度。,如果在某趟比较时，没有进行数据交换，则说明已经有序，无需再进行排序操作。排序算法提前终止执行。,6) 算法的空间复杂度,类似于算法的时间复杂度，我们采用空间复杂度作为算法所需存储空间的量度，记作： S(n) = O( f(n) ),一个算法除需要存储空间来存储本身所用的指令、常量、变量和输入数据外，还需要存储一些为实现计算所需信息的辅助空间。,若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间，否则应同时考虑输入数据本身所占的存储空间。, 本章小结 数据、数据结构等基本概念 数据结构的三个方面的内容 抽象数据类型的概念 线性和非线性结构的逻辑特征 数据存储的四种基本方法 算法的概念和特征 算法的时间复杂度及其分析方法,