数据结构 第1章 绪论

《数据结构 第1章 绪论》由会员分享，可在线阅读，更多相关《数据结构 第1章 绪论（42页珍藏版）》请在金锄头文库上搜索。

1、数数 据据 结结 构构王少波前 言 v系统软件和应用软件研制者的必修课程。 v数据结构主要解决非数值计算应用问题。 v每种数据结构类型描述层次 概念层、逻辑层、存储层、运算实现层 。v数据结构描述的内容看上去如同程序， 但不是程序，它是程序设计思想的抽象化 。v数据结构既是一门理论性很强的课程，同时 又是一门实践性很强的课程。 第一章 绪 论 v信息表示包括组成信息的元素之间的相互关系（逻辑顺 序）和信息元素在计算机中的存储方式（物理顺序） 。 v“计算”有别于数学概念中的一般计算，通常将计算又 称为“运算”或“操作”。 运算或操作的内涵： 四则运算和各种函数运算（公式化运算） 还包括数据存取

2、、插入、删除、查找、排序和遍历等运 算（非公式化运算） 。 v计算机的应用主要包括两个方面：数值计算和非数值计 算。 数值计算特点：是计算过程复杂，数据类型相对简单、 数据量相对较少； 非数值计算特点：计算过程相对简单，数据类型相对复 杂、数据的组织排列从某种意义上决定着非数值计算应 用有效性。 第一章 绪 论 v数值计算问题： 程序设计主要围绕 程序设计技巧，是典型地以程序为中 心的设计过程。 v非数值计算问题： 是以复杂的数据 为中心，研究数据的合理组织形式， 并设计出基于合理数据组织结构下的 高效程序。 第一章 绪 论 1.1 什么是数据结构1.1.1 数据结构相关事例 问题一：电话号码

3、簿的使用及字典的使用。 v构建电话号码簿的多级分类目录（数据组织结构 ）v大、小类别可以看作电话号码簿的目录或索引。 v缺少类别的电话号码簿无人使用，除非少量电话 号码（数据的大量性） 。v从特定的大类别中查找小类别直至所需要的电话 号码（计算方法）。 事例：1.1 什么是数据结构党政机关77 省委5555 省委办公厅一处88060001 大学12市委127省委办公厅二处88060002企业25区委224 127 市委办公一处85800203 市委办公二处85800105 旅游3212 综合类大学325325 华中科技大学87870001 理工大学430武汉大学86880206电话号码簿1.1

4、 什么是数据结构问题二：车皮调度问题 v有若干个发往同一方向不同城市的货车车皮以随 机的次序到达货站的进车道, 货站由三部分构成 ：进车道，出车道和调度道（中间多条车道）。v货车发出本站时，列车的尾部所挂接的车皮应该 是发往距本货站最近的车皮，这样可以保证到达 某车站时从尾部“甩下”若干到站的车皮。 v车皮发出本站前应调整它们的次序 。v实现调整过程，货运站通过调度车道完成 。 事例：1.1 什么是数据结构车皮调度 7，6 5，1 4，3，2进车道： 3，4，2，5，1，7，6出车道：7，6，5，4，3，2，1图1.1. 车皮调度问题问题三：某省各城市之间要架设电话通信线路。v要保证各城市间互

5、通，不一定两两城市间都要连 线v又要使设成本最少。使用的线路，人工成本等。就是数据结构中讨论的图结构的应用 最小生成树。v实现过程，构造最小生成树。事例：1.1 什么是数据结构架设电话通信线路442551245257117834城市连接及距离512711最小生成树ABECDACDEB1.1.2 数据结构的定义 定义：数据结构就是研究计算机中大量数据存 储的组织形式，并定义且实现对数据的相应 的运算，以提高计算机的数据处理能力的一 门科学。 全释： 计算机中大量数据问题 数据存储的组织结构 定义且实现相应高效的运算 数据的组织形式（结构） 是基础 “运算”或 “操作”是数据结构讨论内容的一个 核

6、心 1.1 什么是数据结构1.2 数据结构的相关概念1.2.1 数据和信息数据：是描述客观事物的数字、字符，以 及所有能输入到计算机中并能为计算机所接 受的符号集合的总称。信息：是描述客观事物的数据集合。数据是信息以某一类特定符号表示的形式 1.2 数据结构的相关概念1.2.2 数据元素v数据元素是数据集合中的个体，是数据组成 的基本单位。v数据通常是由若干个数据元素组成，数据元 素是不可再分的最小单位。v构成商品数据元素的每个项目称为“数据项 ”（DATA ITEM）v有的数据项是由单一的数据类型组成，称为 原子项，而有的数据项又可再分为若干个子 数据项组成，称为组合项。 事例： 1.2 数

7、据结构的相关概念数据元素商品元素商品名商品编号商品数量商品价格出厂价格批发价格零售价格商品数据元素v数据元素通常又表达为“记录”、“结点”或“ 顶点”。v在计算机的高级语言中又可以有不同的表述。 C语言:定义为“结构类型”（STRUCTURE TYPE） PASCAL语言:定义为“记录类型”（RECORD TYPE） 数据库:定义为“元组”（TUPLE）或字段（FIELD）v数据元素是数据集合中的个体，是数据组成的基 本单位。v在数据元素的多个数据项中能起标识作用（确定 或识别）的数据项称为关键字或关键码（key）。v关键码如能唯一标识一数据元素，又称为主关键 码，反之称为次关键码或次码。 1

8、.2 数据结构的相关概念1.2.3 结构类型数据结构中讨论的结构类型分为两个:逻辑结构和物理结构 1. 逻辑结构:逻辑结构描述数据元素与数据元素之间的关 联方式，简称为关系，表示的是事物本身的内在联系。 逻辑结构又可以分为：线性结构和非线性结构两大类。v线性结构分为：线性表、堆栈、队列等。事例： 线性结构的特点:数据元素之间存在前后次序，排在某 个数据元素b前面的数据元素a称为b的直接前驱元素，而 数据元素b则称为数据元素a的直接后继元素，对于某个数 据元素，如果存在直接前驱元素或直接后继元素，则都是 唯一的。线性结构中数据元素之间的正逆关系都是“一对 一”的。1.2 数据结构的相关概念逻辑结

9、构刘丹，88彭亮，97李智，90王明，95肖象，78空第一个数据元素地 址图 线性结构ABCEFD图 非线性结构v非线性结构又可再分为树形结构、图状或网状结 构、纯集合结构。线性结构分为：线性表、堆栈 、队列等。事例： 非线性结构的特点：数据元素不一定存在确 定的前后次序，甚至是无序的，数据元素之间存 在从属或互为从属的关系或离散关系。v树型结构中，数据元素之间存在着“一对多”的关系。 v图或网状结构中，数据元素之间存在着“多对多”的关系 。 v在纯集合结构中，数据元素具有“同属于一个集合”的关 系。所有逻辑结构类型都可以看作集合结构类型 或纯集合结构类型的特例。 1.2 数据结构的相关概念2

10、. 物理结构:物理结构也称为存储结构，是逻辑结构的数据元素在计算机的物理存 储空间上地映象，映象不仅包含数据元素本身，而且包含着数据元素之间的 关联方式，即关系的映象。 逻辑结构又可以分为：顺序映象和非顺序映象。1) 顺序映象顺序映象是指数据元素在一块连续地物理存储空间上存储，物理存储空 间只用于存放数据元素本身，数据元素之间的关联以两个数据元素存储的相 邻关系来表示或通过某个函数来表示。或者说，利用数据元素在存储空间上的相对位置来表示数据元素之间 的逻辑关系。事例:2)非顺序映象非顺序映象是指数据元素在物理存储空间上非连续地存储，物理存储空 间不仅存放数据元素本身，而且为实现数据元素之间的关

11、联，在每个数据元 素存储的相邻空间中存储该数据元素关联的另一个或多个数据元素的起始地 址。也可以说数据元素之间的关系是由附加“链接或指针”来表示。事例:非顺序映象存储结构中，数据元素的逻辑结构一般在物理空间上不是 以物理空间的相邻来表现，而是在每个数据元素本身所占用空间的相邻空间 中，存放该数据元素所关联的另一个或多个数据元素的位置，通常将这个空 间称为链地址空间。 1.2 数据结构的相关概念物理结构彭亮，97，王明，95，李智，90，刘丹，88，肖象，78 彭亮，97王明，95李智，90刘丹，88肖象，78图 成绩信息的顺序映象1234100002A0003BC004DEF05GHIJ500

12、000ABCDEFGHIJ图 下三角矩阵的顺序映象DBACFE空空空空图1.2.6 树的存储结构树的起点地址ABCEFD图 二分枝的树逻辑结构3. 数据域和链接域1)数据域数据域是物理存储空间中存储数据元素中数 据值的空间，如成绩数据问题中，存储姓名和成 绩两个数据项，所占用的空间大小（字节数）依 实际应用的数据元素中包含的信息量的大小而定 。2)链接域链接域又称指针域，是非顺序存储映象时表 示数据元素之间关系的地址存储空间，是额外的 空间付出。 一般地，在特定计算机中，存放存储单元的地址 所占用的空间大小（字节数）是一定的。在顺序 存储映象结构中，链接域是不存在的，数据元素 之间关系是以物理

13、存储的邻接方式隐含表示的。 1.2 数据结构的相关概念1.2.4 静态存储空间分配和动态存储空间分配存储管理是研究数据元素的空间分配、回收的方法和机 制。 1. 静态存储空间分配静态存储空间分配模式下，数据元素的存储过程是分 两步完成的，一是一次性获取连续的物理存储空间，二是 在获取的物理空间上的物理映象。如：程序中需要使用数组 2. 动态存储空间分配动态存储空间分配模式下，数据元素的存储过程是一 步完成的，即，获取单个物理存储空间的同时完成数据元 素在物理空间上的映象。如：在C语言中利用malloc()函数或new申请变量空间（动态空间申请 ），如果某变量空间不再使用，则利用free()函数

14、或delete释放变量空间（ 动态空间释放）。 1.2 数据结构的相关概念1.2 数据结构的相关概念结构类型 逻辑结构 物理结构 线性结构：线性表、堆栈、队列等 非线性结构：树形结构、图结构、纯集合结构 顺序映象非顺序映象：数据域和链接域 1.3 数据类型、抽象数据类型和数 据结构 1.数据类型（data type） 数据类型具体含义是，它描述了一组数 据和在这组数据上的操作或运算及其操作或 运算的接口。 2.抽象数据类型抽象数据类型是指不涉及数据值的具体 表示，只涉及数据值的值域，操作或运算与 具体实现无关，只描述操作或运算所满足的 抽象性质的数据类型和接口。1.3 数据类型、抽象数据类型和

15、数据结构 3.抽象数据类型的三元组表示 ADT 抽象数据类型名 Dset：【数据元素集描述】 Rset：【数据元素的关系集描述】 OPSet：【数据元素操作集描述】 ADT 二叉树抽象数据类型 Dset： 数据元素具有三个成员【数据值、左链接指针、右链接指针】 Rset： 数据元素如果不空，则被分为根结点、左子树、右子树，每个子 树仍是一个二叉树 OPSet： void PreOrder (BinaryTreeNode *t) 二叉树的 前序遍历 void PostOrder (BinaryTreeNode *t) 二叉树的 后序遍历 1.3 数据类型、抽象数据类型和数据结构 1.4 算法及算法分析、算法描 述 1.4.1 算法和程序 1. 算法 算法是指解决问题的一种方法或一个过程。算法可以理解为函数的另 一种表述，所以，一个给定的算法解决一个特定的问题。算法也可以 描述为：算法（algorithm）:算法是非空的、有限的指令序列，遵循它就可 以完成某一确定的任务。它有五大特征：v有穷性：一个算法在执行有限步骤之后必须终止。 v确定性：一个算法所给出的每一个计算步骤（通常是指算法描述中的 下一步）必须是精确定义的，无二义性。v可行性：算法中要执行的每一个步骤都可以在有限时间内完成。v输入：算法一般有一组作为加工对象的量值，即对算