绪论

数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间关系和操作的学科。注意：开始本篇学习之前，请确保你完成了 C语言程序设计 篇视频教程，否则无法进行学习。

这里也说一下面试推荐书籍，内含多种常用算法以及解题分析，值得一看：

人们普遍认为程序设计的实质就是对所处理的问题选择一种好的数据结构，并在此结构基础上施加一种好的算法。，正是这种观点的集中体现。

一、数据

：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。：是数据的基本单位，是一个静态的概念描述个体的基本信息。也简称为元素，或称为记录、结点或顶点。：是组成数据元素的、有独立含义的、不可分割的最小单位。：是性质相同的数据元素的集合，是数据的一个子集。是一个动态的概念描述个体基本信息+个体间操作。

二、数据结构的概念

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构包括逻辑结构和存储结构两个层次。

比如现在我们需要保存100个学生的数据，那么你首先想到的肯定是使用数组吧！没错，没有什么比数组更适合存放这100个学生的数据了，但是如果我们现在有了新的需求呢？我们不仅仅是存放这些数据，我们还希望能够将这些数据按顺序存放，支持在某个位置插入一条数据、删除一条数据、修改一条数据等，这时候，数组就显得有些乏力了。

我们需要一种更好的数据表示和组织方式，才能做到类似于增删改查这样的操作，而完成这些操作所用到的方法，我们称其为“算法”，所以数据结构和算法，一般是放在一起进行讲解的。

三、算法的概念

算法是特定问题求解步骤的描述，在计算机中表现为指令的有限序列，算法是独立存在的一种解决问题的方法和思想。对于算法而言，语言并不重要，重要的是思想。

比如现在我们希望你求出1-100所有数字的和，请通过程序来实现：

int main() {
    int sum = 0;
    for (int i = 1; i <= 100; ++i) sum += i;
    printf("%d", sum);
}

我们很容易就能编写出这样的程序，实际上只需要一个for循环就能搞定了，而这就是我们设计的算法。

在之前的C语言程序设计阶段，我们其实已经学习了许多算法，包括排序算法、动态规划等。

当然，解决问题的算法并不是只有一种，实际上我们上面的方式并不是最优的算法，如果想要求得某一段整数的和，其实使用高斯求和公式能够瞬间得到结果：

$$\sum =\frac{(\mathrm{首}\mathrm{项}+\mathrm{末}\mathrm{项})\times \mathrm{项}\mathrm{数}}{2}$$

所以，我们完全没必要循环那么多次进行累加计算，而是直接使用数学公式：

int main() {
    printf("%d", (1 + 100) * 100 / 2);
}

所以，算法的尽头还得是数学啊。

可见，不同的算法，执行的效率也是有很大差别的，这里我们就要提到算法的复杂度了。

3.1 算法的复杂度

衡量一个算法的复杂程度需要用到以下两个指标：

• 时间复杂度T(n)：算法程序在执行时消耗的时间长度，一般与输入数据的规模n有关。
• 空间复杂度S(n)：算法程序在执行时占用的存储单元长度，同样与数据的输入规模n有关，大部分情况下，我们都是采取空间换时间的算法。

比如我们上面的两种算法，第一种需要执行n次循环，每轮循环进行一次累加操作，而第二种只需要进行一次计算即可。实际中我们计算时间复杂度时，其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用O渐进表示法。

• 大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

而这里的循环次数，实际上就是我们需要知道的大致执行次数，所以第一种算法的时间复杂度为：O(n)，其中n就是项数，因为它需要执行n次计算才能得到最后的结果。而第二种算法的时间复杂度为：O(1)，因为它只需要执行一次计算（更准确的说它的执行次数是一个常数，跟项数n毫无关系），显然，当n变得非常大时，第二种方法的计算速度远超第一种。

再比如我们之前使用的冒泡排序算法，需要进行两轮循环，而循环的次数在经过优化之后为(n - 1)(n - 1)/2，得到的结果中包含了一个n的平方，此时这种算法的时间复杂度就来到O(n^2)了。

在不同的空间复杂度下，可能n小的时候还没什么感觉，但是当n变得非常大时，差距就不是一点半点了，我们来看看常用函数的增长曲线：

所以我们在设计算法的时候，一定要考虑到时间和空间复杂度的问题，这里列出常用函数的增长表：

函数	类型	解释
$\text{Omicron}(1)$	常数阶	如果算法能够优化到这个程度，那么基本上算是最快的算法了。
$\text{Omicron}({\log }_{2}n)$	对数阶	仅次于常数阶的速度，我们后面会介绍的二分搜索算法，就能够到达这个级别。
$\text{Omicron}(n)$	线性阶	我们后面介绍的线性表插入、删除数据，包括动态规划类算法能够达到线性阶。
$\text{Omicron}(n{\log }_{2}n)$	线性对数阶	相当于在对数阶算法外层套了一层线性阶循环。
$\text{Omicron}(n^2)$	平方阶	我们前面学习的冒泡排序，需要进行两重循环，实际上就是平方阶。
$\text{Omicron}(n^3)$	立方阶	从立方阶开始，时间复杂度就开始变得有点大了。
$\text{Omicron}(2^n)$	指数阶	我们前面介绍的斐波那契数列递归算法，就是一个指数阶的算法，因为它包含大量的重复计算。
$\text{Omicron}(n!)$	阶乘	这个增长速度比指数阶还恐怖，但是一般很少有算法能达到这个等级。

我们在编写算法时，一定要注意算法的时间复杂度，当时间复杂度太大时，可能计算机就很难在短时间内计算出结果了。

3.2 算法的比较

现在我们需要写一个求1 + 2 + 3 + … + 100的结果程序，你应该怎么写呢？

大多数人马上回写出下面C语言代码（或者其他语言）

int  i ，sum = 0; n = 100;
for (int i = 1; i <= n; i++){
    sum = sum + i;
}
printf(“ % d ”, sum);

当然，如果这个问题让高斯来去做，他可能会写如下代码：

int sum = 0, n = 100;
sum = (1 + n) * n / 2
printf(“ % d”, sum)

很显然，不论是从人类还是计算机的角度来看，下列的算法效率会高出很多，这就是一个好的算法会让你的程序更加的高效。

3.3 算法的特性

算法具有五个基本的特性：

输入输出：算法具有零个或多个输入、至少有一个或多个输出。

有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。

确定性：算法的每一步骤都有确定的含义，不会出现二义性。

可行性：算法的每一步都必须是可行的，也就是说，每一步都能通过执行有限次数完成。

3.4 算法和数据结构区别

数据结构只是静态的描述了数据元素之间的关系，高效的程序需要在数据结构的基础上设计和选择算法。

• 算法是为了解决实际问题而设计的。

• 数据结构是算法需要处理的问题载体。

• 数据结构与算法相辅相成

四、数据结构分类

按照视点的不同，我们把数据结构分为逻辑结构和物理结构。

4.1 逻辑结构

集合结构

集合结构中的数据元素除了同属于一个集合外，他们之间没有其他关系。各个数据元素是平等的。他们共同属于同一个集合，数据结构中的集合关系类似于数学中的集合，如下图所示

线性结构

线性结构中的数据元素之间是一对一的关系。如图：

树形结构

树形结构中是数据元素之间存在一种一对多的层次关系，如图：

图形结构

图形结构的数据元素是多对多的关系，如果：

4.2 物理结构

说完了逻辑结构，再说下物理结构，也有的书称为存储结构。

物理结构：是指数据的逻辑结构在计算机中的存储形式，共分为两种：顺序存储和链式存储。

顺序存储结构

是把数据元素存放在地址连续的存储单元里，其数据的逻辑关系和物理关系是一致的，如图：

如果所有数据结构都很简单有规律，一切就好办了，可实际上，总有人想要插队，或者放弃排队，所以元素集合中就会添加、删除掉成员，显然面对这样时常要变化的结构，顺序存储是不科学的，那怎么办呢

链式存储结构

是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关数据的位置。如图：

小结

本章介绍了数据结构的基本概念和术语， 以及算法和算法时间复杂度的分析方法。主要内容如下。

• 数据结构是一门研究非数值计算程序设计中操作对象， 以及这些对象之间的关系和操作 的学科。
• 数据结构包括两个方面的内容：数据的逻辑结构和存储结构。同一逻辑结构采用不同的 存储方法， 可以得到不同的存储结构。
  • 逻辑结构是从具体问题抽象出来的数学模型，从逻辑关系上描述数据，它与数据的存储无 关。根据数据元素之间关系的不同特性， 通常有四类基本逻辑结构：集合结构、线性结构、 树形 结构和图状结构。
  • 存储结构是逻辑结构在计算机中的存储表示，有两类存储结构：顺序存储结构和链式存储 结构。
• 抽象数据类型是指由用户定义的、 表示应用问题的数学模型 ， 以及定义在这个模型上的 一组操作的总称， 具体包括三部分：数据对象、 数据对象上关系的集合， 以及对数据对象的基本 操作的集合。
• 算法是为了解决某类问题而规定的一个有限长的操作序列。算法具有五个特性：有穷性、 确定性、可行性、 输入和输出。一个算法的优劣应该从以下四方面来评价：正确性、 可读性、 健 壮性和高效性。
• 算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度， 以考察算法的时间和 空间效率。一般情况下， 鉴于运算空间较为充足， 故将算法的时间复杂度作为分析的重点。算法 执行时间的数量级称为算法的渐近时间复杂度，T(n) = 0(/(n) ), 它表示随着问题规模n的增大， 算法执行时间的增长率和.f(n)的增长率相同， 简称时间复杂度。

学完本章后，要求掌握数据结构相关的基本概念 ， 包括数据、数据元素、数据项、数据对象、 数据结构、 逻辑结构、 存储结构等；重点掌握数据结构所含两个层次的具体含义及其相互关系； 了解抽象数据类型的定义、 表示与实现方法；了解算法的特性和评价标准；重点掌握算法时间复 杂度的分析方法。