《程序是怎样跑起来的》读书笔记——第四章熟练使用有棱有角的内存

1 内存的物理机制很简单
2 内存的逻辑模型是楼房
3 简单的指针
4 数组是高效使用内存的基础
5 栈、队列以及环形缓冲区
- 队列一般是以环状缓冲区(ring buffer)的方式来实现的
6 链表使元素的追加和删除更容易
- 6.1 如何往链表中删除数据
- 6.2 如何往链表中追加数据
7 二叉查找树使数据搜索更有效

1 内存的物理机制很简单

内存实际上是一种名为内存 IC 的电子元件。内存IC 中有电源、地址信号、数据信号、控制信号等用于输入输出的大量引脚(IC 的引脚)，通过为其指定地址(address)，来进行数据的读写。

那么，这个内存 IC 中能存储多少数据呢?
数据信号引脚有 D0~D7 共八个，表示一次可以输入输出 8 位(= 1 字节)的数据。
地址信号引脚有 A0~A9 共十个，表示可以指定 0000000000~1111111111 共 1024 个地址。而地址用来表示数据的存储场所，因此我们可以得出这个内存 IC 中可以存储 1024 个 1 字节的数据。因为 1024 = 1K，所以该内存 IC 的容量就是 1KB。

往该内存 IC 中写入 1 字节的数据。
为了实现该目的，可以给 VCC 接入+5V，给 GND 接入 0V 的电源，并使用 A0~A9 的地址信号来指定数据的存储场所，然后再把数据的值输入给 D0~D7 的数据信号，并把 WR(write = 写入的简写)信号设定成 1。执行完这些操作，就可以在内存 IC 内部写入数据(图 4-2 (a))了。

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

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

2 内存的逻辑模型是楼房

1KB 内存的模型

程序员眼里的内存模型中，还包含着物理内存中不存在的概念，那就是数据类型。

编程语言中的 数据类型表示存储的是何种类型的数据。从内存来看，就是占用的内存大小(占有的楼层数)的意思。

这是一个往 a、b、c 这 3 个变量中写入数据 123 的 C 语言程序。这 3 个变量表示的是内存的特定区域。通过使用变量，即便不指定物理地址，也可以在程序中对内存进行读写。这是因为，在程序运行时，Windows 等操作系统会自动决定变量的物理地址。

// 定义变量 
char a; //表示 1 字节长度的 char
short b; //表示 2 字节长度的 short
long c;//以及表示 4 字节长度的 long
// 给变量赋值 
a = 123;
b = 123;
c = 123;

3 简单的指针

指针也是一种变量，它所表示的不是数据的值，而是存储着数据的内存的地址。通过使用指针，就可以对任意指定地址的数据进行读写。大家在 Windows 计算机上使用的程序通常都是 32 位(4 字节)的内存地址。这种情况下，指针变量的长度也是 32 位。

指针变量长度都一样，那么之所以要定义成不同类型的指针变量，是因为这些数据类型表示的是从指针存储的地址中一次能够读写的数据字节数。

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

数组是指多个同样数据类型的数据在内存中连续排列的形式。作为数组元素的各个数据会通过连续的编号被区分开来，这个编号称为 索引(index)。索引和内存地址的变换工作则是由编译器自动实现的。

5 栈、队列以及环形缓冲区

栈和队列，都可以不通过指定地址和索引来对数组的元素进行读写。需要临时保存计算过程中的数据、连接在计算机上的设备或者输入输出的数据时，都可以通过这些方法来使用内存。

栈和队列的区别在于数据出入的顺序是不同的。在对内存数据进行读写时，栈用的是 LIFO(Last Input First Out，后入先出)方式，而 队列用的则是 FIFO(First Input First Out，先入先出)方式。如果我们在内存中预留出栈和队列所需要的空间，并确定好写入和读出的顺序，就不用再指定地址和索引了。