数据结构的基本概念

数据结构基本概念

1. 数据

​ 数据（Data）是信息的载体，是对客观事物的符号化表示，是能被计算机识别、存储和处理的信息集合。各种数据在计算机内部都是用二进制形式保存的。数据是计算机程序加工的原料。

​ 例如：整数、浮点数、文本、图片、音视频等。

2. 数据元素

​ 数据元素（Data Element）是数据结构中的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

​ 例如：学生记录（含学号、姓名、成绩等）

3. 数据项

​ 数据项（Data Item）是构成数据元素的最小逻辑单位，在所处抽象层次上不再拆分。

​ 例如：学生记录中的“学号”字段。

4. 数据对象

​ 数据对象（Data Object）是**具有相同性质（类型）**的数据元素的集合，是数据的一个子集。

​ 例如：所有正整数构成的数据对象 N = {1, 2, 3, …}。

5. 数据结构

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

​ 数据结构的分类如图所示：

graph TD
    数据结构 --> 逻辑结构
    数据结构 --> 存储结构

    逻辑结构 --> 线性结构
    逻辑结构 --> 非线性结构
    非线性结构 --> 树形结构
    非线性结构 --> 图状结构
    逻辑结构 --> 集合结构

    存储结构 --> 顺序存储
    存储结构 --> 链式存储
    存储结构 --> 索引存储
    存储结构 --> 散列存储

5.1 逻辑结构的特点：

逻辑结构	特点	常见实现	典型应用
线性结构	一对一，首元节点无直接前驱，尾节点无直接后驱	顺序表、链表、队列、栈	缓冲区、任务调度
树形结构（非线性结构）	一对多，根节点无父节点	二叉树、B树、堆	文件索引、数据库索引
图状结构（非线性结构）	多对多	邻接矩阵、邻接表	社交网络、路径规划
集合结构	元素之间只有包含与不包含关系，除此之外无其他关系	顺序存储、链式存储、位向量、哈希集合、平衡树集合	去重、权限集合、关键词过滤

对于集合结构的补充：

​ 集合结构的经典操作是：并、交、差、补、判定。类似数学上对集合的描述

5.2 存储结构的描述

存储方式	描述	优点	缺点	典型应用
顺序存储	用一组地址连续的存储单元存放数据元素	支持随机访问，访问效率高，存储密度大	插入、删除效率低，最坏的情况下，时间复杂度为O(N)	顺序表、数组
链式存储	用节点（数据域+指针域）表示元素，通过指针表示关系	插入、删除效率高	不支持随机访问，访问指定节点需要遍历，最坏的情况下，时间复杂度为O(N)，存储密度低，需要额外的空间存放指针	单链表、双链表
索引存储	为数据元素建立附加索引表，加快查找	查找效率高	需要额外的空间维护索引	数据库索引、倒排索引
散列存储	根据关键字通过哈希函数直接计算存储地址	查找速度快（平均常数级）	可能发生冲突，需要解决方案（如扩充空间）	哈希表、符号表

graph TD
    %% 顺序存储
    subgraph Seq["顺序存储（数组）"]
    A[元素1] --> B[元素2] --> C[元素3]
    end

    %% 链式存储
    subgraph Link["链式存储（链表）"]
    A1[节点1: 数据+指针] -.-> N1[节点2: 数据+指针] -.-> N2[节点3: 数据+空指针]
    end

graph TD

	%% 索引存储
    subgraph Index["索引存储"]
    I1[索引1] --> D1[数据块1]
    I2[索引2] --> D2[数据块2]
    I3[索引3] --> D3[数据块3]
    end
    
    %% 散列存储
    subgraph Hash["散列存储（哈希表）"]
    K1[关键字1] --> H1["哈希函数 h(k1)"] --> B1[桶1: 存放元素1]
    K2[关键字2] --> H2["哈希函数 h(k2)"] --> B3[桶3: 存放元素2]
    K3[关键字3] --> H3["哈希函数 h(k3)"] --> B3
    end

5.3 数据的运算

​ 描述对该数据结构能够进行的操作集合及其实现算法。

• ​ 常见操作：
  • 查找（Search）：按值或按关键字查找元素
  • 插入（Insert）：在指定位置或条件下加入新元素
  • 删除（Delete）：移除指定元素
  • 修改（Update）：改变元素的值
  • 遍历（Traverse）：按一定顺序访问所有元素

6. 数据类型

​ 数据类型（Data Type）是一个值集合、定义在该集合上的一组操作以及相关约束规则的总称。

​ 例如：

// 学生信息
typedef struct {
    char name[100]; // 值集合：长度≤99 的可打印字符
    char student_id[20]; // 约束：10 位数字字符串，首位非 0
    ...
} Student;

// 相关操作
// 添加学生信息
void Add(Student *stu);
// 更新学生姓名
void updateStudentOfName(Student *stu, char *name);

6.1 抽象数据类型（ADT, Abstract Data Type)

​ 抽象数据类型是一种数学模型，由数据对象、数据对象上元素之间的逻辑关系以及一组定义良好的基本操作组成。

​ 使用时只需要知道定义什么和能够执行什么操作，而不用关心具体实现方式。

6.1.1 表示

​ $ADT=(D,R,P)$

• D: 数据对象（Data Object），即元素的取值范围。
• R：关系集（Relation），描述数据元素之间的关系。
• P：操作集（Operation），定义数据对象能够进行的操作。

6.1.2 核心思想

• 抽象：隐藏实现细节，对外只暴露接口
• 封装：通过接口暴露操作，保证数据和操作是一体的，外部不能随意破坏数据的正确性。
• 独立性：实现方式可以更换（例如数组或链表），而不影响使用者。

实际上这也是面对对象编程的核心思想