You need to enable JavaScript to run this app. 使用二维vector实现邻接表图结构时反复出现vector下标越界报错问题
优惠活动
大模型
产品
解决方案
定价
更多

使用二维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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.22 09:06:07