矩阵转置与相加实验报告

一、实验容和要求 1、 稀疏矩阵A,B均采用三元组表示，验证实现矩阵A快速转置算法，设计并验证A,B相加得到矩阵C的算法。 （1） 从键盘输入矩阵的行数和列数，随机生成稀疏矩阵。 （2） 设计算法将随机生成的稀疏矩阵转换成三元组顺序表示形式存储。 （3） 设计算法将快速转置得到的与相加得到的三元组顺序表分别转换成矩阵形式。 （4） 输出随机生成的稀疏矩阵A,B及其三元组顺序表、快速转置得到的与相加得到的三元组顺序表及其矩阵形式。

二、实验过程及结果

一、需求分析 1、将随机生成的数定义为int型（为方便起见设定围为-20至20（不含0），可修改），三元组存储的元素分别为非零元的行下标、列下标及该位置的元素值，零元不进行存储。实际上在生成稀疏矩阵时是随机选取一些位置生成非零元然后存入三元组中。 2、从键盘输入矩阵的行数和列数后应能输出三元组顺序表及相应矩阵（按行和列排列形式输出）。 3、 程序能实现的功能包括： ①随机产生稀疏矩阵；②输出阵列形式的矩阵；③输出三元组顺序表；④将矩阵快速转置；⑤将两个稀疏矩阵相加生成新的矩阵。

二、概要设计 1、稀疏矩阵的抽象数据类型定义： ADT TSMatrix{ 数据对象：D={ aij|i=1,2,…,m,j=1,2,…,n; Ai,j∈ElemSet,m和n分别称为矩阵的行数和列数} 数据关系：R={Row，Col} Row={|1≤i≤m, 1≤j≤n-1} Col ={|1≤i≤m-1, 1≤j≤n} 基本操作: CreateTSMatrix(&M) 操作结果：创建矩阵M PrintTSMatrix(M) 初始条件：矩阵M已存在 操作结果：输出矩阵M中三元组形式的非零元素 PrintTSMatrix1(M) 初始条件：矩阵M已存在 操作结果：以阵列形式输出矩阵 UnZore(M, row, col) 初始条件：矩阵M已存在 操作结果：若位置(row,col)处存在非零元素，则返回该元素存储在矩阵中的序号 TSMatrix_Add(M, N,&Q) 初始条件：矩阵M，N已存在 操作结果：将矩阵M,N相加得到Q并返回矩阵Q FastTransposeSMatrix(M,&N) 初始条件：矩阵M已存在 操作结果：将矩阵M快速转置得到转置矩阵N并返回 }ADT TSMatrix； ⒊ 本程序模块结构 ⑴ 主函数模块 void main(){ 初始化迷矩阵； 创建矩阵并输出； 将矩阵转置并输出； 将矩阵相加并输出结果； ｝

三、详细设计 1、基本数据类型操作 ⑴typedef int ElemType; typedef struct{ int i,j; ElemType e; }Triple;//数据类型 三元组 typedef struct{ Triple data[maxsize+1];//矩阵大小 int mu,nu,tu; // }TSMatrix;//矩阵抽象数据类型 2、参数设置： #define maxsize 10000 //----------基本操作的算法描述-------------------- Status CreateTSMatrix(TSMatrix *M){ //创建一个随机矩阵（data[0]未用） srand((int)time(NULL)); printf("Please Input The Lines And Columns Of The Matrix:\n"); printf("...(矩阵的期望规格大于4*5(或5*4))...\n"); scanf(M->mu，M->nu); for(m=0;mmu;m++){ for(n=0;nnu;n++){ k[m][n]=rand()%20; if(k[m][n]==0){ if(rand()%2) M->data[p].e=rand()%20+1; else M->data[p].e=rand()%20-20; M->data[p].i=m+1; M->data[p].j=n+1; p++; } } } M->tu=p-1; //p从1开始，非零元个数刚好等于p-1 return OK; }

void PrintTSMatrix(TSMatrix M){ //输出矩阵的三元组顺序表 if(M.tu==0) printf("无非零元!\n"); else{ printf("该矩阵的行数为%d、列数为%d、非零元素个数为%d.\n非零元的坐标及值:\n\n",M.mu,M.nu,M.tu); printf(" 行 列 元素值\n"); for(i=1;i<=M.tu;i++){ printf("%4d%4d%6d\n",M.data[i].i,M.data[i].j,M.data[i].e); } printf("\n"); } }

void PrintTSMatrix1(TSMatrix M){ //输出矩阵的阵列形式 printf("阵列形式为:\n"); for(i=1;i<=M.mu;i++){ for(j=1;j<=M.nu;j++) if (ki==i&&p->j==j){ printf("%4d",p->e); //data[0]未用，p从data[1]开始 p++; k++; } else printf("%4d",0); printf("\n"); } printf("\n"); }

int UnZore(TSMatrix M,int row,int col){ while(order<=M.tu){ if(M.data[order].i==row&&M.data[order].j==col)//order从1开始 return order; order++; } return 0; }

Status TSMatrix_Add(TSMatrix M,TSMatrix N,TSMatrix *Q){ //矩阵相加得到新的矩阵，order从1开始 if(M.mu==N.mu&&M.nu==N.nu){ for(row=1;row<=M.mu;row++){ for(col=1;col<=M.nu;col++){ order1=UnZore(M,row,col); order2=UnZore(N,row,col); if(order1&&order2){ Q->data[order].i=row; Q->data[order].j=col; Q->data[order].e=M.data[order1].e+N.data[order2].e; order++; } else if(order1&&(!order2)){ Q->data[order].e=M.data[order1].e; Q->data[order].i=M.data[order1].i; Q->data[order].j=M.data[order1].j; order++; } else if((!order1)&&order2){ Q->data[order].e=N.data[order2].e; Q->data[order].i=N.data[order2].i; Q->data[order].j=N.data[order2].j; order++; } } } Q->mu=M.mu; Q->nu=M.nu; Q->tu=order-1; return OK; } else{ printf("\n不是同型矩阵不能进行相加!\n"); return ERROR; } } Status FastTransposeSMatrix(TSMatrix M,TSMatrix *N){ //采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵N N->mu=M.nu; N->nu=M.mu; N->tu=M.tu; if(N->tu){ for(i=1;i<=M.nu;++i) num[i]=0; for(t=1;t<=M.tu;++t) ++num[M.data[t].j];//求M中每一列非零元个数 cpot[1]=1; //求第col列中第一个元素在b.data中的序号 for(i=2;i<=M.nu;++i) cpot[i]=cpot[i-1]+num[i-1]; for(p=1;p<=M.tu;++p){ i=M.data[p].j; q=cpot[i]; N->data[q].i=M.data[p].j; N->data[q].j=M.data[p].i; N->data[q].e=M.data[p].e; ++cpot[i]; } } return OK; } ⑶ 主函数算法： void main(){ TSMatrix A,A1,B,C; printf("矩阵A:\n"); CreateTSMatrix(&A); PrintTSMatrix(A); PrintTSMatrix1(A); printf("由矩阵A转置得矩阵A1...\n"); FastTransposeSMatrix(A,&A1); PrintTSMatrix(A1); PrintTSMatrix1(A1); printf("矩阵B:\n"); CreateTSMatrix(&B); PrintTSMatrix(B); PrintTSMatrix1(B); printf("矩阵A加矩阵B得到矩阵C...\n"); if(TSMatrix_Add(A,B,&C)){ PrintTSMatrix(C); PrintTSMatrix1(C);