重点：计算机是进行数据处理的设备，而程序表示的就是处理顺序和数据结构。由于处理对象数据是存储在内存和磁盘上的，因此程序必须能自由地使用内存和磁盘。因此，大家有必要对内存和磁盘的构造有一个物理上的（硬件的）和逻辑上的（软件的）认识。本章的主题是内存（磁盘部分会在第 5 章中讲解）。其实，从物理上来看，内存的构造非常简单。只要在程序上花一些心思，就可以将内存变换成各种各样的数据结构来使用。譬如，物理上有棱有角的内存，在程序上是可以按照逻辑很流畅地使用的。而且这并不特别，它是很多程序中都会用到的一般方法。
热身问题
- 有十个地址信号引脚的内存 IC（集成电路）可以指定的地址范围是多少？
- 高级编程语言中的数据类型表示的是什么？
- 在32 位内存地址的环境中，指针变量的长度是多少位？
- 与物理内存有着相同构造的数组的数据类型长度是多少？5.
- 用LIFO 方式进行数据读写的数据结构称为什么？
- 根据数据的大小链表分叉成两个方向的数据结构称为什么？
答案
- 用二进制数来表示的话是 0000000000～1111111111（用十进制数来表示的话是 0～1023）
- 占据内存区域的大小和存储在该内存区域的数据类型
- 32位
- 1字节
- 栈
- 二叉查找树（二叉搜索树）
4.1 内存的物理机制很简单
内存实际上是一种名为内存集成电路的电子元件。虽然内存集成电路包括内存、SRAM、.ROM一个等多种形式，但从外部来看，其基本机制都是一样的。内存 IC中有电源、地址信号、数据信号、控制信号等用于输入输出的大量引脚（IC的引脚），通过为其指定地址（address），来进行数据的读写。
图4-1是内存集成电路（在这里假设它为RAM）的引脚配置示例。虽然这是一个虚拟的内存集成电路[IC]，但它的引脚和实际的内存集成电路[IC]是一样的。VCC和GNB是电源，A0～A9是地址信号的引脚，D0～D7是数据信号的引脚，RD[研发]和WR[水利]是控制信号的引脚。将电源连接到VCC[可变资本公司]和GND[接地]后，就可以给其他引脚传递比如0或者1这样的信号。大多数情况下，+ 5V的直流电压表示1，0V表示0。
那么，这个内存集成电路中能存储多少数据呢？数据信号引脚有D0～D7共八个，表示一次可以输入输出8位（=1字节）的数据。此外，地址信号引脚有答0～答9共十个，表示可以指定0000000000～1111111111共1024个地址。而地址用来表示数据的存储场所，因此我们可以得出这个内存集成电路中可以存储1024个1字节的数据。因为1024=1K一个，所以该内存集成电路的容量就是1KB。
4.2 内存的逻辑模型是楼房
在介绍程序时，大部分参考书都会用类似于楼房的图形来表示内存。在这个楼房中，1层可以存储1个字节的数据，楼层号表示的就是地址。对于程序员来说，这种形象的解说有助于了解内存。虽然内存的实体是内存集成电路，不过从程序员的角度来看，也可以把它假想成每层都存储着数据的楼房，并不需要过多地关注内存集成电路的电源和控制信号等。因此，之后的讲解中我们也同样会使用楼房图（或者与楼房相似的图）。内存为1KB时，表示的是如图4-3所示的有1024层的楼房（这里地址的值是从上往下逐渐变大，不过也有与此相反的情况）。
不过，程序员眼里的内存模型中，还包含着物理内存中不存在的概念，那就是数据类型。编程语言中的数据类型表示存储的是何种类型的数据。从内存来看，就是占用的内存大小（占有的楼层数）的意思。即使是物理上以1个字节为单位来逐一读写数据的内存，在程序中，通过指定其类型（变量的数据类型等），也能实现以特定字节数为单位来进行读写。
下面我们来看一个具体的示例。如代码清单4-1所示，这是一个往一个、b、c这3个变量中写入数据123的C语言程序。这3个变量表示的是内存的特定区域。通过使用变量，即便不指定物理地址，也可以在程序中对内存进行读写。这是因为，在程序运行时，窗户等操作系统会自动决定变量的物理地址。
这3个变量的数据类型分别是，表示1字节长度的煳，表示2字节长度的短，以及表示4字节长度的长一个。因此，虽然同样是数据123，存储时其所占用的内存大小是不一样的。这里，我们假定采用的是将数据低位存储在内存低位地址的低字节序（小端序）B方式（图4-4）。
仔细思考一下就会发现，根据程序中所指定的变量的数据类型的不同，读写的物理内存大小也会随之发生变化，这其实是非常方便的。大家不妨想一想，假如程序中只能逐个字节地对内存进行读写，那该多么不便啊。在处理超过1个字节的数据时，还必须要编写分割处理程序。此外，在不同的编程语言中，变量可以指定的数据类型的最大长度也不相同。C语言中，8字节（=64位）的双类型是最大的。
4.3 简单的指针
指针也是一种变量，它所表示的不是数据的值，而是存储着数据的内存的地址。通过使用指针，就可以对任意指定地址的数据进行读写。虽然前面所提到的假想内存集成电路中仅有10位地址信号，但大家在窗户计算机上使用的程序通常都是32位（4字节）的内存地址。这种情况下，指针变量的长度也是32位。
请大家看一下代码清单4-2。这是定义一个了d、e、f这3个指针变量的C语言程序。和通常的变量定义有所不同，在定义指针时，我们通常会在变量名前加一个星号（*）。我们知道，d、e、f都是用来存储32位（4字节）的地址的变量。然而，为什么这里又用来指定煳（1字节）、短（2字节）、长（4字节）这些数据类型呢？大家是不是也感到很奇怪？实际上，这些数据类型表示的是从指针存储的地址中一次能够读写的数据字节数。
假设d、e、f的值都是100。在这种情况下，使用d时就能够从编号100的地址中读写1个字节的数据，使用e时就是2个字节（100地址和101地址）的数据，使用f时就是4个字节（100地址～103地址）的数据。
4.4 数组是高效使用内存的基础
回到主题，解释一下本章标题中出现的"熟练使用有棱有角的内存"。在熟练使用前，我们先来看一下内存最直接的使用方法。在这里，我们要用到数组。
数组是指多个同样数据类型的数据在内存中连续排列的形式。作为数组元素的各个数据会通过连续的编号被区分开来，这个编号称为索引（指数）。指定索引后，就可以对该索引所对应地址的内存进行读写操作一个。而索引和内存地址的变换工作则是由编译器自动实现的。
代码清单4-3表示的是在C语言中定义煳类型、短类型和长类型这三个数组。用括号围起来的[100]，表示数组的元素有100个。由于在C语言中，数组的索引是从0开始的，因此，字符[100];表示的就是可以使用克[0]～克[99]这100个元素。
数组的定义中所指定的数据类型，也表示一次能够读写的内存大小。煳类型的数组以1个字节为单位对内存进行读写，而短类型和长类型的数组则分别以2个字节、4个字节为单位对内存进行读写。数组是使用内存的基本。本章后半部分会讲述各种各样的内存使用技能，其中每一种都需要以数组为基础。
4.5 栈、队列以及环形缓冲区
栈B和队列，都可以不通过指定地址和索引来对数组的元素进行读写。需要临时保存计算过程中的数据、连接在计算机上的设备或者输入输出的数据时，都可以通过这些方法来使用内存。如果每次保存临时数据都需指定地址和索引，程序就会变得比较麻烦，因此要加以改进。
栈和队列的区别在于数据出入的顺序是不同的。在对内存数据进行读写时，栈用的是后进先出（最后输入先出，后入先出）方式，而队列用的则是先进先出（先输入先出，先入先出）方式。如果我们在内存中预留出栈和队列所需要的空间，并确定好写入和读出的顺序，就不用再指定地址和索引了。
如果要在程序中实现栈和队列，就需要以适当的元素数来定义一个用来存储数据的数组，以及对该数组进行读写的函数对。当然，在这些函数的内部，对数组的读写会涉及索引的管理，但从使用函数的角度来说，就没有必要考虑数组及索引了。
队列这一方式也称为排队。排队指的是买车票时在自动售票机前等候的队列等。排队时，站在最前面的乘客先买票，购买后率先从队列中走出来。当随机前来的购票乘客数量和自动售票机的处理速度不相符时，排队能起到很好的缓冲作用。程序中也是如此，为了协调好数据输入和处理时机间的关系，采用类似于排队的机制是很方便的。在内存上，实现这种机制的方式就是队列。当我们需要处理通讯中发送的数据时，或由同时运行的多个程序所发送过来的数据时，会用到这种对队列中存储的不规则数据进行处理的方法。
队列一般是以环状缓冲区（环形缓冲器）的方式来实现的，也就是本章标题中所说的"熟练使用有棱有角的内存"。例如，假设我们要用有6个元素的数组来实现一个队列。这时可以从数组的起始位置开始有序地存储数据，然后再按照存储时的顺序把数据读出。在数组的末尾写入数据后，后一个数据就会被写入数组的起始位置（此时数据已经被读出所以该位置是空的）。这样，数组的末尾就和开头连接了起来，数据的写入和读出也就循环起来了（图4-9）。
4.6 链表使元素的追加和删除更容易
接下来介绍的链表和二叉查找树，都是不用考虑索引的顺序就可以对数组元素进行读写的方式。通过使用链表，可以更加高效地对数组数据（元素）进行追加和删除处理。而通过使用二叉查找树，则可以更加高效地对数组数据进行检索。
在数组的各个元素中，除了数据的值之外，通过为其附带上下一个元素的索引，即可实现链表。数据的值和下一个元素的索引组合在一起，就构成了数组的一个元素。这样，数组元素相连就构成了念珠似的链表。由于链表末尾的元素没有后续的数据，因此就需要用别的值（在这里是－1）来填充（图4-10）。
在需要追加或删除数据的情况下，使用链表是很高效的。首先，让我们来看一下删除的情况。在图4-10表示的链表中，假设要删除从起始位置开始的第3个元素。此时，我们只需要把第2个元素的"下一个元素：2"变成"下一个元素：3"即可。由于数组的元素通常是按照索引顺序来引用的，因此当我们需要引用构成链表的数组的某一个元素时，通过该元素的索引信息就可以找到下一个元素。当第2个元素的下一个元素变成第4个元素后，那么第3个元素就被删除了。虽然第3个元素在物理内存上还残留着，但在逻辑上则确实被删除了
4.7 二叉查找树使数据搜索更有效
二叉查找树一个是指在链表的基础上往数组中追加元素时，考虑到数据的大小关系，将其分成左右两个方向的表现形式。例如，假设我们事先把50这个值保存到了数组中。那么，如果接下来的值比先前保存的数值大的话，就要将其放到右边，反之如果小的话就放在左边。但实际的内存并不会分成两个方向，这是在程序逻辑上实现的（图4-15）。
为了实现二叉查找树，怎么处理比较好呢？其实数组的每个元素中只要有数据的值和两个索引信息就可以了。图4-16向我们展示了如何用数组来实现图4-14中的二叉查找树。二叉查找树是由链表构造发展而来的表现形式，因此在追加或删除元素方面也同样是有效的。
使用二叉查找树的便利之处在于可以使数据的搜索等更有效率。在使用一般的数组时，必须从数组的开头按照索引顺序来查找目标数据。而使用二叉查找树时，当目标数据比现在读出来的数据小时就可以转到左侧，反之目标数据较大时即可转到链表的右侧，这样就加快了找到目标数据的速度。
标签：字节,元素,地址,有棱有角,内存,数组,数据,第四章 From： https://www.cnblogs.com/Chenyaxuan/p/17073796.html