什么？你想学习数据结构？你还在为搞不懂数据结构而发愁？那么看这一篇文章就够了！

本文涵盖：

• 数据结构的基本概念
• 线性表
• 栈和队列
• 串、数组、广义表
• 树和二叉树
• 图
• 查找
• 排序

本文将解决你面对离散数学时一切困惑！

---

数据结构是计算机存储、组织数据的方式。它并不是一门具体的编程语言，而是教会我们的是一种思维方式，即如何以更优的方式存储数据。但也正是由于这个原因，很多读者感觉数据结构虚无缥缈，无法触及，不如学习 Python、Java 等这些编程语言可以随学随用、掷地有声，久而久之觉得学习数据结构没用。

但是，数据结构真的无用吗？当然不是。作为计算机专业最重要的必修学科之一，计算机专业考研的必考知识，以及众多 IT 公司笔、面试的侧重考点，仅仅这些光环，就足以说明学习数据结构的重要性。

虽然网上已经有很多诸如王道的优质视频课程，但是却没有一篇完整且系统地讲解了数据结构的文章，大多都是知识点的堆砌。故此我写这篇文章，不仅仅是为了巩固自己的知识体系，更是为了与大家一起分享学习，共同进步。

本文适用人群：

• 想要通过期末考试
• 想要在考研取得高分
• 想要自学数据结构
• 在学习人工智能、数据库、编译原理等课程前补充一些前置知识

本文参考用书：《数据结构（C语言版）》 (严蔚敏）

---

1绪论

1.1数据结构的基本概念

1.1.1基本概念与术语

 在学习数据结构之前，我们先要知道数据是什么。数据，是客观事物的符号表示，是所有能输入计算机中并被计算机程序处理的符号总和，例如你的班级学号，你的姓名年龄乃至你的家庭关系都是数据。这里，我们假设有一个你们学校学生的信息表，里面包含了你们每个人的学号、姓名、年龄等信息：

姓名	年龄	学号
张三	18	1001
李四	17	1002
wangwu	19	1004

 其中，张三和他的年龄学号一起构成了一个数据元素，是数据的基本单位；他的姓名、年龄、学号每一项都是一个数据项，是组成数据元素，不可分割的最小单位。这里我们再假设，你们不仅有学生的信息表，还有老师的信息表，而每一张这个表就是一个数据对象，是性质相同的数据元素的一个集合。

1.1.2数据结构

 数据结构是相互之间存在一种特定关系的数据元素的集合，例如你家的关系图、你在排队时队列的顺序等。其又分为逻辑结构和物理结构，物理结构又称储存结构。

• 逻辑结构：
  逻辑结构是从具体问题中抽象出来的数学模型，逻辑结构=数据元素+关系。它又分为：
  • 集合结构
  • 线性结构
  • 树结构
  • 图结构、网状结构
• 物理结构：
  物理结构是计算机各种逻辑结构的储存方式。它又分为：
  • 顺序存储结构
  • 链式存储结构
  • 索引存储结构
  • 散列存储结构

1.1.3数据类型和抽象数据类型

 这里，我们再引入数据类型的概念，数据类型就是一个值的集合及定义在此集合上的操作的总和。学过离散数学的同学会发现数据类型的定义与代数系统的定义非常相似，没学过离散数学的同学也可以看看我的离散数学专栏中相关的文章了解一下。而数据类型又分为原子类型、结构类型两种。
 其中原子类型是值不可再分割的类型，例如c语言中的bool类型，值包括T和F，操作包括与、或、非等，它的每一个值就是确定的T或F，每个值都不能再细分为更小的部分。
 结构类型是值可再被分割的类型，例如c语言中的结构体，每一个值都包含了多个项。

 而抽象数据类型则是用户自己定义的数据类型，我们不仅要知道抽象数据类型的逻辑结构，也要知道相关的运算和物理结构。

1.2算法与算法分析

1.2.1算法的定义和特性

 算法，是为解决某种问题而规定的有限长的操作序列。它有五条性质：

• 有穷性：一个有用的算法不可以算不到头，它必须有结束且每一步都必须可以有穷时间内完成。
• 确定性：算法中每条指令必须有明确的含义，且对同一个输入，必须要有相同的输出。
• 可行性：说白了就是你的算法描述必须可以用代码来完成。
• 输入：一个算法必须要有零个或一个或多个输入。
• 输出：一个算法必须要有一个或多个输出。

1.2.2评价算法优劣

• 正确性：算法需要有正确的结构。
• 可读性：算法的代码需要易于理解。
• 健壮性：输入非法数据时算法需要有适当的反应与处理，不会输出莫名其妙的结果。
• 高效性：时间复杂度与空间复杂度低。

1.2.3算法的时间复杂度

 我们求一个算法时间复杂度有两种方法，一种是事后统计法，就是将算法放到计算机中运行一遍得到结果。但是这种方法受限较大，例如你家的计算机肯定跑的没神威太湖之光快，r语言写的算法和c语言写的同一个算法肯定是c语言跑得快，不同编译程序产生的机器指令的质量也会影响，而且一些例如导弹控制算法，你总不能发射一颗导弹去测试吧。因为，我们着重学习事前分析估算法。

1. 问题规模和语句频度
   问题规模是算法求解问题时输入量的多少，用整数n表示。
   语句频度是一条语句的重复次数。我们可以用语句频度之和度量算法执行时间。
2. 算法的时间复杂度定义
   我们记时间开销为T，显而易见T应该与n有函数关系T=T（n）。
   例如代码

int World(int n) {     
    int i=1;    //1
    for(i=1; i<n; i++) {    //2
        printf("Hello, World!\n");    //3
    }
    printf("Goodbye, World!\n");       //4
    return 0;    //5
}

 这里的形参n就是问题规模，显而易见，语句1执行了1次，语句2执行了n，语句3执行了n-1次，语句4和5执行了1次，所以我们可以得出T(n)=2n+2。但是，当n趋于无穷大时，T（n）=2n是不是和T（n）=2n+2差不多，所以我们可以把低阶的部分忽略掉。我们甚至可以根据高等数学，2n与n是同阶的，将2也忽略掉，记为T（n）=O（n）=n。
 这里我们要遵循两个规则。

• 加法规则：$$T(n)=T_1(n)+T_2(n)=O_1(n)+O_2(n)=max(O_1(n),O_2(n))$$
• 乘法法则：$$T(n)=T_1(n)\ast T_2(n)=O_1(n)\ast O_2(n)=O(O_1(n)\ast O_2(n))$$

并且数量级大小遵循：

 3. 最好、最坏、平均时间复杂度
  我们多关心最坏与平均时间复杂度

1.2.4算法的空间复杂度

---

本文将持续更新

---