认识数据结构

数据结构,说白了就是研究数据的存储方式。如何存储具有复杂关系的数据更有助于后期对数据的再利用

常见的数据结构

  • 栈(Stack)
  • 队列(Queue)
  • 数组(Array)
  • 链表(Linked List)
  • 树(Tree)
  • 图(Graph)
  • 堆(Heap)
  • 散列表(Hash table)

线性表

线性表又可以细分为顺序表链表栈和队列。线性表并不是一种具体的存储结构,它包含顺序存储结构链式存储结构,是顺序表链表的统称。

顺序表

顺序表,可以简单的理解为我们常用的数组,只是名字不同而已,因为顺序表结构的底层是借助数组实现的。数组是由相同类型的元素的集合所组成的数据结构,分配一块连续的内存来存储。利用元素的索引可以计算出该元素对应的存储地址。

链表

使用顺序表(底层实现靠数组)时,需要提前申请一定大小的存储空间,这块存储空间的物理地址是连续的。链表则完全不同,使用链表存储数据时,是随用随申请,因此数据的存储位置是相互分离的,换句话说,数据的存储位置是随机的。

链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。

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

链表由一系列节点组成,这些节点不必在内存中相连。每个节点由数据部分Data和链部分Next,Next指向下一个节点,这样当添加或者删除时,只需要改变相关节点的Next的指向。

链表又分为单向链表双向链表循环链表

栈和队列

栈和队是特殊的线性表,因为它们对线性表中元素的进出做了明确的要求。

栈中的元素只能从线性表的一端进出,且要遵循先进后出的原则,即先进栈的元素后出栈。

栈结构示意图

栈中含有 3 个元素,分别是 A、B 和 C,从在栈中的状态可以看出 A 最先进的栈,然后 B 进栈,最后 C 进栈。根据先进后出的原则,3 个元素出栈的顺序应该是:C 最先出栈,然后 B 出栈,最后才是 A 出栈。

队列中的元素只能从线性表的一端进,从另一端出,且要遵循先进先出的特点,即先进队列的元素也要先出队列。

队列结构示意图

队列中有 3 个元素,分别是 A、B 和 C,从在队列中的状态可以看出是 A 先进队列,然后 B 进,最后 C 进。根据先进先出的原则,3 个元素出队列的顺序应该是 A 最先出队列,然后 B 出,最后 C 出。

树存储结构适合存储具有“一对多”关系的数据。它看上去像一棵 "树",它的根在上,叶朝下。

树有多个节点(node),用以储存元素。某些节点之间存在一定的关系,用连线表示,连线称为边(edge)。边的上端节点称为父节点,下端称为子节点。树像是一个不断分叉的树根。类似下面这种结构

树又分为:

  • 无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树;
  • 有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树;
    • 二叉树:每个节点最多含有两个子树的树称为二叉树;
      • 完全二叉树:对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树;
      • 满二叉树:所有叶节点都在最底层的完全二叉树;
      • 平衡二叉树(AVL树):当且仅当任何节点的两棵子树的高度差不大于1的二叉树;
      • 排序二叉树(二叉查找树(英语:Binary Search Tree)):也称二叉搜索树、有序二叉树;
    • 霍夫曼树:带权路径最短的二叉树称为哈夫曼树或最优二叉树;
    • B树:一种对读写操作进行优化的自平衡的二叉查找树,能够保持数据有序,拥有多于两个子树。

图存储结构适合存储具有“多对多”关系的数据。在这种结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关

堆是一种特别的树状数据结构

区别树和堆

散列表

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

哈希表最大的特点就是可以快速实现查找、插入和删除。因为它独有的特点,Hash表经常被用来解决大数据问题。

数组的最大特点就是:寻址容易,插入和删除困难;而链表正好相反,寻址困难,而插入和删除操作容易。根据这个思想,哈希表结合了两者的优点,是一种集查找、插入和删除操作于一身的数据结构。

comments powered by Disqus