Page 169 - 《软件学报》2026年第5期

2048 软件学报 2026 年第 37 卷第 5 期

算法 1. 基于邻接表的粗粒度用例分组过程.
输入: 无序用例集 T, 用例覆盖语句集 S;
输出: 关键用例集 K, 普通用例集 N, 关键用例覆盖语句集 S k , 普通用例覆盖语句集 S n .

Begin
1. 关键用例集 K ← ∅;
2. 普通用例集 N ← ∅;
3. for t i in T // 遍历无序用例集 T
4. if t i in K then // 当前用例为关键用例
5. continue; // 接下来无需寻找与 t i 覆盖语句具有包含关系的用例
6. end if
7. for t j in T
8. if t j in K then
9. continue;
10. end if
11. if S[i] ⊆ S[j] then // 用例 t j 的覆盖语句可包含 t i 的覆盖语句
12. Add t j into K; // 将可包含 t i 覆盖语句的用例 t j 加入关键用例集
13. break; // 搜寻下一个能包含当前用例覆盖语句的用例
14. end if
15. if S[j] ⊆ S[i] then // 用例 t i 的覆盖语句可包含 t j 的覆盖语句
16. Add t i into K; // 将可包含 t j 覆盖语句的用例 t i 加入关键用例集
17. end if
18. if S[i] ⊈ S[j] and S[i] ⊉ S[j] then // t i 与 t j 的覆盖语句不存在包含关系
19. Add t i and t j into K; // 将 t j 与 t i 加入关键用例集
20. end if
21. j = j + 1;
22. end for
23. i = i + 1;
24. end for
25. N ← T – K; // 将未分组用例视为普通用例
26. Output K, N, S k , S n ;
End
在算法 1 中, 第 1, 2 行初始化关键用例集 K 和普通用例集 N. 第 3–26 行通过集合判断操作检测各用例间的语
句包含关系. 先判断当前检测用例是否已在关键用例集 K 和普通用例集 N 中, 若在, 则跳过检测该用例与其他用
例间的包含关系以加快检测效率. 再判断是否存在包含关系, 将可包含其他用例覆盖信息的用例与覆盖信息互不
存在包含关系的用例加入关键用例集 K. 第 25 行, 将无序用例集 T 中不属于关键用例集 K 的用例加入普通用例
集 N. 第 26 行输出关键用例集 K 和普通用例集 N 以及对应的覆盖语句集 S k 和 S n .
2.2 细粒度测试用例分组排序
为同时提高排序的有效性和效率, 我们对测试用例进行细粒度分组排序. 一方面, 在 Zhang 等人 [11] 分区排序
算法基础上, 提出以用例潜力度为二次选择指标的 TP-Additional 策略对部分关键用例进行排序, 实现 TPG-TCP
方法; 另一方面, 受 Li 等人 [8] 利用多列表储存排序数据的启发, 我们增加了语句-用例数表 SC, 以加快计算待排用