资源描述
数 据 结 构,蒋洪波 华中科技大学电信系 (hongbojiang2004) ,2,3,数据结构课程的地位,针对非数值计算的程序设计问题,研究计算机的操作对象以及它们之间的关系和操作。 是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,关系,对象 关系 操作,对象 关系 操作,Data_Structure=(D, R),4,学时数:56(4412) 教 材:严蔚敏等,数据结构(C语言版),清华大学出版社,1997年4月第1版 (配题集) 参考书: 1 高一凡,数据结构算法实现及解析(第二版),西电出版社,2004年10月 2 李春葆,数据结构(C语言篇)-习题与解析(修订版),清华大学出版社,2002年4月 2 殷人昆等,数据结构(用面向对象方法与C+描述),清华大学出版社,1999年7月(2002年配题集),5,内 容 安 排,第1-12周,周二9-10节 第1-12周,周四1-2节,6,目 录,第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序,7,第1章 绪 论,讨论5个问题:,1.1 什么是数据结构 1.2 学习数据结构的意义 1.3 数据结构涵盖的主要内容 1.4 什么是抽象数据类型 1.5 算法效率的度量,8,1.1 什么是数据结构,是相互之间存在一种或多种特定关系的数据元素的集合,表示为:,(数值或非数值),Data_Structure=(D, R),是指同一数据元素类型中各元素之间存在的关系,元素有限集,关系有限集,9,数据(data)所有能被计算机识别、存储和处理的符号的集合(包括数字、字符、声音、图像等信息 )。 数据元素(data element)是数据的基本单位,具有完整确定的实际意义(又称元素、结点,顶点、记录等)。 数据项(Data item)构成数据元素的项目。是具有独立含义的最小标识单位(又称字段、域、属性 等)。,三者之间的关系:数据 数据元素 数据项,例:班级通讯录 个人记录 姓名、年龄,数据、数据元素和数据项,术语简介:,10,1.2 学习数据结构的意义,计算机内的数值运算依靠方程式,而非数值运算(如表、树、图等)则要依靠数据结构。 数据结构是一门学科,针对非数值计算的程序设计问题,研究计算机的操作对象以及它们之间的关系和操作等等。,程序设计好算法好结构,同样的数据对象,用不同的数据结构来表示,运算效率可能有明显的差异。,11,1.3 数据结构涵盖的内容,12,集合结构: 仅同属一个集合 线性结构: 一对一(1:1) 树 结 构: 一对多(1:n) 图 结 构: 多对多 (m:n),非线性,线 性,逻辑结构可细分为4类:,答:指数据元素之间的逻辑关系。即从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。,解释1: 什么叫数据的逻辑结构?,13,(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,此结构为线性的。,例:用图形表示下列数据结构,并指出它们是属于线性结构还是非线性结构。,14,d1 d5 d2 d4 d3,该结构是非线性的。,解:上述表达式可用图形表示为:,(2) S=(D, R) D=di | 1i5 R=(di , dj ), ij,15,答:物理结构亦称存储结构,是数据的逻辑结构在计算机存储器内的表示(或映像)。它依赖于计算机。,存储结构可分为4大类:,例:复数3.02.3i 的两种存储方式:,顺序、链式、索引、散列,法1:地址 内容,法2:地址 内容,2字节,解释2:什么叫数据的物理结构?,16,答:在数据的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。,最常用的数据运算有 5 种:,插入、删除、修改、查找、排序,解释3:什么是数据的运算?,17,1.4 什么是抽象数据类型,1.4.1 数据类型与抽象数据类型的区别? 1.4.2 抽象数据类型如何定义? 1.4.3 抽象数据类型如何表示和实现?,讨论:,抽象数据类型和伪码是学习数据结构的工具,18,ADT =Abstract Data Type,1.4.1 数据类型与抽象数据类型的区别,数据类型:是一个值的集合和定义在该值上的一组操作的总称。,抽象数据类型:由用户定义的一个数学模型与定义在该模型上的一组操作,它由基本的数据类型构成。,ADT与数据类型实质上是一个概念,但其特征是使用与实现分离,实行封装和信息隐蔽(独立于计算机) “抽象”的意义在于数据类型的数学抽象特性,19,1.4.2 抽象数据类型如何定义,抽象数据类型可以用以下的三元组来表示: ADT = (D,R,P),ADT抽象数据类型名 数据对象: 数据关系: 基本操作 : ADT抽象数据类型名,ADT常用定义格式,数据对象,D上的关系集,D上的操作集,20,例1:给出自然数(Natural Number )的抽象数据类型定义。,ADT Natural_Number 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)返回 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 Natural_Number,“抽象”的意义在于数据类型的数学抽象特性,21,1.4.3 抽象数据类型如何表示和实现,抽象数据类型可以通过固有的数据类型(如整型、实型、字符型等)来表示和实现。,注1 :它有些类似C语言中的结构(struct)类型,但增加了相关的服务(或操作)。 注2 :教材中用类C语言(介于伪码和C语言之间)作为描述工具。其描述语法汇总在教材P10-11上。,但上机时要用具体语言实现,如C或C+等,22,提示: 教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现,请自己先试读一遍。 当课程学到50%以后,你再回头看这个例子,会发现自己已能完全看懂了!,例2:给出抽象数据类型三元组(Triplet)的定义。,23,例2:给出抽象数据类型三元组(Triplet)的定义。,ADT Triplet 数据对象:D=e1,e2,e3 | e1,e2,e3 ElemSet, (定义了关系运算的某个集合) 数据关系:R1=, 基本操作: InitTriplet(&T,v1,v2,v3) /建三元组,给e1,e2,e3赋初值 DestroyTriplet(&T) /销毁三元组 Get(T, i, &e) /读取第i元的值输出给e Put(T,i,e) /修改第i元的值=e IsAscending(T) /三元素单调增则返回1,否则返回0 IsDscending(T) /三元素单调减,则返回1,否则返回0 Max(T, &e) /求三元素中的最大值并输出给e Min(T, &e) /求三元素中的最小值并输出给e ADT Triplet,“抽象”的意义在于数据类型的数学抽象特性,24,1.5 算法效率的度量,1.5.1 什么是算法?如何评判算法的好坏? 1.5.2 时间复杂度和空间复杂度如何表示? 1.5.3 计算举例,讨论:,25,1.5.1 什么是算法?如何评判一个算法的好坏?,常用时间复杂度来衡量,算法的基本特性:,算法评价指标:,有穷性、确定性、可行性、必有输出,正确性、可读性、健壮性、效率与低存储量需求,常用空间复杂度来衡量,程序设计的实质:好算法好结构,算法是对特定问题求解步骤的一种描述,它是指令的有限序列,是一系列输入转换为输出的计算步骤。,26,注: 1) O()为渐近符号。 2) 空间复杂度S(n)按数量级递增顺序也与上表类似。,复杂度高,复杂度低,时间复杂度T(n)按数量级递增顺序为:,1.5.2 时间复杂度和空间复杂度如何表示?,多项式阶,27,3n+2=O(n) 因为 3n+24n for n2 6*2n+n2=O(2n) 因为6*2n+n2 7*2n for n4,例:,渐进符号(O)的定义:当且仅当存在一个正的常数 C,使得对所有的 n n0 ,有 f(n) Cg(n),则: f(n) = O(g(n),28,1.5.3 计算举例,该算法的运行时间由程序中所有语句的频度(即该语句重复执行的次数)之和构成。,解:,分析:显然,语句的频度是1。设语句2的频度是f(n),则有:,算法的时间复杂度由嵌套最深层语句的频度决定,即f(n)log2n,取最大值f(n)=log2n,所以该程序段的时间复杂度T(n)=1+f(n)=1+ log2n= O( log2n),29,本章小结,数据结构课程 数据结构算法程序,涉及数学、计算机硬件和软件。 数据结构定义指互相有关联的数据元素的集合,可用data_Structure=(D,R)表示。 数据结构内容数据的逻辑结构、存储结构和基本运算(计算机处理非数值对象) 数据结构学习工具抽象数据类型和伪码(类C) 算法效率指标时间效率和空间效率,第1章结束,30,作业:,见 :8001/classroom/, 配套习题集的1.6 1.7 1.8 1.10 1.17 1.20 题。 复习C语言,重点是结构类型和递归概念。,
展开阅读全文