《1.1数据结构绪论》 包括但不限于：

• 数据结构的研究内容
  • 从早期的数值计算到非数值计算
  • 而非数值计算就引出了更多非数值的具有逻辑关系的数据类型
  • 数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。
• 基础术语
  • 数据——信息的载体
    • 数值型：整数，实数等。非数值型：文字图像图形声音等
    • 是能输入计算机且能被计算机处理的各种符号的集合
    • （计算机处理的数据，像是处理一个学校的学生考试成绩排名，此时所有学生的考试成绩就是数据。他的指向范围和研究的问题挂钩）
  • 数据元素——数据的基本单位
    • 数据元素在计算机程序中通常作为一个整体进行考虑和处理
    • 也称为元素、记录、结点、顶点
    • （类似c语言里的结构体变量，含有多个属性）
  • 数据项
    • 构成数据元素的不可分割的最小单位
    • （类似c语言里结构体的属性名）
  • 数据对象
    • 性质相同的数据元素的集合
    • 是数据的一个子集
    • （类似同一个结构体类型的变量）
  • 数据结构
    • 数据元素之间的关系称为结构
    • 是指带结构的数据元素的集合
    • 研究
      • 逻辑结构
        • 元素之间的逻辑关系和存储无关
      • 存储结构/物理结构/映像的表示
        • 如何在内存里存储数据元素
      • 运算和实现
• 逻辑结构
  • 划分一
    • 线性结构
      • 有且仅有一个开始和一个终端结点
      • 所有的节点都最多只有一个直接前趋和一个直接后继
      • 例如：线性表、栈、队列、串
    • 非线性结构
      • 一个结点可能有多个直接前趋和直接后继
      • 例如：树、图
  • 划分二
    • 集合
    • 线性
    • 树
    • 图
• 存储结构
  • 顺序
    • 用连续的空间依次存储数据
    • 逻辑关系用存储位置表示（所以可以快速推元素的存储位置）
  • 链式
    • 用任意的空间存储数据，数据之间的逻辑关系用指针来表示
  • 索引*
    • 建立附加的索引表来标识结点数据
    • 有稠密和稀疏索引
  • 散列*
    • 根据结点的关键字直接算出结点的存储地址

---

1.1 数据结构绪论

数据结构研究的是：如何组织数据、数据之间有什么关系，以及如何高效地对这些数据进行操作。

学习数据结构时，可以始终围绕三个问题展开：

1. 数据元素之间是什么关系？
2. 这些数据怎样存入计算机？
3. 怎样实现查找、插入、删除等操作？

一、数据结构的研究内容

1. 从数值计算到非数值计算

早期计算机主要用于数值计算，例如计算弹道、求解方程和进行科学计算。

随着计算机的发展，人们开始使用计算机处理越来越多的非数值问题，例如：

• 学生档案；
• 文字和图片；
• 文件目录；
• 城市交通路线；
• 社交网络；
• 课程之间的先修关系。

这些问题不只是处理数字，还要处理对象之间的逻辑关系。

例如，在学生成绩管理系统中，可能存在：

• 学生按照成绩排列的前后关系；
• 学生与班级之间的隶属关系；
• 学生与课程之间的选课关系。

因此，数据结构主要研究：

非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作。

这里的“非数值”是从问题意义上说的。

文字、图像和声音在计算机内部仍然会被编码成二进制数据。它们之所以称为非数值数据，是因为程序通常把它们当作文字、像素、声音片段或记录来处理，而不是把它们当作普通数字进行算术运算。

2. 数据结构研究的三个方面

可以把整个过程理解为：

实际问题 → 数据元素 → 逻辑关系 → 存储方式 → 运算实现

同一种逻辑结构可以使用不同的存储结构实现。

例如，逻辑上的线性表既可以用数组实现，也可以用链表实现。它们表达的是同一种逻辑关系，但具体操作的效率不同。

二、基础术语

下面使用学生成绩表来理解这些概念。

1. 数据

数据是能够被输入计算机，并且能够被计算机存储、处理和传输的各种符号的集合。

数据可以分为：

• 数值型数据：整数、实数等；
• 非数值型数据：文字、图形、图像、声音等。

在上面的成绩表中，学号、姓名和成绩都属于数据。

数据的具体范围取决于研究的问题。

例如：

• 研究学生排名时，需要学号、姓名和成绩；
• 研究分数段人数时，可能只需要成绩；
• 研究选课关系时，还需要学生和课程的信息。

所以，不能脱离具体问题来判断“哪些内容属于数据”。

2. 数据元素

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

在成绩表中：

一名学生的一整条记录就是一个数据元素。

例如：

1001，张三，92

这三个数据共同构成了张三这个数据元素。

数据元素在不同场景中有不同叫法：

3. 数据项

数据项是构成数据元素的、在当前问题中不再继续划分的最小单位。

在张三的学生记录中：

• 1001 是一个数据项；
• 张三 是一个数据项；
• 92 是一个数据项。

可以简单理解为：

数据元素像一整行记录，数据项像这一行中的一个字段值。

例如：

typedef struct {
    int id;
    char name[20];
    float score;
} Student;

这里：

• id、name、score 是字段名或成员名；
• 某个学生的 1001、张三、92 是具体的数据项值；
• 一个 Student 变量可以表示一个数据元素。

所以，数据项不完全等同于结构体中的属性名。属性名描述的是“这一项叫什么”，数据项通常指的是这项具体保存的数据。

“不可分割”也是相对当前问题而言的。

例如：

• 在普通通讯录中，电话号码可以作为一个数据项；
• 在研究电话号码地区的程序中，电话号码还可以继续分成国家码、区号和本地号码。

4. 数据对象

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

在成绩表中：

所有学生记录组成一个学生数据对象。

张三、李四和王五的记录都包含学号、姓名和成绩，具有相同的数据结构，因此可以放在同一个数据对象中。

用 C 语言类比：

• Student 是一种结构体类型；
• 一个 Student 变量可以表示一个数据元素；
• 多个 Student 变量组成的集合，可以看作一个数据对象。

5. 数据、数据元素、数据项和数据对象的关系

三、数据结构

数据元素之间的关系称为结构。

因此：

数据结构是带有特定关系的数据元素的集合。

例如，如果把学生按照成绩从高到低排列：

张三 → 王五 → 李四

此时，学生记录之间产生了明确的前后关系，这些记录及其关系就构成了一个线性数据结构。

数据结构主要研究：

1. 数据元素；
2. 数据元素之间的逻辑关系；
3. 数据元素的存储方式；
4. 作用于数据的运算；
5. 运算的具体实现。

在只描述逻辑关系时，可以把数据结构抽象表示为：

$$DS=(D,R)$$

其中：

• $D$ 表示数据元素的集合；
• $R$ 表示数据元素之间的关系。

四、逻辑结构

逻辑结构描述数据元素之间的关系，与数据实际存放在内存中的什么位置无关。

例如：

张三排在王五前面。

这是逻辑关系。

至于张三和王五的记录在内存中是否相邻，则属于存储结构研究的内容。

1. 线性结构

线性结构中的数据元素呈一对一的前后关系。

例如：

张三 → 王五 → 李四

对于一个包含两个或更多元素的有限线性结构：

• 有且只有一个开始结点；
• 有且只有一个终端结点；
• 开始结点没有直接前驱；
• 终端结点没有直接后继；
• 中间结点各有一个直接前驱和一个直接后继；
• 每个结点最多有一个直接前驱和一个直接后继。

需要注意两种特殊情况：

• 空结构没有开始结点和终端结点；
• 只有一个元素时，该元素既是开始结点，也是终端结点。

常见的线性结构包括：

• 线性表；
• 栈；
• 队列；
• 串。

栈和队列本质上也具有线性关系，只是允许进行的操作受到限制：

• 栈遵循“后进先出”；
• 队列遵循“先进先出”。

2. 非线性结构

非线性结构中的元素不再构成一条单一的前后序列，一个结点可能与多个结点存在关系。

典型的非线性结构包括树和图。

树形结构

树主要表示层次关系。

例如，电脑中的文件目录：

在有根树中：

• 最上面的结点叫根结点；
• 一个结点可以有多个子结点；
• 除根结点外，每个结点通常只有一个父结点。

所以，树主要表示一对多的关系。

图状结构

图主要表示网状关系或多对多关系。

例如，城市交通网络中：

• 城市是顶点；
• 道路是边；
• 一个城市可以连接多个城市；
• 两个城市之间也可能有多条不同路线。

社交网络、计算机网络、交通网络和课程先修关系都可以用图表示。

需要注意：

非线性结构并不意味着每个结点都一定有多个前驱和后继。

例如：

• 树中的普通结点通常只有一个父结点；
• 图中的某个顶点可能没有相邻顶点，也可能连接很多顶点。

3. 按集合、线性、树和图划分

有些教材会从更细的角度把逻辑结构分为四类：

这两种分类方式并不矛盾：

• “线性结构和非线性结构”是一种粗略划分；
• “集合、线性、树、图”是一种更具体的划分。

不同教材对集合结构是否归入非线性结构，可能有不同处理。学习时应重点掌握每种结构的关系特点。

五、存储结构

存储结构研究的是：

数据元素及其逻辑关系怎样保存在计算机中。

常见的存储结构包括：

1. 顺序存储；
2. 链式存储；
3. 索引存储；
4. 散列存储。

六、顺序存储结构

顺序存储使用一段连续的存储空间，依次存放数据元素。

可以把它想象成一排连续编号的座位：

因为座位是连续的，所以只要知道座位编号，就可以快速找到对应的元素。

如果：

• 第一个元素的地址为 $base$；
• 每个元素占用 $L$ 个字节；
• 第 $i$ 个元素从 $0$ 开始编号；

那么第 $i$ 个元素的地址为：

$$LOC(a_i)=base+iL,\quad 0\le i<n$$

这就是数组能够根据下标快速访问元素的原因。

顺序存储的特点：

• 存储空间连续；
• 可以根据下标快速访问；
• 逻辑上的先后关系可以用存储位置表示；
• 在中间插入元素时，可能需要移动后面的许多元素；
• 删除元素后，也可能需要移动其他元素。

例如，在排好队的队伍中间插入一个人，后面的人可能都要向后移动。

七、链式存储结构

链式存储不要求结点放在连续的存储位置中，而是通过链接信息表示结点之间的逻辑关系。

可以把它想象成一组纸条：

• 每张纸条保存一个人的信息；
• 每张纸条还写着“下一张纸条在哪里”。

链表中的结点通常包含：

• 数据域：保存数据；
• 指针域或链接域：保存下一个结点的位置。

链式存储的特点：

• 结点不需要连续存放；
• 插入和删除结点时，通常只需要修改链接；
• 访问第 $i$ 个结点时，通常要从头结点开始逐个寻找；
• 需要额外空间保存链接信息。

“指针”是 C 语言中的一种常见实现方式。在其他语言或外存结构中，也可以使用引用、数组下标或文件偏移量表示链接。

八、索引存储结构

索引存储会在数据之外，另外建立一张索引表。

它很像书本的目录：

先查目录中的关键字，再根据目录给出的位置找到具体内容。

索引项通常包含：

• 关键字；
• 数据所在的位置。

例如：

查找学号 1002 时，可以先查索引，再直接定位李四的记录。

稠密索引

稠密索引通常为每个搜索键值或每条记录建立索引项。

例如：

优点是查找比较直接，缺点是索引占用空间较多。

稀疏索引

稀疏索引只为部分数据或数据块建立索引。

例如，每100名学生建立一个索引：

查找学号 1150 时：

1. 先通过索引找到第2块；
2. 再在第2块中继续查找。

稀疏索引占用空间较少，但定位到数据块后，通常还需要继续查找。

九、散列存储结构

散列存储根据数据的关键字，通过散列函数计算一个候选存储位置。

例如，学校有10个资料柜，编号为 0～9，规定：

$$柜号=学号\bmod 10$$

那么：

• 学号 1001 放入1号柜；
• 学号 1002 放入2号柜；
• 学号 1008 放入8号柜。

查找学生时，可以根据学号直接计算出应该去哪个柜子。

散列冲突

如果有两个学号：

• 1001
• 1011

那么：

$$1001\bmod 10=1$$ $$1011\bmod 10=1$$

两个学号都被计算到1号柜，这种情况叫作散列冲突。

发生冲突后，需要采用额外方法处理，例如：

• 在同一个位置建立链表；
• 继续寻找其他空位置；
• 使用其他冲突处理策略。

所以，“根据关键字直接算出存储地址”需要更准确地理解为：

根据关键字计算出候选位置；如果发生冲突，再按照规定的方法继续寻找数据。

散列存储的特点：

• 适合按照关键字进行精确查找；
• 查找效率通常较高；
• 不同关键字可能得到相同位置；
• 必须处理散列冲突；
• 不适合按照关键字顺序遍历或进行范围查询。

十、四种存储结构对比

十一、运算和实现

数据结构上的常见运算包括：

• 创建；
• 销毁；
• 插入；
• 删除；
• 查找；
• 修改；
• 遍历；
• 排序；
• 合并。

运算回答的是：

要对数据完成什么操作？

算法实现回答的是：

具体怎样完成这个操作？

例如，同样是在线性表中插入一个元素：

• 使用数组时，可能需要移动后续元素；
• 使用链表时，找到位置后通常只需修改链接。

因此，同一种逻辑结构使用不同的存储方式实现时，运算效率可能不同。

选择数据结构时，应先考虑程序最常进行的操作：

• 经常按下标访问，可以考虑顺序存储；
• 经常插入和删除，可以考虑链式存储；
• 经常根据关键字定位，可以考虑索引或散列存储；
• 经常进行范围查询或顺序遍历，则需要选择能够保持顺序的结构。

核心结论

1. 数据结构研究数据元素、元素之间的关系，以及对数据进行的操作。
2. 数据是能够被计算机存储和处理的符号集合。
3. 数据元素是通常作为整体处理的基本单位。
4. 数据项是数据元素中相对于当前问题不再划分的最小单位。
5. 数据对象是性质相同的数据元素组成的集合。
6. 逻辑结构描述元素之间的抽象关系，与内存位置无关。
7. 常见逻辑结构包括集合、线性、树形和图状结构。
8. 存储结构描述数据及其关系如何保存在计算机中。
9. 顺序、链式、索引和散列存储各有适用场景。
10. 数据结构的选择应根据程序最主要、最频繁的操作来决定。

常见误区

1. 非数值数据在计算机中不是数字

错误。文字、图片和声音最终仍然会以二进制形式保存。“非数值”描述的是它们的含义和处理方式。

2. 数据项就是结构体的属性名

不完全正确。结构体成员名是字段名称，字段中保存的具体值才是数据项。

3. 数据项永远不能继续划分

错误。是否继续划分取决于当前问题和建模粒度。

4. 逻辑结构就是内存中的排列方式

错误。逻辑结构描述抽象关系，内存中的排列属于存储结构。

5. 非线性结构中的每个结点都有多个前驱和后继

错误。非线性只表示关系不再是一条简单的线性次序。例如，树中的普通结点通常只有一个父结点。

6. 链式存储一定使用 C 语言指针

错误。链接也可以通过引用、数组下标或文件偏移量表示。

7. 散列函数可以保证每个关键字得到唯一地址

错误。不同关键字可能映射到同一个位置，因此需要处理散列冲突。

8. 数据结构存在唯一最好的存储方式

错误。不同存储结构适合不同的操作，应该结合具体问题进行选择。