数据结构课件(清华版)

《数据结构课件(清华版)》由会员分享，可在线阅读，更多相关《数据结构课件(清华版)（539页珍藏版）》请在金锄头文库上搜索。

1、数据结构 Data Structure河南大学计算机与信息工程学院 83,学 分： 5 教 材：严蔚敏等，数据结构（C语言版），清华大学出版社，1997年4月 参考书： 1 殷人昆等，数据结构（用面向对象方法与C+描述），清华大学出版社，1999年7月。￥26 2 殷人昆等，数据结构习题解析，清华大学出版社，2002年4月。￥26 3 李春葆，数据结构习题与解析（C语言篇），清华大学出版社，2001年1月。￥28 4 严蔚敏等，数据结构题集(C语言版)，清华大学出版社， 1997年4月。￥16,内 容 安 排,注：本学期共85学时，机动5学时。,第1章 序 论,1.1 什么是数据结构 1.2

2、基本概念和术语 1.3 抽象数据类型的表示和实现 1.4 算法和算法分析,作业,5,1.1 什么是数据结构,Q1 如何采用计算机解决问题？ Q2 数据结构解决什么样的问题？ Q3 数据结构课程介绍,6,Q1：如何采用计算机解决问题？,答：,寻求数学模型的实质：分析问题，从中提取操作的对象，并找出这些 操作对象之间含有的关系，然后用数学的语言加以 描述。,(2) 设计解此数学模型的算法；,(1) 从具体问题抽象出一个适当的数学模型；,(3) 编程，测试、调整直至得到最终解答。,7,Q2：数据结构解决什么样的问题？,答：,数据结构研究非数值计算的程序设计问 题中计算机的操作对象以及它们之间的关系

3、和操作等的学科。,8,介于数学、计算机硬件和计算机软件三者之间的一门核心课程,关系,对象 关系 操作,对象 关系 操作,Q3：数据结构课程介绍,1.2 基本概念和术语,Q1 什么是数据结构？ Q2 学习数据结构有什么用？ Q3 数据结构涵盖的主要内容？,讨论：,Q1：什么是数据结构？,答: (见教材P5) 是相互之间存在一种或多种特定关系的数据元素的集合，表示为：,（数值或非数值）,Data_Structure=（D, S）,或：是指同一数据元素类中各元素之间存在的关系。,亦可表示为：S（D, R） 或 B=（K, R）,元素有限集,关系有限集,术语：数据、数据元素和数据项,（见教材P4定义）

4、： 数据(data)所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息 ）。 数据元素(data element)是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。 数据项(Data item)构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性 等）。,三者之间的关系：数据 数据元素 数据项,例：班级通讯录 个人记录 姓名、年龄,Q2：学习数据结构有什么用？,答：计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科

5、。,程序设计实质好算法好结构,同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。,Q3：数据结构涵盖的内容？,解释1： 什么叫数据的逻辑结构？,答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。逻辑结构可细分为4类：,集合结构： 仅同属一个集合线性结构: 一对一（1:1) 树 结 构: 一对多（1:n)图 结 构: 多对多 (m:n),非线性,线 性,例：用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。,（1） S=(D, R)D= a, b, c, d, e, f R=(a,e), (b,c), (c,a), (e,

6、f), (f,d),解： 上述表达式可用图形表示为：,b c a e f d,此结构为线性的。,（2） S=(D, R) D=di | 1i5 R=(di , dj ), ij,d1d5 d2d4 d3,该结构是非线性的。,解：上述表达式可用图形表示为：,解释2：什么叫数据的物理结构？,答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。,存储结构可分为4大类：,例：（见教材P6）复数3.02.3i 的两种存储方式：,顺序、链式、索引、散列,法1：地址 内容,法2：地址 内容,2字节,解释3：什么是数据的运算？,答：在数据的逻辑结构上定义的操作算法。 它

7、在数据的存储结构上实现。,最常用的数据运算有5种：,插入、删除、修改、查找、排序,1.3 抽象数据类型的表示和实现,Q1 数据类型与抽象数据类型的区别？ Q2 抽象数据类型如何定义？ Q3 抽象数据类型如何表示和实现？,讨论：,提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请试阅读。,Q1 数据类型与抽象数据类型的区别？,数据类型：是一个值的集合和定义在该值上的一组操作的总称。,抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）,它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息

8、隐蔽（独立于计算机）。,Q2 抽象数据类型如何定义？,抽象数据类型可以用以下的三元组来表示：ADT = （D，S，P）数据对象 D上的关系集 D上的操作集,ADT抽象数据类型名 数据对象：数据关系： 基本操作 ： ADT抽象数据类型名,ADT常用定义格式,例：给出自然数(Natural Number )的抽象数据类型定义。,ADT Natural_Number is objects: 一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数 (MAX INT) functions: 对于所有的 x, y Natural_Number； TRUE, FALSE Boolean； +, -,

9、, = = ,=等都是可用的服务。 Zero ( )： Natural Number 返回 0 IsZero(x)： Boolean if (x=0) 返回TRUE else 返回 FALSE Add(x, y)： Natural Number if (x+y = MAX INT)返回 x+yelse 返回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 =

10、 MAX INT)返回x else 返回x+1 end Natural_Number,Q3 抽象数据类型如何表示和实现？,抽象数据类型可以通过固有的数据类型 （如整型、实型、字符型等）来表示和实现。即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。,注 ：教材中用的是类C语言（介于伪码和C语言之间）作为描述工具。其描述语法见P10-11。,但上机时要用具体语言实现，如C或C+等,1.4 算法和算法分析,Q1. 什么是算法？ Q2. 算法设计的要求？ Q3. 时间复杂度如何表示？ Q4. 空间复杂度如何表示？,讨论：,答：算法是解决某一特定类型问题的有限运算 序列。是

11、一系列输入转换为输出的计算步骤。,Q1. 什么是算法？,算法有5个基本特性：,有穷性、确定性、可行性、输入和输出,26,Q2. 算法设计的要求？,答：,(1) 正确性,(2) 可读性,(3) 健壮性,(4) 效率与低存储需求,时间复杂度T(n)按数量级递增顺序为：,注1 O（）为渐近符号。 注2 空间复杂度S(n)按数量级递增顺序也与上表类同。,复杂度高,复杂度低,Q3. 时间复杂度如何表示？,渐进符号（O）的定义：当且仅当存在一个正的常数 C，使得对所有的 n n0 ，有 f(n) Cg(n)， 则f(n) = O(g(n),3n+2=O(n) /* 3n+24n for n2 */ 3n+

12、3=O(n) /* 3n+34n for n3 */ 100n+6=O(n) /* 100n+6101n for n10 */ 10n2+4n+2=O(n2) /* 10n2+4n+211n2 for n5 */ 6*2n+n2=O(2n) /* 6*2n+n2 7*2n for n4 */,例：,例：分析以下程序段的时间复杂度。,i=1; while(i=n)i=i*2; ,该算法的运行时间由算法中所有语句的频度（即该语句重复执行的次数）之和构成。,解：,分析：显然，语句的频度是1。设语句2的频度是f(n)，则有：,即f(n)log2n，取最大值f(n)=log2n,所以该程序段的时间复杂度

13、T(n)=1+f(n)=1+ log2n= O( log2n),算法的时间复杂度是由嵌套最深层语句的频度决定的。,30,Q4. 空间复杂度如何表示？,S(n) = O(f(n),一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。,原地工作：若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。,注：若额外空间所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。,作业：,思考:数据结构、数据类型、抽象数据类型的区别算法与程序的区别 2. 请试做配套习题集(P10_16)。 3.

14、 复习C+语言。,32,上堂课要点回顾,数据结构课程涉及数学、计算机硬件和计算机软件 数据结构定义指互相有关联的数据元素的集合，用D_S=( D, S ) 或 S=( D, R) 表示。 数据结构内容数据的逻辑结构、存储结构和运算 算法效率指标时间效率和空间效率,33,数据结构课程的内容,逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构,34,近3周 上课 内容,第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表,线性结构,若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。,可表示为：（a1 , a2 , , an）,线性结构的定义：,（逻辑、存储和运算）,35,线性结构的特点：, 只有一个首结点和尾结点； 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。,线性结构表达式：（a1 , a2 , , an）,线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是-,线性表,简言之，线性结构反映结点间的逻辑关系是 一对一 的,见第2章,36,第2章 线性表,2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例 （一元多项式的表示及相加）,