数据结构基础 - 知识体系
数据结构的作用
数据结构实际上可以理解为数据在计算机中的存储和使用结构。如果借助C++容器的概念，数据结构可以认为是以某种特定的布局方式存储数据的容器。
这种“布局方式”决定了数据结构对于某些操作是高效的，而对于其他操作则是低效的。首先我们需要理解各种数据结构，才能在处理实际问题时选取最合适的数据结构。不同的数据结构适用于不同的应用场景。
常见数据结构
目前通用的计算机专业教材将《数据结构》列为专业必修课，数据结构的主要研究内容是：
- 数组
- 链表（单链表/双链表/循环链表）
- 栈
- 队列
- 树（二叉树/红黑树）
- 图
- 字典树（这是一种高效的树形结构，但值得单独说明）
- 散列表（哈希表）
1.数组
数组是任何编程语言都会谈及的数据结构，是最简单的数据结构。
数据整体我们可以分为单个变量的数据存储方式和大量数据的数据存储方式。单个数据的变量存储方式一般就是由变量类型而决定，比如int占4字节，char占1字节等等。大量数据的存储方式主要就是数据结构了，是一种特定的数据存储方式。
数组是最简单、也是使用最广泛的数据结构。栈、队列等其他数据结构均由数组演变而来。
每个数据元素都关联一个正数值，我们称之为索引，它表明数组中每个元素所在的位置。大部分语言将初始索引定义为零。
2.栈
栈的特点是last in first out，与队列正好可以对照学习。栈和队列都是顺序存储元素的线性数据结构。也就是学会栈，队列也就学会了。
3.队列
栈的特点是first in first out，与栈正好可以对照学习。栈和队列都是顺序存储元素的线性数据结构。也就是学会队列，栈也就学会了。
4.链表
链表也是重要的线性数据结构，链表就像一个节点链，其中每个节点包含着数据和指向后续节点的指针。 链表还包含一个头指针，它指向链表的第一个元素，但当列表为空时，它指向null或无具体内容。
链表一般用于实现文件系统、哈希表和邻接表。
5.树
树形结构是一种层级式的数据结构。树类似于图，但区分树和图的重要特征是树中不存在环路。
6.图
图是一组以网络形式相互连接的节点。节点也称为顶点。 一对节点（x，y）称为边（edge），表示顶点x连接到顶点y。边可以包含权重/成本，显示从顶点x到y所需的成本。
图的类型：
- 无向图
- 有向图
在程序语言中，图可以用两种形式表示：
- 邻接矩阵
- 邻接表
常见图遍历算法：
- 广度优先搜索
- 深度优先搜索
7.字典树（trie）
字典树，也被称为“前缀树”，是一种特殊的树状数据结构，对于解决字符串相关问题非常有效。它能够提供快速检索，主要用于搜索字典中的单词，在搜索引擎中自动提供建议，甚至被用于IP的路由。
8.哈希表
哈希表是一个用于唯一标识对象并将每个对象存储在一些预先计算的唯一索引中的过程。因此，对象都是以键值对的形式存储的，这些键值对的集合被称为字典。可以使用键类搜索对象，基于哈希有很多不同的数据结构，但最常用的还是哈希表。
哈希表通常用数组实现。
散列数据结构的性能取决于下面的因素：
- 哈希函数
- 哈希表的大小
- 碰撞处理方法