使用二维vector实现邻接表图结构时反复出现vector下标越界报错问题
嵌套vector实现邻接表的下标越界问题排查
直接触发越界的核心错误
- 外层
vecOfVectors的索引访问完全错位:C++ vector为0起始索引,调用resize(n)后,合法访问范围为0 ~ n-1,不存在下标为n的元素- 初始化流程中,第一次
numberIndices++后值为1,resize(1)后用numberIndices-1即下标0访问,逻辑正确 - 第二次
numberIndices++后值为2,resize(2)后合法最大下标为1,但代码直接以numberIndices也就是下标2访问,直接触发越界报错,这就是输入完两个初始顶点值就立刻崩溃的直接原因 - 注释中提到的将下标改为
[numberIndices + 1]的尝试,会让访问的越界值更大,完全无法解决问题
- 初始化流程中,第一次
- 调整
numberIndices初始值到10的操作完全无效:vecOfVectors.resize(numberIndices)会直接把外层vector的长度强制修改为当前numberIndices的值,不管初始构造时设置了多大的长度,resize会直接裁剪到目标长度,对解决越界没有任何帮助 - 逻辑遗漏引发的隐患:
valIsFound为全局变量,初始值为false,但整个邻接表查找环节没有在每轮查找前把该值重置为false,只要某一轮查找成功把值改为true,后续哪怕新的连接目标值查找失败,程序仍会误判为查找成功,触发错误的边添加逻辑 - 设计匹配性说明:邻接表要求每个内层vector的第一个元素为对应顶点本身,作为邻接项的索引标识,最开始初始化第一条边的两个内层vector完全符合这个设计要求,但因为下标越界,根本没有走到合法的写入流程
修正后的核心代码
将越界的下标访问替换为合法的numberIndices - 1,同时补上每轮查找前的标记重置逻辑、缺失的变量定义:
int indexVal; int secIndexVal; int numberIndices = 0; bool valIsFound = false; vector <vector <int>> vecOfVectors(numberIndices); char userPrompt; int main() { cout << "\nEnter first value: "; cin >> indexVal; cout << "\nEnter second value: "; cin >> secIndexVal; numberIndices++; vecOfVectors.resize(numberIndices); vecOfVectors[numberIndices - 1].push_back(indexVal); vecOfVectors[numberIndices - 1].push_back(secIndexVal); numberIndices++; vecOfVectors.resize(numberIndices); // 修正原代码的越界下标:从numberIndices改为numberIndices - 1 vecOfVectors[numberIndices - 1].push_back(secIndexVal); vecOfVectors[numberIndices - 1].push_back(indexVal); cout << "\nExit? (y/n)"; cin >> userPrompt; while (userPrompt != 'y') { cout << "\nEnter a new value: "; cin >> indexVal; numberIndices++; vecOfVectors.resize(numberIndices); cout << "\n enter a value to connect it to: "; cin >> secIndexVal; vecOfVectors[numberIndices - 1].push_back(indexVal); // 每轮查找前重置标记,避免上次的查找结果残留 valIsFound = false; for (int j = 0; j < numberIndices; ++j) { if (vecOfVectors[j].at(0) == secIndexVal) { valIsFound = true; vecOfVectors[j].push_back(indexVal); } } if (valIsFound == true) { vecOfVectors[numberIndices - 1].push_back(secIndexVal); } cout << "\nExit? (y/n)"; cin >> userPrompt; } }
优化提示:如果后续顶点规模较大,可以给外层vector增加一个顶点值到下标的哈希映射表,替代当前每新增一条边就遍历全表查找匹配顶点的逻辑,能将查找边的时间复杂度从O(n)降到O(1)。
内容的提问来源于stack exchange,提问作者Jake Orantes
相关产品推荐
相关产品推荐

