C++基于链表实现稀疏矩阵时触发EXC_BAD_ACCESS错误的排查

• 触发EXC_BAD_ACCESS (address=0x8)的直接原因是头节点的next指针未初始化。
  Matrixnode为带联合的结构体，头节点（head=true）使用联合中的next字段，但构造函数中，当节点为头节点时仅设置right=down=this，完全未给next赋值，next为随机野指针（大概率是0x0）。当执行标注的报错行head[t.col]->next->down=last时，先读取野指针head[t.col]->next得到空地址，再访问该空地址中down成员的位置——64位环境下down在结构体中的偏移量恰好是8字节，最终访问地址就是0x8，直接触发内存访问异常。
  对应原构造函数的缺失逻辑：

  if(head){right=down=this;} // 缺少next成员的初始化
  

• 除了直接触发报错的问题，代码还存在几处逻辑错误，修复直接报错后会连续触发其他异常：
  • 矩阵总根节点构造错误。读入的第一行参数是(行数,列数,非零元个数)，代码将这组值作为普通三元组，构造了head=false的普通节点作为矩阵总头。按照十字链表的设计，总头节点必须是head=true类型的头节点，不能存储三元组数据。
  • 头节点数组长度计算错误。代码取p=max(行数,列数)生成head指针数组，将行头、列头混放。实际十字链表需要行数 + 列数个独立的行、列头节点，当列数大于行数时会直接出现数组越界。
  • 下标体系不匹配。用户输入的行、列号为1起始值，但数组下标从0开始，未做偏移映射，会导致节点挂载到错误的行/列链表上。
  • 列链表挂载逻辑错误。未初始化列头的next指针，也未按列号正确匹配对应的列头，盲目通过next查找列链表尾节点，必然出现空指针访问。

• 构造函数中头节点分支补充next的自初始化：

  if(head){
      right = down = this;
      next = this; // 必须补充的初始化
  }
  

• 矩阵总根节点改为头节点类型构造，不传入第一行的矩阵参数：

  // 原错误代码：matrix.headnode =new Matrixnode(false,&s);
  matrix.headnode = new Matrixnode(true, nullptr);
  

• 拆分行头、列头的存储数组，输入的行、列号减1后映射到数组下标，避免数组越界。
• 按照十字链表常规逻辑，新非零元节点分别沿行链表的right指针、列链表的down指针走到链表尾部挂载，最后将行、列链表首尾相连成环。

内容的提问来源于stack exchange，提问作者Henry