学习目标

完成本节后，你应该能够：

• 解释数据结构要解决什么问题；
• 区分逻辑结构与存储结构；
• 识别集合、线性、树形和图结构中的元素关系；
• 理解抽象数据类型与具体代码实现的区别；
• 根据主要操作初步选择数据组织方式。

从实际问题开始

假设你要为中山大学计算机学院编写一个学生信息管理程序。每名学生都有学号、姓名和成绩，程序需要完成以下工作：

• 保存不断增加的学生记录；
• 按学号查找并修改一名学生；
• 在指定位置插入或删除记录；
• 按当前顺序浏览全部学生。

当记录只有三五条时，把数据写在几个变量里似乎也能工作。记录增长到几百、几万条以后，问题就变成了：一条记录由哪些数据项组成？记录之间是否有顺序？它们在内存中怎样放置？查找、插入和删除分别要付出什么代价？

IDEA直觉理解

数据结构不仅负责“把数据存起来”，还要描述数据元素之间的关系、它们在计算机中的表示方式，以及程序允许执行的操作。

数据结构的基本术语

先用学生信息管理这一例子建立共同语言。

数据

数据是对客观事物的描述，是能够被计算机输入、存储和处理的符号。例如，计算机学院某名本科生的学号 20260017、姓名 "李明" 和成绩 86.5 都可以成为程序中的数据。

数据元素

数据元素是数据集合中的一个基本单位。在学生信息表中，“李明这一名学生的完整记录”是一个数据元素。

数据项

数据项是构成一个数据元素的属性。在一条学生记录中，学号、姓名和成绩分别是数据项。数据项通常是当前讨论层次中具有独立含义的最小单位。

数据对象

数据对象是具有相同性质的数据元素的集合。例如，计算机学院 2026 级所有学生记录共同组成一个学生数据对象。

数据结构

DEF定义 · 数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素集合，以及这些关系在计算机中的表示和相关操作。

在学生信息管理程序中，数据元素是学生记录；记录可能按录入顺序形成线性关系；程序还要规定查找、插入、删除和遍历等操作。这些内容共同构成一个数据结构，而不是某个孤立变量。

数据结构的三个层面

分析数据组织方案时，可以把问题分成三个层面。

层面	需要回答的问题	学生信息示例
逻辑结构	元素之间有什么关系？	学生记录按某个先后次序排列
存储结构	元素在计算机中怎样保存？	连续数组或由指针连接的节点
基本操作	程序需要对元素做什么？	查找、插入、删除、遍历和更新

逻辑结构描述问题本身，存储结构描述计算机中的实现方式，基本操作描述程序对数据的使用需求。一个逻辑结构可以有多种存储实现；同一种存储方式也能服务不同的逻辑结构。

常见逻辑结构

逻辑结构只关心元素之间的抽象关系，暂时不讨论指针或内存地址。

集合结构

集合结构中的元素除了“同属于一个集合”之外，没有额外的先后或层级关系。例如，计算机学院这一学期开设的全部课程编号可以看作一个集合。后续学习散列等结构时，会再次遇到强调成员关系与快速判定的场景。

线性结构

线性结构中的元素形成一对一的先后关系。除第一个元素外，每个元素最多有一个直接前驱；除最后一个元素外，每个元素最多有一个直接后继。按录入顺序排列的学生记录、抢课时的候补名单和开学报到的排队队伍都是线性结构。第 1 章将从线性表开始研究这种关系。

树形结构

树形结构表达一对多的层级关系。一个元素可以有多个直接后继，但通常只有一个直接前驱。中山大学“校区 → 学院 → 系/专业”的组织结构、文件目录和表达式语法树都是树形关系。后续树章节会研究节点之间的父子关系及其遍历方法。

图结构

图结构表达多对多的任意关联。一个元素可以与多个其他元素直接相连，例如社交关系、康乐园里连接各栋建筑的道路网络和课程先修关系。后续图章节会研究顶点、边、路径以及不同的图存储方式。

常见存储结构

确定逻辑关系后，还要选择怎样把元素和关系放进内存。下面仍使用计算机学院学生记录进行比较。

顺序存储

顺序存储把元素放在一段连续的存储区域中，元素位置可以通过起始位置和下标计算。它便于按位置访问，也有利于利用连续内存；但在中间插入或删除时，往往需要移动后续元素。

链式存储

链式存储让每个节点除了保存数据，还保存指向相关节点的链接。节点在物理内存中不必连续；调整链接可以改变逻辑次序，但按位置访问通常需要沿链接逐个经过节点。

下面的代码只展示两种存储方式的“外观”，不实现完整线性表。

sequential-storage.cpp

#include <array>
#include <cstddef>
#include <string>

struct Student {
    int id;
    std::string name;
};

std::array<Student, 100> records{};
std::size_t record_count = 0;

linked-storage.cpp

#include <string>

struct Student {
    int id;
    std::string name;
};

struct Node {
    Student value;
    Node* next = nullptr;
};

Node* head = nullptr;

左侧代码用数组中的相邻位置保存学生记录；右侧代码用 next 描述下一条记录的位置。两者都可以表示相同的线性逻辑关系，但物理布局和操作代价不同。

索引存储会额外维护“关键字到位置”的索引，散列存储则根据关键字计算存储位置。它们都能加快某些访问操作，但会引入额外空间和维护成本，本节只作预告。

数据结构的基本操作

数据结构的价值最终体现在它支持的操作上。

操作类别	典型动作	设计时要问的问题
创建与销毁	初始化、释放资源	容量何时确定？资源由谁管理？
访问与遍历	读取指定元素、依次处理全部元素	更常按位置访问，还是从头到尾扫描？
查找与更新	按学号定位并修改记录	使用什么关键字？查找是否频繁？
插入与删除	增加或移除记录	操作集中在表尾、表头还是任意位置？

因此，选择数据结构时应先列出最重要、最频繁的操作，再比较不同方案。先决定“必须用数组”或“必须用链表”，再反过来迁就需求，通常会掩盖真正的取舍。

抽象数据类型

抽象数据类型（Abstract Data Type，ADT）从使用者角度规定数据对象、数据关系和允许执行的操作，但不限定操作的具体实现。

以学生线性表为例，使用者关心能否查询长度、按学号查找、插入和删除；实现者才需要决定内部使用数组、链表还是其他方式。

#include <cstddef>

struct Student;

class StudentList {
public:
    virtual ~StudentList() = default;

    virtual std::size_t size() const = 0;
    virtual const Student* find_by_id(int id) const = 0;
    virtual bool insert(std::size_t position, const Student& student) = 0;
    virtual bool erase_by_id(int id) = 0;
};

student-list-interface.cpp

这段接口只描述“可以做什么”，没有给出成员数组或节点指针。顺序表和链表都可以兑现同一组约定，因此“ADT 是什么”与“ADT 怎样实现”是两个不同问题。

DEF定义 · 抽象数据类型

ADT 是对数据对象、数据关系和基本操作的抽象约定。它隐藏实现细节，使使用者可以依据接口思考行为，使实现者可以在不改变约定的前提下更换存储方案。

综合例题

题面

计算机学院需要维护一个小型通讯录。联系人按用户设定的顺序显示，程序需要顺序浏览全部联系人、按学号查找联系人、在任意位置插入新联系人，并删除离校学生。通讯录初期只有几十条记录，之后可能持续增长。

请描述它的逻辑结构、基本操作、可选存储结构和主要取舍。

分析

1. 逻辑结构：联系人存在明确的显示顺序，因此主体是线性结构。
2. 基本操作：需要遍历、按学号查找、按位置插入和按学号删除；其中哪些操作最频繁，需要通过真实使用情况确认。
3. 顺序存储方案：连续存放便于按位置访问和完整遍历，结构简单；但在中间插入或删除时，可能移动许多后续元素。
4. 链式存储方案：找到目标位置后可以通过修改链接完成插入或删除，且容量较灵活；但按位置访问需要沿链接前进，每个节点还要保存链接信息。
5. 进一步改进：如果按学号查找非常频繁，可以在主体结构之外维护索引或采用适合关键字查找的结构，但这会增加空间和同步维护成本。

结论

需求没有给出“唯一正确”的实现。如果记录规模较小、遍历和按位置访问更常见，顺序存储通常更直接；如果中间插入、删除频繁且已有目标节点位置，链式存储可能更合适。最终选择必须建立在操作频率、规模和空间限制之上。

常见误区

常见误区

• “数据结构就是某个容器类。” 容器类只是某种具体实现；数据结构还包括元素关系和操作约定。
• “逻辑结构决定了唯一的存储结构。” 同一线性结构既可以顺序存储，也可以链式存储。
• “链式存储一定比顺序存储高级。” 两者优化的操作不同，还要考虑缓存局部性、额外链接和实现复杂度。
• “存在所有场景下都最好的数据结构。” 任何选择都必须说明规模、主要操作和资源限制。
• “先选数组或链表，再写需求。” 正确顺序应是先分析问题和操作，再选择表示方法。

小结与自测

分析一个数据组织问题时，可以沿着下面的路径思考：

实际问题 → 逻辑关系 → 抽象操作 → 存储方式 → 具体实现

自测题

1. 学生记录中的“姓名”是数据元素还是数据项？一条完整学生记录呢？
2. 线性结构与顺序存储有什么区别？
3. 文件目录通常属于哪一种逻辑结构？道路网络呢？
4. 为什么同一个线性表 ADT 可以同时有顺序表和链表实现？
5. 设计一个选课名单时，应该先问哪些操作最常发生？

查看参考答案

1. 姓名是数据项，一条完整学生记录是数据元素。
2. 线性结构描述元素间一对一的逻辑关系；顺序存储描述元素在连续存储区域中的物理表示。
3. 文件目录通常是树形结构，道路网络通常用图结构表示。
4. ADT 只约定数据与操作行为，不限定内部存储；两种实现可以遵守同一接口。
5. 至少应确认是否频繁遍历、按位置访问、按关键字查找、在何处插入和删除，以及数据规模如何增长。

同一种需求可能有多种正确实现。下一节将建立统一的分析方法，比较这些实现随输入规模增长时需要付出的时间与空间代价。