❝

渔夫出海前，并不知道鱼在哪里，可是他们还是选择出发， 因为他们相信，一定会满载而归。人生很多时候，是「选择了才有机会，是相信了才有可能」。
-- 「稻盛和夫」

❞

大家好，我是「柒八九」。

今天，我们继续「计算机底层知识」的探索。我们来谈谈关于「小数运算」的相关知识点。

如果，想了解该系列的文章，可以参考我们已经发布的文章。如下是往期文章。

文章list

1. 计算机底层知识之CPU
2. 计算机底层知识之二进制
3. 计算机底层知识之处理小数

你能所学到的知识点

❝

1. 内存的物理机制 「推荐阅读指数」 ⭐️⭐️⭐️⭐️⭐️
2. 内存的逻辑模型是楼房 「推荐阅读指数」 ⭐️⭐️⭐️
3. 数组是高效使用内存的基础 「推荐阅读指数」 ⭐️⭐️⭐️
4. 栈、队列以及环形缓冲区 「推荐阅读指数」 ⭐️⭐️⭐️
5. 链表 「推荐阅读指数」 ⭐️⭐️⭐️
6. 二叉树 「推荐阅读指数」 ⭐️⭐️⭐️

❞

好了，天不早了，干点正事哇。

---

计算机是进行「数据处理」的设备，而程序表示的就是处理顺序和数据结构。由于处理对象（数据）是存储在「内存」和「磁盘」上的，因此我们今天来聊聊内存和磁盘。

---

内存的物理机制

❝

内存实际上是一种名为「内存IC」的电子元件。

❞

「内存IC」中有「电源」、「地址信号」、「数据信号」、「控制信号」等用于输入输出的大量「引脚」（IC的引脚），通过为其「指定地址」，来进行数据的读写。

下图是「内存IC」的引脚配置示例。

• VCC和GND是「电源」
• A0~A9是「地址信号」的引脚
• D0~D7是「数据信号」的引脚
• RD和WR是「控制信号」的引脚

将电源连接到VCC和GND后，就可以给其他引脚传递比如0或1这样的信号。大部分情况下，+5V的「直流电压」表示1,0V表示0。

• 「数据信号」引脚有D0~D7共8个，表示「一次可以输入输出8位」(=1字节)的数据。
• 「地址信号」引脚有A0~A9共10个，表示可以指定0000000000~1111111111共1024个地址

由于地址用来表示数据的存储场所，因此我们可以得出这个「内存IC」可以存储1024个1字节的数据。又因为1024=1K，所以内存IC的容量就是1KB。

向内存IC读写数据

写入数据

假设我们往内存IC中写入1字节的数据。

• 可以给VCC接入+5V,给GND接入0V的电源
• 并使用A0~A9的「地址信号」来指定「数据的存储场所」
• 然后把数据的值输入给D0~D7的数据信号
• 并「把WR(write的缩写)信号设定为1」

执行完这些操作，就可以在「内存IC」内部写入数据了。

读取数据

在读取数据时，只需要通过A0~A9的地址信号指定数据的存储场所，然后再「将RD(read的缩写)信号设成1」即可。执行完这些操作，指定地址中存储的数据就会被输出到D0~D7的数据信号引脚中。

像WR和RD这样可以让IC运行的信号称为「控制信号」。

❝

「内存IC」内部有大量可以存储8位数据的地方，通过地址指定这些场所，之后即可进行数据的读写。

❞

---

内存的逻辑模型

❝

内存的逻辑模型是楼房

❞

上图表示的是，内存为1KB时，有1024层的楼房，每层都有1字节的数据。并且地址的值是从上往下逐渐变大的。

不过，在实际的「编程环境」下，还包含着物理内存中不存在的概念，那就是「数据类型」。在编程语言中的「数据类型」表示存储的是何种类型的数据。从内存来看，就是占用的内存大小（占有的楼层数）的意思。

❝

即使是「物理」上以1个字节位单位来逐一读取数据的内存，在「程序」中，通过指定其类型，也能实现以「特定字节数」为单位来进行读写

❞

我们通过一个具体示例来进行说明。

下面是一个往a、b、c这三个变量中写入数据123的C语言程序，

// 定义变量
char a;
short b;
long c;

// 给变量赋值
a = 123;
b = 123;
c = 123;

这3个变量表示的是内存的特定区域。

❝

通过使用变量，即便不指定「物理地址」，也可以在程序中对内存进行读写。

❞

这是因为，在程序运行时候，操作系统会「自动决定」变量的物理地址。

在3个变量的数据类型分别是

• char:1字节长度
• short:2字节长度
• long:4字节长度

因此，虽然同样是数据123，存储时其占据的内存大小是不一样的。

上面的示例图中，采用的是「将数据低位存储在内存低位地址」的低字节序 Little Endian方式。

由此，我们可以得出一个结论：「根据程序中所指定的变量的数据类型的不同，读写的物理内存大小也会随之发生变化」。

---

数组是高效使用内存的基础

❝

「数组」是指多个「同样数据类型」的数据在内存中连续排列的形式。

❞

作为数组元素的各个数据会通过「连续的编号」被区分开来，这个编号称为「索引」。「指定索引后，就可以对该索引对应地址的内存进行读写操作」。

如下用C语言定义char类型、short类型、long类型三个数组。

char g[100];
short h[100];
long i[100];

数组的定义中所指定的数据类型，表示一次能够读取的内存大小。

❝

数组是使用内存的基本，因为其他的内存使用技能，每一种都需要以数组为基础

❞

---

栈、队列以及环形缓冲区

❝

栈和队列，都可以不通过指定地址和索引来对数组的元素进行读写。

❞

栈和队列的区别在于「数据出入的顺序是不同的」。在对内存数据进行读写时，「栈」用的LIFO(Last Input First Out,「后入先出」)方式，而「队列」用的是FIFO(First Input First Out,「先进先出」)方式。

❝

在内存中「预留」出栈和队列所需要的空间，并确定好写入和读出的顺序，就不用再指定地址和索引了

❞

我们假定往栈中写入数据的函数名为Push，把栈中读出数据的函数名为Pop

使用栈

// 往栈中写入数据
Push(123);  // 写入123
Push(456);  // 写入456
Push(789);  // 写入789

// 从栈中读出数据
j = Pop();  // 读出789
k = Pop();  // 读出456
l = Pop();  // 读出123

❝

当我们需要「暂时」舍弃当前的数据，随后再「恢复」原貌时候，优先选用栈

❞

使用队列

假定往队列中写入数据的函数名为EnQueue，把栈中读出数据的函数名为DeQueue

// 往栈中写入数据
EnQueue(123);  // 写入123
EnQueue(456);  // 写入456
EnQueue(789);  // 写入789

// 从栈中读出数据
m = DeQueue();  // 读出123
n = DeQueue();  // 读出456
o = DeQueue();  // 读出789

❝

当我们需要处理「通讯」中发送的数据时，或由「同时运行的多个程序」所发送过来的数据时，会用到这种队列中存储的不规则数据进行处理的方法

❞

队列一般是以环形缓冲区Ring Buffer的方式来实现的。

假设我们要有6个元素的数组来实现一个队列。这时可以从数组的「起始位置」开始有序地存储数据，然后再按照存储时的顺序数据读出。在数组的末尾写入数据后，后一个数据就会被写入数据的起始位置（此时数据已经被读出所以该位置是空的）

---

链表

❝

通过使用链表，可以更加高效地对数组数据(元素)进行「追加」和「删除」处理

❞

在数组的各个元素中，「除了数据的值之外，通过为其附带上下一个元素的索引」，即可实现链表。「数据的值和下一个元素的索引组合在一起」，就构成了数组的一个元素。

由于链表末尾的元素没有「后续」的数据，因此就需要用别的值（这里是-1）来填充。

在需要追加或删除数据的情况下，使用链表是很高效的。

这里，我们把之前我们针对JS链表相关算法的一些技巧直接迁移过来了。这里使用「哨兵节点」来对链表操作进行简化处理。

❝

「哨兵节点」是为了简化处理链表「边界条件」而引入的「附加链表节点」

❞

哨兵节点通常位于「链表的头部」，它的值没有任何意义。在一个有哨兵节点的链表中，「从第二个节点开始才真正的保存有意义的信息」。

追加数据

function append(head,value) {
  // 哨兵节点 
  let dumy = new ListNode(0);
  dumy.next = head;
  
  // 遍历链表，直到链表尾部
  let node = dumy;
  while(node.next!=null){
    node = node.next;
  }

  node.next = new ListNode(value);
  return dumy.next;
}

首先，创建一个「哨兵节点」（该节点的「值」没有意义 -即ListNode(0)参数为啥不重要），并把该节点当做链表的头节点，「把原始的链表添加到哨兵节点的后面」（dumy.next = head）。

然后，返回真正的头节点（哨兵节点的下一个节点）node.next

这里有一个小的注意点，就是在「遍历」链表的时候，并不是直接对dumy进行处理，而是用了一个「零时游标节点」(node)。这样做的好处就是，在append操作完成以后，还可以通过dumy节点来，直接返回链表的头节点dumy.next。 因为,dumy一直没参与遍历过程。

删除数据

❝

为了删除一个节点，需要找到被删除节点的「前一个节点」，然后把该节点的next指针指向它「下一个节点的下一个节点」。

❞

「哨兵节点」，在删除指定节点

function delete(head ,value){
  let dumy = new ListNode(0);
  dumy.next = head;
  
  let node = dumy;
  while(node.next!=null){
    if(node.next.value==value){
      node.next = node.next.next;
      barek;
    }
    node = node.next;
  }
  return dumy.next;
}

通过哨兵节点(dumy)直接将「链表为空」和「被删除节点是头节点」的两种特殊情况，直接囊括了。用最少的代码，处理最多的情况

---

二叉树

「二叉树查找树」是指在链表的基础上往数组中追加元素时，考虑到数据的大小关系，将其分成左右两个方向的表现形式。

❝

二叉查找树使「数据搜索」更有效。

❞

---

❝

「我们这里不对具体的数据结构进行详细的介绍。如果了解更多关于数据结构的和对应的算法的东西，可以移步到我们之前的文章中。」 总有一款适合你。

❞

后记

「分享是一种态度」。

参考资料：《程序是怎样跑起来的》

「全文完，既然看到这里了，如果觉得不错，随手点个赞和“在看”吧。」