稀疏矩阵A、B均采用三元组顺序表表示，验证实现矩阵A快速转置算法，并设计、验证矩阵A、B相加得到矩阵C的算法。

2024-07-10 12:07| 来源: 网络整理| 查看: 265

数据结构实验题目：稀疏矩阵A、B均采用三元组顺序表表示，验证实现矩阵A快速转置算法，并设计、验证矩阵A、B相加得到矩阵C的算法。

(1)从键盘输入矩阵的行数和列数，随机生成稀疏矩阵。 (2) 设计算法将随机生成的稀疏矩阵转换成三元组顺序表形式存储。 (3) 设计算法将快速转置得到的与相加得到的三元组顺序表分别转换成矩阵形式。 (4) 输出随机生成的稀疏矩阵A、B及其三元组顺序表、快速转置得到的与相加得到的三元组顺序表及其矩阵形式。

从键盘输入矩阵的行数和列数，随机生成稀疏矩阵。（老师要求不能用二维数组去贮存矩阵）也就是说直接生成三元组 //动态随机生成三元组 TSMatrix Romand(int m,int n){ TSMatrix M; int t=1; int num[100]={0};//记录数组位置是否是非0元 M.mu=m; M.nu=n; M.tu=(int)(m*n*factor)+1;//factor为稀疏因子 srand((unsigned)time(0)); while(t!=M.tu+1){ M.data[t].i = rand() % m+1; M.data[t].j = rand() % n+1; if(num[(M.data[t].i-1)*n+M.data[t].j] == 0){//如果该位置没有数据，属于0元 M.data[t].v = rand() % 10+1; t++; num[(M.data[t].i-1)*n+M.data[t].j] = 1; } } //对三元组排序 for(int i=1;i if((M.data[i].i > M.data[j].i)||(M.data[i].i == M.data[j].i&&M.data[i].j > M.data[j].j)){ Triple a; a = M.data[i]; M.data[i] = M.data[j] ; M.data[j] = a; } } } return M; } 算法将快速转置得到的与相加得到的三元组顺序表分别转换成矩阵形式。这一步呢我们就按照矩阵形式输出就行了，不用实际转。 //打印矩阵 void printMatrix(TSMatrix M,int m,int n){ int t=1,k=0; for(int i= 1; i if(M.data[t].i == i&&M.data[t].j == j){ printf("%d\t", M.data[t].v ); t++; }else{ printf("0\t"); } } printf("\n"); } }

3.快速转置算法

/快速转置 void fastTSMatrix(TSMatrix M,TSMatrix *T){ //初始化T（行数、列数、元素个数） int q,p,col; int num[100]; int cpot[100]; T->mu=M.nu; T->nu=M.mu; T->tu=M.tu; if(T->tu>0){ for(col=1;col if(c1.i==c2.i){ if(c1.j==c2.j){//位置相同 return 0; } else if(c1.j return 1;//B在A的前 } } else if(c1.i return 1;//B在A的前 } } //三元组相加 int addTSMatrix(TSMatrix A,TSMatrix B,TSMatrix *C){ int i,j; int p=1,q=1; C->tu=1; while((p//A在B的前 C->data[C->tu].i=A.data[p].i; C->data[C->tu].j=A.data[p].j; C->data[C->tu++].v=A.data[p].v; p++; } if(cmp(A.data[p],B.data[q])==1){//B在A的前 C->data[C->tu].i=B.data[q].i;// C->data[C->tu].j=B.data[q].j;// C->data[C->tu++].v=B.data[q].v; q++; } if(cmp(A.data[p],B.data[q])==0){//i，j 相同 if(A.data[p].v+B.data[q].v != 0){ C->data[C->tu].i=A.data[p].i; C->data[C->tu].j=A.data[p].j; C->data[C->tu++].v=A.data[p].v+B.data[q].v; } p++; q++; } } //将剩下的三元组的合并 C->mu=A.mu; C->nu=A.nu; while((p C->data[C->tu].i=B.data[q].i; C->data[C->tu].j=B.data[q].j; C->data[C->tu++].v=B.data[q].v; q++; C->mu=B.mu; C->nu=B.nu; } C->tu--; return 0; }

5.三元组的数据结构：

#define maxsize 1250 typedef struct{ int i;//元素的行下标 int j;//元素的列下标 int v;//元素的值 }Triple; //定义三元组 typedef struct{ Triple data[maxsize+1]; // data[0]未用 int mu,nu,tu;//元素的总行数，总列数，不为0元素个数 }TSMatrix;

6.测试结果：请输入A矩阵的行数，列数 2 2 A矩阵为： 0 5 0 0 三元组顺序表形式A为： 1 2 5 请输入B矩阵的行数，列数 2 2 B矩阵为： 0 0 0 5 三元组顺序表形式B为： 2 2 5 转置后的TA: 2 1 5 转置后的TA的矩阵形式: 0 0 5 0 A+B矩阵三元组表示: 1 2 5 2 1 5 TC的矩阵形式： 0 5 5 0

【本文地址】

公司简介

联系我们