【精品数据结构】概述.PPTVIP

第一章 概述 数据结构的兴起与发展 数据结构的研究对象 数据结构的概念 数据结构的图示 数据结构的分类 §1.1 数据结构的兴起与发展 数据结构问题起源于程序设计的发展。 程序设计现在已经历了三个阶段： 无结构阶段 结构化程序设计阶段 面向对象阶段 §1.2 数据结构的研究对象 计算机应用系统中的两个关键问题： 表示 ----- 对象/实体及其关系在计算机中的表示。只有对象及其相互关系已存储（表示）在计算机中，才能被进一步处理； 操作 ------ 对对象/实体进行处理、访问。 §1.2 数据结构的研究对象 例1：解一元二次方程ax2+bx+c=0. 问题：如何在计算机中表示该方程 ？ 用三个系数的线性排列在来表示 3x2-x+1=0表示为（3, -1, 1） x2-3=0 表示为(1, 0, -3) 一元二次方程ax2+bx+c=0在计算机中表示为线性表（a, b, c） 解方程实质上是对线性表(a, b, c)进行操作。 §1.2 数据结构的研究对象 例2：计算机管理家谱 ：主要实现家庭成员的登记、查询及变更处理等 在数据结构中，该层次结构称为树。 §1.2 数据结构的研究对象 除了确定表示方式外，数据结构的任务还有对这棵树的计算机物理存储、操作的抽象化。 数据结构的研究内容为： 数据的组织方式 相应的抽象操作 §1.3 数据结构的概念 数据：描述客观事物的信息的符号化，是计算机系统可加工处理的对象 数据类型：一个值的集合和定义在这个值集上的一组操作的总称。 原子类型 复合类型（或导出类型或结构类型） §1.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 集合 如果数据结构中，数据元素之间不考虑关系问题（无前驱/后继之分），则称这种结构为集合。 在集合中，各元素是“平等”的，它们的共同关系是：都属于同一个集合。 1.5.2 线性结构 如果数据结构中，数据元素之间只存在前后顺序关系，则称这种结构为线性结构。 每个元素都有唯一前趋和后继，第一个元素可以没有前驱，最后一个可以没有后继 线性结构是一种最常见的数据结构。线性表、栈、队列、串等均为线性结构。 1.5.2 线性结构 上图表示的数据结构为： DS=(D, S) D={d1, d2, …, dn} S={ r } r={d1, d2, d2, d3 , …, dn-1, dn} 1.5.3 树形结构 如果除一个特殊元素没有前驱外，其他每个元素都有唯一的前驱（后继个数不限），则称该结构为树型结构（简称树）。其中，将无前驱的元素称为树根。 1.5.3 树形结构 树形结构中的数据元素（结点）可分为三种: 根，每个树结构只有一个根（空树无根），根无前趋，但可有若干个后继； 叶子，叶子无后继，但只有且必有一个前趋， 普通结点，有且必有一个前趋，后继有若干个。 树型结构的应用 常用来表达层次关系 另一个重要应用是快速检索：为了提高数据检索速度，可将数据按树结构组织，如二叉排序树、平衡二叉树、B树等。 1.5.4 图状结构 图状结构： 任一数据元素，均可有多个前趋和多个后继。该种结构也称网状结构。 例如，交通图 树形结构 图状结构 1.6 数据结构的存储----存储结构 计算机的存贮器 内部存储器（简称内存，也称主存） 外部存储器（简称外存，也称辅存） 本课程的几点说明： 数据结构的存储问题，除最后一章外，都针对内存 . 用高级语言中的数组模拟计算机存贮器 C/C++中的指针的概念 1.6.2 存贮映象(存储结构)问题 数据结构的存贮映象，是指数据结构在计算机中的存储方式/方法 将一个逻辑上的数据结构存储在计算机中，必需满足下列两点： 内容存储