数据结构

数据结构

在计算机科学中,数据结构(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)而直接访问在内存存储位置的数据结构。
它通过计算一个关于键值的函数,将所需查询的数据映射到表中的一个位置来访问记录,这加快了查找速度。这种映射函数称为散列函数,存放记录的数组称为散列表。