稀疏矩阵的乘法实现.doc

稀疏矩阵的乘法实现程序：print?1 # include 2 # include 3 # define NULL 0 4 # define OK 1 5 # define ERROR 0 6 # define MAXSIZE 100 /* 矩阵中非零元的最大值 */ 7 # define MAXRC 10 /* 矩阵的最大行值 */ 8 9 typedef int status ; 10 11 /* 稀疏矩阵的行逻辑链接的顺序表存储表示 */ 12 13 typedef struct /* 非零元的三元组 */ 14 15 int i, j ; /* 非零元的行下标和列下标 */ 16 int e ; 17 Triple; 18 19 typedef struct /* 稀疏矩阵的行逻辑链接的顺序表 */ 20 21 Triple dataMAXSIZE+1; /* 非零三元组表，data0未用，以下定义的数组都是从1开始 */ 22 int rposMAXRC+1; /* 代表各行第一个非零元的序号表，其值为data的下标 */ 23 int mu,nu,tu; /* 矩阵的行数、列数、非零元的个数 */ 24 RLSMatrix; /* R:row L:logic S:sequence */ 25 26 27 /* 基本操作的函数原型的声明 */ 28 29 status CreateSMatrix_RL(RLSMatrix * matrix); 30 / 创建一个稀疏矩阵； 31 / 输入行数、列数，支持乱序输入三元组，并计数； 32 / 以行为主序进行重新排列，并记录每行起始位置于matrix-rposrow； 33 / 若非零元超过 MAXSIZE或行数超过MAXRC，则返回ERROR，否则OK； 34 35 void PrintSMatrix_RL(RLSMatrix * matrix); 36 / 输入矩阵，打印出矩阵的行数、列数、非零元个数，以及整个矩阵； 37 38 status MultSMatrix_RL(RLSMatrix * M,RLSMatrix * N,RLSMatrix * Q); 39 / 输入两个稀疏矩阵M和N，并初始化Q，然后计算M*N的值赋给Q； 40 / 如果M-mu!=N-nu或列数大于MAXRC或者计算出的非零元个数大于MAXSIZE，都返回ERROR,否则OK； 41 / 计算过程如下： 42 / 1. 由于矩阵M和Q的行数相等并且C语言以行为主序进行存储，所以以M进行逐行的扫描。 43 / 2. 使Q的此行逻辑表的序号等于其非零元个数Q.tu+1，以表示其行的首个元素的序号。 44 / 3. 从行中找到M的非零元，并以它的列值为N的行号，对N进行行的扫描，若存在，则依次计算它们，并把其值累加到一个以N中这个对应非零元的列值为序号的临时数组ctempccol中。 45 / 4. 在M的当前行完成扫描后，将ctempccol不为0的值，压入到Q矩阵的三元组，累加+Q.tu，若Q.tu大于了MAXSIZE，这返回ERROR。 46 47 /* main( ) 函数对矩阵乘法的实现 */ 48 49 void main() 50 51 RLSMatrix * M,* N,* Q; 52 if(!(M=(RLSMatrix *)malloc(sizeof(RLSMatrix) 53 exit(ERROR); 54 if(!(N=(RLSMatrix *)malloc(sizeof(RLSMatrix) 55 exit(ERROR); 56 if(!(Q=(RLSMatrix *)malloc(sizeof(RLSMatrix) 57 exit(ERROR); 58 if(CreateSMatrix_RL(M)&CreateSMatrix_RL(N) 59 60 printf(/nput out M:/n); 61 PrintSMatrix_RL(M); /* 打印出M */ 62 printf(/nput out N:/n); 63 PrintSMatrix_RL(N); /* 打印出N */ 64 if(MultSMatrix_RL(M,N,Q) 65 66 printf(/n/n/n M * N :/n); 67 PrintSMatrix_RL(Q); /* 计算结果 */ 68 69 else 70 printf(M.mu and N.nu are not mathing/n); 71 72 else 73 printf(input error./n); 74 75 76 77 /* 基本操作的算法描述 */ 78 79 status CreateSMatrix_RL(RLSMatrix * matrix) 80 / 创建一个稀疏矩阵； 81 / 输入行数、列数，支持乱序输入三元组，并计数； 82 83 int num=0,p,q,min,temp; / 中间变量； 84 int row; 85 printf(input the total row and col:/n); 86 scanf(%d%d,&matrix-mu,&matrix-nu); / 输入行数、列数； 87 if(matrix-muMAXRC) 88 return ERROR; 89 printf(row col val/n); 90 scanf(%d%d%d,&matrix-datanum+1.i,&matrix-datanum+1.j,&matrix-datanum+1.e); 91 while(matrix-datanum+1.i) / 乱序输入三元组； 92 93 if(+numMAXSIZE) 94 return ERROR; 95 scanf(%d%d%d,&matrix-datanum+1.i,&matrix-datanum+1.j,&matrix-datanum+1.e); 96 97 matrix-tu=num; / num的值即为此矩阵的非零元个数； 98 for(p=1;ptu-1;+p) / 按行为主序依次重新排列非零元 99 100 min=p; / 使较小的行数、列数的元的序号min为当前值p； 101 for(q=p+1;qtu;+q) / 开始依次比较； 102 103 if(matrix-datamin.imatrix-dataq.i|(matrix-datamin.i=matrix-dataq.i&matrix-datamin.jmatrix-dataq.j) 104 min=q; / 在乱序的三元表中，始终保证min是较小的行列数的序号； 105 106 temp=matrix-datamin.i; / 交换行值； 107 matrix-datamin.i=matrix-datap.i; 108 matrix-datap.i=temp; 109 temp=matrix-datamin.j; / 交换列值； 110 matrix-datamin.j=matrix-datap.j; 111 matrix-datap.j=temp; 112 temp=matrix-datamin.e; / 交换元素值； 113 matrix-datamin.e=matrix-datap.e; 114 matrix-datap.e=temp; 115 116 for(row=1,num=0;rowmu;+row) / 记录matrix-rposrow; 117 118 matrix-rposrow=num+1; 119 while(matrix-datanum+1.i=row) 120 +num; 121 122 return OK; 123 124 / 时间复杂度分析： 125 / 1. 输入非零元：O(tu); 2. 重新排列（最坏情况下）;O(tu*(tu-1) ; 3. 记录行逻辑表：O(mu) 126 void PrintSMatrix_RL(RLSMatrix * matrix) 127 / 输入矩阵，打印出矩阵的行数、列数、非零元个数，以及整个矩阵； 128 129 int row,col; 130 int num=0; 131 printf(/nrow:%d col:%d number:%d/n,matrix-mu,matrix-nu,matrix-tu); 132 for(row=1;rowmu;+row) 133 134 for(col=1;colnu;+col) 135 136 if(num+1tu&matrix-datanum+1.i=row&matrix-datanum+1.j=col) 137 138 +num; 139 printf(%4d,matrix-datanum.e); /* 当扫描到非零元的行列值与之相等时，输出其值 */ 140 141 else 142 printf(%4d,NULL); /* 没有非零元的地方补0 */ 143 144 printf(/n); /* 每行输入完毕后，换行 */ 145 146 147 148 / 时间复杂度：O(mu*nu). 149 150 151 152 status MultSMatrix_RL(RLSMatrix * M,RLSMatrix * N,RLSMatrix * Q) 153 / 输入两个稀疏矩阵M和N，并初始化Q，然后计算M*N的值赋给Q 154 155 int arow,brow,ccol; 156 int * ctemp; /* 以N的列值为序号的临时数组 */ 157 int tp,p,tq,q; /* 中间变量 */ 158 if(M-nu!=N-mu) 159 return ERROR; 160 Q-mu=M-mu; /* 初始化Q */ 161 Q-nu=N-nu; 162 Q-tu=0; 163 if(!(ctemp=(int *)malloc(N-nu+1)*sizeof(int) /* 动态建立累加器 */ 164 exit(ERROR); 165 if(M-tu*N-tu!=0) /* Q是非零矩阵 */ 166 167 for(arow=1;arowmu;+arow) /* 逐行扫描 */ 168 169 for(ccol=1;ccolnu;+ccol) 170 ctempccol=0; /* 初始化累加器 */ 171 Q-rposarow=Q-tu+1; 172 if(arowmu) 173 tp=M-rposarow+1; /* tp是M下一行的序号 */ 174 else 175 tp=M-tu+1; 176 for(p=M-rposarow;pdatap.j; /* 对应元在N中的行号 */ 179 if(browmu) 180 tq=N-rposbrow+1; /* tq是N下一行的行号 */ 181 else 182 tq=N-tu+1; 183 for(q=N-rposbrow;qdataq.j; /* 提取对应元的列号 */ 186 ctempccol+=M-datap.e*N-dataq.e; 187 /* 两个对应元的值相乘并累加到以列号为序号的累加器中 */ 188 189 190 for(ccol=1;ccolnu;+ccol) /* 将此行非零元压缩入Q中 */ 191 192 if(ctempccol) 193 194 if(+Q-tuMAXSIZE) 195 return ERROR; 196 Q-dataQ-tu.i=arow; 197 Q-dataQ-tu.j=ccol; 198 Q-dataQ-tu.e=