数据结构――稀疏矩阵(二)
b_value = b[0].value;
if(a_col != b_row)
{
std::cout << "error";
return;
}
//c矩阵为b的转置矩阵
//先获取结果矩阵最大长度
item* c = new item[b_value+1];
transpose(b,c); //下面所述的row表示结果数组的行标，col表示结果数组的列标
int row = a[1].row; //结果矩阵的行标row一定是从这里开始的
int col = 0; //列标col暂置为0
//_begin用于标记row行初始位置。
int _begin=1; //如：循环时，前面row行已经处理完了，这时a数组的前面row行对于后续计算也就没意义了，这里_begin的作用就是用于记录a数组的row+1行位置作用
int sum,num=1; //sum存储的结果数组（row,col）处的value值，num用于存储结果数组的下标
for(int i=1;i<=a_value;) //从a数组1开始遍历，直至a数组尾
{
col = c[1].row; //由于c为b数组转置矩阵，其行标就是结果数组的列标col，由矩阵的乘法性质知，每次col都从c[1].row开始的，故每次循环开始时，要重置下。
sum = 0;
for(int j=1;j<=b_value+1;) //此处value+1的作用是应对这种情况：a数组未遍历完，而j值已经取遍c的下标，而j++的作用导致超出c数组范围，可能会越界，而下面的第一个if作用也正是处理这种状况
{
if(j>b_value) //j值已经超出了b_value，意味着数组已被完全遍历，说明当前行row的值已经完全找出了。
{
result[num].row = row; //这时我们就可以把之前记录的sum填入结果数组中，同时下标num要自加1
result[num].col = col;
result[num].value = sum;
num++;
break; //当前行的所有非0值均已找出，可以跳出该循环了
}
if(i>a_value||a[i].row != row) //1、此时a矩阵该行已迭代完，没有可算的值2、当前row行已经迭代完，若继续迭代，行值就变了，
{
result[num].row = row; //所以此时也可以将sum值存入结果数组中，同时下标num要自加1.
result[num].col = col;
result[num].value = sum;
num++;
i = _begin; //为了计算当前行的下一个（下一个col值）非零值，i要为该行的起始位置开始遍历
for(;j<=b_value&&c[j].row==col;j++);//主要作用为了将当前行值为col的全部遍历过，但不作任何其他处理，然后进入下一col值
if(j>b_value)break; //可能出现j的值比b_value大，就要跳出循环了。
col = c[j].row; //将列值置为下一个col值
}
else if(c[j].row != col) //由于c数组的row表示结果数值的列值，该条件说明当前列值与c数组的row值不等，意味着结果数组的列值应该下移了。
{
result[num].row = row; //处理方式与上述有些类似
result[num].col = col;
result[num].value = sum;
num++;
i = _begin;
col = c[j].row;
}
else if(a[i].col < c[j].col) //下面3个条件很好理解。
{
i++;
}
else if(a[i].col == c[j].col)
{
sum += a[i++].value * c[j++].value;
}
else if(a[i].col > c[j].col)
{
j++;
}
}
for(;i<=a_value&&a[i].row == row;i++); //通过递归，将当前行迭代，直到进行下一个row行值。
if(i>a_value) //如果i的值超出最大值，说明已经算完所有行了。
break; //终止循环
row = a[i].row;
_begin = i; //同时记下此时row对应的开始下标。
}
result[0].row = a_row;
result[0].col = b_col;
result[0].value = num-1;
delete[] c;
}