绪论¶

程序是一系列指令的集合。程序设计 = 数据结构 + 算法

数据，由 N 个 0 和 1 组成，本质上是一串二进制代码，利于计算机计算，但不利于人类阅读思考。所以在此之上经过层层抽象，将计算机中的数据抽象出诸如 对象、实例、结点、数据对象 等概念。

Note

数据结构，就是以 对象、实例、结点、数据对象 为单位，研究各个单位之间的关系。

由此明确，在数据结构中需要研究两个东西：单位、关系

单位¶

数据的单位在数据结构中通常称为 数据对象，数据对象可以是一个人、一辆车、一个数字、一个字符、或者多种数据的组合，在代码中表现为结构体变量或对象。

而一个人，会有多种数据：名字（name）、年龄（age）、学号（ID），在代码中表现为结构体成员变量或对象成员变量。

而名字、年龄、学号这些，我们称为 数据项。

Note

即 N 个数据项构成了数据对象

每个人都有学号、姓名、年龄，例如张三李四王五，但张三不是李四、王五不是赵六，他们都是各自独立的。

但他们都是人类，所以我们把人类称为 数据元素，在代码中表现为结构体定义或类定义。

// 结构体定义 <--> 数据元素
typedef struct {
    // 结构体成员变量 <--> 数据项
    long ID;
    int age;
    char* name;
} Person;

// 数据对象 <--> 结构体变量
Person Zhangsan = {
    1213, 
    18, 
    "Boii"
};

关系¶

说完单位，剩下就是关系了。

这些单位之间的关系，理论上有很多种：线性表、广义表、链表、栈、队、树、图；这种我们称为逻辑结构。

而在代码、或者说物理上的实现，只有两种：顺序存储结构、链式存储结构；这些我们称为物理结构。

逻辑结构¶

逻辑上的各种关系可以分为 4 大类：

集合结构：各个单位之间，除了同属一个集合，没有别的关系；各个单位是“平等”的。
线性结构：各个单位之间是 一对一 的关系
树形结构：各个单位之间是 一对多 的关系
图形结构：各个单位之间是 多对多 的关系

集合结构比较少见，这里暂时不做讨论。我们主要讨论常见的线性、树形、图形结构。

物理结构¶

程序是运行在内存中的，而内存是顺序排列的，没那么多花里胡哨的，而且受计算机物理实现所束缚，物理结构中：

要么是一个挨着一个的 顺序存储结构，要么是单位（数据对象）之间并不一定挨着的 链式存储结构。

两种结构都有各自的特点。

顺序存储结构 - 特点：数据对象之间在物理上一个挨着一个、有序，只要知道了第一个数据对象的地址，可以很快找到后面其他的数据对象。与此同时，为了保持这种一个挨着一个和有序的特点，当插入或者删除某一个数据对象时，后面的数据对象要一个一个往后挪腾出中间的位置，或者一个一个往前挪填补中间的空缺，导致插入和删除很慢。 - 优点：查找速度快。 - 缺点：插入和删除慢。

链式存储结构 - 特点：数据对象之间在物理上并不一定相互挨着、无序，要查找某一个数据对象时需要从第一个数据对象开始，一个接着一个往后一路查下去才能找到。与此同时，因为物理上不一定相互挨着，所以插入和删除时只需要修改前后的链条即可。 - 优点：插入和删除快。 - 缺点：查找速度慢。

这里的快慢，指的是计算机需要执行多次计算称为慢，计算机需要执行少量计算称为快。

ADT 抽象数据类型¶

抽象数据类型是用来表示某一种逻辑结构（栈、队、树、...）的具体信息，具有什么样的操作等等。

描述 ADT 的标准格式：

ADT 抽象数据类型名
Data
    数据元素之间逻辑关系的定义
Operation
    操作1
        初始条件
        操作结果描述
    操作2
        ...
        ...
    操作n
        ...
        ...
endAD

ADT 就像一张蓝图。

在建房子之前我们需要先设计好房子的功能、结构等，之后再依照图纸开工。

ADT 就是数据结构的图纸，事先定义好各种关系和操作，写起代码来才能有条不紊。

绪论¶

单位¶

关系¶

逻辑结构¶

物理结构¶

ADT 抽象数据类型¶

总结¶