数据结构课程介绍课件

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

1、数据结构Data Structure 教教 材：材：严蔚敏严蔚敏等，数据结构（等，数据结构（C语言版），清华大语言版），清华大学出版社学出版社参考书：参考书：1 殷人昆殷人昆等等，数据结构（用面向对象方法与数据结构（用面向对象方法与C+描描述），清华大学出版社，述），清华大学出版社，1999年年7月。月。2 殷人昆殷人昆等等，数据结构习题解析，清华大学出版社，数据结构习题解析，清华大学出版社，2002年年4月。月。3 李春葆李春葆，数据结构习题与解析（数据结构习题与解析（C语言篇），清语言篇），清华大学出版社，华大学出版社，2001年年1月。月。4 严蔚敏严蔚敏等等，数据结构题集数据结构题集(

2、C语言版语言版)，清华大学，清华大学出版社，出版社， 1997年年4月。月。内内 容容 安安 排排注：本学期共注：本学期共64学时。学时。考核方式考核方式闭卷考试，卷面闭卷考试，卷面 70% + 平时平时 30%；平时成绩包含：实验（平时成绩包含：实验（20分）、作业分）、作业+考勤（考勤（10分）；分）；平时成绩采用倒扣分方式：平时成绩采用倒扣分方式： （1）缺一次实验）缺一次实验 扣扣3 （2）缺一次作业扣）缺一次作业扣1分；分； （3）缺勤（含请假）一次扣）缺勤（含请假）一次扣2分，缺分，缺6次（含实验）取消次（含实验）取消 考试资格；考试资格；加分项：每章的总结加分项：每章的总结 ，交

3、，交1次次 + 2分；分；平时成绩最多平时成绩最多30分！分！第第1章章 序序 论1.1 什么是数据什么是数据结构构1.2 基本概念和基本概念和术语1.3 抽象数据抽象数据类型的表示和型的表示和实现1.4 算法和算法分析算法和算法分析作业作业1.1 什么是数据什么是数据结构构Q1 Q1 如何采用计算机解决问题？如何采用计算机解决问题？Q2 Q2 数据结构解决什么样的问题？数据结构解决什么样的问题？Q3 Q3 数据结构数据结构课程介绍课程介绍Q1：如何采用计算机解决问题？如何采用计算机解决问题？答：答：编写解决写解决实际问题的程序的一般的程序的一般过程：程：(2) 问题所涉及的数据量大小及数据间

4、的关系；问题所涉及的数据量大小及数据间的关系；(1)如何用数据形式描述问题？如何用数据形式描述问题？ 从具体问题抽象出一个适当的数学模型；从具体问题抽象出一个适当的数学模型；(3) 如何在计算机中存储数据和体现数据间的如何在计算机中存储数据和体现数据间的关系？关系？(4) 处理问题时需要对数据做何种运算？处理问题时需要对数据做何种运算？(5) 所编写的程序的性能是否良好？所编写的程序的性能是否良好？这些问题基本上是由数据结构这门课程来回答。这些问题基本上是由数据结构这门课程来回答。8寻求数学模型的实质：寻求数学模型的实质： 分析问题，从中提取分析问题，从中提取操作的对象操作的对象，并找出这些，

5、并找出这些操作对象之间含有的操作对象之间含有的关系关系，然后用，然后用数学的语言数学的语言加以加以描述。描述。Q2：数据结构解决什么样的问题？数据结构解决什么样的问题？答：答：9 数据结构研究数据结构研究非数值非数值计算的程序设计问计算的程序设计问题中计算机的操作对象以及它们之间的关系题中计算机的操作对象以及它们之间的关系和操作等的学科。和操作等的学科。图书检索系统、电话号码查询系统人机对弈、家谱交通灯管理系统10111213深蓝是美国IBM公司生产的一台超级国际象棋电脑。“深蓝”和卡斯帕罗夫曾于1996年交过手，结果卡斯帕罗夫以4：2战胜了“深蓝”。“更深的蓝”是美国IBM公司生产的一台超级

6、国际象棋电脑，重1270公斤，有32个大脑(微处理器)，每秒钟可以计算2亿步。“更深的蓝”输入了一百多年来优秀棋手的对局两百多万局。1997 年 5 月 11 日，加里卡斯帕罗夫以 2.5:3.5 输给 “更深的蓝”141516Q3：数据数据结构构课程介程介绍 介于介于数学、计算机硬件和计算机软件数学、计算机硬件和计算机软件三三者之间的一门核心课程，不仅是一般程序者之间的一门核心课程，不仅是一般程序设计的基础，也是设计和实现编译程序、设计的基础，也是设计和实现编译程序、操作系统、数据库系统及其他系统软件和操作系统、数据库系统及其他系统软件和大型应用软件的重要基础。大型应用软件的重要基础。关系对

7、象关系操作数学软件硬件对象关系操作1.2 基本概念和基本概念和术语Q1 什么是数据什么是数据结构？构？Q2 学学习数据数据结构有什么用？构有什么用？ Q3 数据数据结构涵盖的主要内容？构涵盖的主要内容？ 讨论：讨论： 数据(Data)：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号总称。 数据元素（Data Element）：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。 一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最新单位。数据项是对客观事物某一方面特性的数据描述。 数据对象（Data Object）：

8、是性质相同的数据元素的集合，是数据的一个子集。如字符集合 Char = A, B, C,数据数据 包括数字、字符、声音、包括数字、字符、声音、图像等信息像等信息 。数据元素数据元素 又称元素、又称元素、结点，点，顶点、点、记录等。等。数据数据项 又称字段、域、属性又称字段、域、属性 等。等。三者之间的关系：数据三者之间的关系：数据 数据元素数据元素 数据项数据项例：例：班级通讯录班级通讯录 个人记录个人记录 姓名、年龄姓名、年龄Q1：什么是数据什么是数据结构？构？答答: (见教教材材P5) 是相相互互之之间存存在在一一种种或或多多种种特特定定关系关系的的数据元素数据元素的集合，表示的集合，表示

9、为：（数值或非数值数值或非数值）Data_Structure=（D, S）或：是指同一数据元素类中各元素之间存在的关系。或：是指同一数据元素类中各元素之间存在的关系。亦可表示为：亦可表示为：S（D, R） 或或 B=（K, R）元素有限集元素有限集关系有限集关系有限集Q2：学学习数据数据结构有什么用？构有什么用？答答：计算算机机内内的的数数值运运算算依依靠靠方方程程式式，而而非非数数值运运算算（如表、（如表、树、图等）等）则要依靠数据要依靠数据结构。构。 这是是一一门研研究究非非数数值计算算的的程程序序设计问题中中计算算机机的的操操作作对象象以及它以及它们之之间的的关系和操作关系和操作等等的学

10、科。等等的学科。程序设计实质好算法好结构程序设计实质好算法好结构同样的数据对象，用不同的数据结构来表示，同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。运算效率可能有明显的差异。解解释1： 什么叫数据的什么叫数据的逻辑结构？构？答答：指指数数据据元元素素之之间的的逻辑关关系系。即即从从逻辑关关系系上上描描述述数数据据，它它与与数数据据的的存存储无无关关，是是独独立立于于计算机算机的。的。 数数据据元元素素之之间的的关关系系可可以以是是元元素素之之间代代表表某某种种含含义的的自自然然关关系系，也也可可以以是是为处理理问题方方便便而而人人为定定义的的关关系系，这种种自自然然或或人

11、人为定定义的的“关关系系”称称为数据元素之数据元素之间的的逻辑关系。关系。解解释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,

12、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该结构该结构是非线性的是非线性的。解：解：上述表达式可用图形表示为：上述表达式可用图形表示为：解解释2：什么叫数据的物理什么叫数据的物理结构？构？答答：物物理理结构构亦亦称称存存储结构构，是是数数据据的的逻辑结构构在在计算算机机存存储器器内内的的表表示示（或或映映像）。它像）。它依依赖于于计算机算机。 数数据据结构构在在计算算机机内内存存中中的的存存储包

13、包括括数数据据元元素素的的存存储和和元元素素之之间的的关关系系的的表表示。示。解解释2：什么叫数据的物理什么叫数据的物理结构？构？存储结构可分为存储结构可分为4大类：大类：顺序、链式、索引、散列顺序、链式、索引、散列顺序存储结构顺序存储结构：用数据元素在存储器中的相对位用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构（关系）。置来表示数据元素之间的逻辑结构（关系）。链式存储结构：链式存储结构：在每一个数据元素中增加一个存在每一个数据元素中增加一个存储另一个元素地址的指针，用该指针来表示数据储另一个元素地址的指针，用该指针来表示数据元素之间的逻辑结构（关系）。元素之间的逻辑结构（关系）

14、。例：例：设有数据集合设有数据集合A=3， 4， 0， 8 顺序结构：数据元素存放的地址是连续的；顺序结构：数据元素存放的地址是连续的； 链式结构：数据元素存放的地址是否连续不做要求。链式结构：数据元素存放的地址是否连续不做要求。例：例：（见见教材教材P6）复数）复数3.02.3i 的两种存储方式：的两种存储方式：2.303023.00300041503023.0030004152.3法法1：地址地址 内容内容法法2：地址地址 内容内容2字节字节 数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计算法的设计取决于所选定的逻辑结构逻辑结构，而算法的实算法的实现现依赖于所采用的存储结构存

15、储结构。解解释3：什么是数据的运算？什么是数据的运算？答：在数据的答：在数据的逻辑结构上构上定定义的操作算法。的操作算法。它它在数据的存在数据的存储结构上构上实现。最常用的数据运算有最常用的数据运算有5种：种：插入、删除、修改、查找、排序插入、删除、修改、查找、排序Q3：数据数据结构涵盖的内容？构涵盖的内容？1.3 抽象数据抽象数据类型的表示和型的表示和实现Q1 数据类型与抽象数据类型的区别？数据类型与抽象数据类型的区别？Q2 抽象数据类型如何定义？抽象数据类型如何定义？Q3 抽象数据类型如何表示和实现？抽象数据类型如何表示和实现？ 讨论：讨论：提示：教材中例提示：教材中例1-6和例和例1-7

16、分别给出了抽象数据类分别给出了抽象数据类型型“三元组三元组”的定义、表示和实现，请试阅读。的定义、表示和实现，请试阅读。Q1 数据数据类型与抽象数据型与抽象数据类型的区型的区别？数据类型：数据类型：是一个值的集合和定义在该值上 的一组操作的总称。 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。Q1 数据数据类型与抽象数据型与抽象数据类型的区型的区别？抽象数据类型：抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。 它与数据类型实质上是一个概念，但其特它与数据类型实质

17、上是一个概念，但其特征是征是使用与实现分离使用与实现分离，实行，实行封装封装和和信息隐蔽信息隐蔽（独立于计算机）。（独立于计算机）。 抽象数据类型的定义仅是一组逻辑特性描述， 与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。Q2 抽象数据抽象数据类型如何型如何定定义？抽象数据类型抽象数据类型可以用以下的三元组来表示：可以用以下的三元组来表示： ADT = （D，S，P） 数据对象数据对象 D上的关系集上的关系集 D上的操作集上的操作集 ADTADT抽象数据类型名抽象数据类型名 数据数据对象对象： 数据数据关系关系： 基本基本操作操作

18、： ADT ADT抽象数据类型抽象数据类型名名ADT常用常用定义定义格式格式例：例：给出自然数出自然数(Natural Number )的抽象数据的抽象数据类型定型定义。ADT Natural_Number isobjects: 一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数 (MAX INT)functions: 对于所有的 x, y Natural_Number； TRUE, FALSE Boolean； +, -, , = = ,=等都是可用的服务。Zero ( )Zero ( )： NaturalNatural NumberNumber 返回返回 0 0IsZero(x)

19、IsZero(x)： Boolean if (x=0) Boolean if (x=0) 返回返回TRUETRUE else else 返回返回 FALSEFALSEAdd(x, y)Add(x, y)： NaturalNatural NumberNumber if (x+y = MAX INT)if (x+y = MAX INT)返回返回 x+yx+y else else 返回返回MAX INTMAX INTSubtract(x,y): NaturalNatural NumberNumber if (xy)返回返回0 else 返回返回x-yEqual(x,y): Boolean Equal

20、(x,y): Boolean if (x= y)if (x= y)返回返回TRUE else TRUE else 返回返回FALSEFALSESuccessor(x) : NaturalNatural NumberNumber if (x = MAX INT)返回返回x else 返回返回x+1end Natural_Number Q3 抽象数据抽象数据类型如何型如何表示和表示和实现？ 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。 即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。注注 ：教材中用的是教材中用的是类类C语言（介于伪码和语

21、言（介于伪码和C语言之间）语言之间） 作为描述工具。其描述语法见作为描述工具。其描述语法见P10-11。但上机时要用具体语言实现，如但上机时要用具体语言实现，如C C或或C+C+等等1.4 算法和算法分析算法和算法分析Q1. 什么是算法？什么是算法？Q2. 算法算法设计的要求的要求？Q3. 时间复复杂度如何表示？度如何表示？Q4. 空空间复复杂度如何表示？度如何表示？讨论：讨论：答：算法答：算法是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。 一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述。 算法和

22、程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。Q1. 什么是算法？什么是算法？Q1. 什么是算法？什么是算法？算法有算法有5个基本特性：个基本特性：u有穷性有穷性u确定性确定性u可行性可行性u输入输入u输出输出一个好的算法有以下几个标准：Q2. 算法设计的要求？算法设计的要求？(1) (1) 正确性正确性(2) (2) 可读性可读性(3) (3) 健壮性健壮性(4) (4) 通用性通用性(5) (5) 效率与低存储需求效率与低存储需求作作业：1.简述述下下列列术语：数数据据、数数据据元元素素、数数据据对象象、数数据据结构构、存存储结构构、数数据据类型型、抽抽象象数数据据类型型2.设有数据有数据结构构(D, R)，其中，其中 D=d1, d2, d3, d4 R=r， r=（d1, d2）（）（d2, d3）（）（d3, d4） 问数据数据结构构D是那种是那种类型的数据型的数据结构？构？3 试写一算法，自大到小依次输出顺序输入的三个整数X、Y和Z的值。4 复习C语言的知识