数据结构

常见的数据结构及特点

常见的数据结构

• 数组
• 链表
• 栈
• 队列
• 树
• 堆
• 散列表
• 图

数据结构分类

• 按 排列方式 分： 集合(元素之间无关)、线性结构(一对一)、树形结构(一对多)、图形结构(多对多)
• 按 逻辑结构 分： 线性结构(链表、栈和队列)、非线性结构(树、图)

数组

• 数组（Array）：数组是有序元素的序列，在内存中的分配是连续的，数组会为存储的元素都分配一个下标（索引），此下标是一个自增连续的，访问数组中的元素通过下标进行访问；数组下标从0开始访问；
• 数组的优点是：查询速度快；
• 数组的缺点是：插入、删除慢；由于数组为每个元素都分配了索引且索引是自增连续的，因此一但删除或者新增了某个元素时需要调整后面的所有元素的索引；

链表

• 链表（Linked List）：链表是由一系列节点Node（也可称元素）组成，数据元素的逻辑顺序是通过链表的指针地址实现，通常情况下，每个节点包含两个部分，一个用于存储元素的内存地址，名叫数据域，另一个则指向下一个相邻节点地址的指针，名叫指针域；根据链表的指向不同可分为单向链表、双向链表、循环链表等；我们本章介绍的是单向链表，也是所有链表中最常见、最简单的链表；
• 通俗点说就是每个元素都有一个指针域指向下一个元素，把数据链起来。
• 链表的优点：插入节点、删除节点快；
• 链表的缺点：查询速度慢，查询从头部开始一直查询到尾部，如果元素刚好是在最尾部那么查询效率势必非常低；

栈

• 栈（Stack）：是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出。从栈顶放入元素的操作叫入栈（压栈），取出元素叫出栈（弹栈）。

队列

• 队列（Queue）：队列与栈一样，也是一种特殊的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。队列的特点是先进先出。从一端放入元素的操作称为入队，取出元素为出队。

树

• 树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
• 二叉树的特点：每个节点最多有两颗子树；

堆

• 堆（Heap）：堆可以看做是一颗用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。

散列表

• 散列表（Hash），也叫哈希表，是根据键和值 ( key 和 value ) 直接进行访问的数据结构，通过 key 和 value 来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。它利用数组支持按照下标访问的特性，所以散列表其实是数组的一种扩展，由数组演化而来。
• 散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。
• 在散列表中，左边是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

图

• 图（Graph）：图是一系列顶点（元素）的集合，这些顶点通过一系列边连接起来组成图这种数据结构。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。
• 图分为有向图和无向图。
• 实现了图这种数据结构之后我们可以在此数据结构上做一些复杂的算法计算，如广度优先搜索算法、深度优先搜索算法等；
  • 广度搜索：搜索到一个顶点时，先将此顶点的所有子顶点全部搜索完毕，再进行下一个子顶点的子顶点搜索；
  • 深度搜索：搜索到一个顶点时，先将此顶点某个子顶点搜索到底部（子顶点的子顶点的子顶点…），然后回到上一级，继续搜索第二个子顶点一直搜索到底部；

深度优先搜索和广度优先搜索比较

• 深度优先搜索算法：通用做法是采用栈，不全部保留节点，遍历完的节点弹出，这样存储的节点数就是深度值，因此它占用空间较少。所以，当搜索树的节点较多，推荐使用深度优先搜索。
• 广度优先搜索算法：通用做法是采用队列，一般需存储产生的所有节点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。