《《数据库系统原理》第一章》由会员分享，可在线阅读，更多相关《《数据库系统原理》第一章（44页珍藏版）》请在金锄头文库上搜索。
1、1,算法与数据结构,河海大学计算机及信息工程学院尹燕敏,2,课程的性质和目的,数据结构是计算机学科的核心专业基础课程，是计算机程序设计的重要理论和实践基础。本课程讨论了软件设计中经常遇到的线性表、堆栈、队列、串、数组、二叉树、图等典型数据结构的设计方法以及各种典型排序和查找算法的性能和设计方法，并介绍了各种典型数据结构的应用。通过本课程的学习，学生对软件设计的基本要素和软件的基本结构有了深入理解，并通过算法设计方法学习和上机编程实践，编程能力有了进一步提高。,3,学习要求,熟练掌握C,C+上课听讲有问题及时答疑课后需要多读课文和参考书，上网查看相关内容，在理解基本内容的基础上，多看、多做习题。
2、上机实验十分重要，一定要在上机前做好充分准备，多采用不同的数据存储结构和不同的实现算法解决一个问题。,4,参考书籍,C+编程相关书籍（选择其中一本）严蔚敏、吴伟民编著，数据结构（C语言版），清华大学出版社王晓东编著,算法设计与分析,清华大学出版社相关习题集,5,第一章 概述,这一章，我们重点概述数据结构中一些基本概念和基本方法，是以后各章的重要基础。,6,数据结构问题起源于程序设计的发展。程序设计现在已经历了三个阶段：无结构阶段结构化程序设计阶段面向对象阶段,1.1 数据结构的兴起与发展,7,计算机应用系统中有两个关键问题：表示：对象/实体及其关系在计算机中的表示。只有对象及其相互关系已存储（
3、表示）在计算机中，才能被进一步处理；操作：对对象/实体进行处理、访问,1.2 数据结构的研究对象,8,利用计算机解此方程，第一个问题就是如何在计算机中表示该方程。分析该方程，可知决定方程的是方程的三个系数值：a、b、c，而它们的次序表示它们分别属于那一项，其他符号是为增加可读性而引入的，因此，可用这三个系数的线性排列在计算机中表示该方程。例如，3x2-x+1=0表示为（3, -1, 1）x2-3=0 表示为(1, 0, -3),例 解一元二次方程ax2+bx+c=0,9,家谱管理主要实现家庭成员的登记、查询及变更处理等。在这个问题中，实体对象是人（家庭成员），关系是父子关系。每个实体用一个记录
4、（元素）表示，包含姓名、出生日期、性别、死亡日期等。为了表示父子关系，在实体记录中可增加若干字段，每个字段用于指示一个儿子/女儿，这样，一个家族就构成了一个层次结构。在数据结构中，该层次结构称为树。,例 计算机管理家谱,10,一个家族结构的树表示,11,归纳起来，数据结构的研究内容为：为了在计算机上实现具体问题，所需的表示数据/信息及其关系应如何组织（组织起来的数据就具有了结构关系），以及如何对它们进行基本操作。简言之，研究数据的组织方式（结构）及相应的抽象操作。,12,数据：数据是描述客观事物的信息的符号化，是计算机系统可加工处理的对象数据类型：数据类型定义为：一个值的集合和定义在这个值集上
5、的一组操作的总称。数据元素、数据项：能独立、完整地描述问题世界中的实体的最小数据单位称为数据元素（也称记录）。构成数据元素的不可分割的数据单位，称为数据项。数据对象：同类数据元素的集合称为数据对象。有了上面几个概念，我们就可以给出数据结构的概念了。数据结构：我们把数据元素之间的关系称为结构。进一步地，我们称相互之间存在着一定关系的数据元素的集合及定义在其上的基本操作（运算）为数据结构。,1.3 数据结构的概念,13,如果不考虑定义在数据结构上的操作，则数据结构也可借助集合论述语定义为：数据结构是一个二元组（D,S），其中D是数据元素的有限集，S是D上的关系的有限集。在这个定义中，数据元素之间的
6、关系采用集合论中关系的形式化描述方法来定义。型为的二元关系中，我们称d1为关系的前件，d2为后件。称d2为d1的后继，而d1为d2的前驱。,14,用小圆圈代表数据元素，用小圆圈之间的连线代表小圆圈对应的数据元素之间的关系，如果强调关系的方向性，可用带箭头的线段表示关系。具体地讲，若d1和d2表示两个数据元素，它们具有关系d1,d2，则表示为,d1,d2,1.4 数据结构的图示,15,1.5 数据结构的分类,16,1.5.1 集合,如果数据结构中，数据元素之间不考虑关系问题（无前驱/后继之分），则称这种结构为集合。在集合中，各元素是“平等”的，它们的共同关系是：都属于同一个集合。,17,如果数据
7、结构中，数据元素之间只存在前后顺序关系（每个元素都有唯一前趋和后继，第一个元素可以没有前驱，最后一个可以没有后继），则称这种结构为线性结构。线性结构是一种最常见的数据结构。线性表、栈、队列、串等均为线性结构。下图表示的数据结构可表示为：DS=(D, S)D=d1, d2, , dnS= r r=, , , ,1.5.2 线性结构,18,如果除一个特殊元素没有前驱外，其他每个元素都有唯一的前驱（后继个数不限），则称该结构为树型结构（简称树）。其中，将无前驱的元素称为树根。用图表示树时，通常习惯将树根画在最上面。某元素的各后继画在该元素的下面，且连线不带箭头，隐含着从上到下。这样，树型结构就象用一
8、棵倒立的树。,1.5.3 树形结构,19,DS= ( D, S)D = W1, W11, W12, W13, W111, W121, W122, W131, W132, W133, W1111, W1112, W1221S = rr = , , , , , , , , , , ,20,在图状结构中，任一数据元素，均可有多个前趋和多个后继。该种结构也称网状结构。图状结构表达能力最强，它可表达任意复杂的数据结构。例如，交通图就是一种图状结构，结点代表城市，连线（关系）代表城市间的道路。树形结构与图状结构均称为非线性结构。,1.5.4 图状结构,21,22,1.6.1 存贮器表示问题 本课程中，数据
9、结构的存储问题，除最后讲到外存的数据存储，其余都针对内存。大多数高级语言支持的访问存贮器的方式是相当高级的，隐蔽了存贮器的许多特性，不利于表示数据的存贮结构。不过，许多高级语言都提供按数组访问存贮器的方式。数组很接近存贮器，所以用高级语言中的数组模拟计算机存贮器。,1.6 数据结构的存储-存储结构,23,数据结构的存贮映象，是指数据结构在计算机中的存储方式/方法，是数据结构的另一种表示方式，称为数据结构的存储结构/方式。将一个逻辑上的数据结构存储在计算机中，必需满足下列两点：内容存储：数据结构中的各数据元素的内容（数据），都分别存贮在一个独立的可访问的存贮区中;关系存储：数据元素的存放方式方法
10、，必须能显示地或隐式地体现数据元素间的逻辑关系。 在满足上述必要条件的基础上，存贮映象还应考虑存贮使用效率（空间复杂度）及数据结构的操作的实现的方便性等。,1.6.2 存贮映象(存储结构)问题,24,一、顺序存储这是一种主要面向线性关系的存贮方法。对线性数据结构，可将其数据元素，按相应的线性关系下的前后次序，存贮在物理存贮器中，使得数据元素在此线性关系下的逻辑次序与它们在存贮器中的存放次序一致。这种存贮方式称为顺序方法（也称连续方法）。 为了能使存贮次序表达逻辑次序，显然，在存贮器中，任意相邻两数据元素之间的存贮单元数目应相等。,1.6.3 基本存储方法,25,例 设有数据结构DS=（D,S）
11、，其中，D=d1, d2, d3, d4，S=r，r=，D中每个元素需占用两个存贮单元，则该结构的顺序存贮结构如下图所示（称存贮结构图）.,26,每个数据元素的存储区分两大部分，第一部分为数据区，存贮元素的内容，第二部分为指针区，存放该数据元素与其它数据元素之间的关系信息，这种关系信息一般为地址（与此数据元素相关的其他数据元素的存贮地址）。对于线性结构，指针区中可以只设一个地址；对非线性关系，可能需多个地址。另外，数据元素的存贮区之间，可以是连续的，也可不连续。,二、链式结构,27,D=d1, d2, d3, d4，S=r，r=，,28,例设数据结构为DS=（D,S），其中D=d1,d2,d3
12、,d4,d5,d6，S=r1, r2，r1=，, r2=，它的一种链式存贮映象下表所示,29,索引存储主要针对集合和线性表，面向检索（查找）操作。它主要是在数据结构的存储区（称数据区）外，增加一个（或若干个）索引区。 索引区本身也是个线性表或其他数据结构，结构中每个元素用于记录数据区中一个（对稠密索引）或一组（对非稠密索引）元素的存储位置（起始位置）。 索引存储并不强调对关系的存储，而主要针对数据内容，所以，一般只适合集合结构或线性结构。,三、索引存储,30,散列存储（也称杂凑法）是一种按元素内容存储元素的方法。其基本思想是：设置一个函数，称为散列函数：元素内容地址；规定元素内容到存储地址的映
13、射；存储时，通过散列函数求出元素的应存储的地址，按此地址存储；读取时，通过散列函数求出元素的存储地址，按此地址读取；与索引存储类似，散列存储也是面向内容存储，不适合存储复杂数据结构,四、散列存储,31,1.7.1 访问接口与逻辑结构 数据的访问（也称操作）是指对数据的读、修改、加工、处理等操作。数据存在的目的是进行操作。操作的种类很多，随不同的应用而不同。数据结构中的一个重要的问题是：对每种数据结构，如何设置一些操作，使得各种应用都能通过这些操作就能实现对数据结构的各种操作，我们把这类操作称为数据结构的基本操作或运算。操作的调用形式与规范，称为该操作的接口；将针对某一数据结构的基本操作的接口的
14、全体，称为该数据结构的访问接口；,1.7 数据结构访问接口,32,基本操作有下列关键点：抽象性：基本性：完备性：支撑性：,33,尽管不同的数据结构对应不同的基本操作集合，但可按功能归纳为下列几种基本类型：属性读取(Get)：属性设置(Set)：查找插入删除关系访问遍历,1.7.2 基本操作的种类,34,操作的实体是计算机程序，因此，基本操作的实现，是个针对相应的数据结构编程的问题。由于程序是算法的实现，所以操作实现也是算法实现问题,1.7.3 基本操作的实现,35,1.8 面向对象方法,在面向对象方法中，将问题世界中所涉及的实体抽象为对象（Objects）， 每个对象，是对应的实体的一个抽象模
15、型，它刻画实体的状态和行为状态称为对象的属性或数据成员，行为称为对象的方法或操作或服务，亦即对象由描述实体的状态的属性与用于改变自身状态的操作两大部分构成： 对象 = 属性 + 操作类是对象的型，它与数据类型的概念是类似的定义了对象的属性的取值范围与一组操作。每个类都是一批属性与结构类似且操作相同的对象的抽象。由于类中含数据与操作两部分，所以它既可看作类型，又可看作模块。继承的引入，会使这点更加明确。,36,C + + 的数据声明,1常数值：25，”hello”2变量：3常量：const int MAX=5004枚举：声明整型常数序列，enum BooleanFALSE，TRUE5指针：存放对象的存储地址， int i = 5 ; int *np; /np为指向整型变量的指针 np= &i; /取整型变量i的地址赋给np int k = *np; /整型变量k中存入np所指地址i的内容56引用：给一个对象提供一个替代的名字， int i = 5; int &j = i; /j为引用类型，代表i的一个替代名 i = 7; printf(i=%d,j=%d,i,j); /i，j 的值均为7,
