思考问题
-
- 有十个地址信号引脚的内存IC（集成电路）可以指定的地址范围是多少
用二进制数表示的话就是0000 0000 00~1111 1111 11
用十进制数表示的话就是0~1023（即2的10次方-1）
-
- 高级编程语言中的数据类型表示的是什么
占据内存区域的大小和存储在该内存区域的数据类型。
解析：如在C语言中，short类型，它表示的是占据2字节的内存区域，并且存储 整数。
-
- 在32位内存地址的环境中，指针变量的长度是多少
32位。
解析：指针指的是用于存储内存地址的变量。
-
- 与物理内存有着相同构造的数组的数据类型长度是多少
1字节
解析：物理内存是以字节为单位进行数据存储的
-
- 用LIFO方式进行数据读写的数据结构称为什么
栈
解析：栈是一种后入先出（LIFO= Last in First out）式的数据结构
-
- 根据数据的大小链表分叉成两个方向的数据结构成为什么
二叉查找树（binary search tree）
二叉查找树指的是从节点分成两个叉的树状数据结构
章节重点
计算机是进行数据处理的设备，而程序表示的就是处理顺序和数据结构。由于处理对象数据是存储在内存和磁盘上的，因此程序必须能自由地使用内存和磁盘。
章节结构
- 内存的物理机制很简单
- 内存的逻辑模型是楼房
- 简单的指针（为什么定义指针变量时要定义类型）
- 数组是高效实用内存的基础
- 栈、队列以及环形缓冲区
- 链表使元素的追加和删除更容易
- 二叉查找树使数据搜索更有效
内存的物理机制很简单
内存的物理机制：内存实际上是一种名为内存IC的电子元件。
内存IC包括DRAM、SRAM、ROM等多种形式，但从外部来看，其基本机制是一样的。
内存IC中有电源、地址信号、数据信号、控制信号等用于输入输出的大量引脚（IC的引脚），通过为其指定地址，来进行数据的读写。
内存IC的容量计算
- 数据信号引脚的数量决定一次可以输入输出多大的数据
数据信号引脚有8个，那么表示一次可以输入输出8位（=1字节）的数据。 - 地址信号引脚的数量决定地址的数量
地址引脚若有10个，则表示可以指定0000000000~1111 1111 11共1024个地址。
地址是用来表示数据的存储场所，
综上所述，若一个内存IC有数据信号引脚8个，地址引脚10个，则它可以存储1024个1字节的数据。因为1024 =1K,所以该内存IC的容量是1KB
通常情况下，一个内存IC中会有很多个地址引脚。
内存的工作机制
以比较简单的一个内存IC举例，
2个电源：VCC、GND
RD和WR是控制信号的引脚
A0~A9是地址信号的引脚
D0~D7是数据信号的引脚 此为1KB的内存IC。
若要往该内存写入1字节的数据。
- 先可以给VCC接入+5V,给GND接入0V的电源
- 并使用A0~A9的地址信号来指定数据的存储场所
- 然后再将RD（read = 读出）信号设置成1即可
- 执行完这些操作，指定地址中存储的数据就会被输出到D0~D7的数据信号引脚中。
其中RD和WR这类可以让IC 运行的信号被称为控制信号。其中当WR 和RD同时为0时，写入和读出的操作都无法进行。
内存的逻辑模型是楼房
- 内存可以用类似于楼层的图形来表示。每层可以存储1个字节的数据
楼层好表示的就是地址。
对于一个1KB（1024B）大小的内存，则有1024个楼层。 - 对于程序员来说，内存模型中还包含着物理内存中不存在的概念——数据类型
- 在编程语言中的数据类型表示存储的是何种类型的数据
- 从内存来看，数据类型表示占用的内存大小（占有的楼层数）。
数据存储有两种方式：低字节序方式和高字节序方式。
低字节序（little endian）方式：将数据低位存储在内存低位地址。
高字节序方式：把数据的高位字节存储在内存高位地址。
简单的指针
指针也是一种变量，它所表示的不是数据的值，而是存储着数据的内存的地址。
通过使用指针，就可以对任一指定地址的数据进行读写。
windows上的程序是32位（4字节）的内存地址。这种情况下，指针变量的长度也是32位
指针变量类型的含义
在C语言中我们知道定义指针变量的时候是需要指定数据类型的。
这里的数据类型表示的是从指针存储的地址中一次能够读写的数据字节数
char *d;
short *e;
long *f;
/*
假设d、e、f的值都是100。
这种情况下，使用d时就能够从编号00的地址中读写1字节的数据，
使用e时就是2个字节（地址100和101）的数据，
使用f时就是4个字节（地址100~103）的数据。
数组是高效实用内存的基础
数组是指多个同样数据类型的数据在内存中连续排列的形式。
作为数组元素的各个数据会通过连续的编号被区分开来，这个编号称为索引。
指定索引后，就可以对该索引所对应地址的内存进行读写操作。
索引和内存地址的变换工作是由编译器自动实现的。
数组是内存的使用方法的基础，是因为数组和内存的物理构造是一样的。
特别是1字节类型的数组，他和内存的物理构造完全一致。
栈、队列以及环形缓冲区
栈和队列的特点和应用场景
栈和队列，都不需要指定地址和索引来对数组的元素就可以进行读写
这里所说的栈不是函数调用时使用的栈，这里的栈指的是LIFO形式的数据存储方式，该栈的实体是数组
一般的，需要临时保存计算过程中的数据、连接在计算机上的设备或者输入输出的数据时，都可以通过这些方法来使用内存。
- 当需要暂时舍弃当前的数据，随后在原貌还原时，会使用栈。
- 当我们需要处理通讯中返送的数据时，或有同时运行的多个程序所发送过来的数据时，会用到这种对队列中存储的不规则数据进行处理的方法。
栈和队列的区别
在于数据出入的顺序是不同的。 在对内存数据进行读写时，
- 栈用的是LIFO（Last in First out，后进先出）方式
- 队列用的是FIFO（First in First out，先进先出）方式
使用栈和队列的前提
前提是：在内存中必须预留出栈和队列所需要的空间，并确定好写入和读出的顺序，这样就可以不用再指定地址和索引了。
如果要在程序中使用栈和队列，就需要以适当的元素数来定义一个用来存储数据的数组，以及对该数组进行读写的函数对。
在这些函数的内部，对数组的读写会涉及索引的管理，但从使用函数的角度来说，就没有必要考虑数组及索引了。
一般这样的函数对，
栈：写入Push，读出Pop
队列：写入EnQueue，读出DeQueue
队列
队列这种先进先出的方式也成为了排队。
形象说明：
排队指的是买车票时在自动售票机前等候的队列等。排队时，站在最前面的乘客先买票，购买后率先从队列中走出来。
当随机前来的购票乘客数量和自动售票机的处理速度不相符时，排队起到很好的缓冲作用。
- 程序为了协调好数据输入和处理时机间的关系，采用类似于排队的机制。
- 在内存上，实现这种机制的方式就是队列。
队列的实现方式
队列一般是以环状缓冲区（ring buffer）的方式来实现的。
举例：6个元素的数组来实现一个队列。这是可以从数组的起始位置开始有序的存储数据，然后再按照存储时的顺序把数据对出。
在数据的末尾写入数据后，后一个数据就会被写入数组的起始位置（此时数据已经被读出所以该位置是空的）。
这样，数据的末尾就和开头连接起来了。
数据的写入和读出也就循环起来了。
链表使元素的追加和删除更容易
链表和二叉查找树，都是不用考虑索引顺序就可以对数组元素进行读写的方式。
- 通过链表，可以更加高效的对数组数据（元素）进行追加和删除处理。
- 通过使用二叉查找树，则可以更加高效地对数组数据进行检索
如何实现链表：
在数组的各个元素中，除了数据的值之外，通过为其附带上下一个元素的索引，即可实现链表。
数组的值和下一个元素的索引组合在一起，就构成了数组的一个元素。这样，数组元素项链就构成了链表
栈、堆、队列、链表都是数组的一种变形方法
回顾第1章中提到CPU四大构件之一控制器的作用：把内存上的指令、数据等读入寄存器，并根据指令的执行结果来控制整个计算机
