7. 数据结构与算法

1.前言

编程的本质,实际上就是在尽可能高效的存储、使用数据。

而数据结构便是数据在计算机中的存储方式,至于算法,就是如何去高效的利用数据。

对于计算机来说,由于其底层内存、硬盘的物理组成形式为一块内存挨着一块内存,最终操作系统用内存地址来标注内存的位置,因为其最基本的结构就是线性结构。

比如我们存一系列数据:1、2、3、4、5。将其存入到内存中,那么最直接的形式就是这五个数字挨个写入相邻地址的内存块中。

而读取的时候也能顺序的根据地址读取这五个数据。

这便是最基本的数据结构:数组。

至于其它类型的数据结构,都是在此之上进行组织的,本文会循序渐进、从整体上的对这些常见的数据结构、算法特性进行基本的介绍。

如果你想要更加详细的了解这方面的知识,那么可以参考:Hello 算法

2.数组

正如前面所说,数组是最基本的数据结构,同时也是内存物理结构的直观显示。

image.png

正因为连续,所以它可以非常方便的取数据,只要你知道了其中一个元素的位置,那么直接在该位置上加减数字就是该元素前面、或者后面的元素所在的位置,取元素的效率是非常高的。

但又因为它是连续的,这导致如果我们想要在其中间插入一个元素,就需要先将该位置之后的元素全部后移一位,然后才能插入,会导致插入数值的效率变得缓慢。

另一个名词叫做“列表”,但实际上两者本质上区别不大,都是用连续的内存存取数据,唯一区别可能是大多数时候在很多语言中,数组的长度不可变,只能初始化的时候插入值,而列表的长度可变,可以动态插入值,这里不做区分。

注意,这里的“后移”,实际上就是将所有元素向后一位进行复制。

所以对于数组来说,它适用于下面的场景:

  1. 大多数只在尾部位置添加元素/甚至不需要插入数据
  2. 需要经常随机位置取元素、或者遍历元素。

在C语言中,我们可以用malloc分配一块连续的内存作为数组使用,后续的C++中,存在现成的Vector库,这是官方封装好的数组实现,可以直接给我们使用。

同样的,其它高级语言都会有自己的官方库实现,所以大多数并不需要我们自己去实现这么一个数组结构,但在你前期的学习过程中,推荐你自己去实现一个方便好用的抽象数组结构,就能更好的理解其原理了。

3.链表

正因为上述数组的缺点,所以又出现一种叫做链表的结构,它解决了数组的缺陷,但又拥有了它自己的缺陷。

与数组相反,链表的每个元素并不是在内存中连续的,它靠在每个元素中记录上一个、下一个元素的地址,从逻辑上实现类似于数组的结构:

image.png

由于我们访问元素是通过地址实现的,所以列表的原理便是,每个元素存储上/下一个元素的地址。

此时如果我们想要获取第三个元素的值,那么我们就只能从第一个元素挨个找过去:第一个元素内存放第二个元素的地址,第二个元素内存放第三个元素的地址。

绝大多数情况下,我们只会在链表结构创建的时候,保存第一个元素、乃至最后一个元素的地址。

这便导致了,我们无法像数组那样,可以随机访问某个元素了,只能从头/尾挨个查过去。

但同样的,这种结构利于插入新的元素,此时无论你想要在哪个位置中插入新元素,都只需要新开辟一块内存,将前一个元素存放下一个元素的地址改为新内存,后一个元素存放前一个元素的地址改为新内存。

而我们新内存就需要存放前一个元素、后一个元素的地址。

此时你会发现,我们在任何一个位置插入元素,最多只会影响相邻的两个元素数组,而不会像前面数组那样,将所有后面的元素都进行后移复制。

因此,链表适用于以下场景:

  1. 需要频繁插入数据
  2. 不需要频繁的进行随机位置元素访问操作

链表也有单链表和双链表之分,上面我们介绍的都是双向链表,也就是你既可以从头到尾遍历,也可以从尾到头遍历。

而单向链表则是每个元素只保留它后一个元素的地址,不保留前一个元素的地址,这可以节省空间,但也导致只能从头到尾进行遍历。

4.栈

前两种是最基本、最底层的程序存储数据方式,而后面要介绍的便是相对抽象的概念。

第一种便是栈:

image.png

它的特点便是只能从栈顶添加元素、或者移除元素。

你可以用上面的数组、链表任意一种方式来实现这个结构。

实现方式非常简单:

  1. 维护一个内存块结构体。
  2. 添加一个添加元素的函数,该函数只会将元素往内存块最后面添加。
  3. 添加一个移除元素的函数,该函数只能将最后面的元素删除掉。

并且你需要将该结构“私有化”,保证别人不能直接操作你的内存结构,而只能通过你提供的函数进行操作。

这样你就完成了一个最简单的栈结构的封装。

但栈有什么用呢?它的用处非常大。

比如你用各种软件,很多都会有“撤销”功能,便是用栈实现的,你的每个操作都会入栈,每次撤销上一步操作就是出栈操作。

5.队列

相比于栈,队列就简单多了,就是排队的意思。

image.png

排队的特点是什么?就是先来的先走,后来的排最后,不允许插队。

根据它的特性,它最好的实现方式便是用上面提到的链表,因为它不需要随机访问中间的元素,也就是不允许插队。

作者:余识
全部文章:0
会员文章:0
总阅读量:0
c/c++pythonrustJavaScriptwindowslinux