八总常见的数据结构

八总常见的数据结构

文章发布于 2020-09-04 16:36:52,最后更新于 2020-09-08 16:14:01

带你重学数据结构和算法(一)

前言

    这个系列准备将数据结构和算法复习一遍,毕竟都知道在一些互联网大厂面试的时候会经常手撕算法,把自己的知识体系梳理一遍以便于平时查阅或是之后使用。而且对于一个开发来讲,只有对算法了如指掌才能做到随机应变,设计出更好的系统。这一节主要介绍一下数据结构是什么,都有哪些常见的数据结构。本节的内容相对简单,这一系列的内容将会由易到难。

1 什么是数据结构

决定了数据的顺序和位置关系!

数据结构包含数据的存储、数据之间的关系、数据操作。

数据存储在计算机的内存中,如下图,形似排成一列的箱子,一个箱子存储一个数据。当数据存储在内存时,决定他们数据顺序和位置关系的就是“数据结构”。

数据的存储就是物理结构,也就是数据在计算机内存的存储表示。

数据之间的关系就是对于逻辑结构,一种是线性关系,另一种是非线性。

线性关系:

  1. 最常用的数据结构,特点就是元素直接一对一的线性关系。
  2. 线性结构有两种不同的存储结构,顺序存储和链式存储。前者为顺序表,后者为链表。
  3. 顺序表存储元素的逻辑地址和内存地址是一样的,连续的。
  4. 链表存储相邻的元素内存上不一定连续,元素节点除了存放数据,还要存储相邻节点地址信息。
  5. 常见的线性结构:数组、队列、链表、栈。

非线性关系:

  1. 非一对一的线性关系。可能存在多个节点,如树形结构。
  2. 常见的非线性结构:二维数组,多维数组,广义表,树、图。

1.1 数据结构的重要性

如果你觉得数据结构不重要那就大错特错了。下面举一个电话簿的数据结构的例子来展示效率差异。

从上往下添加数据

举个简单的例子。假设我们有1个电话簿——虽说现在很多人都把电话号码存在手机里,但是这里我们考虑使用纸质电话簿的情况——每当我们得到了新的电话号码,就按从上往下的顺序把它们记在电话簿上。

假设此时我们想给“张伟”打电话,但是因为数据都是按获取顺序排列的,所以我们并不知道张伟的号码具体在哪里,只能从头一个个往下找(虽说也可以“从后往前找”或者“随机查找”,但是效率并不会比“从上往下找”高)。

如果电话簿上号码不多的话很快就能找到,但如果存了500个号码,找起来就不那么容易了。

按照姓名拼音排列顺序

接下来,试试以联系人姓名的拼音顺序排列吧。

因为数据都是以字典顺序排列的,所以它们是有“结构”的。使用这种方式给联系人排序的话,想要找到目标人物就轻松多了。通过姓名的拼音首字母就能推测出该数据的大致位置。

那么,如何往这个按拼音顺序排列的电话簿里添加数据呢?假设我们认识了新朋友“柯津博”并拿到了他的电话号码,打算把号码记到电话簿中。

由于数据按姓名的拼音顺序排列,所以柯津博必须写在韩宏宇和李希之间,但是上面的这张表里已经没有空位可供填写,所以需要把李希及其以下的数据往下移1行。此时我们需要从下往上执行“将本行的内容写进下一行,然后清除本行内容”的操作。如果一共有500个数据,一次操作需要10秒,那么1个小时也完成不了这项工作。

优缺点对比

总的来说,数据按获取顺序排列的话,虽然添加数据非常简单,只需要把数据加在最后就可以了,但是在查询时较为麻烦;

以拼音顺序来排列的话,虽然在查询上较为简单,但是添加数据时又会比较麻烦。

虽说这两种方法各有各的优缺点,但具体选择哪种还是要取决于这个电话簿的用法。

如果电话簿做好之后就不再添加新号码,那么选择后者更为合适;如果需要经常添加新号码,但不怎么需要再查询,就应该选择前者。

最佳方案

我们还可以考虑一种新的排列方法,将二者的优点结合起来。那就是分别使用不同的表存储不同的拼音首字母,比如表L、表M、表N等,然后将同一张表中的数据按获取顺序进行排列。

这样一来,在添加新数据时,直接将数据加入到相应表中的末尾就可以了,而查询数据时,也只需要到其对应的表中去查找即可。因为各个表中存储的数据依旧是没有规律的,所以查询时仍需从表头开始找起,但比查询整个电话簿来说还是要轻松多了。

1.2 选择合适的数据结构以提高内存的利用率

数据结构方面的思路也和制作电话簿时的一样。

将数据存储于内存时,根据使用目的选择合适的数据结构,可以提高内存的利用率。

其实上面的两个例子就类似于数据结构中的数组、链表、图。

2 链表

链表是数据结构之一,他的数据呈线性排列。特点就是添加和删除特别方便,但是访问比较费时。

逻辑结构:从图上看他们是连续的(线性排列)每个节点都有一个“指针”指向下一个数据的内存地址。

存储结构:链式存储,从图上看,数据是分散存储的,虽然逻辑上元素连续,但是内存中不连续。

2.1 元素访问

2.2 元素添加

2.3 元素删除

2.4 链表扩展

除了基本的链表结构,还存在几种扩展后的链表,分别是循环链表,双向链表。

2.5 总结

对链表的操作所需的运行时间到底是多少呢?

在这里,我们把链表中的数据量记成n。

访问数据时,我们需要从链表头部开始查找(线性查找),如果目标数据在链表最后的话,需要的时间就是O(n)。

另外,添加数据只需要更改两个指针的指向,所以耗费的时间与n无关。如果已经到达了添加数据的位置,那么添加操作只需花费O(1)的时间。

删除数据同样也只需O(1)的时间。

3 数组

数组也是线性排列的他和链表的不同就是,数组的访问很简单但是添加和删除比较麻烦。

存储结构:顺序存储,从图上看他们在内存中是连续的。

逻辑结构:从图上看他们是连续的(线性排列)从0开始排,因为他们在内存中是连续的所有我们可以根据数组下标计算出目标元素的位置,从而达到之间访问元素("随机访问")第n个元素就是a[n-1].

3.1 元素访问

比如现在我们想要访问Red。如果使用指针就只能从头开始查找,但在数组中,只需要指定a[2],便能直接访问Red。

3.2 元素添加

举一个添加元素到位置1的例子

  1. 首先数组末尾要确保添加元素的空间存在,如果内存不足(添加元素后超过数组大小)就无法添加。

    2. 把元素一个一个开始后移。

    3. 写入数据。

3.3 元素删除

继续尝试删除刚才添加的元素

  1. 删除元素。

    2. 所有元素挨着前移。

    3. 删除完成。

3.4 总结

这里讲解一下对数组操作所花费的运行时间。

假设数组中有n个数据,由于访问数据时使用的是随机访问(通过下标可计算出内存地址),所以需要的运行时间仅为恒定的O(1)。

但另一方面,想要向数组中添加新数据时,必须把目标位置后面的数据一个个移开。所以,如果在数组头部添加数据,就需要O(n)的时间。删除操作同理。

4 栈

栈也是一种数据呈线性的数据结构,特点就是只能访问到最新加的数据,就像一摞书,放新书时会放到最上面,拿书时会从最上面拿。

逻辑结构:很明显这东西是连续的

存储结构:他是“特殊”的线性存储结构,实现方式可以自己决定,顺序栈、链栈都是可以的

4.1 元素添加

4.2 元素获取(删除)

4.3 使用场景

例如,我们经常使用浏览器在各种网站上查找信息。

假设先浏览的页面 A,然后关闭了页面 A 跳转到页面 B,随后又关闭页面 B 跳转到了页面 C。

而此时,我们如果想重新回到页面 A,有两个选择:

重新搜索找到页面 A;

使用浏览器的"回退"功能。浏览器会先回退到页面 B,而后再回退到页面 A。

浏览器 "回退" 功能的实现,底层使用的就是栈存储结构。当你关闭页面 A 时,浏览器会将页面 A 入栈;同样,当你关闭页面 B 时,浏览器也会将 B入栈。因此,当你执行回退操作时,才会首先看到的是页面 B,然后是页面 A,这是栈中数据依次出栈的效果。

不仅如此,栈存储结构还可以帮我们检测代码中的括号匹配问题。多数编程语言都会用到括号(小括号、中括号和大括号),括号的错误使用(通常是丢右括号)会导致程序编译错误,而很多开发工具中都有检测代码是否有编辑错误的功能,其中就包含检测代码中的括号匹配问题,此功能的底层实现使用的就是栈结构。

同时,栈结构还可以实现数值的进制转换功能。例如,编写程序实现从十进制数自动转换成二进制数,就可以使用栈存储结构来实现。

以上也仅是栈应用领域的冰山一角,这里不再过多举例。

4.4 总结

像栈这种最后添加的数据最先被取出,即“后进先出”的结构,我们称为Last InFirst Out,简称LIFO。

与链表和数组一样,栈的数据也是线性排列,但在栈中,添加和删除数据的操作只能在一端进行,访问数据也只能访问到顶端的数据。想要访问中间的数据时,就必须通过出栈操作将目标数据移到栈顶才行。

5 队列

和栈相似但是添加数据和删除数据是在两端,就像平时生活中的排队,队头出人,队尾进入一样。

逻辑结构:参考栈

存储结构:参考栈

5.1 元素添加

5.2 元素获取

5.3 元素删除

5.4 总结

像队列这种最先进去的数据最先被取来,即“先进先出”的结构,我们称为FirstIn First Out,简称FIFO。

与栈类似,队列中可以操作数据的位置也有一定的限制。在栈中,数据的添加和删除都在同一端进行,而在队列中则分别是在两端进行的。队列也不能直接访问位于中间的数据,必须通过出队操作将目标数据变成首位后才能访问。

6 哈希表

哈希表是一个特殊的数据结构,他根据key访问数据,也就是通过关键码值映射到表中的一个位置来访问记录,它的特点是查询效率十分高效。当然这个映射函数是散列函数。

哈希表的存储是由键(key)和(value)值组成

6.1 哈希表的结构

6个箱子(即长度为6的数组)来存储数据。假设我们需要查询Ally的性别,由于不知道Ally的数据存储在哪个箱子里,所以只能从头开始查询。这个操作便叫作“线性查找”。

数据量越多,线性查找耗费的时间就越长。由此可知:由于数据的查询较为耗时,所以此处并不适合使用数组来存储数据。

但使用哈希表便可以解决这个问题。

首先准备好数组,这次我们用5个箱子的数组来存储数据,我们先尝试把Joe存进去

  1. 使用哈希函数(Hash)计算Joe的键,也就是字符串“Joe”的哈希值。得到的结果为4928
  2. 将得到的哈希值除以数组的长度5,求得其余数。这样的求余运算叫作“mod运算”。此处mod运算的结果为3。
  3. 因此,我们将Joe的数据存进数组的3号箱子中。重复前面的操作,将其他数据也存进数组中。

6.2 哈希冲突

  1. Nell键的哈希值为6276, mod 5的结果为1。本应将其存进数组的1号箱中,但此时1号箱中已经存储了Sue的数据。这种存储位置重复了的情况便叫作“冲突”。
  2. 遇到这种情况,可使用链表在已有数据的后面继续存储新的数据。
  3. Ally键的哈希值为9143, mod 5的结果为3。本应将其存储在数组的3号箱中,但3号箱中已经有了Joe的数据,所以使用链表,在其后面存储Ally的数据。
  4. ......
  5. 像这样存储完所有数据,哈希表也就制作完成了。

在存储数据的过程中,如果发生冲突,可以利用链表在已有数据的后面插入新数据来解决冲突。这种方法被称为“链地址法”。

除了链地址法以外,还有几种解决冲突的方法。

其中,应用较为广泛的是“开放地址法”。这种方法是指当冲突发生时,立刻计算出一个候补地址(数组上的位置)并将数据存进去。

如果仍然有冲突,便继续计算下一个候补地址,直到有空地址为止。可以通过多次使用哈希函数或“线性探测法”等方法计算候补地址。

6.3 哈希表的查询

假设我们要查询Dan的性别。

  1. 为了知道Dan存储在哪个箱子里,首先需要算出Dan键的哈希值,然后对其进行mod运算。最后得到的结果为4,于是我们知道了它存储在4号箱中。

  2. 查看4号箱可知,其中的数据的键与Dan一致,于是取出对应的值。由此我们便知道了Dan的性别为男(M)。

  3. 那么,想要查询Ally的性别时该怎么做呢?为了找到它的存储位置,先要算出Ally键的哈希值,再对其进行mod运算。最终得到的结果为3。

  4. 然而3号箱中数据的键是Joe而不是Ally。此时便需要对Joe所在的链表进行线性查找。

  5. 于是我们找到了键为Ally的数据。取出其对应的值,便知道了Ally的性别为女(F)。

6.4 总结

在哈希表中,我们可以利用哈希函数快速访问到数组中的目标数据。

如果发生哈希冲突,就使用链表进行存储。这样一来,不管数据量为多少,我们都能够灵活应对。

如果数组的空间太小,使用哈希表的时候就容易发生冲突,线性查找的使用频率也会更高;

反过来,如果数组的空间太大,就会出现很多空箱子,造成内存的浪费。

因此,给数组设定合适的空间非常重要。

7 堆

堆是一种图的树形结构,关于图的详细内容将在后续文章介绍。在堆的树形结构中,各个顶点被称为“结点”(node),数据就存储在这些结点中。

下面我们来看一个堆的示例:

节点内的数字就是堆存储的数据,堆中的每个节点最多有两个子节点,树的形状取决于数据的个数,节点排列顺序从上到下,同一侧从做到右。

7.1堆的规则

在堆中存储数据时必须遵守这样一条规则:子结点必定大于父结点。因此,最小值被存储在顶端的根结点中。

往堆中添加数据时,为了遵守这条规则,一般会把新数据放在最下面一行靠左的位置。

当最下面一行里没有多余空间时,就再往下另起一行,把数据加在这一行的最左端。

7.2 堆的添加

举一个添加元素5的例子

  1. 最下面一排空着一个位置,所以将数据加在此处。

  2. 如果父结点大于子结点,则不符合上面提到的规则,因此需要交换父子结点的位置。

  3. 这里由于父结点的6大于子结点的5,所以交换了这两个数字。重复这样的操作直到数据都符合规则,不再需要交换为止。

  4. 现在,父结点的1小于子结点的5,父结点的数字更小,所以不再交换。

7.3 堆的取数据

从堆中取出数据时,取出的是最上面的数据。这样,堆中就能始终保持最上面的数据最小。由于最上面的数据被取出,因此堆的结构也需要重新调整。

  1. 将最后的数据(此处为6)移动到最顶端。

  2. 如果子结点的数字小于父结点的,就将父结点与其左右两个子结点中较小的一个进行交换。

  3. 这里由于父结点的6大于子结点(右)的5大于子结点(左)的3,所以将左边的子结点与父结点进行交换。重复这个操作直到数据都符合规则,不再需要交换为止。

  4. 现在,子结点(右)的8大于父结点的6大于子结点(左)的4,需要将左边的子结点与父结点进行交换。

  5. 这样,从堆中取出数据的操作便完成了。

7.4 总结

堆中最顶端的数据始终最小,所以无论数据量有多少,取出最小值的时间复杂度都为O(1)。

另外,因为取出数据后需要将最后的数据移到最顶端,然后一边比较它与子结点数据的大小,一边往下移动,所以取出数据需要的运行时间和树的高度成正比。

假设数据量为n,根据堆的形状特点可知树的高度为log2n,那么重构树的时间复杂度便为O(logn)。

添加数据也一样。在堆的最后添加数据后,数据会一边比较它与父结点数据的大小,一边往上移动,直到满足堆的条件为止,所以添加数据需要的运行时间与树的高度成正比,也是O(logn)。

8 二叉查找树

二叉查找树(又叫作二叉搜索树或二叉排序树)是一种数据结构,采用了图的树形结构(关于树形结构的详细说明请参考4-2节)。数据存储于二叉查找树的各个结点中。

8.1 特点

每个结点的值均大于其左子树上任意一个结点的值

8.2 二叉查找数添加数据

下面我们来试着往二叉查找树中添加数据。比如添加数字1。

  1. 首先,从二叉查找树的顶端结点开始寻找添加数字的位置。将想要添加的1与该结点中的值进行比较,小于它则往左移,大于它则往右移。

  2. 由于1<9,所以将1往左移。

  3. 由于1<3,所以继续将1往左移,但前面已经没有结点了,所以把1作为新结点添加到左下方。

  4. 这样,1的添加操作便完成了。

8.3 二叉查找数删除数据

试试删除结点9。

  1. 如果需要删除的结点有两个子结点,那么先删掉目标结点……
  2. 然后在被删除结点的左子树中寻找最大结点……
  3. 最后将最大结点移到被删除结点的位置上。这样一来,就能在满足二叉查找树性质的前提下删除结点了。如果需要移动的结点(此处为4)还有子结点,就递归执行前面的操作

8.4 二叉查找数查找数据

  1. 从二叉查找树的顶端结点开始往下查找。和添加数据时一样,把12和结点中的值进行比较,小于该结点的值则往左移,大于则往右移。

删除9的时候,我们将“左子树中的最大结点”移动到了删除结点的位置上,但是根据二叉查找树的性质可知,移动“右子树中的最小结点”也没有问题。

由于12>4,所以往右移。

找到结点12了。

8.5 总结

我们可以把二叉查找树当作是二分查找算法思想的树形结构体现(二分查找的详细说明在3-2节)。

因为它具有前面提到的那两个性质,所以在查找数据或寻找适合添加数据的位置时,只要将其和现有的数据比较大小,就可以根据比较结果得知该往哪边移动了。

比较的次数取决于树的高度。所以如果结点数为n,而且树的形状又较为均衡的话,比较大小和移动的次数最多就是log2n。

因此,时间复杂度为O(logn)。但是,如果树的形状朝单侧纵向延伸,树就会变得很高,此时时间复杂度也就变成了O(n)。

有很多以二叉查找树为基础扩展的数据结构,比如“平衡二叉查找树”。这种数据结构可以修正形状不均衡的树,让其始终保持均衡形态,以提高查找效率。

结束语

    看完这篇文章,我对数据结构的基础概念已经复习的差不多了,后面的话将会对算法进行细致的讲解,当然其中还会参杂一些重要的数据结构的使用。懂得这些基础才能更好的学习算法,就像大厦的基石,地盘稳,算法的大楼才会屹立不倒!

    最后老话,欢迎有问题,有建议,有好资料的哥们和我分享,当然我也很乐意分享我的资料。只要你主动我们就有故事!!!

我是星宇,一个满头黑发,渴望秃头的开发,我们下期见!

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://mxyblogs.club/archives/八总常见的数据结构

Buy me a cup of coffee ☕.