数据结构序章

每日一言

It doesn’t matter what you achieve in life. It’s how you live that really matters. Countless men have lost their lives in war without fulfilling their life’s ambitions. Shiba stood by his convictions, no matter how lonely he got. So I think that in the end, he must’ve been happier than anyone. – Deerhound

数据结构绪论

数据的定义

数据（data）是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理（输入、存储、运算、输出）的符号的总称。

数据的分类

1. 数值数据：数据的类型就是一个数据，我们可以对数据进行运算等
2. 非数值数据：字符、文字、图形、图像、声音等，数据只是编码，解码后显示的内容才是信息

数据结构的定义

• 数据结构（data struct）：是指相互之间存在着一种或多种特定关系的数据元素的集合。
• 数据元素（data element）：是数据的基本单位；在计算机中通常做为一个整体进行考虑和处理；一个数据元素可以由若干个数据项组成
• 数据项：是具有独立含义的表示单位，是数据的不可分割的最小单位
• 数据：是对客观事物的符号表示；是能被计算机识别、存储、和加工处理的符号的总称

大小关系： 数据>数据元素>数据项（最小不可分割单位）

数据由多个数据元素按照一种或多种关系组成，单个数据元素往往由多个数据项组成。

数据结构的组成

• 多个数据元素间的逻辑关系，数据的逻辑结构。 如：集合、线性结构、树形结构、图形结构
• 数据在计算机中的实际存储方式，数据的存储结构。如：顺序存储、链式存储、索引存储、散列存储
• 在这些数据上定义的一组运算，数据的运算或操作。如：引用型运算、加工型运算。

逻辑结构：数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。

存储结构：数据元素及其关系在计算机存储器中的存储方式。

逻辑结构的划分

粗化法

1. 线性结构—— 有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。
2. 非线性结构—— 一个结点可能有多个或0个直接前趋和直接后继。

细化法

1. 集合—— 数据元素间除了同属一个集合外无任何关系
2. 线性结构—— 一个对一个，有逻辑的先后关系
3. 树形结构—— 一个对多个
4. 图形结构—— 多个对多个

总结：

存储结构的划分

1. 顺序存储结构——数据元素依次放在连续的存储单元中
2. 链式存储结构——借助指示元素存储地址的指针
3. 索引存储
4. 散列存储

随机存取与其他存取方式

随机存取（Random Access）

• 定义： 可以直接通过索引（下标）访问数据，无需按顺序逐一查找。
• 特点： 访问时间与数据位置无关，几乎是常数时间O(1)。
• 示例： 数组。

顺序存取（Sequential Access）

• 定义： 必须按照特定的顺序逐一访问数据。
• 特点： 访问时间与数据位置有关，通常需要遍历前面的数据。
• 示例： 链表、磁带。

直接存取（Direct Access）

• 定义： 可以通过一个或多个关键字直接访问数据，但访问时间可能不固定。
• 特点： 介于随机存取和顺序存取之间。
• 示例： 哈希表（通过哈希函数计算出数据的位置）。

索引存取

• 定义： 通过索引结构（如B+树）来定位数据。
• 特点： 结合了随机存取和顺序存取的优点，可以快速定位数据，同时支持范围查询。
• 示例： 数据库索引。