详解计算机内存及基于内存理解的几种数据结构
详解计算机内存及基于内存理解的⼏种数据结构
详解计算机内存
前⾔
计算机是进⾏数据处理的设备，⽽程序表⽰的就是处理顺序和数据结构。。由于处理对象数据是存储在内存和磁盘上的，因此程序必须能⾃由地使⽤内存和磁盘。本⽂详解内存的物理结构，逻辑结构以及利⽤内存构建各种各样数据结构的应⽤。
⼀、内存的物理结构
内存实际上是⼀种名为内存IC的电⼦元件。内存 IC 中有电源、地址信号、数据信号、控制信号等⽤于 输⼊输出的⼤量引脚（IC的引脚），通过为其指定地址（address），来进⾏数据的读写。内存 IC 的引脚配置如下图
将电源连接到VCC和GND后， 就可以给其他引脚传递⽐如0或者1这样的信号。⼤多数情况下，+ 5V 的直流电压表⽰1，0V表⽰0。
公顷与亩的换算那么上图内存IC可以存储多少数据呢？⼀个内存IC能够存储多少数据要看地址信号的个数，因为数据在计算机中存储，每个数据必须对应⼀个地址，这样这个数据才是有意义的数据。也就是说这个内存IC有多少地址就可以存储多少数据。上⾯的内存IC有A0～A9 共⼗个地址信 号引脚，表⽰可以指定 0000000000～1111111111 共 1024个地址，因此上⾯的内存IC可以存储1024个数据。
那么⼀个数据是多⼤呢？它是由数据信号引脚所确定的，上图内存IC中有D0～D7 共⼋个数据信号引脚，表⽰⼀次可以输⼊输出8位（= 1字节）的数据。因此，该内存IC⼀共可以存储1024个1字节的数据。因为1024 = 1K（计算机领域K代表2的10次幂），所以该内存IC的容量就是1KB。
但现在⼤家使⽤的计算机⾄少有512M的内存，也就是512000个1KB⼤⼩的内存IC，当然，⼀台计算机中不太 可能放⼊如此多的内存IC。通常情况下，计算机使⽤的内存IC中会有 更多的地址信号引脚，这样就能在⼀个内存IC中存储数⼗兆字节的数据。因此，只⽤数个内存IC，就可以达到512MB的容量。
内存IC写⼊数据的过程是，⾸先接通电源(+5V或0V)指定数据，然后地址信号指定存储场所，再把数据的值输⼊给数据信号存储在指定位置。读取数据时，只需通过A0～A9的地址信号指定数据的存储场所，指定地址中存储的数据就会被输出到 D0～D7 的数据信号引脚 。控制信号是⽤以控制⽬前是读操作还是写操作。当写⼊数据时WD设为1，读取数据时RD设为1。
总体来讲，内存IC内部有⼤量可以存储8位数据的地⽅，通过地址指定这些场所， 之后即可进⾏数据的读写。
⼆、内存的逻辑模型
一年级新生家长会发言稿虽然内存的实体是内存IC，不过从程序员的⾓度来看，也可以把 它假想成每层都存储着数据的楼房，并不需要过多地关注内存IC的电源和控制信号等。如内存为1KB 时，表⽰的是下图所⽰的有1024 层的楼房（这⾥地址的值是从上往下逐渐变⼤，不过也有与此相反的情况）。
不过，程序员眼⾥的内存模型中，还包含着物理内存中不存在的概念，那就是数据类型。编程语⾔中的数据类型表⽰存储的是何种类型的数据，它从内存来看，就是占⽤的内存⼤⼩（占有的楼层数）的意思。⽐如C语⾔中数据类型char代表占⽤⼀字节内存⼤⼩，short 代表占⽤2字节内存⼤⼩，long代表占⽤4字节内存⼤⼩。因此不同的数据类型虽然存放同样的数据，但是他们占⽤内存的⼤⼩是不⼀样的。审计学专业就业前景
仔细思考⼀下就会发现，根据程序中所指定的变量的数据类型的 不同，读写的物理内存⼤⼩也会随之
发⽣变化，这其实是⾮常⽅便的。 ⼤家不妨想⼀想，假如程序中只能逐个字节地对内存进⾏读写，那该 多么不便啊。在处理超过1个字节的数据时，还必须要编写分割处理 程序。此外，在不同的编程语⾔中，变量可以指定的数据类型的最⼤ 长度也不相同。C语⾔中，8字节（= 64位）的double 类型是最⼤的。
昼的部首三、理解指针变量
有了上⾯内存的理解，我想指针就⾮常容易理解了。因为数据都是存放在计算机相应的地址中，那么，如果有⼀种变量专门⽤来存储地址，是不是就可以通过这个地址⾃由的读写这个地址中的数据了呢？这个变量就是指针变量。指针也是⼀种变量，它所表⽰的不是数据的值，⽽是存储着数据的内存的地址。通过使⽤指针，就可以对任意指定地址的数据进⾏读写。如下代码⽰例了⼏种数据类型指针的定义：
上⾯代码中，我们知道d,e,f分别是⽤来存储内存地址的变量，那么为什么还需要char，short，long这些数据类型呢？实际上，这些数据类型表⽰的是从指针存储的地址中⼀次能够读写的数据字节数。⽐如d⼀次能够从地址开始位置读取1个字节的数据，⽽short可以读取2个字节的数据，long可以读取4个字节的数据。
四、数组是⾼效使⽤内存的基础
数组是指多个同样数据类型的数据在内存中连续排列的形式。作为数组元素的各个数据会通过连续的编号被区分开来，这个编号称为索引（index）。指定索引后，就可以对该索引所对应地址的内存进⾏读写操作。⽽索引和内存地址的变换⼯作则是由编译器⾃动实现的。
之所以说数组是内存的使⽤⽅法的基础，是因为数组和内存的物理构造是⼀样的。特别是1字节类型的数组，它和内存的物理构造完全⼀致。
五、栈、队列以及环形缓冲区
虽然是通过指定索引来使⽤数组，但这和内存的物理读 写并没有特别⼤的区别。有没有更⼈性化的⽅法来操作计算机的物理内存呢？
不灭之王波罗丁称号怎么做
其中，栈和队列，都可以不通过指定地址和索引来对数组的元素进⾏读写。那么，栈和队列是如何实现不⽤指定地址和索引呢？其实很简单，如果我们在内存中预留出栈和队列所需要的空间，并确定好写⼊和读出的顺序， 就不⽤再指定地址和索引了。
那么，栈的写⼊和读出顺序按照“后进先出”的⽅式（LIFO，Last Input First Out）；⽽相对应队列的写⼊和读出顺序按照“先进先出”的⽅式（FIFO,First Input First Out）。同时，如果要在程序中实现栈和队列，就需要以适当的元素数来定义⼀ 个⽤来存储数据的数组，以及对该数组进⾏读写的函数对（栈的函数对是Push和Pop；队列的函数对是EnQueue和DeQueue）。总之，这些数据结构都是为了更⽅便的使⽤内存。通过使⽤这些函数，可以很⽅便的将数据临时保存（写⼊）， 然后再在需要时候把这些数据读出来。
为了充分利⽤内存空间，队列⼀般是以环状缓冲区（ring buffer）的⽅式来实现的。让出队数据的位置可以循环给其它要⼊队的数据使⽤。
六、链表使元素的追加和删除更容易
不知道⼤家有没有发现，队列和栈这种数据结构有⼀个很⼤的缺陷，那就是对于数据的读写必须按照顺序进⾏读写。如果想要在数据中间硬夹⼀个数据，或者从中间删除⼀个数据，这都需要耗费极⼤的动作去移动整个数据结构。那么有没有⼀种更⾼效且⽅便的数据结构可以不⽤考虑索引的顺序就可以对数组元素进⾏读写操作呢？这个时候链表就出现了。
在数组的各个元素中，除了数据的值之外，通过为其附带下⼀ 个元素的索引，即可实现链表。数据的值和下⼀个元素的索引组合在⼀起，就构成了数组的⼀个元素。由于链表末尾的元素没有后续的数据，因此就需要⽤别的 值（在这⾥是－1）来填充。
宜城大虾
在需要追加或删除数据的情况下，使⽤链表是很⾼效的。只需要将数据删除或者追加，然后修改上⼀个元素中的下⼀个元素索引即可。
如果不使⽤链表数组，那么中途删除或追加元素时，其后的元素就必须要全部移动。
七、⼆叉查树使数据搜索更有效
⼆叉查树是指在链表的基础上往数组中追加元素时，考虑到数据的⼤⼩关系，将其分成左右两个⽅向的表现形式。例如，假设我们事先把50这个值保存到了数组中。那么，如果接下来的值⽐先前保存 的数值⼤的话，就要将其放到右边，反之如果⼩的话就放在左边。
那么如何实现⼆叉查树呢？其实数组的每个元素 中只要有数据的值和两个索引信息（左右值的索引信息）就可以了。如下图实现上图⼆叉查树的逻辑
使⽤⼆叉查树的便利之处在于可以使数据的搜索等更有效率。 在使⽤⼀般的数组时，必须从数组的开头按照索引顺序来查⽬标数据。⽽使⽤⼆叉查树时，当⽬标数据⽐现在读出来的数据⼩时就可 以转到左侧，反之⽬标数据较⼤时即可转到链表的右侧，这样就加快 了到⽬标数据的速度。
总结
其实上⾯⽆论是栈，队列，链表还是⼆叉查树他们都是数组的改造，⽽数据是使⽤内存的基础，因为数组的结构和内存的物理结构是“⼀样”的。因此，各种数据结构都是为了更好的使⽤物理内存，同时根据各种需求对内存的改造⽽且，⽽在程序中对内存操作的基础就是数组。
参考：[图灵程序设计丛书].程序是怎样跑起来的

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。