三元组表示稀疏矩阵的转置(一般算法和快速算法).doc

一、设计要求
1．1 问题描述
稀疏矩阵是指那些多数元素为零的矩阵。利用稀疏特点进行存储和计算可以大大节省存储空间，提高计算效率。求一个稀疏矩阵A的转置矩阵B。
1．2需求分析
（1）以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现稀疏矩阵的转置运算。
（2）稀疏矩阵的输入形式采用三元组表示，运算结果则以通常的阵列形式列出。
（3）首先提示用户输入矩阵的行数、列数、非零元个数，再采用三元组表示方法输入矩阵，然后进行转置运算，该系统可以采用两种方法，一种为一般算法，另一种为快速转置算法。
（4）程序需要给出菜单项，用户按照菜单提示进行相应的操作。
二、概要设计
2．1存储结构设计
采用“带行逻辑链接信息”的三元组顺序表表示矩阵的存储结构。三元组定义为：
typedef struct
{
int i； //非零元的行下标
int j； //非零元的列下标
ElemType e; //非零元素值
}Triple;
矩阵定义为：
Typedef struct

{
Triple data[MAXSIZE+1]; //非零元三元组表
int rpos[MAXRC+1]; //各行第一个非零元的位置表
int mu,nu,tu; //矩阵的行数、列数和非零元个数
}RLSMatrix;
例如有矩阵A，它与其三元组表的对应关系如图

2．2 系统功能设计
本系统通过菜单提示用户首先选择稀疏矩阵转置方法，然后提示用户采用三元组表示法输入数据创建一个稀疏矩阵，再进行矩阵的转置操作，并以通常的阵列形式输出结果。主要实现以下功能。
（1） 创建稀疏矩阵。采用带行逻辑连接信息的三元组表表示法，提示用户输入矩阵的行数、列数、非零元个数以及各非零元所在的行、列、值。
（2） 矩阵转置。<1>采用一般算法进行矩阵的转置操作，再以阵列形式输出转置矩阵B。
<2>采用快速转置的方法完成此操作，并以阵列形式输出转置矩阵B。

三、模块设计
3．1 模块设计
程序包括两个模块：主程序模块、矩阵运算模块。
3．2 系统子程序及其功能设计
系统共设置了8个子程序，各子程序的函数名及功能说明如下。
（1）CreateSMatrix(RLSMatrix &M) //创建稀疏矩阵
（2）void DestroySMatrix(RLSMatrix &M) //销毁稀疏矩阵
（3）void PrinRLSMatrix(RLSMatrix M) //遍历稀疏矩阵
（4）void print(RLSMatrix A) //打印矩阵函数，输出以阵列形式表示的矩阵
（5）TransposeSMatrix(RLSMatrix M,RLSMatrix &T) //求稀疏矩阵的转置的一般算法
（6）FastTransposeSMatrix(RLSMatrix M,RLSMatrix &T) //快速转置算法
（7）void showtip() //工作区函数，显示程序菜单
（8）void main() //主函数

3．3 程序主要调用关系图
8 main
1
2
3
4
5
6
7

四、详细设计
4．1 数据类型定义
采用矩阵“带行逻辑连接信息”的三元组顺序表存储结构。
4．2 系统主要子程序详细设计
（1）主函数：
void main()
{
int result;
int j;
RLSMatrix A,B;
COORD Co={0,0};DWORD Write;
SetConsoleTitle("稀疏矩阵的转置");
HANDLE hOut=GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hOut,FOREGROUND_RED|FOREGROUND_BLUE|FOREGROUND_INTENSITY);
FillConsoleOutputAttribute(hOut,FOREGROUND_RED|FOREGROUND_BLUE|FOREGROUND_INTENSITY,100000000,Co,&Write);
///windows的API函数，用来设置控制台标题及颜色。
do
{
showtip(); //调用菜单函数
int i;
scanf("%d",&i);
switch(i)
{
case 1:
printf("创建矩阵A：");
if((result=CreateSMatrix(A))==0)
exit(ERROR);
printf("矩阵A的三元组表为:\n");
PrinRLSMatrix(A);
printf("求A的转置矩阵B(一般算法)：\n");
TransposeSMatrix(A,B);
printf("矩阵B的三元组表为:\n");
PrinRLSMatrix(B);
printf("以通常的阵列形式输出转置前的矩阵A:\n");
print(A);
printf("\n\n");
printf("以通常的阵列形式输出转置后的矩阵B:\n");
print(B);
DestroySMatrix(B);
printf("\n\n");break;
case 2:
printf("创建矩阵A：");
if((result=CreateSMatrix(A))==0)
exit(ERROR);
printf("矩阵A的三元组表为:\n");
PrinRLSMatrix(A);
printf("求A的转置矩阵B(快速转置):\n");
FastTransposeSMatrix(A,B);
printf("矩阵B的三元组表为:\n");
PrinRLSMatrix(B);
printf("以通常的阵列形式输出转置前的矩阵A:\n");
print(A);
printf("\n\n");
printf("以通常的阵列形式输出转置后的矩阵B:\n");
print(B);
DestroySMatrix(A);
DestroySMatrix(B);
printf("\n\n");break;
case 3:
printf("创建矩阵A：");
if((result=CreateSMatrix(A))==0)
exit(ERROR);
printf("矩阵A的三元组表为:\n");
PrinRLSMatrix(A);
printf("求A的转置矩阵B------(一般算法)：\n");
TransposeSMatrix(A,B);
printf("矩阵B的三元组表为:\n");
PrinRLSMatrix(B);
printf("以通常的阵列形式输出转置前的矩阵A:\n");
print(A);
printf("\n\n");
printf("以通常的阵列形式输出转置后的矩阵B:\n");
print(B);
DestroySMatrix(B);
printf("\n\n");
printf("求A的转置矩阵B------(快速转置):\n");
FastTransposeSMatrix(A,B);
printf("矩阵B的三元组表为:\n");
PrinRLSMatrix(B);
printf("以通常的阵列形式输出转置前的矩阵A:\n");
print(A);
printf("\n\n");
printf("以通常的阵列形式输出转置后的矩阵B:\n\n\n\n");
print(B);
DestroySMatrix(A);
DestroySMatrix(B);
printf("\n\n");break;
}
printf(" **********请选择是否继续输入其他稀疏矩阵？**********\n\n");
printf(" 1 是，输入其他矩阵\n");
printf(" 0 否，不输入\n\n");
printf(" ****************************************************\n\n\n\n\n\n\n\n\n\n");
fflush(stdin);//清除输入缓存区
scanf("%d",&j);
}while(j==1);

}
（2）创建矩阵
CreateSMatrix(RLSMatrix &M) //创建稀疏矩阵M
{
int i,m,n;
ElemType e;
int k,j;
printf("输入矩阵的行数、列数、非零元的个数：");
scanf("%d%d%d",&M.mu,&M.nu,&M.tu);
M.data[0].i=0;
for(i=1;i<=M.tu;i++)
{
j=0;
do
{
j++;
if(j>3) //控制跳出死循环
{
printf("本次输入失败！");
return ERROR;
}
printf("按行序输入第%d个非零元素所在的行(1~%d)列(1~%d)值：",i,M.mu,M.nu);
scanf("%d%d%d",&m,&n,&e);
k=0;
if(m<1||m>M.mu||n<1||n>M.nu) //行或列超出范围
k=1;
if(m<M.data[i-1].i||m==M.data[i-1].i&&n<M.data[i-1].j)
k=1;
}while(k);
M.data[i].i=m;
M.data[i].j=n;
M.data[i].e=e;
} //end for
printf("\n");
return(OK);
}
（3）销毁矩阵
void DestroySMatrix(RLSMatrix &M) //销毁稀疏矩阵M
{
M.mu=0;
M.nu=0;
M.tu=0;
}
（4）遍历矩阵
void PrinRLSMatrix(RLSMatrix M) //遍历稀疏矩阵 M
{
int i;
printf("稀疏矩阵对应的三元组表为：\n\n");
printf("行 列 元素值、\n\n");
for(i=1;i<=M.tu;i++)
printf("%2d%4d%8d\n",M.data[i].i,M.data[i].j,M.data[i].e);
printf("\n\n");
}
（5）打印矩阵函数
void print(RLSMatrix A) //打印矩阵函数，以通常形式输出矩阵
{
int k=1,a,b;
printf("稀疏矩阵的通常形式为：\n\n");
int M[MAXSIZE][MAXSIZE];
for(a=0;a<A.mu;a++) //初始化矩阵M
{
for(b=0;b<A.nu;b++)
M[a][b]=0;
}
while(k<=A.tu)
{
M[A.data[k].i-1][A.data[k].j-1]=A.data[k].e;
k++;
}
for(a=0;a<A.mu;a++)
{
printf(" | ");
for(b=0;b<A.nu;b++)
printf("%d ",M[a][b]);
printf(" | \n");
}
}
（6）工作区函数，显示程序菜单
void showtip() //菜单
{
printf(" ********************请选择要执行的操作********************\n\n");
printf(" 1 采用一般算法实现 \n\n");
printf(" 2 采用快速转置的算法实现 \n\n");
printf(" **********************************************************\n");
}
（7）矩阵的转置(一般算法)
TransposeSMatrix(RLSMatrix M,RLSMatrix &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<=M.nu;++col) //按列序求转置
for(p=1;p<=M.tu;++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;
}
}
return OK;
}
（8）快速转置算法
采用此算法时引用两个辅助数组num[],cpot[], num[col]表示矩阵M中第col列中非零元的个数，cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置。（即指M中每一列的第一个非零元在B中表示为第几个非零元）
FastTransposeSMatrix(TSMatrix M,TSMatrix &T)
{
int p,q,t,col,*num,*cpot;
num=(int*)malloc((M.nu+1)*sizeof(int));
cpot=(int*)malloc((M.nu+1)*sizeof(int));
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu)
{
for(col=1;col<=M.nu;++col)
num[col]=0;
for(t=1;t<=M.tu;++t)
++num[M.data[t].j];
cpot[1]=1;
for(col=2;col<=M.nu;++col)
cpot[col]=cpot[col-1]+num[col-1];
printf("\n辅助数组的值为：\n\n");
printf("列号：");
for(t=1;t<=M.nu;++t)
printf("%4d",t);
printf("\n");
printf("num[]");
for(t=1;t<=M.nu;++t)
printf("%4d",num[t]);
printf("\n");
printf("cpot[]");
for(t=1;t<=M.nu;++t)
printf("%4d",cpot[t]);
printf("\n\n");
for(p=1;p<=M.tu;++p)
{
col=M.data[p].j;
q=cpot[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;
++cpot[col];
}
}
free(num);
free(cpot);
return OK;
}
五、测试分析
系统运行后显示主菜单，提示用户选择使用何种算法，如图所示。

图5——1 （主菜单）
5．1 一般算法
用户根据需要选择算法。 输入1，选择采用一般算法实现矩阵的转置。

图 5——2
提示用户创建矩阵A，输入矩阵A的行列值以及非零元个数，用户输入 3 4 5并回车（表示创建一个3行4列有5个非零元的稀疏矩阵），系统然后会提示用户输入非零元素对应的行、列、值

图5——3
输入完成后 回车 ， 系统执行矩阵转置功能，得到结果，如图

（矩阵A对应的三元组表） （转置矩阵B对应的三元组表） （以阵列形式表示B）
图5——4 图5——5 图5——6
5．2 快速转置算法
用户若输入2，选择使用快速转置方法来实现

图5——7
输入数据后回车，得到结果如图：

（矩阵A对应的三元组表） （辅助数组的值） （B的三元组表及其阵列形式）
图5——8 图5——9 图5——10

5．3 当用户输入3时，运用两种算法，输出采用不同算法运算的过程及结果。
本次转置操作执行完毕后，下面附有另一个菜单选项，提示用户是否继续输入其他矩阵，1表示继续输入不同的矩阵再次执行如上转置操作，0表示不继续输入，操作结束。如图：

图5——11
用户输入1，再次出现如图5——1（主菜单）所示，提示继续输入，继续执行稀疏矩阵的转置操作。输入0则结束操作。

六、源程序清单
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<windows.h>
#define OK 1
#define ERROR 0
#define OVERFLOW 0
#define MAXSIZE 100
#define MAXRC 100
typedef int ElemType;
typedef struct
{
int i,j;
ElemType e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1]; //非零元三元组
int rpos[MAXRC+1]; //各行第一个非零元的位置表
int mu,nu,tu; //矩阵的行数、列数和非零元个数
}RLSMatrix;

CreateSMatrix(RLSMatrix &M) //创建稀疏矩阵M
{
int i,m,n;
ElemType e;
int k,j;
printf("输入矩阵的行数、列数、非零元的个数：");
scanf("%d%d%d",&M.mu,&M.nu,&M.tu);
M.data[0].i=0;
for(i=1;i<=M.tu;i++)
{
j=0;
do
{
j++;
if(j>3) //控制跳出死循环
{
printf("本次输入失败！");
return ERROR;
}
printf("按行序输入第%d个非零元素所在的行(1~%d)列(1~%d)值：",i,M.mu,M.nu);
scanf("%d%d%d",&m,&n,&e);
k=0;
if(m<1||m>M.mu||n<1||n>M.nu) //行或列超出范围
k=1;
if(m<M.data[i-1].i||m==M.data[i-1].i&&n<M.data[i-1].j)
k=1;
}while(k);
M.data[i].i=m;
M.data[i].j=n;
M.data[i].e=e;
} //end for
printf("\n");
return(OK);
}
void DestroySMatrix(RLSMatrix &M) //销毁稀疏矩阵M
{
M.mu=0;
M.nu=0;
M.tu=0;
}
void PrinRLSMatrix(RLSMatrix M) //遍历稀疏矩阵 M
{
int i;
printf("稀疏矩阵对应的三元组表为：\n\n");
printf("行 列 元素值、\n\n");
for(i=1;i<=M.tu;i++)
printf("%2d%4d%8d\n",M.data[i].i,M.data[i].j,M.data[i].e);
printf("\n\n");
}
void print(RLSMatrix A) //打印矩阵函数，以通常形式输出矩阵
{
int k=1,a,b;
printf("稀疏矩阵的通常形式为：\n");
int M[MAXSIZE][MAXSIZE];
for(a=0;a<A.mu;a++) //初始化矩阵M
{
for(b=0;b<A.nu;b++)
M[a][b]=0;
}
while(k<=A.tu)
{
M[A.data[k].i-1][A.data[k].j-1]=A.data[k].e;
k++;
}
for(a=0;a<A.mu;a++)
{
printf(" | ");
for(b=0;b<A.nu;b++)
printf("%d ",M[a][b]);
printf(" | \n");
}
}
void showtip() //菜单
{
printf(" ********************请选择要执行的操作********************\n\n");
printf(" & 1 采用一般算法实现 &\n");
printf(" & 2 采用快速转置的算法实现 &\n");
printf(" & 3 同时采用两种算法，先显示一般算法，再显示快速算法 &\n");
printf(" **********************************************************\n\n");
}
////头文件结束
TransposeSMatrix(RLSMatrix M,RLSMatrix &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<=M.nu;++col) //按列序求转置
for(p=1;p<=M.tu;++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;
}
}
return OK;
}
FastTransposeSMatrix(RLSMatrix M,RLSMatrix &T) //快速转置算法
{
int p,q,t,col,*num,*cpot;
num=(int*)malloc((M.nu+1)*sizeof(int));
cpot=(int*)malloc((M.nu+1)*sizeof(int));
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu)
{
for(col=1;col<=M.nu;++col)
num[col]=0;
for(t=1;t<=M.tu;++t)
++num[M.data[t].j];
cpot[1]=1;
for(col=2;col<=M.nu;++col)
cpot[col]=cpot[col-1]+num[col-1];
printf("\n辅助数组的值为：\n");
printf("列号：");
for(t=1;t<=M.nu;++t)
printf("%4d",t);
printf("\n");
printf("num[]");
for(t=1;t<=M.nu;++t)
printf("%4d",num[t]);
printf("\n");
printf("cpot[]");
for(t=1;t<=M.nu;++t)
printf("%4d",cpot[t]);
printf("\n\n");
for(p=1;p<=M.tu;++p)
{
col=M.data[p].j;
q=cpot[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;
++cpot[col];
}
}
free(num);
free(cpot);
return OK;
}
void main()
{
int result;
int j;
RLSMatrix A,B;
//************************************************
COORD Co={0,0};DWORD Write;
SetConsoleTitle("稀疏矩阵的转置\n");
HANDLE hOut=GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hOut,FOREGROUND_RED|FOREGROUND_BLUE|FOREGROUND_INTENSITY);
FillConsoleOutputAttribute(hOut,FOREGROUND_RED|FOREGROUND_BLUE|FOREGROUND_INTENSITY,100000000,Co,&Write);
///windows的API函数，用来设置控制台标题
do
{

showtip(); //调用菜单函数
int i;
scanf("%d",&i);
switch(i)
{
case 1:
printf("创建矩阵A：");
if((result=CreateSMatrix(A))==0)
exit(ERROR);
PrinRLSMatrix(A);
printf("求A的转置矩阵B(一般算法)：\n");
TransposeSMatrix(A,B);
PrinRLSMatrix(B);
print(B);
DestroySMatrix(B);
printf("\n\n");break;
case 2:
printf("创建矩阵A：");
if((result=CreateSMatrix(A))==0)
exit(ERROR);
PrinRLSMatrix(A);
printf("求A的转置矩阵B(快速转置):\n");
FastTransposeSMatrix(A,B);
PrinRLSMatrix(B);
print(B);
DestroySMatrix(A);
DestroySMatrix(B);
printf("\n\n");break;
case 3:
printf("创建矩阵A：");
if((result=CreateSMatrix(A))==0)
exit(ERROR);
PrinRLSMatrix(A);
printf("求A的转置矩阵B------(一般算法)：\n");
TransposeSMatrix(A,B);
PrinRLSMatrix(B);
print(B);
DestroySMatrix(B);
printf("\n\n");
printf("求A的转置矩阵B------(快速转置):\n");
FastTransposeSMatrix(A,B);
PrinRLSMatrix(B);
print(B);
DestroySMatrix(A);
DestroySMatrix(B);
printf("\n\n");break;
}
printf(" **********请选择是否继续输入其他稀疏矩阵？**********\n");
printf(" 1 是，输入其他矩阵\n");
printf(" 0 否，不输入\n");
printf(" ****************************************************");
fflush(stdin);//清除输入缓存区
scanf("%d",&j);
}while(j==1);

}七、用户手册
（1）本程序执行文件为“稀疏矩阵的转置.exe”。
（2）进入本系统后，根据提示输入数据。
八、总结及答疑

16