《数据结构PPT全套教学课件（完整版）》由会员分享，可在线阅读，更多相关《数据结构PPT全套教学课件（完整版）（543页珍藏版）》请在金锄头文库上搜索。
1、数 据 结 构,汪赫瑜 电子与信息工程学院计算机系,2019/11/1,2,数据结构课程的地位,针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。 是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,关系,对象 关系 操作,对象 关系 操作,Data_Structure=（D, R）,2019/11/1,3,学时数：80 教 材：严蔚敏等，数据结构（C语言版），清华大学出版社，1997年4月第1版 （配题集） 参考书： 1 殷人昆等，数据结构（用面向对象方法与C+描述），清华大学出版社，1999年7月（2002年配习题集） 2资讯教育小组，数据结构C语言版，中
2、国铁道出版社。,2019/11/1,4,第1章 绪 论,1.1 什么是数据结构 1.2 学习数据结构的意义 1.3 数据结构涵盖的主要内容 1.4 什么是抽象数据类型 1.5 算法效率的度量,2019/11/1,5,2019/11/1,6,数据结构产生的背景,例2 人机对奕问题,2019/11/1,7,例3多叉路口交通灯管理问题,2019/11/1,8,1.1 什么是数据结构,是相互之间存在一种或多种特定关系的数据元素的集合，表示为：,（数值或非数值）,Data_Structure=（D, R）,是指同一数据元素类型中各元素之间存在的关系。,元素有限集,关系有限集,2019/11/1,9,数据
3、(data)所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息 ）。 数据元素(data element)是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。 数据项(Data item)构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性 等）。,三者之间的关系：数据 数据元素 数据项,例：班级通讯录 个人记录 姓名、年龄,数据、数据元素和数据项,术语简介：,2019/11/1,10,2019/11/1,11,1.2 学习数据结构的意义,计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。 数据结构是一
4、门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等等。,程序设计好算法好结构,同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。,2019/11/1,12,1.3 数据结构涵盖的内容,2019/11/1,13,集合结构： 仅同属一个集合 线性结构: 一对一（1:1) 树 结 构: 一对多（1:n) 图 结 构: 多对多 (m:n),非线性,线 性,逻辑结构可细分为4类：,答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。,解释1： 什么叫数据的逻辑结构？,2019/11/1,14,（1） S=(D, R
5、) D= a, b, c, d, e, f R=(a,e), (b,c), (c,a), (e,f), (f,d),解： 上述表达式可用图形表示为：,b c a e f d,此结构为线性的。,例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。,2019/11/1,15,d1 d5 d2 d4 d3,该结构是非线性的。,解：上述表达式可用图形表示为：,（2） S=(D, R) D=di | 1i5 R=(di , dj ), ij,2019/11/1,16,答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。,存储结构可分为4大类：,例：
6、复数3.02.3i 的两种存储方式：,顺序、链式、索引、散列,法1：地址 内容,法2：地址 内容,2字节,解释2：什么叫数据的物理结构？,2019/11/1,17,答：在数据的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。,最常用的数据运算有 5 种：,插入、删除、修改、查找、排序,解释3：什么是数据的运算？,2019/11/1,18,1.4 什么是抽象数据类型,1.4.1 数据类型与抽象数据类型的区别？ 1.4.2 抽象数据类型如何定义？ 1.4.3 抽象数据类型如何表示和实现？,讨论：,抽象数据类型和伪码是学习数据结构的工具,2019/11/1,19,1.4.1 数据类型与抽象数据
7、类型的区别,数据类型：是一个值的集合和定义在该值上的一组操作的总称。,抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）,它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）,2019/11/1,20,1.4.2 抽象数据类型如何定义,抽象数据类型可以用以下的三元组来表示： ADT = （D，R，P）,ADT抽象数据类型名 数据对象： 数据关系： 基本操作 ： ADT抽象数据类型名,ADT常用定义格式,数据对象,D上的关系集,D上的操作集,2019/11/1,21,例：给出自然数(Natural
8、Number )的抽象数据类型定义。,ADT Natural_Number is objects: 一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数 (MAX INT) functions: 对于所有的 x, y Natural_Number； TRUE, FALSE Boolean； +, -, , = = ,=等都是可用的服务。 Zero ( )： Natural Number 返回 0 IsZero(x)： Boolean if (x=0) 返回TRUE else 返回 FALSE Add(x, y)： Natural Number if (x+y = MAX INT)返回
9、x+y else 返回 MAX INT Subtract(x,y): Natural Number if (xy)返回0 else 返回x-y Equal(x,y): Boolean if (x= y)返回TRUE else 返回FALSE Successor(x) : Natural Number if (x = MAX INT)返回x else 返回x+1 end Natural_Number,2019/11/1,22,1.4.3 抽象数据类型如何表示和实现,抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。,注1 ：它有些类似C语言中的结构（struct)类型，但
10、增加了相关的服务。 注2 ：教材中用类C语言（介于伪码和C语言之间）作为描述工具。其描述语法汇总在教材P10-11上。,但上机时要用具体语言实现，如C或C+等,2019/11/1,23,提示： 教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请自己先试读一遍。 当课程内容学习到50%以后，你再回头看这个例子，会发现自己已能完全看懂了！,2019/11/1,24,1.5 算法效率的度量,1.5.1 什么是算法？如何评判算法的好坏？ 1.5.2 时间复杂度和空间复杂度如何表示？ 1.5.3 计算举例,2019/11/1,25,1.5.1 什么是算法？如何评判一个算法的好
11、坏？,常用时间复杂度来衡量,算法的基本特性：,算法评价指标：,有穷性、确定性、可行性、必有输出,正确性、可读性、健壮性、效率与低存储量需求,常用空间复杂度来衡量,程序设计的实质：好算法好结构,算法是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。,4个层次,2019/11/1,26,算法中实现基本操作的语句（基本语句）重复执行的次数，称为算法的频度。 记作：T(n)=O(f(n) 随问题规模n的增大，算法的频度T(n)和f(n)的增长率同阶。 例1： x+=5; 单个语句的频度为1，则 程序段的时间复杂度为T(n)=O(1)。,2019/11/1,27,1.
12、5.3 计算举例,该算法的运行时间由程序中所有语句的频度（即该语句重复执行的次数）之和构成。,解：,分析：T(n)=2n2 +2n+1 当n充分大时， T(n)与n2是同阶的。 该算法时间复杂度为：T(n)=O( n2 ),算法的时间复杂度由嵌套最深层语句的频度决定,2019/11/1,28,例题 s=0 /* 1 */ for (i=0; in; i +) /* n+1 */ for (j=0; jm; j +) /* n(m+1) */ s+=B ij; /* n*m */ sum=s /* 1 */ 时间复杂度:,T(n)=O(2(n*m)+2n+3)=O(n*m),2019/11/1,
13、29,注： 1） O（）为渐近符号。 2） 空间复杂度S(n)按数量级递增顺序也与上表类似。,复杂度高,复杂度低,时间复杂度T(n)按数量级递增顺序为：,1.5.2 时间复杂度和空间复杂度如何表示？,多项式阶,2019/11/1,30,本章小结,数据结构课程 数据结构算法程序，涉及数学、计算机硬件和软件。 数据结构定义指互相有关联的数据元素的集合，可用data_Structure=(D,R)表示。 数据结构内容数据的逻辑结构、存储结构和基本运算 数据结构学习工具抽象数据类型和伪码（类C） 算法效率指标时间效率和空间效率,第1章结束,2019/11/1,31,练习：,复习C语言，重点是结构体和递
14、归概念，链表操作。,有下列几种用二元组表示的数据结构，画出它们分别对应的图形表示，并指出它们分别属于何种结构 1）A=(K,R),其中： K=a,b,c,d,e,f,g,h R=r r=, 2) B=(K,R),其中： Ka,b,c,d,e,f,g,h R=r r=, 3)C=(K,R) K=1,2,3,4,5,6 R=r r(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6),2019/11/1,32,练习,计算下列程序段的时间复杂度： 1) i=s=0 while(sn) i+; S+=i; 2）i=1； while(i=n) i=i*2;,201
15、9/11/1,33,数据结构课程的起点：,2019/11/1,34,线性结构的定义：,若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。 可表示为：（a1 , a2 , , an）,简言之，线性结构反映结点间的逻辑关系是 的。,特点 只有一个首结点和尾结点； 特点 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。,线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是-,线性表,一对一 (1:1),2019/11/1,35,第2章 线性表,2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例,2019/11/1,36,（a1, a2, ai-1，ai, ai1 ，, an）,2.1 线性表的逻辑结构,线性表的定义：用数据元素的有限序列表示,n=0时称为,数据元素,
