1数据结构的定义及概念.pdf
数据结构的定义数据结构的定义 Data Structure 引例 数据结构的基本概念 数据结构的研究内容 本讲授课目录 引例1：书目自动检索系统 登录号：登录号： 书名：书名： 作者名： 分类号：分类号： 出版单位：出版单位： 出版时间：出版时间： 价格： 书目卡片书目卡片 001高等数学樊映川S01 002 理论力学罗远祥 L01 003高等数学华罗庚S01 004线性代数栾汝书S02 线性表线性表 引例2：博弈树 4/56 树 引例3：TSP问题 图 求解非数值计算的问题 描述这类非数值计算问题的数学模型不再是数学方程，而 是诸如表、树和图之类的数据结构。 主要考虑的是设计出合适的数据结构及相应的算法。即： 首先要考虑对相关的各种信息如何表示、组织和存储？ 因此，可以认为：数据结构是一门研究非数值计算的程序 设计问题中计算机的操作对象以及它们之间的关系和操作 的学科。 引例 数据结构的基本概念 数据结构的研究内容 本讲授课目录 数据 数据元素 数据对象 数据结构 二、数据结构基本概念 ， 数据（Data） 数据是描述客观事物的数值、字符以及能输入机器且能被 处理的各种符号集合。 数据包含整型、实型、布尔型、图象、字符、声音等一切 可以输入到计算机中的符号集合。 数据元素（数据元素（Data Element） 数据元素是组成数据的基本单位 ，是数据集合的个体，在 计算机中通常作为一个整体进行考虑和处理。例如： . . . . . . 北京北京 1983.111983.11 河北河北 女女 赵虹玲赵虹玲 101 住住 址址 出生年月出生年月 籍籍 贯贯 性性 别别 姓姓 名名 学学 号号 数数 据据 元元 素素 数据项数据项 数据对象（数据对象（Data Object） 数据对象是性质相同的数据元素的集合，是数据的一个子数据对象是性质相同的数据元素的集合，是数据的一个子 集。集。 整数集合：整数集合：N=0，1，2， 无限集无限集 字符集合：字符集合：C=A，B，Z 有限集有限集 什么是数据结构 是相互之间存在一种或多种特定关系的数据元素的集合。是相互之间存在一种或多种特定关系的数据元素的集合。 或按照一定逻辑关系组织，并按一定存储方法存储的数据或按照一定逻辑关系组织，并按一定存储方法存储的数据 的集合，且需要定义一系列运算。的集合，且需要定义一系列运算。逻辑结构逻辑结构、存储结构存储结构和和 运算运算合称为三要素。表示为：合称为三要素。表示为： Data_Structure=（D, R） 其中，其中，D D元素有限集，元素有限集，R R关系有限集关系有限集 引例 数据结构的基本概念 数据结构研究内容 本讲授课目录 数据的逻辑结构 数据的存储结构 数据的运算 三、数据结构中的三个问题 数据的逻辑结构 数据的逻辑结构从逻辑关系上描述数据，与数据的存储无 关 数据的逻辑结构可以看作是从具体问题抽象出来的数据模 型 逻逻 辑辑 结结 构构 集合集合 线性线性 树树 图图 例1：集合结构 set =（D，R） D = 01,02,03,04,05,06,07,08,09,10 R = 数据元素之间的联系：0:0 05 01 03 05 02 07 04 06 09 10 集合结构示意图集合结构示意图 例2:线性结构 linearity =（D，R） D = 01,02,03,04,05,06,07,08,09,10 R = , , 数据元素之间的联系： 1:1 05 01 03 08 02 07 04 06 09 10 线性结构示意图线性结构示意图 例3：树结构 tree =（D，R） D = 01,02,03,04,05,06,07,08,09,10 R = , , 数据元素之间的联系： 1:N 01 02 03 04 07 08 09 05 06 10 例4：图结构 graphics =（D，R） D = 01,02,03,04,05,06,07,08,09,10 R = , , , 例4：图结构 数据元素之间的联系：M:N 01 02 03 04 07 05 06 01 02 03 04 07 05 06 数据的存储结构 数据的存储结构（又叫物理结构）是逻辑结构用计算机语 言的实现 数据的存储结构依赖于计算机语言 逻逻 辑辑 结结 构构 集合集合 线性线性 树树 图图 物物 理理 结结 构构 顺序顺序 链式链式 索引索引 散列散列 存储方式对比 顺序存储借助元素在存储器中的相对位置来表示数据 元素间的逻辑关系 链式存储借助指示元素存储地址的指针表示数据元素 间的逻辑关系 a b c d e f g h i j Ha a b c d 数据结构的内容数据结构的内容 数据的逻辑结构 数据的存储结构 数据的运算:查找,排序,插入,删除,修改等 线性结构 非线性结构 顺序存储 非顺序存储 线性表 栈 队 树形结构 图形结构 Questions and answers
