C++实现DAG路径计数程序触发SIGSEGV错误,求排查及避免方案
问题定位
核心错误如下:
- 你直接将函数输入的
edges参数当成邻接表使用,但题目给出的edges是边列表(每一项是[u, v]格式,表示一条从u到v的边,而非u对应的所有邻接点集合)。当start的数值大于等于edges的总长度时,访问edges[start]会直接触发数组越界,这是导致SIGSEGV的直接原因。 - 次要风险点:递归调用
path_count时edges采用值传递,每次递归都会完整拷贝整个边列表,当图规模较大时会快速耗尽栈空间触发栈溢出,也会导致SIGSEGV。 - 额外逻辑问题:题目明确是DAG场景,本身不存在环,不需要加
visited数组标记访问状态,加了反而会漏掉部分合法路径(比如多条路径共享部分节点的场景),不过该问题不是段错误的诱因。
修复代码示例
class Solution{ public: // 邻接表加const引用修饰,避免拷贝同时防止误修改 void path_count(const vector<vector<int>>& adj, int start, int destination, int &count){ if(start == destination){ count++; return; } // DAG无环无需visited标记 for(auto next : adj[start]){ path_count(adj, next, destination, count); } } int possible_paths(vector<vector<int>>edges, int n, int start, int destination){ // 先将边列表转换为邻接表再使用 vector<vector<int>> adj(n); for(auto& e : edges) { adj[e[0]].push_back(e[1]); } int count = 0; path_count(adj, start, destination, count); return count; } };
预防SIGSEGV的通用建议
- 访问数组、STL容器前先校验下标合法性,确认下标处于
[0, 容器长度-1]范围内,避免越界访问。 - 大体积容器、结构体传参时优先使用引用或指针,避免值传递导致的栈内存耗尽。
- 递归实现前先评估递归深度上限,若深度可能超过系统默认栈限制(通常为1~8MB),改用迭代方式实现。
- 指针访问前先判空,避免访问空指针、野指针指向的内存区域。
- 动态内存分配后校验分配结果,避免访问分配失败的内存块。
const关键字使用实践建议
- 函数传入的不需要修改的参数,统一加
const修饰,既可以避免误改入参,也能让编译器做更多优化,同时提高代码可读性。 - 类中不会修改成员变量的成员函数,在函数声明末尾加
const修饰,允许const类对象调用该函数。 - 指向常量内容的指针、引用,优先用
const修饰,避免意外修改指向的内容。 - 不要强行用
const_cast去掉变量的const属性,除非完全确认该变量原本就是非const定义的,否则会触发未定义行为。
内容的提问来源于stack exchange,提问作者JAHNVI SRIVASTAVA
相关产品推荐
相关产品推荐

