为什么有了内存,还要数组、链表和树

为什么有了内存,还要数组、链表和树

内存：内存本质上是一种由内存芯片构成的存储装置，常见的有 RAM、ROM 这些类型

内存是什么

可以想象内存就是一个中药柜

• 在我们现在这个语境里,可以先理解成每个柜子对应 1 字节
• 每个柜子有唯一编号(地址)
• CPU 想要读写数据怎么办？CPU 会报一个柜子编号，内存就把对应柜子的内容交给它

那么它们之间是如何沟通的?有三根线

1. 地址线：CPU 用来告诉内存“我要第几号柜子”
2. 数据线:实际传输柜子里的内容,双向(表示读写都走这条)
3. 控制线:控制数据线,我是读数据,还是写数据

地址线的数量决定了最多能表示多少个地址

就像一个密码锁一样

• 地址线数量为 1 时,只能拨出 0 和 1 两种状态,能表示 2 个地址
• 地址线数量为 2 时,能拨出 00、01、10、11 四种状态,能表示 4 个地址

可以用这样一个公式来表达:2^地址线数量

举例：10 根地址线，那就是 2^10 = 1024，也就是能表示 1024 个地址。如果按 1 个地址对应 1 字节来理解,那就是 1024 字节,也就是 1KB。还有像 MB、GB，都是逢 1024 进 1

内存就是一堆储物柜,每个柜子都占 1 字节。到这都没有问题。那么，我定义一个 int ，它占四个字节，那怎么知道它代表的是一个整数还是一个小数？

数据类型

首先,内存并不知道这代表什么意义,它只负责存 0 和 1

那么数据类型,它就出现了

举例

1. 当成一个字符（char）来读，只读 1 格

01000001 -> 字符表 -> 'A'

1. 当成一个整数（int）来读，读 4 格

00000000 00000000 00000000 01000001 -> 65

数据类型:解读规则。它来告诉计算机"读几格" "怎么翻译"

指针

指针:访问地址,按地址去拿数据

举个例子:拿快递

你去拿快递,你怎么知道你的快递在哪里? 取件码。它告诉你,你的包裹在 5-3-3322

指针本身也要占字节,这根据你程序运行环境是多少位来决定

• 32 位程序里,指针通常占 4 字节
• 64 位程序里,指针通常占 8 字节

来看普通变量和指针变量的区别

假设:0000 地址存储的数据为 0011

• 普通变量,直接去 0000 拿数据 -> 拿到 3
• 指针变量,先看指针里写的地址(0000) -> 再去那个地址拿 -> 拿到 3

那既然有普通变量和指针变量,自然也就有普通数据类型和指针数据类型

那么也就多了一步

• 普通数据类型:读几格、怎么翻译
• 指针数据类型:先到地址 -> 再读几格、怎么翻译

以上面两个类型举例

• char *p -> 到了目标地址后,读 1 格,按字符翻译
• int *p -> 到了目标地址后,读 4 格,按整数翻译

数组

为什么要数组? 来看它解决什么问题

举例:一个班 50 个学生的成绩

如何去存? 写 50 个变量?

int score1 = 100;
int score2 = 90;
...
int score50 = 60;

这样不是不行,但你如何通过地址去找呢? 注意,你定义每一个变量,地址不一定连续,也不好算

这时,数组出现了

int scores[50] = {100, 90, ..., 60};

那它们的地址关系就很好找了

假设起始地址为 0100(这里先按十进制理解),那么我要找第 24 个学生的成绩呢?

目标地址 = 0100 + (24 - 1) × 4
         = 0100 + 92
         = 0192

所以数组最适合这种:元素类型一样,而且你还想快速按下标找数据

栈和队列

存讲完了,接下来是取。很多场景下,你需要按特定的规则去存取数据

在之前的文章也讲过,栈和队列,分别对应的是后进先出和先进先出

• 栈(LIFO):就像厨房洗盘子,洗完的叠上去,每次使用都拿最上面的盘子用
• 队列(FIFO):就像排队吃饭,先到先吃

栈最常用的用途:函数调用

• main() 调用 funcA()
• funcA() 调用 funcB()
• funcB() 执行完成,返回给 funcA()
• funcA() 执行完成,返回给 main()

可以看到, 是最先进来,但最后出去的main()

队列也一样很常见,就像for循环一样

链表

数组挺好用的,查找非常快,但它有个问题:长度固定,且元素最好连续排列

举例:[1, 2, 3, 4, 5] 在 2 和 3 之间插入数据 99,就得把 3、4、5 全部往后挪动一格,再放进去 99,这非常麻烦

链表就非常适合插入数据了,它的核心概念为:每个人都手拿下一个人的地址

举例:在 B 和 C 之间插入一个 X

• 插入之前:A -> B -> C -> D 第一步:X 指向 C 第二步:B 指向 X
• 插入之后:A -> B -> X -> C -> D

那么对比一下它们在内存中地址的变化,假设初始位置都为 0100

1. 数组
   • 插入之前: 1:0100 -> 2:0104 -> 3:0108 -> 4:0112
   • 变化过程: 1:0100 -> 2:0104 -> 3:0108 -> 3:0112(复制上一个数据,再重写) -> 4:0116(复制上一个数据,再重写)
   • 插入之后: 1:0100 -> 2:0104 -> 99:0108 -> 3:0112 -> 4:0116
2. 链表
   • 插入之前: A:0100 -> B:0114 -> C:0208 -> D:0312
   • 插入之后: A:0100 -> B:0114 -> X:0908 -> C:0208 -> D:0312

那代价就是:查找十分麻烦,必须从头找到尾。如果中间 C 丢了,你将找不到 D

二叉查找树

从一个问题说起

假设你手上有一个已经排好序的数组,里面存了 1 万个学号,现在要查"学号 5678 在不在里面"

因为数组是排好序的,可以用折半查找。翻到中间看一眼,大了往前找,小了往后找,每次排除一半。1 万个数据最多 14 次就能找到

但问题来了:新学期 100 个新生入学,要把学号插进去还得保持排序。数组是连续排列的,往中间插一个数据,后面所有元素都要往后搬一格。数据量一大,这个搬家的代价很重

查得快,但插得慢。有没有一种结构能同时解决这两个问题?

这就是二叉查找树要做的事

它的规则其实很简单

• 每个节点最多有两个子节点
• 左边的值比自己小
• 右边的值比自己大

这样一来,你查一个数的时候,就不用从头一个个看了

• 如果目标比当前节点小,就往左走
• 如果目标比当前节点大,就往右走
• 一路走下去,直到找到或者走到空位置

插入新数据也一样,不需要像数组那样把后面的元素整体往后搬,只要找到合适的空位置,把它挂上去就行

当然,它也不是完美的。如果这棵树长歪了,比如数据总是按从小到大的顺序插进去,那它最后可能会越来越像链表,查找效率也会跟着变差

总结

看到这里其实能发现一件事

内存本身只负责按地址存字节,它并不关心你存的是整数、字符,还是一堆学生成绩

真正决定你程序好不好用、快不快的,往往是你怎么去组织这些数据

数组、栈、队列、链表、树,本质上都是人为了更高效地使用内存,想出来的不同办法