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

一、设计要求11 问题描述稀疏矩阵是指那些多数元素为零的矩阵。利用稀疏特点进行存储和计算可以大大节省存储空间，提高计算效率。求一个稀疏矩阵A的转置矩阵B。12需求分析（1）以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现稀疏矩阵的转置运算。（2）稀疏矩阵的输入形式采用三元组表示，运算结果则以通常的阵列形式列出。（3）首先提示用户输入矩阵的行数、列数、非零元个数，再采用三元组表示方法输入矩阵，然后进行转置运算，该系统可以采用两种方法，一种为一般算法，另一种为快速转置算法。（4）程序需要给出菜单项，用户按照菜单提示进行相应的操作。二、概要设计21存储结构设计采用“带行逻辑链接信息”的三元组顺序表表示矩阵的存储结构。三元组定义为：typedef struct int i； /非零元的行下标int j； /非零元的列下标 ElemType e; /非零元素值Triple;矩阵定义为： Typedef struct Triple dataMAXSIZE+1; /非零元三元组表 int rposMAXRC+1; /各行第一个非零元的位置表 int mu,nu,tu; /矩阵的行数、列数和非零元个数RLSMatrix;例如有矩阵A，它与其三元组表的对应关系如图 22 系统功能设计本系统通过菜单提示用户首先选择稀疏矩阵转置方法，然后提示用户采用三元组表示法输入数据创建一个稀疏矩阵，再进行矩阵的转置操作，并以通常的阵列形式输出结果。主要实现以下功能。（1） 创建稀疏矩阵。采用带行逻辑连接信息的三元组表表示法，提示用户输入矩阵的行数、列数、非零元个数以及各非零元所在的行、列、值。（2） 矩阵转置。采用一般算法进行矩阵的转置操作，再以阵列形式输出转置矩阵B。采用快速转置的方法完成此操作，并以阵列形式输出转置矩阵B。三、模块设计31 模块设计程序包括两个模块：主程序模块、矩阵运算模块。32 系统子程序及其功能设计系统共设置了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() /主函数 33 程序主要调用关系图 8 main1234567四、详细设计41 数据类型定义采用矩阵“带行逻辑连接信息”的三元组顺序表存储结构。42 系统主要子程序详细设计 （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函数，用来设置控制台标题及颜色。doshowtip(); /调用菜单函数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(nn);printf(以通常的阵列形式输出转置后的矩阵B:n);print(B);DestroySMatrix(B); printf(nn);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(nn);printf(以通常的阵列形式输出转置后的矩阵B:n);print(B);DestroySMatrix(A); DestroySMatrix(B);printf(nn);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(nn);printf(以通常的阵列形式输出转置后的矩阵B:n);print(B); DestroySMatrix(B); printf(nn); printf(求A的转置矩阵B-(快速转置):n);FastTransposeSMatrix(A,B); printf(矩阵B的三元组表为:n);PrinRLSMatrix(B); printf(以通常的阵列形式输出转置前的矩阵A:n);print(A);printf(nn);printf(以通常的阵列形式输出转置后的矩阵B:nnnn);print(B);DestroySMatrix(A); DestroySMatrix(B);printf(nn);break;printf( *请选择是否继续输入其他稀疏矩阵？*nn);printf( 1 是，输入其他矩阵n);printf( 0 否，不输入nn);printf( *nnnnnnnnnn);fflush(stdin);/清除输入缓存区scanf(%d,&j);while(j=1);（2）创建矩阵 CreateSMatrix(RLSMatrix &M) /创建稀疏矩阵Mint i,m,n; ElemType e;int k,j;printf(输入矩阵的行数、列数、非零元的个数：);scanf(%d%d%d,&M.mu,&M.nu,&M.tu);M.data0.i=0;for(i=1;i3) /控制跳出死循环printf(本次输入失败！);return ERROR;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(mM.datai-1.i|m=M.datai-1.i&nM.datai-1.j)k=1;while(k);M.datai.i=m;M.datai.j=n;M.datai.e=e; /end forprintf(n);return(OK);（3）销毁矩阵void DestroySMatrix(RLSMatrix &M) /销毁稀疏矩阵M M.mu=0;M.nu=0;M.tu=0;（4）遍历矩阵void PrinRLSMatrix(RLSMatrix M) /遍历稀疏矩阵 Mint i;printf(稀疏矩阵对应的三元组表为：nn);printf(行 列 元素值、nn);for(i=1;i=M.tu;i+)printf(%2d%4d%8dn,M.datai.i,M.datai.j,M.datai.e);printf(nn);（5）打印矩阵函数void print(RLSMatrix A) /打印矩阵函数，以通常形式输出矩阵 int k=1,a,b; printf(稀疏矩阵的通常形式为：nn);int MMAXSIZEMAXSIZE;for(a=0;aA.mu;a+) /初始化矩阵Mfor(b=0;bA.nu;b+)Mab=0;while(k=A.tu)MA.datak.i-1A.datak.j-1=A.datak.e;k+;for(a=0;aA.mu;a+)printf( | );for(b=0;bA.nu;b+)printf(%d ,Mab);printf( | n);（6）工作区函数，显示程序菜单void showtip() /菜单printf( *请选择要执行的操作*nn);printf( 1 采用一般算法实现 nn);printf( 2 采用快速转置的算法实现 nn);printf( *n);（7）矩阵的转置(一般算法)TransposeSMatrix(RLSMatrix M,RLSMatrix &T) /求稀疏矩阵M的转置矩阵Tint 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.datap.j=col) T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+q;return OK;（8）快速转置算法采用此算法时引用两个辅助数组num,cpot, numcol表示矩阵M中第col列中非零元的个数，cpotcol指示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)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;printf(n辅助数组的值为：nn);printf(列号：);for(t=1;t=M.nu;+t)printf(%4d,t);printf(n);printf(num);for(t=1;t=M.nu;+t)printf(%4d,numt);printf(n);printf(cpot);for(t=1;t=M.nu;+t)printf(%4d,cpott);printf(nn);for(p=1;p=M.tu;+p)col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol;free(num);free(cpot);return OK;五、测试分析系统运行后显示主菜单，提示用户选择使用何种算法，如图所示。 图51 （主菜单）51 一般算法用户根据需要选择算法。 输入1，选择采用一般算法实现矩阵的转置。 图 52提示用户创建矩阵A，输入矩阵A的行列值以及非零元个数，用户输入 3 4 5并回车（表示创建一个3行4列有5个非零元的稀疏矩阵），系统然后会提示用户输入非零元素对应的行、列、值 图53输入完成后 回车 ， 系统执行矩阵转置功能，得到结果，如图 （矩阵A对应的三元组表） （转置矩阵B对应的三元组表） （以阵列形式表示B） 图54 图55 图5652 快速转置算法用户若输入2，选择使用快速转置方法来实现 图57输入数据后回车，得到结果如图： （矩阵A对应的三元组表） （辅助数组的值） （B的三元组表及其阵列形式） 图58 图59 图51053 当用户输入3时，运用两种算法，输出采用不同算法运算的过程及结果。本次转置操作执行完毕后，下面附有另一个菜单选项，提示用户是否继续输入其他矩阵，1表示继续输入不同的矩阵再次执行如上转置操作，0表示不继续输入，操作结束。如图： 图511用户输入1，再次出现如图51（主菜单）所示，提示继续输入，继续执行稀疏矩阵的转置操作。输入0则结束操作。六、源程序清单#include#include#include#include#define OK 1#define ERROR 0#define OVERFLOW 0#define MAXSIZE 100#define MAXRC 100typedef int ElemType;typedef structint i,j;ElemType e;Triple;typedef structTriple dataMAXSIZE+1; /非零元三元组int rposMAXRC+1; /各行第一个非零元的位置表int mu,nu,tu; /矩阵的行数、列数和非零元个数RLSMatrix;CreateSMatrix(RLSMatrix &M) /创建稀疏矩阵Mint i,m,n;ElemType e;int k,j;printf(输入矩阵的行数、列数、非零元的个数：);scanf(%d%d%d,&M.mu,&M.nu,&M.tu);M.data0.i=0;for(i=1;i3) /控制跳出死循环printf(本次输入失败！);return ERROR;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(mM.datai-1.i|m=M.datai-1.i&nM.datai-1.j)k=1;while(k);M.datai.i=m;M.datai.j=n;M.datai.e=e; /end forprintf(n);return(OK);void DestroySMatrix(RLSMatrix &M) /销毁稀疏矩阵MM.mu=0;M.nu=0;M.tu=0;void PrinRLSMatrix(RLSMatrix M) /遍历稀疏矩阵 Mint i;printf(稀疏矩阵对应的三元组表为：nn);printf(行 列 元素值、nn);for(i=1;i=M.tu;i+)printf(%2d%4d%8dn,M.datai.i,M.datai.j,M.datai.e);printf(nn);void print(RLSMatrix A) /打印矩阵函数，以通常形式输出矩阵 int k=1,a,b; printf(稀疏矩阵的通常形式为：n);int MMAXSIZEMAXSIZE;for(a=0;aA.mu;a+) /初始化矩阵Mfor(b=0;bA.nu;b+)Mab=0;while(k=A.tu)MA.datak.i-1A.datak.j-1=A.datak.e;k+;for(a=0;aA.mu;a+)printf( | );for(b=0;bA.nu;b+)printf(%d ,Mab);printf( | n);void showtip() /菜单printf( *请选择要执行的操作*nn);printf( & 1 采用一般算法实现 &n);printf( & 2 采用快速转置的算法实现 &n);printf( & 3 同时采用两种算法，先显示一般算法，再显示快速算法 &n);printf( *nn);/头文件结束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.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.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)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-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,numt);printf(n);printf(cpot);for(t=1;t=M.nu;+t)printf(%4d,cpott);printf(nn);for(p=1;p=M.tu;+p)col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol;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函数，用来设置控制台标题doshowtip(); /调用菜单函数int i;scanf(%d,&i)