数据结构三要素

数据结构的三要素包括数据逻辑结构、数据存储结构和数据的运算。

数据逻辑结构

数据的逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的具体存储形式无关，是独立于计算机的。数据逻辑结构通常分为线性结构和非线性结构。典型的数据结构与其逻辑结构的对应关系如下：

对于线性表、集合、树、图这四种典型的数据结构，他们分别有以下特点：

• 集合结构：数据元素之间只存在 “同属于一个集合”的关系。
• 线性结构：数据元素之间只存在“一对一”的关系。
• 树形结构：数据元素之间存在“一对多”的关系。
• 图状结构或网状结构：数据元素之间存在“多对多”的关系。

数据存储结构

数据的存储结构指的是数据结构在计算机中的表示，也称为物理结构，又称映像。它包括数据元素的表示和关系的表示。数据存储结构依赖于计算机语言，它是用计算机语言实现的逻辑结构。数据的线性存储结构主要有：顺序存储、链式存储、索引存储、散列存储。

1. 顺序存储：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里，元素之间的关系由存储单元之间的位置关系，即相邻关系来体现。如顺序表。
   • 优点：容易实现随机存取，每个元素占用最少的存储空间。
   • 缺点：只能使用相邻的一整块存储空间，容易产生较多的外部内存碎片。
2. 链式存储：使用表示元素存储地址的指针来表示元素之间的逻辑关系，此时不要求逻辑上相邻的数据元素在物理位置上也相邻。如单链表。
   • 优点：不会出现碎片内存，能充分利用存储单元。
   • 缺点：每个元素由于存储指针而占用额外的存储空间，且只能通过遍历实现顺序存取。
3. 索引存储：在存储数据元素的同时，建立一个附加的索引表。索引表中的每一项称为索引项项，其形式通常为（关键字，地址）。
   • 优点：检索速度快。
   • 缺点：附加的索引表会占用额外的存储空间。在添加或者删除数据元素时，需要同步修改索引表，因此会花费额外的时间。
4. 散列存储：根据元素的关键字以某种方式计算出该元素的存储地址，又称为 hash 存储。如哈希表。
   • 优点：检索、添加、删除的操作速度都很快。
   • 如果散列函数（或者 hash 函数）设计不好的话，可能会出现 hash 冲突，解决冲突又会增加时间和空间开销。

而数据的非线性存储结构主要有：树形存储、图形存储。

数据的运算

数据的运算主要体现为运算的定义，以及运算的实现。

运算的定义是针对数据逻辑结构的，它描述了运算所能实现的功能。

运算的实现是针对数据存储结构的，它描述了运算的具体操作过程。