前阵子有位读者私信我问一道某高校2021年春操作系统课的期末模拟题——空闲空间合并。我一看这题目典型的结构体二级排序题背后对应的是操作系统里一个非常实在的场景内存碎片整理和空闲块合并。这种题在考试里出现频率不低表面上是考排序实际上考的是你对“先排序、再线性扫描合并”这种经典思路的掌握程度以及 C 语言结构体排序的基本功。我当时为了帮这位读者把这道题讲透把完整代码写了一遍还顺手整理了排序比较函数、合并边界条件这些考点。这篇文章就是把我自己解题的过程和踩过的坑完整复盘一遍给正在准备操作系统考试、或者想巩固 C 语言结构体排序的同学做一个参考。如果你是刚接触结构体二级排序的新手或者对“空闲空间合并”这个场景不太熟悉这篇文章能帮你把这块知识补齐。1. 题目在考什么从一道模拟题看空闲空间管理1.1 这道题的背景操作系统里的空闲空间问题在操作系统课程里内存管理这部分一定会讲到动态分区分配。系统维护一个空闲分区表记录当前可用的内存块每个块包括起始地址和大小。当进程释放内存时系统需要把释放出来的空间重新加入空闲区并且把相邻的空闲块合并成更大的块。这个“合并”操作直接决定了后续分配时能否找到足够大的连续空间。题目把它抽象成了一个典型的数组处理问题给定一组空闲区间每个区间有起始地址和长度有些区间是相邻的或者重叠的需要把它们合并成一组不重叠、不相邻的区间。这里有三个细节是这道题的灵魂输入的顺序是不保证的可能乱序给出区间可能首尾相接比如[100, 200)和[200, 300)这两个应该合并成一个[100, 300)区间也可能完全重叠比如[100, 200)和[150, 180)后者应该被吞并掉。如果不做排序直接对着原始顺序去合并就会出现严重漏合并的情况。比如两个应该合在一起的区间在输入里隔了十万八千里你扫一遍根本发现不了它们相邻。1.2 需求拆解从题目描述到可执行逻辑把题目翻译成程序员能直接动手的语言核心就是三步读入 n 个空闲区间每个区间用“起始地址 addr 空间大小 len”表示把所有区间按照起始地址从小到大排序如果起始地址相同再按照长度排序——这就是标题里说的“结构体二级排序”线性扫描排序后的数组把重叠或相邻的区间合并输出合并后的区间列表。这里最容易被忽视的一个点是区间不是用“结束地址”给的而是用“起始地址 长度”表示的。所以判断两个区间是否可以合并不能只看地址要算结束地址。比如第一个区间是[a, alen1)第二个是[b, blen2)能合并的条件是b a len1。注意这里要分“重叠”和“相邻”两种情况区间重叠a b a len1 b也就是第二个的起点落在第一个区间内区间相邻a len1 b也就是第一个区间的结束地址正好是第二个区间的起点。这两种情况在实际题目里都要合并。有些同学只处理了重叠没处理相邻结果考试一跑样例就挂很可惜。1.3 为什么排序是合并的前提我见过不少第一次做这类题的同学他们的第一反应是“我直接遍历遇到重叠就合并不就行了”——听起来好像有道理但实际上问题很大。举个最直观的例子输入三个区间顺序是[300, 100)、[100, 100)、[200, 100)。如果你按照输入顺序就开始合并扫到[300, 100)时不知道前面发生了什么扫到[200, 100)时发现它和[300, 100)能合并合完得到[200, 200)然后回头再看[100, 100)发现它和[200, 200)也能合并最后得到[100, 300)。看着结果对了但这个过程非常脆弱——一旦区间数量增多、交叉关系变复杂这种“无秩序地合并”会导致你必须反复回退扫描代码写着写着就变成一团乱麻。而先排序的优雅之处在于排序之后所有区间的起点从左到右依次排列你只需要一次顺序扫描用当前区间的结束地址去“够”后面的区间能够到就合并够不到就说明后面的区间都不可能与当前区间相邻了因为起点已经更大了。这个逻辑是确定性的、线性的时间复杂度为 O(n log n)排序 O(n)合并既好写又高效。2. 结构体二级排序核心考点与实现细节2.1 结构体定义字段选型要提前想清楚既然题目涉及“结构体二级排序”第一个绕不开的问题就是结构体怎么定义。空闲空间块最自然的描述就是一个结构体包含两个字段起始地址和空间长度。typedef struct Block { int addr; // 起始地址 int len; // 空间长度 } Block;你可能觉得 int 就够了但这里我要提醒一句看题目的数据范围决定到底用 int 还是 long long。有些模拟题数据比较温柔地址和长度都在 int 范围内但如果题目要求模拟真实的系统内存空间或者合并后的总长度可能非常大还是用long long更稳妥。我自己写的时候的习惯是不差那点空间直接用long long或者干脆在结构体里加一个end字段存结束地址避免边合并边计算addr len。有同学会问为什么要多存一个 end不觉得冗余吗确实冗余但实际写代码时很划算。因为合并过程中你要反复比较“当前区间的结束地址”和“下一个区间的起始地址”如果每次比较都现场算一次addr len代码里到处都是这个加法表达式可读性差还容易忘记处理长度为零之类的边界。另一个比较稳妥的写法是结构体里只保留 addr 和 len但在读入之后立刻计算出 end。这个end字段可以直接参与比较和合并输出时再用end - addr恢复长度。我个人推荐用这种“存安数据”的方式考试不容易出低级错误。2.2 二级排序的含义第一关键字、第二关键字所谓“二级排序”就是排序时同时考虑两个字段的优先级而不是只按一个字段排。在这道题里一级排序的键是起始地址 addr二级排序的键是长度 len。为什么要二级排序这是我一开始没想明白的地方。后来做了几道类似的题才意识到二级排序在这道题里其实不是必须的——因为合并时我们会线性扫描遇到可合并的区间直接处理地址相同的区间无论谁在前合并结果都是一样的。但题目明确要求“二级排序”就是希望你把比较函数写成两层判断先比较 addraddr 不同就按 addr 的大小返回addr 相同再比较 len。这其实是一个通用技能。比如后面你遇到“按分数排名分数相同按学号排名”的需求或者“按日期排序日期相同按时间排序”的需求本质都是这个二级排序模式。2.3 qsort 比较函数的规范写法与隐藏陷阱C 语言里最常用的排序函数就是qsort它要求你提供比较函数。这里我用的是 qsort因为它不需要额外引入别的库考试环境下最稳。比较函数的签名是固定的int cmp(const void *a, const void *b) { Block *pa (Block *)a; Block *pb (Block *)b; if (pa-addr ! pb-addr) return pa-addr - pb-addr; return pa-len - pb-len; }这里有一个非常经典的坑return pa-addr - pb-addr在地址差值很大的时候可能溢出特别是如果你把 int 的极端值拿来相减结果可能变成正负反转排序直接乱掉。所以我建议在比较函数里写成显式的分支int cmp(const void *a, const void *b) { Block *pa (Block *)a; Block *pb (Block *)b; if (pa-addr pb-addr) return -1; if (pa-addr pb-addr) return 1; if (pa-len pb-len) return -1; if (pa-len pb-len) return 1; return 0; }这写法看起来啰嗦但绝对安全而且思维负担小比较两个元素时直接按照第一关键字、第二关键字的顺序做“小于返回 -1大于返回 1相等返回 0”的判断。考试的时候手写这么一段基本不会因为溢出丢分。2.4 排序稳定性qsort 到底稳不稳定很多同学在学排序时背过一个结论稳定的排序有冒泡、插入、归并等不稳定的有快排、堆排、希尔排序。而qsort底层通常实现为快速排序所以它是不稳定的也就是说两个关键字段完全相同的结构体排完后相对顺序可能变化。那是不是意味着考试时不能依赖稳定性其实在这道题里你完全不需要稳定性。因为我们的合并逻辑只关心区间最终合并后的结果不关心两个完全相同的区间谁先谁后。这就引出一个重要的细节二级排序在乎的是“逻辑上的有序”而不是“物理上的稳定”。如果题目要求你输出原始顺序中某种特定的次序比如按 id你才需要考虑稳定排序或者记录原始下标。空闲空间合并这道题没有这个要求所以你可以放心地使用 qsort。3. 完整代码实现与逐步讲解3.1 从输入到结构体数组的初始化拿到题目后第一步是读入数据并构建结构体数组。这里的输入格式可能是两列每行一个区间的起始地址和长度。也可能是先给一个总数 n再给 n 行区间。我按最常见的格式来写#include stdio.h #include stdlib.h typedef struct Block { long long addr; long long len; long long end; } Block; int cmp(const void *a, const void *b) { const Block *pa (const Block *)a; const Block *pb (const Block *)b; if (pa-addr pb-addr) return -1; if (pa-addr pb-addr) return 1; if (pa-len pb-len) return -1; if (pa-len pb-len) return 1; return 0; } int main() { int n; scanf(%d, n); Block *blocks (Block *)malloc(sizeof(Block) * n); for (int i 0; i n; i) { scanf(%lld %lld, blocks[i].addr, blocks[i].len); blocks[i].end blocks[i].addr blocks[i].len; } // 后面继续... }有些第一次写这个题的同学会忘记给 end 赋值后面合并时直接用初始值 0结果合并逻辑全乱。这里我特别把 end 字段的初始化放在输入阶段就是为了避免这种问题。3.2 比较函数写法的三个方案对比qsort 的比较函数写法可以有很多变体考试时不需要纠结哪种“最优”用最不容易出错的就行。我做了一个对比方便你自己选写法代码特点风险等级适用场景直接返回差值return pa-addr - pb-addr;高可能溢出地址范围很小时可以用强制转 long longreturn (pa-addr - pb-addr) 0 ? 1 : -1;中逻辑判断繁琐数据范围较大但不放心显式分支显式分支逐字段比较先比 addr再比 len分别返回 -1/0/1低零溢出风险考试、工程实现都推荐我强烈推荐第三种。虽然代码行数多一点但没有任何边界风险。而且这种写法在将来做其他“多关键字排序”的时候可以直接复用比如对成绩表先按总分排再按数学分排再按学号排——只需要在后面再加几段判断即可。3.3 合并的核心一次扫描维护当前合并区间排序完成之后就是这道题的精华步骤——线性合并。我用一个非常直白的策略维护一个“当前累积区间”从第一个区间开始不断尝试把后续区间吞进来。如果吞得进就更新当前区间的结束地址如果吞不进就把当前累积区间输出或放入结果数组然后开启一个新的累积区间。qsort(blocks, n, sizeof(Block), cmp); long long cur_addr blocks[0].addr; long long cur_end blocks[0].end; for (int i 1; i n; i) { if (blocks[i].addr cur_end) { // 可以合并重叠或相邻 if (blocks[i].end cur_end) { cur_end blocks[i].end; } } else { // 不能合并先把前面的区间输出再重新开始 printf([%lld, %lld) length%lld\n, cur_addr, cur_end, cur_end - cur_addr); cur_addr blocks[i].addr; cur_end blocks[i].end; } } // 最后一个区间也要输出 printf([%lld, %lld) length%lld\n, cur_addr, cur_end, cur_end - cur_addr);这段代码的最核心判断就是if (blocks[i].addr cur_end)。注意这里的它同时处理了“部分重叠”“完全包含”“恰好相邻”三种情况非常简洁。我之前写过blocks[i].addr cur_end结果相邻区间的用例挂了因为[100, 200)和[200, 300)这种恰好相接的情况addr cur_end必须用才能合并。在合并时只更新cur_end不需要理会cur_addr因为当前累积区间的起点肯定保持不变。只有当无法合并、开启新区间时才更新cur_addr。这个逻辑也对应了生活中的一个常识一条绳子被你从左边拉过来右边够得着就继续拉长够不着了才从新的一截开始拉。3.4 完整代码可以直接跑起来的版本把上面的片段拼到一起写一个完整的、可直接编译运行的版本#include stdio.h #include stdlib.h typedef struct Block { long long addr; long long len; long long end; } Block; int cmp(const void *a, const void *b) { const Block *pa (const Block *)a; const Block *pb (const Block *)b; if (pa-addr pb-addr) return -1; if (pa-addr pb-addr) return 1; if (pa-len pb-len) return -1; if (pa-len pb-len) return 1; return 0; } int main() { int n; scanf(%d, n); Block *blocks (Block *)malloc(sizeof(Block) * n); for (int i 0; i n; i) { scanf(%lld %lld, blocks[i].addr, blocks[i].len); blocks[i].end blocks[i].addr blocks[i].len; } qsort(blocks, n, sizeof(Block), cmp); long long cur_addr blocks[0].addr; long long cur_end blocks[0].end; for (int i 1; i n; i) { if (blocks[i].addr cur_end) { if (blocks[i].end cur_end) { cur_end blocks[i].end; } } else { printf([%lld, %lld) length%lld\n, cur_addr, cur_end, cur_end - cur_addr); cur_addr blocks[i].addr; cur_end blocks[i].end; } } printf([%lld, %lld) length%lld\n, cur_addr, cur_end, cur_end - cur_addr); free(blocks); return 0; }注意我输出区间用的是左闭右开[addr, end)的表述。这是操作系统课程里描述内存区间时非常标准的写法因为这样描述区间长度直接等于end - addr不需要额外加一减一能少很多边界错误。如果你比较习惯闭区间也可以输出[addr, end-1]但要小心处理长度为 1 的区间容易写成end-1恰好等于 addr 但长度算错的情况。我的经验是能用左闭右开就别用闭区间。3.5 输出格式的常见要求有些题目对输出格式有更严格的要求比如要求按“起始地址 长度”两列输出或者要求输出合并后的块数和总长度。你可以根据题目调整输出部分。如果需要统计合并后的块数就增加一个count变量每次开启新区间时count如果需要输出总长度就每次输出区间时累加长度。这些扩展都很机械核心的排序和合并逻辑完全不变。4. 合并算法里的隐藏考点与边界情况4.1 相邻区间恰好相接的情况上面提到过合并条件必须是addr cur_end而不是。为什么因为左闭右开区间[100, 200)和[200, 300)之间没有空洞它们可以无缝接成[100, 300)。如果你用就会漏掉这种恰好相接的情况把它们当成两个独立区间输出。考试里这个点特别阴险因为正常样例大多是重叠的情况比如[100, 200)和[150, 250)用也能过。但一旦测试数据里出现“首尾相接”的区间你的程序就错了。我记得我当初自己写这段代码时第一次跑测试样例全对交了作业才发现有个隐藏数据点没通过排查了半天才发现就是这个等号的问题。这种坑只有实际写过才会印象深刻。4.2 完全包含与部分重叠的处理假设有两个区间[100, 500)和[200, 300)后者被前者完全包含。合并时当前累积区间cur_end已经是 500而新区间的 end 是 300比cur_end小。所以合并时只保留更大的 end不能让 end 往回缩。这就是代码里if (blocks[i].end cur_end)这个判断存在的原因。再比如[100, 300)和[200, 500)第二个区间起点在第一个内部但终点越出去了。合并后cur_end要更新成 500而不是保持 300。这块的逻辑其实就一句话合并的结果就是取覆盖范围的并集起点取 min终点取 max。由于已经按起始地址排序起点的 min 一定是当前累积区间自身的起点所以你只需要维护终点的 max。我见过有同学在合并时试图重新计算整个合并区间的长度结果又把 start 也更新了逻辑越写越乱。其实记住“排序以后起点不用管只需要向右拓展终点”这个原则就够了。4.3 地址溢出的问题这个坑在数据结构简单的题目里容易被忽略。题目如果给出的地址是int范围相加后可能超过 int 上限吗比如addr 2^31 - 1len 1000addr len就溢出了。因为我们用long long存储一个块的长度所以计算blocks[i].end blocks[i].addr blocks[i].len时是安全的。我在考试时有个习惯凡是涉及地址、大小、长度这类可能变大的变量一律用long long甚至有些保守的同学直接用unsigned long long。虽然有时候显得“小题大做”但能省掉无数莫名其妙的运行时错误。你想想一次溢出可能导致排序的地址比较出错导致合并判断出错排查起来的成本远远大于定义时多写几个字母的成本。4.4 时间复杂度是否够用算法的时间复杂度是判断能否通过大规模数据的关键。排序部分qsort是 O(n log n)合并部分一次线性扫描是 O(n)总时间复杂度 O(n log n)。无论 n 是多少千还是多少万这个复杂度都是很舒服的不会超时。这也反向解释了为什么“先排序再合并”是这道题唯一优雅的解法。如果你用暴力方案两层循环两两比较合并复杂度 O(n^2)在 n10^5 时就非常紧张了。所以考试时看到题目要求合并第一反应就是能不能排序——能排序就排序排序之后线性扫描几乎是必然的选择。5. 常见问题与踩坑实录5.1 qsort 比较函数返回差值溢出这个问题前面已经提过。在写 cmp 函数时如果直接return pa-addr - pb-addr当 addr 是long long时两个大数相减照样可能溢出。用显式分支比较能完全避免这个问题。我强烈建议形成“肌肉记忆”在做多关键字排序时永远写判断式比较而不是返回差值。5.2 合并下标回退引发死循环有些同学想通过“就地合并”方式操作原数组发现两个区间可以合并就把后一个标记掉然后继续扫。如果实现得不好可能会出现下标反复回退甚至死循环。其实完全不用这么麻烦。像我写的版本那样维护一个独立的cur_addr和cur_end扫描一遍就好不需要删除数组元素也不需要标记数组更不需要回退下标。遍历指针永远往前走只是“当前累积区间”的状态在变。这种方式简单、直观、不易错。5.3 漏掉最后一个区间的输出刚开始写这个题时我经常犯一个错误循环体里每次开启新累积区间时就输出前一个区间但循环结束之后最后一个累积区间没人输出。注意上面完整代码最后的那行printf不是多余的它负责输出最后一个累积区间。很多人考试时漏掉这一句导致结果永远少一块。我建议把“循环结束后必须输出最后一块”当成一个 checklist 事项每次写这类合并题都检查一遍。5.4 边界条件“只有一个输入区间”如果 n 1那么排序后只有一个元素循环体一次都不执行此时只有最后一句 printf 输出那一个区间正好符合预期。如果 n 0程序会解引用blocks[0]可能崩溃。考试时一般不会给 n 0 的空数据但如果你在工程场景里复用这段逻辑一定要加上空数组的提前判断。我在自己写工具代码时往往会加一句if (n 0) return 0;这个习惯能省一次崩溃。5.5 常见问题速查表我把写过这段代码时遇到的典型问题和排查思路整理成一个速查表方便你复习问题现象原因解决方案相邻区间没合并输出结果比预期多一块合并条件写成addr cur_end漏掉等号改为addr cur_end输出结果缺少最后一块少一个区间循环结束后没有输出最后一个累积区间循环后补一次输出排序完全乱序合并结果顺序错乱比较函数返回差值溢出或返回值不满足 -1/0/1改为显式分支比较合并后长度不对输出长度变短合并时 end 被错误地回退只有end cur_end时才更新结构体字段未初始化合并逻辑全乱end字段未赋值就参与排序和合并输入时立即计算end这张表里的前三个问题可以说是我见过的“空闲空间合并”这道题的全部高频扣分点。无论谁来写第一次基本都会踩中其中一两个。6. 从模拟题到真实系统的延伸思考6.1 这道题在操作系统课程里的定位操作系统课讲到内存管理时必定会涉及“动态分区分配”和“空闲分区管理”。真实系统里内存释放后会产生很多碎片比如一个进程占用了 300KB释放后只剩一块 300KB 的空闲区另一个进程又释放了相邻的 200KB。如果系统不做合并这两个区域就会一直保持分离状态之后想分配一个 500KB 的连续内存块就会失败。所以“空闲空间合并”不是一道纯为了考试的算法题它是对操作系统内存回收机制的核心抽象。理解了这道题你基本就知道了“合并空闲区”在系统层面是怎么做的把空闲区的地址和长度放入空闲表排序后合并相邻项得到无重叠的空闲块列表后续分配时从中找合适块。6.2 扩展思路为什么排序不是唯一方案我在实际做这类题的时候也会想一想“如果不排序还能怎么做”。一种做法是用“区间树”或者“哈希表按地址映射”来加速合并但在考试这个场景里完全没有必要。排序是最普适、最稳定的思路。不过如果将来你在真实项目中做内存分配器你可能会用更复杂的数据结构。比如在分配器中维护一个按地址排序的红黑树每一次释放操作后尝试与相邻块合并。这本质上还是“先排序后合并”的思路只不过排序是增量维护的不是每次释放都重新全量排序。6.3 后续还能扩展什么按多种条件排序处理动态插入如果你想拿这道题练手可以在基础版本上做几个扩展扩展一按长度从大到小排序输出所有空闲块模拟“最佳适应分配算法”里按长度查找块的需求扩展二在合并后统计最大的空闲块长度和总空闲内存量扩展三输入包含“分配”和“释放”两种操作暂存空闲区每次分配后删除对应块每次释放后插入并合并。这三个扩展题型在各类课程设计里也经常出现。核心思想仍然是“维护有序的空闲块列表”只是从静态变成动态。做熟基础版后再做这些扩展难度提升就很平滑了。我个人在实际操作中的体会是这类“结构体二级排序 线性合并”的题目最值得练的不是语法而是你面对一组凌乱的区间时是否能在几秒钟内意识到“先排序就一切都顺了”。这个思维习惯远比背熟 qsort 的函数签名更有价值。最后再分享一个小技巧考试时如果你不确定自己的合并条件是不是把“相邻”这个场景覆盖了就手动造一个测试用例比如三块连续区间[100,100)、[200,100)、[300,100)跑一遍看输出是不是只有一个大区间。这种测试用例的构造思路在调试任何区间合并问题的时候都极其好用。