《《数据库系统原理》》由会员分享，可在线阅读，更多相关《《数据库系统原理》（44页珍藏版）》请在金锄头文库上搜索。
1、河海大学计算机及信息工程学院河海大学计算机及信息工程学院 1算法与数据结构算法与数据结构算法与数据结构算法与数据结构河海大学计算机及信息工程学院河海大学计算机及信息工程学院 尹燕敏尹燕敏2课程的性质和目的课程的性质和目的课程的性质和目的课程的性质和目的数据结构是计算机学科的核心专业基础课数据结构是计算机学科的核心专业基础课 程，是计算机程序设计的重要理论和实践基础。程，是计算机程序设计的重要理论和实践基础。 本课程讨论了软件设计中经常遇到的本课程讨论了软件设计中经常遇到的线性表、堆线性表、堆 栈、队列、串、数组、二叉树、图栈、队列、串、数组、二叉树、图等典型数据结等典型数据结 构的设计方法以及
2、各种典型排序和查找算法的性构的设计方法以及各种典型排序和查找算法的性 能和设计方法，并介绍了各种典型数据结构的应能和设计方法，并介绍了各种典型数据结构的应 用。用。 通过本课程的学习，学生对软件设计的通过本课程的学习，学生对软件设计的基本基本 要素要素和软件的和软件的基本结构基本结构有了深入理解，并通过算有了深入理解，并通过算 法设计方法学习和法设计方法学习和上机编程实践上机编程实践，编程能力有了，编程能力有了 进一步提高。进一步提高。3学习要求学习要求学习要求学习要求熟练掌握熟练掌握C,C+C,C+C,C+C,C+ 上课听讲上课听讲 有问题及时答疑有问题及时答疑 课后需要多读课文和参考书，上
3、网查看相关内课后需要多读课文和参考书，上网查看相关内 容，在理解基本内容的基础上，容，在理解基本内容的基础上，多看、多做习题多看、多做习题。 上机实验十分重要上机实验十分重要，一定要在上机前做好充分准，一定要在上机前做好充分准 备，多采用不同的数据存储结构和不同的实现算备，多采用不同的数据存储结构和不同的实现算 法解决一个问题。法解决一个问题。4参考书籍参考书籍参考书籍参考书籍C+C+C+C+编程相关书籍（选择其中一本）编程相关书籍（选择其中一本） 严蔚敏、吴伟民编著，数据结构（严蔚敏、吴伟民编著，数据结构（C C C C语言版），语言版）， 清华大学出版社清华大学出版社 王晓东编著王晓东编著
4、, , , ,算法设计与分析算法设计与分析, , , ,清华大学出版社清华大学出版社 相关习题集相关习题集河海大学计算机及信息工程学院河海大学计算机及信息工程学院 5第一章第一章第一章第一章 概述概述概述概述这一章，我们重点概述数据结构中一些基这一章，我们重点概述数据结构中一些基 本概念和基本方法，是以后各章的重要基础。本概念和基本方法，是以后各章的重要基础。 6数据结构问题起源于程序设计的发展。程序数据结构问题起源于程序设计的发展。程序 设计现在已经历了三个阶段：设计现在已经历了三个阶段： 无结构阶段无结构阶段 结构化程序设计阶段结构化程序设计阶段 面向对象阶段面向对象阶段1.1 1.1 1
5、.1 1.1 1.1 1.1 1.1 1.1 数据结构的兴起与发展数据结构的兴起与发展数据结构的兴起与发展数据结构的兴起与发展 7计算机应用系统中有两个关键问题：计算机应用系统中有两个关键问题： 表示表示：对象：对象/ / / /实体及其关系在计算机中的表示。实体及其关系在计算机中的表示。 只有对象及其相互关系已存储（表示）在计算只有对象及其相互关系已存储（表示）在计算 机中，才能被进一步处理；机中，才能被进一步处理； 操作操作：对对象：对对象/ / / /实体进行实体进行处理、访问处理、访问 1.2 1.2 1.2 1.2 1.2 1.2 1.2 1.2 数据结构的研究对象数据结构的研究对象
6、数据结构的研究对象数据结构的研究对象8利用计算机解此方程，第一个问题就是如何在利用计算机解此方程，第一个问题就是如何在 计算机中表示该方程。分析该方程，可知决定方程计算机中表示该方程。分析该方程，可知决定方程 的是方程的三个系数值：的是方程的三个系数值：a a a a、b b b b、c c c c，而它们的次序，而它们的次序 表示它们分别属于那一项，其他符号是为增加可读表示它们分别属于那一项，其他符号是为增加可读 性而引入的，因此，可用这三个系数的线性排列在性而引入的，因此，可用这三个系数的线性排列在 计算机中表示该方程。例如，计算机中表示该方程。例如， 3x3x3x3x2 2 2 2-x+
7、1=0-x+1=0-x+1=0-x+1=0表示为（表示为（3, -1, 13, -1, 13, -1, 13, -1, 1） x x x x2 2 2 2-3=0 -3=0 -3=0 -3=0 表示为表示为(1, 0, -3)(1, 0, -3)(1, 0, -3)(1, 0, -3) 例例例例 解一元二次方程解一元二次方程解一元二次方程解一元二次方程axaxaxaxaxaxaxax2 2 2 2 2 2 2 2+bx+c=0+bx+c=0+bx+c=0+bx+c=0+bx+c=0+bx+c=0+bx+c=0+bx+c=09家谱管理主要实现家庭成员的登记、查询及变家谱管理主要实现家庭成员的登记
8、、查询及变 更处理等。在这个问题中，实体对象是人（家庭成更处理等。在这个问题中，实体对象是人（家庭成 员），关系是父子关系。每个实体用一个记录（元员），关系是父子关系。每个实体用一个记录（元 素）表示，包含姓名、出生日期、性别、死亡日期素）表示，包含姓名、出生日期、性别、死亡日期 等。为了表示父子关系，在实体记录中可增加若干等。为了表示父子关系，在实体记录中可增加若干 字段，每个字段用于指示一个儿子字段，每个字段用于指示一个儿子/ / / /女儿，这样，一女儿，这样，一 个家族就构成了一个层次结构。在数据结构中，该个家族就构成了一个层次结构。在数据结构中，该 层次结构称为树。层次结构称为树。
9、例例例例 计算机管理家谱计算机管理家谱计算机管理家谱计算机管理家谱10WWWW1 1 1 1WWWW12121212WWWW121121121121WWWW122122122122WWWW111111111111WWWW11111111WWWW131131131131WWWW132132132132WWWW133133133133WWWW13131313WWWW1112111211121112WWWW1221122112211221WWWW1111111111111111一个家族结构的树表示一个家族结构的树表示一个家族结构的树表示一个家族结构的树表示11归纳起来，数据结构的归纳起来，数据结构的
10、研究内容研究内容为：为：为了在计算机上实现具体问题，所需的表示为了在计算机上实现具体问题，所需的表示 数据数据/ / / /信息及其关系应如何信息及其关系应如何组织组织（组织起来的数据（组织起来的数据 就具有了结构关系），以及如何对它们进行基本就具有了结构关系），以及如何对它们进行基本操操 作作。简言之，研究数据的组织方式（结构）及相应。简言之，研究数据的组织方式（结构）及相应 的抽象操作。的抽象操作。 12数据数据：数据是描述客观事物的信息的符号化，是计算机系：数据是描述客观事物的信息的符号化，是计算机系 统可加工处理的对象统可加工处理的对象 数据类型数据类型：数据类型定义为：一个值的集合和
11、定义在这个：数据类型定义为：一个值的集合和定义在这个 值集上的一组操作的总称。值集上的一组操作的总称。 数据元素、数据项数据元素、数据项：能独立、完整地描述问题世界中的实：能独立、完整地描述问题世界中的实 体的最小数据单位称为数据元素（也称记录）。构成数据体的最小数据单位称为数据元素（也称记录）。构成数据 元素的不可分割的数据单位，称为数据项。元素的不可分割的数据单位，称为数据项。 数据对象数据对象：同类数据元素的集合称为数据对象。有了上面：同类数据元素的集合称为数据对象。有了上面 几个概念，我们就可以给出数据结构的概念了。几个概念，我们就可以给出数据结构的概念了。 数据结构数据结构：我们把数
12、据元素之间的关系称为结构。进一步：我们把数据元素之间的关系称为结构。进一步 地，我们称相互之间存在着一定关系的数据元素的集合及地，我们称相互之间存在着一定关系的数据元素的集合及 定义在其上的基本操作（运算）为数据结构。定义在其上的基本操作（运算）为数据结构。1.3 1.3 1.3 1.3 1.3 1.3 1.3 1.3 数据结构的概念数据结构的概念数据结构的概念数据结构的概念 13如果不考虑定义在数据结构上的操作，则数据如果不考虑定义在数据结构上的操作，则数据 结构也可借助集合论述语定义为：结构也可借助集合论述语定义为：数据结构数据结构是一个二元组（是一个二元组（D,SD,SD,SD,S），其
13、中），其中D D D D是数是数 据元素的有限集，据元素的有限集，S S S S是是D D D D上的关系的有限集。上的关系的有限集。在这个定义中，数据元素之间的关系采用集合在这个定义中，数据元素之间的关系采用集合 论中关系的形式化描述方法来定义。型为论中关系的形式化描述方法来定义。型为 的的 二元关系中，我们称二元关系中，我们称d d d d1 1 1 1为关系的为关系的前件前件，d d d d2 2 2 2为为后件后件。 称称d d d d2 2 2 2为为d d d d1 1 1 1的的后继后继，而，而d d d d1 1 1 1为为d d d d2 2 2 2的的前驱前驱。 14用小圆
14、圈代表数据元素，用小圆圈之间的连用小圆圈代表数据元素，用小圆圈之间的连 线代表小圆圈对应的数据元素之间的关系，如果强线代表小圆圈对应的数据元素之间的关系，如果强 调关系的方向性，可用带箭头的线段表示关系。具调关系的方向性，可用带箭头的线段表示关系。具 体地讲，若体地讲，若d d d d1 1 1 1和和d d d d2 2 2 2表示两个数据元素，它们具有关表示两个数据元素，它们具有关 系系d d d d1 1 1 1,d,d ,d ,d2 2 2 2，则表示为，则表示为d d d d1 1 1 1d d d d2 2 2 21.4 1.4 1.4 1.4 1.4 1.4 1.4 1.4 数据
15、结构的图示数据结构的图示数据结构的图示数据结构的图示151.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 数据结构的分类数据结构的分类数据结构的分类数据结构的分类 161.5.1 1.5.1 1.5.1 1.5.1 1.5.1 1.5.1 1.5.1 1.5.1 集合集合集合集合如果数据结构中，数据元素之间不考虑关系问如果数据结构中，数据元素之间不考虑关系问 题（无前驱题（无前驱/ / / /后继之分），则称这种结构为集合。后继之分），则称这种结构为集合。 在集合中，各元素是在集合中，各元素是“ “ “ “平等平等” ” ” ”的，它们的共同关的，它们的共同关 系是：都属于同一个
16、集合。系是：都属于同一个集合。17如果数据结构中，数据元素之间只存在前后顺序关系如果数据结构中，数据元素之间只存在前后顺序关系 （每个元素都有唯一前趋和后继，第一个元素可以没有前（每个元素都有唯一前趋和后继，第一个元素可以没有前 驱，最后一个可以没有后继），则称这种结构为驱，最后一个可以没有后继），则称这种结构为线性结构线性结构。 线性结构是一种最常见的数据结构。线性表、栈、队线性结构是一种最常见的数据结构。线性表、栈、队 列、串等均为线性结构。列、串等均为线性结构。 下图表示的数据结构可表示为：下图表示的数据结构可表示为： DS=(D, S)DS=(D, S)DS=(D, S)DS=(D, S) D=dD=dD=dD=d1 1 1 1, d, d, d, d2 2 2 2, ,
