计算机数据结构的知识点(9)

[总结]

数据项组成数据元素，数据元素组成数据对象，数据对象组成数据

数据结构（Data Structure）：是相互之间存在一种或多种特定关系的数据元素的集合。它包括三个方面：数据元素的逻辑结构、存储结构和相适应的运算（操作）。

数据元素之间的逻辑关系被称为数据元素的逻辑结构，可以用一个二元组表示：

Data_Structure = (D, S) // Data_Structure= (Data-part, Logic-Structure-Part)

这里D是数据元素的集合，S是定义在D（或其他集合）上的关系的集合，

S = { R │ R : D×D×...}。

数据的逻辑结构可归结为以下四类:

（1）集合结构

结构中的数据元素之间除了同属于一个集合的关系外别无其他关系

（2）线性结构

结构中的数据元素之间存在一个对一个的前趋后继关系

在此种结构下：

有且仅有一个元素无前趋元素

有且仅有一个元素无后继元素

其余任何一个元素均有且仅有一个前趋有且仅有一个后继元素。

（3）树形结构

结构中的数据元素之间存在一个对多个的关系

任何一个节点最多有一个前趋，可以有多个后继，是一种典型的非线性结构

（4）图状结构（网状结构）

结构中的数据元素之间存在多个对多个的关系

这种结构的特征是任何一个元素可以有多个前趋，也可以有多个后继，是一种多对多的前趋后继关系

表和树是最常用的两种高效数据结构，许多高效的算法可以用这两种数据结构来设计实现。表是线性结构的（全序关系），树(偏序或层次关系)和图（局部有序(weak/local orders)）是非线性结构。

数据结构在计算机中的表示（又称为映像）称为数据的存储结构（物理结构）

数据结构的物理结构是指逻辑结构的存储映像(image)。数据结构 DS 的物理结构 P 对应于从 DS 的数据元素到存储区M（维护着逻辑结构S）的一个映射：

PD,S) -- > M

存储器模型：一个存储器 M 是一系列固定大小的存储单元，每个单元 U 有一个唯一的地址 A(U)，该地址被连续地编码。每个单元 U 有一个唯一的后继单元 U'=succ(U)。

P 的四种基本映射模型：顺序（sequential）、链接（linked）、索引（indexed）和散列（hashing）映射。因此，我们至少可以得到4×4种可能的物理数据结构：

sequential (sets)

linked lists

indexed trees

hashing

graphs


　　　 　

　　需要指出的是：并不是所有的可能组合都合理。

数据结构DS上的操作：所有的定义在DS上的操作在改变数据元素（节点）或节点的域时必须保持DS的逻辑和物理结构。

DS上的基本操作：任何其他对DS的高级操作都可以用这些基本操作来实现。最好将DS和