稀疏矩阵三元组实现矩阵转置算法实验报告
实验三 稀疏矩阵的三元组表示实现矩阵转置算法
学院 专业 班
学号 姓名 一．实习目的
1. 掌握稀疏矩阵的三元组顺序表存储表示；
2. 掌握稀疏矩阵三元组表示的传统转置算法的实现；
3. 掌握稀疏矩阵三元组表示的快速转置算法的实现；
二．实习内容
1. 稀疏矩阵的按三元组形式输入，即按行序输入非零元的行号、列号、值，实现传统转置
算法，输出按通常的阵列形式输出。
2. 稀疏矩阵的按三元组形式输入，即按行序输入非零元的行号、列号、值，实现快速转置
算法，输出按通常的阵列形式输出。
三．实验步骤
1. 三元组的定义
#define MAX_SIZE 100 // 非零元个数的最大值
struct Triple
{
int i,j; // 行下标, 列下标
ElemType e; // 非零元素值
};
struct TSMatrix
{
struct Triple data[MAX_SIZE+1]; // 非零元三元组表，data[0]未用
int mu,nu,tu; // 矩阵的行数、列数和非零元个数
};
2. 创建稀疏矩阵M （按三元组形式输入，即按行序输入非零元的行号、列号、值）
3. 编写三元组传统转置函数。
4. 编写三元组快速转置函数。
4. . 主函数
(1)程序代码
#include "stdio.h"
#include "stdlib.h"
#define MAX_SIZE 100 // 非零元个数的最大值
typedef int ElemType;
struct Triple
{
int i,j; // 行下标, 列下标
ElemType e; // 非零元素值
};
struct TSMatrix
struct Triple data[MAX_SIZE+1]; // 非零元三元组表，data[0]未用 int mu,nu,tu; // 矩阵的行数、列数和非零元个数
};
int CreateSMatrix(TSMatrix &M)
{ // 创建稀疏矩阵M
int i,m,n;
ElemType e;
int k;
printf("请输入矩阵的行数, 列数, 非零元素数：");
scanf("%d,%d,%d",&M.mu,&M.nu,&M.tu);
if(M.tu>MAX_SIZE)
return -1;
M.data[0].i=0; // 为以下比较顺序做准备
for(i=1;i
{
do
{
printf("请按行序顺序输入第%d个非零元素所在的行(1～%d),列(1～%d),元素值:",i,M.mu,M.nu);
scanf("%d,%d,%d",&m,&n,&e); //输入非零元的行号、列号、元素值 k=0;
if(mM.mu||nM.nu) // 行或列超出范围
k=1;
if(m
k=1;
}while(k);
M.data[i].i =m; // 将m,n,e 填入M
M.data[i].j =n;
M.data[i].e =e;
}
return 1;
}
void PrintSMatrix(TSMatrix M)
{ // 按矩阵形式输出M
int i,j,k=1;
Triple *p=M.data;
p++; // p指向第1个非零元素
for(i=1;i
for(j=1;j
if(ki==i&&p->j==j)
// p指向非零元，且p 所指元素为当前处理元素
{
printf("%3d",p->e); // 输出p 所指元素的值
p++; // p指向下一个元素
k++; // 计数器+1
}
else // p所指元素不是当前处理元素
printf("%3d",0); // 输出0
printf("\n");
}
}
void TransposeSMatrix(TSMatrix M,TSMatrix &T)
{ // 求稀疏矩阵M 的转置矩阵T 。
int p,q,col;
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu)
{
q=1;
for(col=1;col
for(p=1;p
if(M.data[p].j==col)
{
T.data[q].i= M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e= M.data[p].e;
++q;
}
}
}
void FastTransposeSMatrix(TSMatrix M,TSMatrix &T)
{ // 快速求稀疏矩阵M 的转置矩阵T 。算法5.2改
int p,q,t, k ,col,*num,*cpot;
num=(int *)malloc((M.nu+1)*sizeof(int)); // 存M 每列(T每行) 非零元素个数([0]不用) cpot=(int *)malloc((M.nu+1)*sizeof(int)); // 存T 每行的下1个非零元素的存储位置([0]不用)
T.mu=M.nu; // 给T 的行、列数与非零元素个数赋值
T.nu=M.mu;
T.tu=M.tu;
if(T.tu) // 是非零矩阵
{
for(col=1;col
num[col]=0; // 计数器初值设为0
for(t=1;t
{ k=M.data[t].j; ++num[ col]; }
cpot[1]=1; // T的第1行的第1个非零元在T.data 中的序号为1
for(col=2;col
cpot[col]=cpot[col-1]+num[col-1];
// 求T 的第col 行的第1个非零元在T.data 中的序号
printf("num数组的值为：\n");
for(col=1;col
printf("%4d",num[col]);
printf("\n");
printf("转置前cpot 数组的值为：\n");
for(col=1;col
printf("%4d",cpot[col]);
printf("\n");
for(p=1;p
{
col= M.data[p].j; // 求得在M 中的列数
q= cpot[M.data[p].j]; // q指示M 当前的元素在T 中的序号 T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
++cpot[col]; // T第col 行的下1个非零元在T.data 中的序号
}
}
printf("转置后cpot 数组的值为：\n");
for(col=1;col
printf("%4d",cpot[col]);
printf("\n");
free(num);
free(cpot);
}
void main()
{
TSMatrix A,T;
printf("创建矩阵A: ");
CreateSMatrix(A);
PrintSMatrix(A);
TransposeSMatrix(A,T);
printf("传统矩阵转置程序执行后的矩阵t(A的转置):\n"); PrintSMatrix(T);
FastTransposeSMatrix(A,T);
printf("快速矩阵转置程序执行后的矩阵t(A的转置):\n"); PrintSMatrix(T);
}
（2）调试程序
(3) 运行程序（截图）
四．实习小结
自己写