问答题

试题三
阅读以下说明和C函数，将应填入（n）处的字句写在答题纸的对应栏内。
[说明]
若一个矩阵中的非零元素数目很少且分布没有规律，则称之为稀疏矩阵。对于m行n列的稀疏矩阵M，进行转置运算后得到n行m列的矩阵MT，如图3-1所示。

为了压缩稀疏矩阵的存储空间，用三元组（即元素所在的行号、列号和元素值）表示稀疏矩阵中的一个非零元，再用一维数组逐行存储稀疏矩阵中的所有非零元素（也称为三元组顺序表）。例如，图3-1所示的矩阵M相应的三元组顺序表如表3-1所示，其转置矩阵MT的三元组顺序表如表3-2所示。

函数TransposeMatrix（MatrixM）的功能是对用三元组顺序表表示的稀疏矩阵M进行转置运算。
对M实施转置运算时，为了将M中的每个非零元素直接存入其转置矩阵MT三元组顺序表的相应位置，需先计算M中每一列非零元素的数目（即MT中每一行非零元素的数目），并记录在向量num中；然后根据以下关系，计算出矩阵M中每列的第一个非零元素在转置矩阵MT三元组顺序表中的位置：
cpot[0]=0
cpot[j]=cpot[j-1]+num[j-1]/*j为列号*/
类型ElemType、Triple和Matrix定义如下：
typedefintElemType；
typedefstruct{/*三元组类型*/
intr，c；/*矩阵元素的行号、列号*/
ElemTypee；/*矩阵元素的值*/
}Triple；
typedefstruct{/*矩阵的三元组顺序表存储结构*/
introws，cols，elements；/*矩阵的行数、列数和非零元素数目*/
Tripledata[MAXSIZE]；
}Matrix；
[C函数]
intTransposeMatrix（MatrixM）
{
intj，q，t；
int*num，*cpot；
MatrixMT；/*MT是M的转置矩阵*/
num=（int*）malloc（M.cols*sizeof（int））；
cpot=（int*）malloc（M.cols*sizeof（int））；
if（!num||!cpot）
returnERROR；
MT.rows=（1）；/*设置转置矩阵MT行数、列数和非零元数目*/
MT.cols=（2）；
MT.elements=M.elements；
if（M.elements>0）{
for（q=0；qnum[q]=0；
for（t=0；tnum[M.data[t].c]++；
/*计算矩阵M中每列第一个非零元素在其转置矩阵三元组顺序表中的位置*/
（3）；
for（j=1；jcpot[j]=（4）；
/*以下代码完成转置矩阵MT三元组顺序表元素的设置*/
for（t=0；tj=（5）；/*取矩阵M的一个非零元素的列号存入j*/
/*q为该非零元素在转置矩阵MT三元组顺序表中的位置（下标）*/
q=cpot[j]；
MT.data[q].r=M.data[t].c；
MT.data[q].c=M.data[t].r；
MT.data[q].e=M.data[t].e；
++cpot[j]；/*计算M中第j列的下一个非零元素的目的位置*/
}/*for*/
}/*if*/
free（num）；free（cpot）；
/*此处输出矩阵元素，代码省略*/
returnOK；
}/*TransposeMatrix*/

点击查看答案