数据的存储结构是数据结构的一个重要内容。在计算机中，数据的存储结构可以采取如下四中方法来表现。

1）          顺序存储方式

简单的说，顺序存储方式就是在一块连续的存储区域

一个接着一个的存放数据。顺序存储方式把逻辑上相连的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接挂安息来体现。顺序存储方式也称为顺序存储结构（sequentialstorage structure），一般采用数组或者结构数组来描述。

              线性存储方式主要用于线性逻辑结构的数据存放，而对于图和树等非线性逻辑结构则不适用。

2）          链接存储方式

链接存储方式比较灵活，其不要求逻辑上相邻的结点

在物理位置上相邻，结点间的逻辑关系由附加的引用字段表示。一个结点的引用字段往往指导下一个结点的存放位置。

              链接存储方式也称为链接式存储结构（LinkedStorage Structure），一般在原数据项中增加应用类型来表示结点之间的位置关系。

3）          索引存储方式

索引存储方式是采用附加索引表的方式来存储结点信

息的一种存储方式。索引表由若干个索引项组成。索引存储方式中索引项的一般形式为：（关键字、地址）。其中，关键字是能够唯一标识一个结点的数据项。

              索引存储方式还可以细分为如下两类：

              *稠密索引（Dense Index）:这种方式中每个结点在索引表中都有一个索引项。其中，索引项的地址指示结点所在的的存储位置；

              *稀疏索引（Spare Index）：这种方式中一组结点在索引表中只对应一个索引项。其中，索引项的地址指示一组结点的起始存储位置。

4）          散列存储方式

散列存储方式是根据结点的关键字直接计算出该结点

的存储地址的一种存储的方式。

              在实际应用中，往往需要根据具体数据结构来决定采用哪一种存储方式。同一逻辑结构采用不同额存储方法，可以得到不同的存储结构。而且这四种节本存储方存储器是计算机结构中必不可少的一部分，每个用户程序都需要向操作系统申请存储资源，那么操作系统在存储管理发挥怎样的作用呢？

主要有一下三点：

1、为用户使用存储空间提供方便。用户只需要在自己的逻辑空间内编程，用户只需要跟操作系统说我要用这么大的内存空间，你分给我。至于我分到哪里（具体在内存中的物理地址），别人分到哪里，我不用管。

2、充分发挥内存的利用率。 操作系统的作用是让尽可能多的用户程序调入内存、尽量快地分配到内存并运行。

3、内存保护。 操作系统必须有一个机制，记录哪些空间用了，哪些空间没有用。必须保护内存不被非法访问。分给用户的空间不会被其他用户（包括系统自己）非法访问。

内存分配

连续分配至为一个用户程序分配一个或多个连续内存空间。

主要的分配方式有下面几种：

单一连续分配

这种分配方式的运用场景是：一个用户独占连续的内存用户去，只能用于单用户、单任务的操作系统中。

这时的内存区包含系统区和用户区，可以要求对系统区进行保护（给一个基址，只能使用基址后面的内存空间，0到基址范围都归系统），也可不对系统进行保护。

固定分区分配

固定分区的意思是将一整个大的内存区域分成多块，每块只能给一个用户程序。使用场景适合多用户、多任务的环境。

分区方法大小划分包括：

分区大小一定：

虽然这种分配方法简单，但是有可能会出现大程序装不下，小程序浪费的尴尬场面。

分区大小不等：

根据用户程序所申请内存空间大小的分布，可以将内存区分成多个较小的分区，适量的中等分区，少量的大分区。

虽然这种方法较好处理了分区大小相等的尴尬场景。但是这种方法有一个问题就是不知道分区的大小如何设置比较好，每个大小分区的比例是多少也不清楚。可能会导致特别大的程序可能还是装不进内存区。

固定分区的分配有两种算法：

1、首次适应算法（FF）:按序选择第一个满足要求的内存区。

2、最佳适应算法（BF）:找一个与程序大小最匹配的空闲分区分配给用户。这样做的好处可以提供内存空间的利用率，不会出现小程序占有大空间的情况，比较好。

动态分区分配

那就把分区的大小不固定吧，于是就来个动态分区分配。

操作系统根据用户程序的大小，动态地分配连续的内存空间，当没有用户程序运行时，内存只有一个连续分区。当用户程序要求分配内存时，依次分配与用户程序大小相等的内存，剩下的是空闲区。当用户程序执行完成，回收内存，留给其他用户程序使用。

要实现动态分区分配，必须考虑一下三个问题：

1、我用什么数据结构来记录空闲区的地址与大小；

数组、链表、红黑树都可以。

2、怎么分给用户程序；

（1）首次适应算法（FF）：从空闲分区表首开始查找，找到第一个合适的分区即分配。

该算法倾向于使用内存中低地址的空闲分区，保留了高地址部分的空间，为以后分配大的内存空间创造了条件。但是低地址部分的内存空间不断被切割，留下许多小碎片（比较小的空闲区），提高了分配时查找空闲分区的开销。

（2）循环首次适应算法：它跟首次适应算法的区别在于它不是从表首开始查找，而是从上次找到的空闲分区开始查找，直到找到一个能满足需求的空闲分区。这样做使得空闲分区的分布比较均匀，但是缺乏大的空闲分区。

（3）最佳适应算法：该算法寻找最合适的分区给用户程序。为了快速查找，一般会使用红黑树来按分区大小排序。这种算法空间利用率比较高，但同样会产生小碎片，而且每次分配必须重新排序，带来一定的开销。

（4）最差适应算法：与最佳适应算法相反，最差适应算法将最大的空闲分区分配给用户程序，这样会产生比较少的小碎片，但是大的空闲分区就被破坏了，维护顺序也带来开销。

3、用户程序使用完后，怎么回收。

其实回收也挺简单，主要参照下面的策略：

如果回收区前面的分区空闲，就合并这两个分区，大小改成它们的大小之和；

如果回收区后面的分区空闲，同样合并这两个分区，大小为它们之和，将起始地址改成回收区的地址。

如果回收区前后的分区都空闲，那么将他们合并成一块，总的块数减一，大小为三者之和。

如果不是上面的情况，就新建一个表项，在合适的位置插入到空闲分区（链）表。

动态重定位分区分配

该分配算法基本上与动态分区分配算法相同，差别在于动态重定位分区分配多了一个紧凑的功能。

紧凑：对内存中正在使用的分区进行搬迁，使得多个小的空闲分区（小碎片）合并为一个大的空闲分区。

要实现紧凑功能，由于分给用户程序的物理地址已经被修改，所以需要一个重定位寄存器，来保存进程的首地址。那么用户程序在访问内存空间的时候，用的是相对地址，这时硬件会将相对地址加上重定位寄存器的值变成实际的物理地址