算法是处理问题的策略，数据结构是描述问题信息的数据模型，程序则是计算机按照处理问题的策略处理问题信息的一组指令集

——《算法+数据结构=程序》Niklaus Wirth

数据结构（Data Structure） 是相互之间存在一种或多种特定关系的数据元素的集合。它可以用形式化的二元组表示为：

Data-Structure=(D,S)

其中：

  • D 是数据元素的有限集

  • S 是 D 上关系的有限集

简单来说，数据结构不仅要存储数据元素本身，还要存储数据元素之间的逻辑关系。它是计算机存储、组织数据的方式，直接影响算法的效率。

2. 数据结构的三个要素

2.1 数据的逻辑结构

逻辑结构是指数据元素之间的逻辑关系，从逻辑关系上描述数据，独立于计算机存储方式。

逻辑结构的四大分类：

表格

逻辑结构

特征描述

示例

集合结构

元素间除"同属一个集合"外，别无其他关系

数学中的集合概念

线性结构

一对一关系，除首尾外，每个元素有唯一前驱和唯一后继

线性表、栈、队列

树形结构

一对多关系，存在层次关系

二叉树、B树、堆

图状结构（网状）

多对多关系，任意两个元素都可能相关

有向图、无向图、网

线性结构的数学定义： R={⟨a1​,a2​⟩,⟨a2​,a3​⟩,…,⟨an−1​,an​⟩}

其中 ⟨x,y⟩ 表示 x 是 y 的直接前驱，y 是 x 的直接后继。

2.2 数据的存储结构（物理结构）

存储结构是数据结构在计算机中的表示（映像），解决逻辑结构如何在内存中物理实现的问题 。

四种基本存储方式：

① 顺序存储

  • 原理：逻辑上相邻的元素存储在物理位置也相邻的存储单元中

  • 优点：支持随机存取，存储密度高（无额外开销）

  • 缺点：插入删除需移动大量元素，可能产生外部碎片

  • 实现：数组

② 链式存储

  • 原理：逻辑相邻的元素物理位置可不相邻，通过指针表示逻辑关系

  • 优点：充分利用存储单元，无外部碎片，插入删除高效

  • 缺点：额外存储指针空间，只能顺序存取

  • 实现：链表（单链表、双向链表、循环链表）

③ 索引存储

  • 原理：存储元素信息的同时，建立附加的索引表（关键字+地址）

  • 优点：检索速度快

  • 缺点：占用额外空间，增删数据需修改索引表

④ 散列存储（哈希存储）

  • 原理：根据元素的关键字通过散列函数直接计算存储地址

  • 优点：增删查操作平均时间复杂度 O(1)

  • 缺点：哈希函数设计不好会产生冲突，解决冲突会增加时空开销

关键理解：同一种逻辑结构可以采用不同的存储结构实现。例如线性表既可以用顺序表（数组）实现，也可以用链表（指针）实现，它们的操作效率截然不同。

2.3 数据的运算

运算包括运算的定义和运算的实现两个层面：

  • 运算的定义：针对逻辑结构，指出运算的功能（做什么）

  • 运算的实现：针对存储结构，指出运算的具体操作步骤（怎么做）

基本运算类型：

运算类型

功能说明

查找

在结构中查找满足条件的元素

插入

在指定位置添加新元素

删除

移除指定位置的元素

修改

改变特定元素的值

排序

按特定规则重新排列元素

遍历

按某种顺序访问所有元素

示例：对于线性表的基本运算

  • InitList(&L)：初始化空表

  • ListInsert(&L, i, e)：在第 i 个位置插入元素 e

  • ListDelete(&L, i, &e)：删除第 i 个元素，值存入 e

  • LocateElem(L, e)：按值查找

  • GetElem(L, i)：按位查找

3. 抽象数据类型（ADT）

3.1 数据类型

数据类型是一个值的集合和定义在该值集上的一组操作的总称。

  • 原子类型：值不可再分（如 int, bool, float）

  • 结构类型：值可分解为若干成分（如 struct, 数组）

3.2 抽象数据类型（ADT）详解

抽象数据类型（Abstract Data Type, ADT） 是抽象数据组织及与之相关的操作，用数学化的语言定义数据的逻辑结构和运算，与具体实现无关

ADT的核心思想："接口与实现分离"

  • 只定义"数据结构要做什么"，不关心"具体怎么做"

  • 同一种ADT可以有多种物理实现（如线性表可用顺序表或链表实现）

  • 使用者无需关注底层细节

ADT的形式化定义（三元组）： ADT=(D,S,P)

  • D ：数据对象（数据元素的集合）

  • S ：D 上的关系集（逻辑结构）

  • P ：对 D 的基本操作集

线性表ADT示例：plai

ADT List {
    数据对象：D = {a_i | a_i ∈ ElemSet, i=1,2,...,n, n≥0}
    数据关系：R = {<a_{i-1}, a_i> | a_{i-1}, a_i ∈ D, i=2,...,n}
    
    基本操作：
    InitList(&L)      // 构造空线性表L
    DestroyList(&L)   // 销毁线性表L
    ListInsert(&L, i, e)  // 在L中第i个位置之前插入元素e
    ListDelete(&L, i, &e) // 删除L中第i个数据元素，用e返回其值
    LocateElem(L, e)  // 在L中查找与e相等的元素
    GetElem(L, i, &e) // 用e返回L中第i个数据元素的值
} ADT List

4. 算法基础

4.1 算法的定义

算法（Algorithm） 是对特定问题求解步骤的一种描述，是指令的有限序列。它取一个或一组值为输入，并产生出一个或一组值作为输出。

4.2 算法的五个重要特征

表格

特征

说明

有穷性

算法必须在执行有限步骤后终止，且每步在有限时间内完成

确定性

每条指令必须有确切的含义，相同输入只能得到相同输出

可行性

算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现

输入

零个或多个输入

输出

一个或多个输出

4.3 算法效率的度量

评价算法优劣的标准：

  • 正确性：算法应满足具体问题的需求

  • 可读性：算法应易于理解和维护

  • 健壮性：输入非法数据时，算法能适当处理而不会产生异常

  • 效率：时间效率和空间效率

时间复杂度和空间复杂度是衡量算法效率的两个核心指标。

5. 数据结构、数据类型与ADT的关系pl

数据类型（Data Type）
    ├── 原子类型（int, float, char...）
    └── 结构类型（struct, array...）
        └── 数据结构（Data Structure）
            ├── 逻辑结构（线性、树、图）
            ├── 存储结构（顺序、链式、索引、散列）
            └── 运算（增删改查...）
                └── 抽象数据类型 ADT（数学模型+操作）
                    └── 具体实现（代码）

关键区别：

  • 数据结构：强调数据元素之间的关系及存储方式

  • 数据类型：强调值的集合和允许的操作

  • ADT：强调逻辑特性，隐藏实现细节，是数据结构的抽象描述

6. 学习数据结构的意义

  1. 程序 = 数据结构 + 算法（Niklaus Wirth）

  2. 选择合适的数据结构可以：

    • 提高程序执行效率（降低时间复杂度）

    • 减少内存占用（降低空间复杂度）

    • 使代码更易维护和扩展

  3. 是操作系统、数据库、编译原理等高级课程的基础

7. 小结

表格

概念

核心要点

数据

信息的载体，可被计算机识别和处理的符号集合

数据元素

数据的基本单位（元素、结点、记录）

数据项

构成数据元素的最小单位（字段、域）

数据结构

数据元素集合 + 元素间关系（逻辑结构+存储结构+运算）

逻辑结构

元素间逻辑关系（集合、线性、树、图）

存储结构

内存中的表示方式（顺序、链式、索引、散列）

ADT

数学模型+操作定义，与实现无关