数据结构课程介绍

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

2、清华大学，清华大学 出版社，出版社， 1997年年4月。月。 内内 容容 安安 排排 章章内内 容容 学时学时 章章 内内 容容 学时学时 1 序序 论论 27 图图 10 2 线性表线性表 108 动态存储管理动态存储管理 略略 3 栈和队列栈和队列 89 查找查找 8 4 串串 210 内部排序内部排序 6 5 数组和广义表数组和广义表 811 外部排序外部排序 略略 6 树和二叉树树和二叉树 1012 文件文件 略略 注：本学期共注：本学期共64学时。学时。 考核方式考核方式 闭卷考试，卷面闭卷考试，卷面 70% + 平时平时 30%； 平时成绩包含：实验（平时成绩包含：实验（20分）、

3、作业分）、作业+考勤（考勤（10分）；分）； 平时成绩采用倒扣分方式：平时成绩采用倒扣分方式： （1）缺一次实验）缺一次实验 扣扣3 （2）缺一次作业扣）缺一次作业扣1分；分； （3）缺勤（含请假）一次扣）缺勤（含请假）一次扣2分，缺分，缺6次（含实验）取消次（含实验）取消 考试资格；考试资格； 加分项：每章的总结加分项：每章的总结 ，交，交1次次 + 2分；分； 平时成绩最多平时成绩最多30分！分！ 第第1章章 序序 论论 1.1 什么是数据结构什么是数据结构 1.2 基本概念和术语基本概念和术语 1.3 抽象数据类型的表示和实现抽象数据类型的表示和实现 1.4 算法和算法分析算法和算法分析

4、 作业作业 1.1 什么是数据结构什么是数据结构 Q1 Q1 如何采用计算机解决问题？如何采用计算机解决问题？ Q2 Q2 数据结构解决什么样的问题？数据结构解决什么样的问题？ Q3 Q3 数据结构数据结构课程介绍课程介绍 Q1：如何采用计算机解决问题？如何采用计算机解决问题？ 答：编写解决实际问题的程序的一般过程：答：编写解决实际问题的程序的一般过程： (2) 问题所涉及的数据量大小及数据间的关系；问题所涉及的数据量大小及数据间的关系； (1) 如何用数据形式描述问题？如何用数据形式描述问题？ 从具体问题抽象出一个适当的数学模型；从具体问题抽象出一个适当的数学模型； (3) 如何在计算机中存

5、储数据和体现数据间的如何在计算机中存储数据和体现数据间的 关系？关系？ (4) 处理问题时需要对数据做何种运算？处理问题时需要对数据做何种运算？ (5) 所编写的程序的性能是否良好？所编写的程序的性能是否良好？ 这些问题基本上是由数据结构这门课程来回答。这些问题基本上是由数据结构这门课程来回答。 8 寻求数学模型的实质：寻求数学模型的实质： 分析问题，从中提取分析问题，从中提取操作的对象操作的对象，并找出这些，并找出这些 操作对象之间含有的操作对象之间含有的关系关系，然后用，然后用数学的语言数学的语言加以加以 描述。描述。 Q2：数据结构解决什么样的问题？数据结构解决什么样的问题？ 答：答：

6、9 数据结构研究数据结构研究非数值非数值计算的程序设计问计算的程序设计问 题中计算机的操作对象以及它们之间的关系题中计算机的操作对象以及它们之间的关系 和操作等的学科。和操作等的学科。 图书检索系统、电话号码查询系统 人机对弈、家谱 交通灯管理系统 10 11 12 13 深蓝是美国IBM公司生产的一台超级国际象棋电脑。 “深蓝”和卡斯帕罗夫曾于1996年交过手，结果卡斯帕罗 夫以4：2战胜了“深蓝”。 “更深的蓝”是美国IBM公司生产的一台超级国际象棋电 脑，重1270公斤，有32个大脑(微处理器)，每秒钟可以计 算2亿步。“更深的蓝”输入了一百多年来优秀棋手的对 局两百多万局。 1997

7、年 5 月 11 日，加里卡斯帕罗夫以 2.5:3.5 输给 “更 深的蓝” 14 15 16 Q3：数据结构数据结构课程介绍课程介绍 介于介于数学、计算机硬件和计算机软件数学、计算机硬件和计算机软件 三者之间的一门核心课程，不仅是一般程三者之间的一门核心课程，不仅是一般程 序设计的基础，也是设计和实现编译程序、序设计的基础，也是设计和实现编译程序、 操作系统、数据库系统及其他系统软件和操作系统、数据库系统及其他系统软件和 大型应用软件的重要基础。大型应用软件的重要基础。 关系 对象 关系 操作 数学 软件硬件 对象 关系 操作 1.2 基本概念和术语基本概念和术语 Q1 什么是数据结构？什么

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

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

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

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

12、理问题方便而含义的自然关系，也可以是为处理问题方便而 人为定义的关系，这种自然或人为定义的人为定义的关系，这种自然或人为定义的“关关 系系”称为数据元素之间的逻辑关系。称为数据元素之间的逻辑关系。 解释解释1： 什么叫数据的逻辑结构？什么叫数据的逻辑结构？ 逻辑结构可细分为逻辑结构可细分为4类：类： 集合结构：集合结构： 仅同属一个集合仅同属一个集合 线性结构线性结构: 一对一（一对一（1:1) 树树 结结 构构: 一对多（一对多（1:n) 图图 结结 构构: 多对多多对多 (m:n) 非线性非线性 线线 性性 例：例：用图形表示下列数据结构，并指出它用图形表示下列数据结构，并指出它 们们 是

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 此结构为此结构为线性线性的。的。 （2） S=(D, R) D=di | 1i5 R=(di , dj ), ij d1 d5 d2 d4 d3 该结构该结构是非线性的是非线性的。 解：解：上述表达式可用图形表示为：上述表达式可用图形表示为： 解释解释2：什么叫数据的物理结构？什么叫数据的物理结构？ 答：物理结构

14、亦称答：物理结构亦称存储结构存储结构，是数据的逻，是数据的逻 辑结构在计算机存储器内的表示（或映辑结构在计算机存储器内的表示（或映 像）。它像）。它依赖于计算机依赖于计算机。 数据结构在计算机内存中的存储包括数据结构在计算机内存中的存储包括 数据元素的存储和元素之间的关系的表数据元素的存储和元素之间的关系的表 示。示。 解释解释2：什么叫数据的物理结构？什么叫数据的物理结构？ 存储结构可分为存储结构可分为4大类：大类：顺序、链式、索引、散列顺序、链式、索引、散列 顺序存储结构顺序存储结构：用数据元素在存储器中的相对位用数据元素在存储器中的相对位 置来表示数据元素之间的逻辑结构（关系）。置来表示

15、数据元素之间的逻辑结构（关系）。 链式存储结构：链式存储结构：在每一个数据元素中增加一个存在每一个数据元素中增加一个存 储另一个元素地址的指针，用该指针来表示数据储另一个元素地址的指针，用该指针来表示数据 元素之间的逻辑结构（关系）。元素之间的逻辑结构（关系）。 例：例：设有数据集合设有数据集合A=3， 4， 0， 8 顺序结构：数据元素存放的地址是连续的；顺序结构：数据元素存放的地址是连续的； 链式结构：数据元素存放的地址是否连续不做要求。链式结构：数据元素存放的地址是否连续不做要求。 例：例：（见见教材教材P6）复数）复数3.02.3i 的两种存储方式：的两种存储方式： 2.30302 3

16、.00300 04150302 3.00300 0415 2.3 法法1：地址地址 内容内容法法2：地址地址 内容内容 2字节字节 数据的逻辑结构和物理结构是密不可分的两个方面， 一个算法的设计算法的设计取决于所选定的逻辑结构逻辑结构，而算法的实算法的实 现现依赖于所采用的存储结构存储结构。 解释解释3：什么是数据的运算？什么是数据的运算？ 答：在数据的逻辑结构上答：在数据的逻辑结构上定义定义的操作算法。的操作算法。 它它在数据的存储结构上实现在数据的存储结构上实现。 最常用的数据运算有最常用的数据运算有5种：种： 插入、删除、修改、查找、排序插入、删除、修改、查找、排序 Q3：数据结构涵盖的

17、内容？数据结构涵盖的内容？ 1.3 抽象数据类型的表示和实现抽象数据类型的表示和实现 Q1 数据类型与抽象数据类型的区别？数据类型与抽象数据类型的区别？ Q2 抽象数据类型如何定义？抽象数据类型如何定义？ Q3 抽象数据类型如何表示和实现？抽象数据类型如何表示和实现？ 讨论：讨论： 提示：教材中例提示：教材中例1-6和例和例1-7分别给出了抽象数据类分别给出了抽象数据类 型型“三元组三元组”的定义、表示和实现，请试阅读。的定义、表示和实现，请试阅读。 Q1 数据类型与抽象数据类型的区别？数据类型与抽象数据类型的区别？ 数据类型：数据类型：是一个值的集合和定义在该值上 的一组操作的总称。 数据结

18、构不同于数据类型，也不同于数 据对象，它不仅要描述数据类型的数据对 象，而且要描述数据对象各元素之间的相 互关系。 Q1 数据类型与抽象数据类型的区别？数据类型与抽象数据类型的区别？ 抽象数据类型：抽象数据类型：由用户定义，用以表示应用问 题的数据模型。它由基本的数据类型构成，并 包括一组相关的服务（或称操作）。 它与数据类型实质上是一个概念，但其特它与数据类型实质上是一个概念，但其特 征是征是使用与实现分离使用与实现分离，实行，实行封装封装和和信息隐蔽信息隐蔽 （独立于计算机）。（独立于计算机）。 抽象数据类型的定义仅是一组逻辑特性描 述， 与其在计算机内的表示和实现无关。因 此，不论ADT

19、的内部结构如何变化，只要其 数学特性不变，都不影响其外部使用。 Q2 抽象数据类型如何抽象数据类型如何定义定义？ 抽象数据类型抽象数据类型可以用以下的三元组来表示：可以用以下的三元组来表示： ADT = （D，S，P） 数据对象数据对象 D上的关系集上的关系集 D上的操作集上的操作集 ADTADT抽象数据类型名抽象数据类型名 数据数据对象对象： 数据数据关系关系： 基本基本操作操作 ： ADT ADT抽象数据类型抽象数据类型名名 ADT 常用常用 定义定义 格式格式 例：例：给出自然数给出自然数(Natural Number )的抽象数据类型定义的抽象数据类型定义。 ADT Natural_N

20、umber is objects: 一个整数的有序子集合，它开始于0，结束于机器能 表示的最大整数 (MAX INT) functions: 对于所有的 x, y Natural_Number； TRUE, FALSE Boolean； +, -, , = = ,=等都是可用 的服务。 Zero ( )Zero ( )： NaturalNatural NumberNumber 返回返回 0 0 IsZero(x)IsZero(x)： Boolean if (x=0) Boolean if (x=0) 返回返回TRUETRUE else else 返回返回 FALSEFALSE Add(x, y

21、)Add(x, y)： NaturalNatural NumberNumber if (x+y = MAX INT)if (x+y = MAX INT)返回返回 x+yx+y else else 返回返回MAX INTMAX INT Subtract(x,y): NaturalNatural NumberNumber if (xy)返回返回0 else 返回返回x-y Equal(x,y): Boolean Equal(x,y): Boolean if (x= y)if (x= y)返回返回TRUE else TRUE else 返回返回FALSEFALSE Successor(x) : Na

22、turalNatural NumberNumber if (x = MAX INT)返回返回x else 返回返回x+1 end Natural_Number Q3 抽象数据类型如何抽象数据类型如何表示和实现表示和实现？ 抽象数据类型可以通过固有的数据类型 （如整型、实型、字符型等）来表示和实现。 即利用处理器中已存在的数据类型来说明新的 结构，用已经实现的操作来组合新的操作。 注注 ：教材中用的是教材中用的是类类C语言（介于伪码和语言（介于伪码和C语言之间）语言之间） 作为描述工具。其描述语法见作为描述工具。其描述语法见P10-11。 但上机时要用具体语言实现，如但上机时要用具体语言实现，如C C或或C+C+等等 1.4 算法和算法分析算法和算法分析 Q1. 什么是算