数据结构总结

常见的数据结构
数组、栈、队列、链表、树、散列表、堆、图

数组

数组在内存中的存储是连续，我们可以通过索引来查找元素。

适用的场景：要预先知道数据量，数据量少，适合频繁查询的场景，对存储空间要求不大。
总结起来就是寻址容易，插入和删除困难，需要移动大量元素。

栈

栈是一种特殊的线性表，它的特点就是先进后出

适用的场景：可以用来逆序输出排列、用在数制转换以及括号匹配等

队列

队列也是特殊的线性表，他的特点是先进先出，可以两端操作

适用的场景：队列调度

链表

链表是物理存储单元上非连续的、非顺序的存储结构，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。

适用的场景：适合做增删操作，查找元素需要挨个遍历，耗时。
总结起来寻址困难，插入和删除容易

树

树就是由根节点、中间节点和叶子结点构成的一种层次结构。

适用的场景：哈夫曼树可以用来搜寻一个最优的路径；二叉查找树适合频繁查找和插入。

散列表（哈希表）

散列表是根据关键码和值直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。
哈希表结合了数组和链表的结构。如下图，左边是数组，右边是链表结构。

适用场景：哈希查找，知道key值，就可以直接计算出这个元素在集合中的位置。

堆

堆通常是一个可以被看做一棵完全二叉树的数组对象。它的特点是堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。

适用场景：可以用来做数组的排序。

图

由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V, E)，其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

适用场景：可以用来查找最短路径（迪杰斯特拉算法、弗洛伊德算法）；最小生成树可以用普里姆算法或克鲁斯卡尔算法求出。