在此前C语言的章节中，曾提到过一个十分有名的等式：算法 + 数据结构 = 程序。本部分的博文会从C语言的角度来对数据结构进行相应的阐述，有利于理清思路，也可以以相似的想法套用至其它编译语言中。

绪论

1. 数据结构的概念

何为数据结构？

在编程的过程中，我们通常遇到的问题能够被分为两类：

1. 数值计算问题
2. 非数值计算问题

数值计算问题往往是能够通过明确的数学公式进行解决的，编译的过程需要思考的问题相对较少。而非数值计算问题则涉及的方面更多，也更考验编译者的抽象思维，这一过程中就涉及到选取正确的数据存储方式，以此使我们在计算机上能够更加便利地对数据进行操作，数据结构的概念由此产生。

我们定义数据结构时，往往通过三方面进行考虑。

• 数据的逻辑结构：即信息的组织方式
• 数据的存储结构：即信息在计算机上的存储方式
• 数据的运算：即在计算机上应当如何处理这些数据

以下举出两例，进行相关的说明：

1. 表：

   表的逻辑结构往往是线性的，这意味着其中的数据组与组之间关系并不十分强烈，因此可以采用在计算机中采用顺序（数组）或链式（链表）存储方式。运算也往往包含插、删、改、查四种方式。

2. 图：

   图的逻辑结构体现在结点与结点之间，其组与组之间的关系更加复杂，因为任意两组数据之间均有可能产生联系。因此在存储时，既要考虑结点本身信息的存储，也要考虑结点之间的关系如何构建。运算相应添加了关键路径、最短路径的问题等。

通过上述示例，我们能看出 数据结构往往解决的是非数值计算问题，它意在数据组织的基础上解决复杂程序的设计问题。

2. 数据的结构

数据

数据是能够被输入到计算机中进行存储、操作的符号的总称。其衍生出的名词还有：

• 数据元素：即数据中的一个个体
• 数据项：数据中的一个个体可能有多项数据，这其中每一项数据都能被称作数据项

结构

逻辑结构

数据元素之间存在某种关系，这种关系被称为逻辑结构。

常见的逻辑结构有：

• 集合
• 线性结构
• 树形结构
• 图 / 网状结构

存储结构

将数据结构在计算机中存储，表示的方式称为存储结构。它也可以理解为逻辑结构在计算机中的映像。（如二进制、顺序存储映像、链式存储映像等）

由于某些数据的逻辑结构极其相似，因此统一用一类存储结构对它们进行存储，这种特定的存储结构叫做 数据类型 （如数组，链表等具体类型）

同时，对相应数据类型的操作有时也极其相似，因此对相应一类操作起个名，叫 抽象数据类型（Abstract Data Type） （不同的教材中叫法不同）
这与很多编译语言中的 类 的概念十分类似。

Abstract Data Type（ADT）

重要特征

由于ADT本身的性质，其具有两个重要的特征：

• 数据抽象：ADT强调数据本身的性质，而其中的操作是一致的，因此对于其本身与外部用户的接口具有严格的要求。
• 数据封装：其内部的实现细节往往对外部用户隐藏。

ADT的定义

ADT抽象数据类型名{
    数据对象：
    数据关系：
    //以上两种定义利用伪码描述
    基本操作：
        基本操作名（参数表）
        初始条件：
        操作结果：
}

基本操作的参数表中含有两种参数：

1. 赋值参数：为操作提供输入值
2. 引用参数（以&开头）：可返回操作结果

初始条件表明了该种操作需要满足的条件，可以为空。
操作结果表明了数据结构的变化状况，以及此操作后应当返回怎样的结果。

3.算法

算法，是对特定问题解决步骤的描述，根据时间、空间占用量的不同有优劣之分。

算法的特点

首先，算法必须具有以下五条基本性质：

• 有穷性
• 确定性（指令明确）
• 可行性（每条指令都可被执行）
• 有输入（0或多个）
• 有输出（0或多个）

其次，要写出一个 好的算法 ，则还应当有如下特点进行辅助：

• 正确性
• 可读性
• 健壮性（程序不会轻易崩溃）
• 高效率 & 低存储量

正确性、可读性、健壮性自然不必多言，下面从高效率与低存储量方面进行说明。

算法执行时间

首先，明确一下与执行时间密切相关的因素：

• 算法策略
• 问题规模
• 使用语言
• 机器代码质量
• 机器性能

在我们的控制范围内的，主要是算法策略与使用语言。其中又以算法策略为重点优化对象。

这里我们继续细分， 算法 = 控制结构 + 原操作
其中控制结构主要指程序的顺序、分支与循环，而原操作则指固有数据类型的操作。

形成习惯的是，算法中原操作的重复次数往往与算法的执行时间成正比，因此以 原操作在算法中重复执行的次数 作为算法执行时间的衡量准则，称为 时间复杂度 ，以 O(n) 表示。
下面举几例常见的时间复杂度：

++x; //O(1) 常量阶

for(int i=1;i<n;i++){
    ++x;
} //O(n) 线性阶

for(int i=1;i<n;i++){
    for(int j=1;j<=n;j++){
        ++x;
    }
} //O(n^2)  平方阶

这里提出两个经典的问题供读者思考，有兴趣也可以自行搜索相应解答：

• 折半查找的算法时间复杂度
• 汉诺塔问题递归解法的时间复杂度

请务必注意，上文中的 原操作 指的是 ADT中的一次基本操作 ，如对于折半查找来说，即进行一次折半操作，对于汉诺塔问题来说，则是挪一次盘子的操作。
请务必不要将原操作理解为一条语句！

算法占用空间

相对应的，算法本身的操作也需要相应的存储空间，这也就产生了 空间复杂度 的概念，不过博主至今并未了解相应的计算机制，烦请读者自行搜索。

这篇博文就到这里~