《数据库系统原理》第一章.ppt

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