数据结构-存储结构.ppt

数据结构的基本概念 数据 数据元素 数据项 数据对象 数据是所有能被输入到计算机中，且能被计算机处理的符号的集合。 数据 数据元素 数据项 数据对象 数据元素是数据的基本单位，在计算机中通常作为一个整体来考虑和处理。 学号 姓名 性别 籍贯 0102345 吴一凡 男 江西南昌 数据 数据元素 数据项 数据对象 数据项是组成数据元素的、有独立含义的、不可分割的最小单位。 学号 姓名 性别 籍贯 0102345 吴一凡 男 江西南昌 数据 数据元素 数据项 数据对象 数据对象是性质相同的数据元素的集合，是数据的一个子集。 学号 姓名 性别 籍贯 0102345 吴一凡 男 江西南昌 0102346 陈圆圆 女 湖北武汉 0102347 李阳 男 江西九江 数据结构是相互之间存在一种或者多种特定关系的数据元素的集合。 这里的结构指的就是数据元素之间存在的关系。 数据结构 数据结构 逻辑结构 存储结构 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关。 数据结构 -逻辑结构 数据结构 -逻辑结构 集合结构 树形结构 线性结构 图状结构 集合结构：数据元素之间除了“属于同一集合”的关系外，别无其它关系。 线性结构：数据元素之间存在一对一的关系。 …… 树状结构：数据元素之间存在一对多的关系。 …… …… …… …… 图状结构或者网状结构：数据元素之间存在多对多的关系。 数据对象在计算机中的存储表示称为数据的存储结构，或者物理结构。 数据结构 -存储结构 存储结构 顺序存储结构 链式存储结构 顺序存储结构借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。通常借助程序设计语言的数组类型来描述，如左图所示。 元素n 元素i 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+(n-1)*m 存储地址 存储内容 … … 顺序存储结构 顺序存储结构要求所有的元素依此存放在一片连续的存储空间中。 链接存储结构不要求逻辑上相邻的结点在物理位置上亦相邻，所以不需要占用一整块的存储空间，但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存储后继元素的存储地址。如下图所示。 链式存储结构 存储地址 存储内容 指针 1345 1536 元素2 1400 元素1 1346 元素3 ∧ 元素4 h 链式存储结构通常借助于程序设计语言的指针类型来描述。 1345 元素1 1400 1400 元素2 1536 1536 元素3 1346 1346 元素4 ^