《稀疏矩阵的乘法实现.pdf》由会员分享，可在线阅读，更多相关《稀疏矩阵的乘法实现.pdf（10页珍藏版）》请在三一文库上搜索。
1、稀疏矩阵的乘法实现 程序： # include # include # define NULL 0 # define OK 1 # define ERROR 0 # define MAXSIZE 100 /* 矩阵中非零元的最大值 */ # define MAXRC 10 /* 矩阵的最大行值 */ typedefint status ; /* 稀疏矩阵的行逻辑链接的顺序表存储表示 */ typedefstruct /* 非零元的三元组 */ int i, j ; /* 非零元的行下标和列下标 */ int e ; Triple; typedefstruct /* 稀疏矩阵的行逻辑链接的顺序表
2、 */ Triple dataMAXSIZE+1; /* 非零三元组表， data0 未用，以下定义的数组都是从1开始 */ int rposMAXRC+1; /* 代表各行第一个非零元的序 号表，其值为 data 的下标 */ int mu,nu,tu; /* 矩阵的行数、列数、非零元的个数 */ RLSMatrix; /* R:row L:logic S:sequence */ /* 基本操作的函数原型的声明 */ status CreateSMatrix_RL(RLSMatrix * matrix); / 创建一个稀疏矩阵； / 输入行数、列数，支持乱序输入三元组，并计数； / 以行为主
3、序进行重新排列，并记录每行起始位置于 matrix-rposrow； / 若非零元超过 MAXSIZE 或行数超过 MAXRC ，则返回 ERROR ，否 则 OK ； void PrintSMatrix_RL(RLSMatrix * matrix); / 输入矩阵，打印出矩阵的行数、列数、非零元个数，以及整个矩 阵； status MultSMatrix_RL(RLSMatrix * M,RLSMatrix * N,RLSMatrix * Q); / 输入两个稀疏矩阵M和 N，并初始化 Q，然后计算 M*N的值赋给 Q ； / 如果 M-mu!=N-nu 或列数大于 MAXRC 或者计算出的
4、非零元个数 大于 MAXSIZE ，都返回 ERROR, 否则 OK ； / 计算过程如下： / 1. 由于矩阵 M和 Q的行数相等并且 C语言以行为主序进行存 储，所以以 M进行逐行的扫描。 / 2. 使 Q的此行逻辑表的序号等于其非零元个数Q.tu+1 ，以 表示其行的首个元素的序号。 / 3. 从行中找到 M的非零元，并以它的列值为N的行号，对 N 进行行的扫描，若存在，则依次计算它们，并把其值累加到一个以N中这个 对应非零元的列值为序号的临时数组ctempccol中。 / 4. 在 M的当前行完成扫描后，将ctempccol不为0的值， 压入到 Q矩阵的三元组，累加 +Q.tu ，若
5、Q.tu 大于了 MAXSIZE ，这返回 ERROR 。 /* main( ) 函数对矩阵乘法的实现 */ void main() RLSMatrix * M,* N,* Q; if (!(M=(RLSMatrix *)malloc(sizeof(RLSMatrix) exit(ERROR); if (!(N=(RLSMatrix *)malloc(sizeof(RLSMatrix) exit(ERROR); if (!(Q=(RLSMatrix *)malloc(sizeof(RLSMatrix) exit(ERROR); if (CreateSMatrix_RL(M) PrintSMat
6、rix_RL(M); /* 打印出 M */ printf(“/nput out N:/n“); PrintSMatrix_RL(N); /* 打印出 N */ if (MultSMatrix_RL(M,N,Q) printf(“/n/n/n M * N :/n“); PrintSMatrix_RL(Q); /* 计算结果 */ else printf(“M.mu and N.nu are not mathing/n“); else printf(“input error./n“); /* 基本操作的算法描述 */ status CreateSMatrix_RL(RLSMatrix * mat
7、rix) / 创建一个稀疏矩阵； / 输入行数、列数，支持乱序输入三元组，并计数； int num=0,p,q,min,temp; / 中间变量； int row; printf(“input the total row and col:/n“); scanf(“%d%d“, / 输入行数、列数； if (matrix-muMAXRC) return ERROR; printf(“row col val/n“); scanf(“%d%d%d“, while (matrix-datanum+1.i) / 乱序输入三元 组； if (+numMAXSIZE) return ERROR; scanf
8、(“%d%d%d“, matrix-tu=num; / num的值即为此 矩阵的非零元个数； for (p=1;ptu-1;+p) / 按行为 主序依次重新排列非零元 min=p; / 使较小的行数、列数的元的 序号 min 为当前值 p； for (q=p+1;qtu;+q) / 开始依次比较； if (matrix-datamin.imatrix-dataq.i|(matrix-datamin .i=matrix-dataq.i / 在乱序的三 元表中，始终保证min 是较小的行列数的序号； temp=matrix-datamin.i; / 交换行值； matrix-datamin.i=m
9、atrix-datap.i; matrix-datap.i=temp; temp=matrix-datamin.j; / 交换列值； matrix-datamin.j=matrix-datap.j; matrix-datap.j=temp; temp=matrix-datamin.e; / 交换元素值； matrix-datamin.e=matrix-datap.e; matrix-datap.e=temp; for (row=1,num=0;rowmu;+row) / 记录 matrix-rposrow; matrix-rposrow=num+1; while (matrix-datanum
10、+1.i=row) +num; return OK; / 时间复杂度分析： / 1. 输入非零元： O(tu); 2. 重新排列（最坏情况 下）;O(tu*(tu-1) ; 3. 记录行逻辑表： O(mu) void PrintSMatrix_RL(RLSMatrix * matrix) / 输入矩阵，打印出矩阵的行数、列数、非零元个数，以及整个矩 阵； int row,col; int num=0; printf(“/nrow:%d col:%d number:%d/n“,matrix-mu,matrix-nu,matrix-tu); for (row=1;rowmu;+row) for (
11、col=1;colnu;+col) if (num+1tu printf(“%4d“,matrix-datanum.e); /* 当扫描到非 零元的行列值与之相等时，输出其值 */ else printf(“%4d“,NULL); /* 没有非零元的地方补 0 */ printf(“/n“); /* 每行输入完毕后， 换 行 */ / 时间复杂度： O(mu*nu). status MultSMatrix_RL(RLSMatrix * M,RLSMatrix * N,RLSMatrix * Q) / 输入两个稀疏矩阵M和 N，并初始化 Q，然后计算 M*N的值赋给 Q int arow,bro
12、w,ccol; int * ctemp; /* 以 N的列值为序号的临时数组 */ int tp,p,tq,q; /* 中间变量 */ if (M-nu!=N-mu) return ERROR; Q-mu=M-mu; /* 初始化 Q */ Q-nu=N-nu; Q-tu=0; if (!(ctemp=(int *)malloc(N-nu+1)*sizeof( int ) /* 动态建立累加器 */ exit(ERROR); if (M-tu*N-tu!=0) /* Q是非零矩阵 */ for (arow=1;arowmu;+arow) /* 逐行扫 描 */ for (ccol=1;ccol
13、nu;+ccol) ctempccol=0; /* 初始化累加器 */ Q-rposarow=Q-tu+1; if (arowmu) tp=M-rposarow+1; /* tp 是 M下一行的序号 */ else tp=M-tu+1; for (p=M-rposarow;pdatap.j; /* 对应元在 N中的行号 */ if (browmu) tq=N-rposbrow+1; /* tq是 N下一行的行号 */ else tq=N-tu+1; for (q=N-rposbrow;qdataq.j; /* 提取对应元的列号 */ ctempccol+=M-datap.e*N-dataq.e
14、; /* 两个对应元的值相乘并累 加到以列号为序号的累加器中 */ for (ccol=1;ccolnu;+ccol) /* 将此行非零元压缩入Q中 */ if (ctempccol) if (+Q-tuMAXSIZE) return ERROR; Q-dataQ-tu.i=arow; Q-dataQ-tu.j=ccol; Q-dataQ-tu.e=ctempccol; return OK; / 时间复杂度： O(M-mu*(N-nu+M-nu*N-nu+N-nu); status CreateSMatrix_RL(RLSMatrix * matrix) 这个函数用2 种算法进行了编写：第一种不支持乱序输入，而且输入很麻 烦。第二种则使得输入很方便、清楚。 总结一下函数流程： 1. 确定功能，详细描述这个功能， 即要达到哪些效果。 好的功能能够使程 序更加人性化。 2. 设计算法。 3. 尽量给出此函数的完整定义。