玩儿转数据结构
liuyubobobo
为什么要学习数据结构
- 数据结构是所有计算机专业同学的课程
- 数据结构研究的是数据如何在计算机中进行组织和存储，使得我们可以高效的获取数据或者修改数据。
数据结构分类：
| 线性结构 | 树结构 | 图结构 |
|---|---|---|
| 数组、栈、队列、链表、哈希表.... | 二叉树、二分搜索树、AVL、红黑树、Treap、Splay、堆、Trie、线段树、K-D树、并查集、哈夫曼树.... | 邻接矩阵、邻接表 |
我们需要根据应用的不同，灵活选择最合适的数据结构。
在计算机的世界里，数据结构是无处不在
- 数据库：
我们需要做一个网站，做一个 APP，我们要接收用户的输入，像注册信息、查询信息，用户可以发布不同的信息，那么这些信息都需要存储在数据库中。数据库已经是一个封装好的软件，我们只需要使用 SQL 语言来操作数据库就可以了。但是，数据库本身也是一个软件，是人们从底层开发出来的。如果我们要想创造一个数据库软件，就需要大量的数据结构的知识。这里，最重要的数据结构知识，可能是和树结构，尤其是和平衡的树结构，像 AVL、红黑树、Treap、伸展树、B 树等等这类的结构，包括另外一个非常重要的数据结构：哈希表。如果没有这些数据结构的知识，我们可能根本无法制造出数据库，如果没有数据库，世界上大多数的互联网业务都将无法运转的。
- 操作系统
操作系统本身就是一个软件系统，在操作系统这个平台上，我们可以进行更加高层的应用。
对于通常的操作系统来说，都是支持多任务的。多任务之间需要进行频繁的切换，就需要涉及到具体的数据结构，典型的数据结构有：栈（系统栈）、堆（优先队列）
我们进行递归调用的时候就需要使用到系统栈，堆数据结构主要用于组建优先队列这种数据结构，由于有了优先队列，操作系统才能够在多个任务之间比较他们之间的优先级来进行任务的切换。
- 文件压缩
我们在计算机世界中使用到的大多数文件，比如：PNG、MP3、MP4、PDF等等，他们都是对不同的文件进行一定的压缩处理，才形成这种专门的文件格式。在进行具体的文件压缩的过程中也需要借助数据结构，这里最基础的数据结构是：哈夫曼树。这里列举的大多数文件压缩的算法其实已经不是哈夫曼树，哈夫曼树相对来说是一种比较简单的文件压缩算法。现代的文件压缩算法需要更复杂的数据结构来提供支撑。
- 通讯录
使用链表设计的通讯录在用户数量巨大的时候，查找效率低下。
微软实习生使用 Trie 树（前缀树）来存储通讯录中所有的联系人，这样处理完后，在通讯录中查找任何联系人就能够在毫秒级别完成，而不管通讯录中有多少的联系人。
数据结构本身就是大量算法的基石
在游戏开发中涉及到大量的算法，其中最常用的算法是：寻路算法。
DFS：使用栈；
BFS：使用队列。
几乎所有的算法都需要以数据结构为基石。数据结构+算法=程序
手把手的底层实现，创建属于自己的小型数据结构库
面向面试：数组、栈、队列、链表、二分搜索树、堆；
面向竞赛：线段树、Trie、并查集；
复杂结构：AVL、红黑树、哈希表。