【华为OD机试真题】堆内存申请 · 堆内存最佳分配（C语言）

一、真题题目描述有一个总空间为100字节的堆现要从中申请一块内存内存分配原则为优先紧接着前一块已使用内存分配空间足够且最接近申请大小的空闲内存。输入描述第1行是1个整数表示期望申请的内存字节数。第2到第N行是用空格分割的两个整数表示当前已分配的内存的情况每一行表示一块已分配的连续内存空间每行的第1和第2个整数分别表示偏移地址和内存块大小如0 1 3 2表示0偏移地址开始的1个字节和3偏移地址开始的2个字节已被分配其余内存空闲。输出描述若申请成功输出申请到内存的偏移若申请失败输出-1。备注若输入信息不合法或无效则申请失败若没有足够的空间供分配则申请失败堆内存信息有区域重叠或有非法值等都是无效输入示例1输入1 0 1 3 2输出说明堆中已使用的两块内存是偏移从0开始的1字节和偏移从3开始的2字节空闲的两块内存是偏移从1开始2个字节和偏移从5开始95字节。根据分配原则新申请的内存应从1开始分配1个字节所以输出偏移为1。二、解题思路图解步骤 1数据结构设计由于 C 语言没有内置的动态列表我们需要定义一个结构体MemoryBlock并使用数组或动态分配的指针数组来存储已分配的块。考虑到机考题通常数据量不大一般 N≤1000 我们可以预设一个足够大的数组MAX_BLOCKS。typedef struct { int offset; int size; int end; // offset size } MemoryBlock;步骤 2数据读取与排序读取reqSize。循环读取offset和size直到文件结束EOF。排序使用qsort库函数按offset升序排列。这是检测重叠和计算空闲块的前提。步骤 3数据清洗与校验基础校验遍历数组检查offset 0、size 0或end 100。重叠检测遍历排序后的数组检查current.offset prev.end。注意[0, 1)和[1, 2)是紧邻但不重叠的判断条件必须是严格小于。步骤 4贪心匹配 (Best Fit)不需要额外分配内存存储空闲块采用一次扫描法维护currentPos当前扫描到的位置初始为0。维护bestOffset最佳起始位置和minDiff最小剩余空间差值初始化为-1和INT_MAX。遍历每个已分配块若block.offset currentPos发现空闲区间[currentPos, block.offset)。计算长度freeSize若满足条件则尝试更新最优解。更新currentPos block.end。尾部检查若currentPos 100检查最后一段空闲区。三、C语言实现代码#include stdio.h #include stdlib.h #include limits.h #include stdbool.h #define MAX_BLOCKS 1005 #define TOTAL_SIZE 100 // 定义内存块结构体 typedef struct { int offset; int size; int end; } MemoryBlock; // qsort 比较函数按 offset 升序排序 int compareBlocks(const void *a, const void *b) { const MemoryBlock *blockA (const MemoryBlock *)a; const MemoryBlock *blockB (const MemoryBlock *)b; return blockA-offset - blockB-offset; } int main() { int reqSize; // 1. 读取申请大小 if (scanf(%d, reqSize) ! 1) { printf(-1\n); return 0; } // 基本合法性检查 if (reqSize 0) { printf(-1\n); return 0; } MemoryBlock blocks[MAX_BLOCKS]; int count 0; int offset, size; // 2. 读取已分配内存块直到 EOF // scanf 返回成功匹配的项数若不为 2 则停止处理末尾换行或非法格式 while (scanf(%d %d, offset, size) 2) { if (count MAX_BLOCKS) { // 防止数组越界虽然题目通常不会给这么多 printf(-1\n); return 0; } blocks[count].offset offset; blocks[count].size size; blocks[count].end offset size; count; } // 如果没有已分配块count 为 0逻辑依然成立 // 3. 排序 qsort(blocks, count, sizeof(MemoryBlock), compareBlocks); // 4. 校验与重叠检测 for (int i 0; i count; i) { // 基础校验负数、零大小、越界 if (blocks[i].offset 0 || blocks[i].size 0 || blocks[i].end TOTAL_SIZE) { printf(-1\n); return 0; } // 重叠检测 if (i 0) { // 如果当前块的起点 前一块的终点则重叠 if (blocks[i].offset blocks[i-1].end) { printf(-1\n); return 0; } } } // 5. 贪心查找最佳适配 (Best Fit) int bestOffset -1; int minDiff INT_MAX; int currentPos 0; for (int i 0; i count; i) { // 检查当前块之前的空闲区域 if (blocks[i].offset currentPos) { int freeSize blocks[i].offset - currentPos; if (freeSize reqSize) { int diff freeSize - reqSize; // 寻找差值最小的最接近 // 若 diff 相等由于是从左向右遍历保留较小的 offset (即不更新) if (diff minDiff) { minDiff diff; bestOffset currentPos; } } } // 移动当前位置到当前块的结束处 currentPos blocks[i].end; } // 6. 检查尾部空闲区域 if (currentPos TOTAL_SIZE) { int freeSize TOTAL_SIZE - currentPos; if (freeSize reqSize) { int diff freeSize - reqSize; if (diff minDiff) { minDiff diff; bestOffset currentPos; } } } // 7. 输出结果 printf(%d\n, bestOffset); return 0; }C语言代码亮点底层控制直接使用struct和数组无额外封装开销内存占用极低。标准库排序利用qsort高效完成排序时间复杂度 O(Nlog⁡N) 。鲁棒的输入处理通过scanf返回值判断输入结束能够正确处理多行输入及末尾空白。极限值处理使用limits.h中的INT_MAX初始化最小差值确保逻辑严密。单次扫描在 O(N) 时间内完成所有空闲区的评估无需二次遍历或额外存储空间。四、核心逻辑推演以示例为例输入1 0 1 3 2执行流程解析reqSize 1。块1{0, 1, 1}块2{3, 2, 5}count 2。排序已有序。校验块10~1合法。块23~5合法。重叠3 1无重叠。扫描currentPos 0,minDiff INT_MAX,bestOffset -1。i0 (块1):offset(0) currentPos(0)无空闲。currentPos更新为1。i1 (块2):offset(3) currentPos(1)。空闲大小2。2 1差值1。1 INT_MAX更新minDiff1,bestOffset1。currentPos更新为5。尾部:currentPos(5) 100。空闲大小95。95 1差值94。94 1不更新。输出1。五、易错点总结⚠️scanf 的返回值很多初学者忽略scanf的返回值。在循环读取不定行数时必须检查 2否则可能陷入死循环或读取错误数据。数组越界C语言不会自动检查数组边界。必须定义足够大的MAX_BLOCKS并在写入前检查count防止 Segmentation Fault。重叠判断符号再次强调[0, 1)和[1, 2)是合法的。判断重叠必须用。若误用会导致相邻块被误判。整数溢出虽然本题数值很小100但在通用内存分配场景中offset size可能会溢出int范围。在实际工程中建议使用long long或进行溢出检查。未初始化变量minDiff必须初始化为最大值bestOffset初始化为-1否则在没有任何合适空闲块时会输出垃圾值。六、复杂度分析时间复杂度排序 O(Nlog⁡N) 。线性扫描 O(N) 。总计 O(Nlog⁡N) 。C语言的常数因子极小执行速度极快。空间复杂度O(N) 用于存储结构体数组。辅助变量 O(1) 。七、结语这道题是考察贪心算法、区间处理以及C语言基本功的绝佳素材。通过手动管理结构体数组、使用qsort以及精细的指针/索引操作我们不仅解决了算法问题更重温了C语言作为“系统编程语言”的魅力。掌握这种“排序 - 扫描 - 贪心”的三段式解法配合C语言的高效执行你将能轻松应对各类资源分配、区间覆盖类的机考题目。祝各位Coder代码无BugOffer 滚滚来