内存碎片与空闲链表的基本概念
内存碎片分为内部碎片和外部碎片两种类型，内部碎片是指已经分配给进程但未被使用的内存空间，外部碎片是指内存中零散的、无法被分配给新请求的小空闲块。空闲链表是管理内存空闲块的常见结构，它将所有空闲的内存块通过指针链接起来，方便内存分配和回收时快速查找可用空间。
空闲链表遍历算法的核心思路
要通过空闲链表统计内存碎片，核心逻辑是遍历整个空闲链表，记录每个空闲块的大小，再结合总空闲内存和最大连续空闲块的大小计算碎片率。具体步骤如下：
- 定义空闲块的结构体，包含块大小和指向下一个空闲块的指针
- 初始化空闲链表，模拟内存分配回收后的空闲块分布
- 遍历空闲链表，统计总空闲内存大小、空闲块数量、最大连续空闲块大小
- 根据统计结果计算外部碎片率，公式为：(1 - 最大连续空闲块大小 / 总空闲内存大小) * 100%
C++实现源码
下面是完整的C++实现代码，包含空闲块结构体定义、链表初始化、遍历统计和结果输出逻辑：
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
// 空闲块结构体定义
struct FreeBlock {
size_t size; // 空闲块大小，单位字节
FreeBlock* next; // 指向下一个空闲块
FreeBlock(size_t s) : size(s), next(nullptr) {}
};
// 初始化空闲链表，模拟随机分布的空闲块
FreeBlock* init_free_list(int block_count, size_t max_block_size) {
if (block_count <= 0) return nullptr;
srand(time(nullptr));
FreeBlock* head = new FreeBlock(rand() % max_block_size + 1);
FreeBlock* curr = head;
for (int i = 1; i < block_count; ++i) {
curr->next = new FreeBlock(rand() % max_block_size + 1);
curr = curr->next;
}
return head;
}
// 遍历空闲链表统计内存碎片相关信息
void traverse_free_list(FreeBlock* head, size_t& total_free, int& block_count, size_t& max_block) {
total_free = 0;
block_count = 0;
max_block = 0;
FreeBlock* curr = head;
while (curr != nullptr) {
total_free += curr->size;
block_count++;
if (curr->size > max_block) {
max_block = curr->size;
}
curr = curr->next;
}
}
// 计算外部碎片率
double calc_fragment_rate(size_t total_free, size_t max_block) {
if (total_free == 0) return 0.0;
return (1.0 - (double)max_block / total_free) * 100.0;
}
// 释放空闲链表内存，避免内存泄漏
void free_free_list(FreeBlock* head) {
FreeBlock* curr = head;
while (curr != nullptr) {
FreeBlock* next = curr->next;
delete curr;
curr = next;
}
}
int main() {
// 模拟生成10个空闲块，单个块最大大小为1024字节
int block_num = 10;
size_t max_size = 1024;
FreeBlock* free_list = init_free_list(block_num, max_size);
size_t total_free_mem = 0;
int free_block_cnt = 0;
size_t largest_block = 0;
// 遍历统计
traverse_free_list(free_list, total_free_mem, free_block_cnt, largest_block);
// 输出统计结果
std::cout << "空闲链表遍历统计结果：" << std::endl;
std::cout << "总空闲内存大小：" << total_free_mem << " 字节" << std::endl;
std::cout << "空闲块数量：" << free_block_cnt << std::endl;
std::cout << "最大连续空闲块大小：" << largest_block << " 字节" << std::endl;
double fragment_rate = calc_fragment_rate(total_free_mem, largest_block);
std::cout << "外部内存碎片率：" << fragment_rate << "%" << std::endl;
// 释放内存
free_free_list(free_list);
return 0;
}
代码说明与扩展
上述代码中，FreeBlock结构体模拟了空闲块的基本结构，init_free_list函数通过随机数模拟了实际场景中零散分布的空闲块。遍历函数traverse_free_list会遍历整个链表收集统计需要的三个核心指标，最后通过公式计算得到碎片率。
如果需要更贴近实际场景，可以在结构体中增加空闲块的起始地址字段，遍历时还可以统计碎片块的分布情况，或者在内存分配回收时动态更新空闲链表，实现实时的碎片监测功能。