数据结构的基本概念

3115 字 阅读约 10 分钟

1.1 数据结构的基本概念

在正式学习各种具体的数据结构之前，我们需要先建立一套公共的语言。什么是"数据"？什么是"数据结构"？它们由哪些要素组成？这一节将为后续所有章节奠定概念基础。

基本概念与术语

数据（Data）

数据是信息的载体，是描述客观事物属性的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

数据不仅仅是我们熟悉的数字——一段文字、一张图片、一段音频，在计算机看来都是数据。

42                     ← 数值数据
"Hello World"          ← 字符数据
[1, 2, 3, 4, 5]        ← 集合数据
{name: "Koyuki", age: 18}  ← 结构化数据

数据元素（Data Element）

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。

  • 一个学生的全部信息是一个数据元素。
  • 一本书的书目记录是一个数据元素。
  • 一条订单记录是一个数据元素。
// 这是一个数据元素
struct Student
{
    int id;
    string name;
    int age;
    double score;
};

数据项（Data Item）

数据项是构成数据元素的不可分割的最小单位。

一个学生数据元素由多个数据项组成：

学生 = {
    学号: 2024001,      ← 一个数据项
    姓名: "Koyuki",     ← 一个数据项
    年龄: 18,            ← 一个数据项
    成绩: 92.5           ← 一个数据项
}

数据对象（Data Object）

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

所有学生 → 一个数据对象（每个学生是一个数据元素）
所有整数 → 一个数据对象（每个整数是一个数据元素）
所有字符 → 一个数据对象（每个字符是一个数据元素）

数据结构（Data Structure）

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

更准确地说：数据结构 = 数据元素 + 元素之间的关系。

数据结构 = {
    数据元素,
    元素之间的结构关系
}

通俗理解

数据元素就像剧院里的观众，数据结构就是观众的"座位安排"——大家坐在哪里、谁挨着谁、入场顺序如何。同样的观众（数据），安排方式（结构）不同，管理效率就不同。

数据结构的三要素

任何数据结构都包含三个不可分割的方面：

数据结构
├── 逻辑结构
├── 存储结构（物理结构）
└── 数据的运算

一、逻辑结构

逻辑结构描述数据元素之间的逻辑关系，与数据的存储无关。它回答的问题是："数据元素之间是怎样的关系？"

逻辑结构分为两大类四种：

分类结构类型特点示例
线性结构线性结构一对一数组、链表、栈、队列
非线性结构树形结构一对多二叉树、B 树、堆
图形结构多对多无向图、有向图
集合结构无关系（同属一个集合）哈希集合

线性结构——数据元素之间存在一对一的线性关系：

[1] → [2] → [3] → [4] → [5]
     每个元素最多有一个前驱和一个后继

树形结构——数据元素之间存在一对多的层次关系：

        [A]
       /   \
     [B]   [C]
    /   \    \
  [D]  [E]  [F]
    每个节点最多有一个前驱，可以有多个后继

图形结构——数据元素之间存在多对多的网状关系：

    [A] ——— [B]
     |  \   /  |
     |   [C]   |
     |  /   \  |
    [D] ——— [E]
    任意两个节点之间都可以有关系

集合结构——数据元素同属一个集合，元素之间没有其他关系：

    { A, B, C, D, E }
    元素之间仅"同属一个集合"这一关系

二、存储结构（物理结构）

存储结构描述数据结构在计算机存储器中的实际存放方式。它回答的问题是："数据在内存中怎么放？"

常见的存储结构有四种：

1. 顺序存储

逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

// 顺序存储：用数组实现
int arr[5] = {1, 2, 3, 4, 5};

// 内存中：arr[0], arr[1], arr[2], arr[3], arr[4] 连续存放

优点：随机访问快、存储密度高。 缺点：插入删除需要移动大量元素、需要连续的大块内存。

2. 链式存储

逻辑上相邻的元素在物理位置上可以不相邻，通过指针来表示元素之间的逻辑关系。

// 链式存储：用指针串联
struct Node
{
    int data;
    Node* next;     // 指向下一个节点
};
内存中可以任意分布：
[Node1] 地址 0x100 → next = 0x300
[Node2] 地址 0x300 → next = 0x200
[Node3] 地址 0x200 → next = nullptr

优点：插入删除只需修改指针、不需要连续的大块内存。 缺点：不能随机访问、存储密度低（需要额外存储指针）。

3. 索引存储

在存储元素信息的同时，建立附加的索引表。索引表中的每一项称为索引项，一般形式为 (关键字, 地址)。

索引表:                         数据区:
| 关键字 | 地址  |             地址  | 数据
|  001   | 0x20  |     →      0x10  | ...
|  005   | 0x50  |     →      0x20  | 数据001
|  010   | 0x30  |     →      0x30  | 数据010
                               0x50  | 数据005

优点：检索速度快。 缺点：需要额外空间存储索引表、增删数据时索引表也要更新。

4. 散列存储

根据元素的关键字直接计算出该元素的存储地址，又称 Hash 存储。

// 散列存储：通过哈希函数直接定位
int hash(string key)
{
    return key.length() % 10;  // 简单的哈希函数
}
// "abc" → hash("abc") = 3 → 存储在 3 号位置

优点：查找、插入、删除速度极快（理想情况下 O(1)）。 缺点：可能出现哈希冲突、空间利用率不高。

三、数据的运算

数据的运算是施加在数据上的操作，包括运算的定义和运算的实现。

  • 运算的定义针对逻辑结构，指出运算的功能，是面向用户的。
  • 运算的实现针对存储结构，指出运算的具体步骤，是面向程序员的。

常见的数据运算包括：

运算含义
查找在数据结构中找出满足特定条件的元素
插入在数据结构中添加新的元素
删除将指定元素从数据结构中移除
修改改变数据结构中某个元素的值
排序将数据结构中的元素按某种规则重新排列
遍历按某种顺序访问数据结构中的每个元素，且每个元素只访问一次

运算与存储结构的关系

同一种运算，在不同的存储结构上实现，效率可能天差地别。比如"在第 i 个位置插入一个元素"：

  • 顺序存储：需要移动 n-i 个元素 → O(n)
  • 链式存储：只需修改几个指针 → O(1)（前提是已经定位到插入位置）

因此，学习数据结构的关键在于：根据实际场景选择最合适的逻辑结构和存储结构。

小结

概念定义
数据信息的载体，计算机可处理的符号集合
数据元素数据的基本单位
数据项数据元素的最小不可分割单位
数据对象相同性质的数据元素的集合
数据结构数据元素 + 元素之间的关系

数据结构的三个要素相互关联：逻辑结构定义"关系"，存储结构决定"怎么存"，数据运算回答"能做什么"。同一逻辑结构可以用不同存储结构实现，反过来，不同的存储结构会影响运算的效率。

下一节我们将讨论什么是算法，以及如何评价一个算法的好坏。