数组(数据结构).doc

矩阵的压缩存储 非0元素的个数为 n(n+1)/2 k = (1+i-1)(i-1)/2+j-1 = i(i-1)/2+j-1 非0元素的个数是 n(n+1)/2 k = (n+n-(i-1)+1)(i-1)/2+j-(i-1)-1= (i-1)(n-i/2)+j-1 非0元素的个数为 3n-2。 k = 3(i-1)-1+j-(i-2)-1 = 2i+j-3 C=A+B的算法设计(MatrixExample.cpp)： for (i=1；i=5；++i) // 下三角部分 for (j=1；j=i；++j) { k = i*(i-1)/2+j-1； A[k]= (-1)^(i+j)*(i-j+1)； B[k]= i-j； C[k]=A[k]+B[k]； } // 对于i=1~5, j=1~i, 输入Aij和Bij的值, 并计算Cij //输出下三角矩阵A for (i=1；i=5；++i) for (j=1；j=5；++j) { if (ji) printf(“0”)；else printf A[i*(i-1)/2+j-1]； } //输出对称矩阵B for (i=1；i=5；++i) for (j=1；j=5；++j) { if (j=i) k=i*(i-1)/2+j-1；else k=j*(j-1)/2+i-1； printf B[k]；} //输出矩阵C=A+B for (i=1；i=5；++i) for (j=1；j=5；++j) { if (j=i) printf C[i*(i-1)/2+j-1]； else printf B[j*(j-1)/2+i-1]；} 三元组顺序表的定义 typedef struct { int i, j; ElemType e; } Triple; typedef Triple data[MaxT]; int mu, nu, tu; //行数，列数，非0元素的个数 将稀疏矩阵M6(7压缩存储到T3[MaxT][3]数组中，再输出M6(7及其转置矩阵MT。 T3[0][0]=6；T3[0][1]=7；// 矩阵行列数 t=-1； // 按行序依次输入三元组到T3中 while (T3[t][0]0) { ++t； scanf: T3[t][0]，T3[t][1]，T3[t][2]； }；// 时间复杂度为O(t) // 输出矩阵M k=1； for (i=1；i=T3[0][0]；++i) for (j=1；j=T3[0][1]；++j) { if (T3[k][0]==i T3[k][1]==j) { printf: T3[k][2]；++k；} else printf( 0 )； } // 时间复杂度为O(m(n) //求转置矩阵的三元组 (或参考算法5.1) for (i=2；i=T3[0][2]；++i) { j=i； while(T3[j][1]T3[j-1][1] j1) { T3[j](T3[j-1]；--j；} } // 时间复杂度为O(t(t) //输出转置矩阵 k=1； for (j=1；j=T3[0][1]；++j) for (i=1；i=T3[0][0]；++i) { if (T3[k][1]==j T3[k][0]==i) { printf: T3[k][2]；++k；} else printf(0 )； } // 时间复杂度为O(m(n) # 三元组矩阵相加 k1=k2=1； for (i=1；i=A[0][0]；++i) for (j=1；j=A[0][1]；++j) { k=0； if (A[k1][0]==i A[k1][1]==j) { k+=A[k1][2]；++k1；} if (B[k2][0]==i B[k2][1]==j) { k+=B[k2][2]；++k2；} printf：k； } // 时间复杂度为O(m(n) 矩阵乘法Am(n(Bn(s for (i=1；i=m；++i) for (j=1；j=s；++j) { C[i][j]=0； for (k=1；k=n；++k) C[i][j]+=A[i][k]*B[k][j]； } // 时间复杂度为O(m(n(s)