数据结构

在计算机科学中，数据结构(data structure) 是计算机中存储、组织数据的方式。 大多数数据结构都有数列、记录、可辨识联合、引用等基本类型构成。

数据结构意味着结构和封装，一个数据结构可被视为两个函数之间的接口，或是由数据类型联合组成的存储内容的访问方法和封装。 数据结构可通过程序语言所提供的数据类型、引用及其它操作加以实现。不同种类的数据结构适合不同种类的应用，部分数据结构甚至是为了解决特定问题而设计。 一个涉及良好的数据结构，应该尽可能使用较少的时间与空间资源的前提下，支持各种程序运行。

正确选择数据结构可以提高算法的效率，在计算机程序设计里，选择适当的数据结构是一项重要工作。

常见数据结构

• 数组(Array);
• 栈(Stack): 后进先出，线性表；
• 队列(Queue): 先进先出，线性表；
• 链表(Linked List): 每个节点包括两部分，一个存储数据元素的数据域，另一个存储下一个节点地址的指针域；
• 树(Tree)；
• 图(Graph)；
• 堆(Heap): 一种动态树形结构；
• 散列表(Hash)；

数组(Array)

数组数据结构，是由相同类型的元素的集合所组成，分配一块连续的内存来存储。利用数组元素的索引(index)可计算出元素对应存储地址。

数组有 一维数组、二维数组、多维数组、可变长数组…。

栈(Stack)

堆栈又称为栈，是计算机科学中一种特殊的串列形式的抽象资料类别。 其特殊之处在于只能允许在链接串列或阵列的一端(栈顶指标:top)，进行加入数据(push)和取出数据(pop)。

由于栈数据结构只允许在一端进行操作，因为按照后进先出(LIFO, last-in-first-out)的原理运行。

队列(Queue)

队列，是先进先出(FIFO, first-in-first-out)的线性表。在具体应用中通常用链表或数组来实现。 队列只允许在后端(Rear)进行插入操作，在前端(Front)进行删除操作。

链表(Linked List)

链表是一种线性表，但并不按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。 由于不必须按顺序存储，链表再插入的时候可以达到 O(1)的时间复杂度，比另一种线性表顺序表快得多。但查找一个节点或访问特定节点则需要 O(n)的时间，而顺序表相应的时间复杂度分别是 O(logn)和O(1)。

是用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了节点的指针域，空间开销比较大。

链表有单向链表、双向链表、循环链表…。 链表用来构建许多其它数据结构，如栈，队列和他们的派生。

树(Tree)

树是一种抽象数据类型，用来模拟具有树状结构性质的数据集合。

树有有序树、无序树（二叉树，B树，霍夫曼树）。

图(Graph)

在数学上，一个图是表示物体与物体之间的关系的方法，是图论的基本研究对象。

图有：有向图、无向图、简单图、多重图。

堆(Heap)

堆是计算机科学中一类特殊的数据结构的统称。 堆通常是一个可以被看做一棵树的数组对象。在队列中，调度程序反复提取队列中的第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

堆常用于排序，这种算法称作堆排序。

散列表(Hash)

散列表也叫哈希表，是根据**键(key)**而直接访问在内存存储位置的数据结构。 它通过计算一个关于键值的函数，将所需查询的数据映射到表中的一个位置来访问记录，这加快了查找速度。这种映射函数称为散列函数，存放记录的数组称为散列表。