什么是顺序表？顺序表是物理结构连续的线性表，它并不要求该线性表在逻辑上也连续。其中物理结构连续，代表着，一个顺序表中的元素按照先后次序紧密地排列在存储空间中，即可认为该顺序表占用了一大段的连续存储空间。
因为顺序表需要占用一整块连续的存储空间。如果多个不同大小的顺序表按左右顺序排列，释放掉中间的任意一个顺序表，并且它的左右相邻顺序表始终驻留。那么，所释放的那个顺序表所占的存储空间就会如一道缝隙留在原地。此时该缝隙最大只能存储缝隙大小的内容。若以小于这道缝隙大小的内容填充在这里，自然会形成一道更小的缝隙。而这种更小的缝隙是可以在程序运行时逐渐积累数量的，如果一个程序长时间运行，并且以一定频率产生这种缝隙，久而久之，这类缝隙越来越多，且所有缝隙无法被使用。这就是所谓的碎片。
20190531更新:
在阅读数据结构一书时，在<动态存储管理>章节中<可利用空间表及分配方法>小节中有三种分配策略，分别是首次拟合法、最佳拟合法和最差拟合法。其中最佳拟合法定义为：将可利用空间表中一个不小于n且最接近n的空闲块的一部分分配给用户。因为根据改分配原则进行分配时，总是找大小最接近请求的内存块，因此系统中可能产生一些存储量甚小而无法利用的小片内存。而与顺序表相似的是首次拟合法。首次拟合法的分配是随机的，介于最佳拟合法和最差拟合法之间。
网友评论