1、/*數據結構C語言版 稀疏矩陣的三元組順序表存儲表示和實現 P98編譯環境：Dev-C+ 4.9.9.2日期：2011年2月8日 */typedef int ElemType;/ 稀疏矩陣的三元組順序表存儲表示 #define MAXSIZE 100 / 非零元個數的最大值 typedef structint i,j;/ 行下標,列下標 ElemType e; / 非零元素值 Triple;typedef structTriple dataMAXSIZE+1; / 非零元三元組表,data0未用 int mu,nu,tu;/ 矩陣的行數、列數和非零元個數 TSMatrix;/ 創建稀疏矩陣Mi

2、nt CreateSMatrix(TSMatrix *M)int i,m,n;ElemType e;int k;printf("請輸入矩陣的行數,列數,非零元素個數：（逗號）n");scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu);(*M).data0.i=0;/ 為以下比較順序做準備 for(i = 1; i <= (*M).tu; i+)doprintf("請按行序順序輸入第%d個非零元素所在的行(1%d),""列(1%d),元素值：(逗號)n&quo

3、t;, 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).datai-1.i | m = (*M).datai-1.i&& n <= (*M).datai-1.j) / 行或列的順序有錯 k=1;while(k);(*M).datai.i = m;/行下標(*M).datai.j = n;/列下標(*M).d

4、atai.e = e;/該下標所對應的值return 1;/ 銷毀稀疏矩陣M，所有元素置空void DestroySMatrix(TSMatrix *M) (*M).mu=0;(*M).nu=0;(*M).tu=0;/ 輸出稀疏矩陣Mvoid PrintSMatrix(TSMatrix M)int i;printf("n%d行%d列%d個非零元素。n",M.mu,M.nu,M.tu);printf("%4s%4s%8sn", "行", "列", "元素值");for(i=1;i<=M.tu

5、;i+)printf("%4d%4d%8dn",M.datai.i,M.datai.j,M.datai.e);/ 由稀疏矩陣M復制得到Tint CopySMatrix(TSMatrix M,TSMatrix *T) (*T)=M;return 1;/ AddSMatrix函數要用到int comp(int c1,int c2) int i;if(c1<c2)i=1;else if(c1=c2)i=0;elsei=-1;return i;/ 求稀疏矩陣的和Q=M+Nint AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q) Tri

6、ple *Mp,*Me,*Np,*Ne,*Qh,*Qe;if(M.mu!=N.mu)return 0;if(M.nu!=N.nu)return 0;(*Q).mu=M.mu;(*Q).nu=M.nu;Mp=&M.data1;/ Mp的初值指向矩陣M的非零元素首地址 Np=&N.data1;/ Np的初值指向矩陣N的非零元素首地址 Me=&M.dataM.tu;/ Me指向矩陣M的非零元素尾地址 Ne=&N.dataN.tu;/ Ne指向矩陣N的非零元素尾地址 Qh=Qe=(*Q).data;/ Qh、Qe的初值指向矩陣Q的非零元素首地址的前一地址 while(M

7、p <= Me && Np <= Ne)Qe+;switch(comp(Mp->i,Np->i)case 1: *Qe=*Mp;Mp+;break;case 0: / M、N矩陣當前非零元素的行相等,繼續比較列switch(comp(Mp->j,Np->j) case 1: *Qe=*Mp;Mp+;break;case 0: *Qe=*Mp;Qe->e+=Np->e;if(!Qe->e) / 元素值為0，不存入壓縮矩陣 Qe-;Mp+;Np+;break;case -1: *Qe=*Np;Np+;break;case -1:

8、 *Qe=*Np;Np+;if(Mp>Me) / 矩陣M的元素全部處理完畢 while(Np<=Ne)Qe+;*Qe=*Np;Np+;if(Np>Ne) / 矩陣N的元素全部處理完畢 while(Mp<=Me)Qe+;*Qe=*Mp;Mp+;(*Q).tu=Qe-Qh; / 矩陣Q的非零元素個數 return 1;/ 求稀疏矩陣的差Q=M-Nint SubtSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q) int i;for(i=1;i<=N.tu;i+)N.datai.e*=-1;AddSMatrix(M,N,Q);retur

9、n 1;/ 求稀疏矩陣的乘積Q=M*Nint MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q) int i,j,h=M.mu,l=N.nu,Qn=0;/ h,l分別為矩陣Q的行、列值,Qn為矩陣Q的非零元素個數，初值為0 ElemType *Qe;if(M.nu!=N.mu)return 0;(*Q).mu=M.mu;(*Q).nu=N.nu;Qe=(ElemType *)malloc(h*l*sizeof(ElemType); / Qe為矩陣Q的臨時數組 / 矩陣Q的第i行j列的元素值存于*(Qe+(i-1)*l+j-1)中，初值為0 for(i=

10、0;i<h*l;i+)*(Qe+i)=0; / 賦初值0 for(i=1;i<=M.tu;i+) / 矩陣元素相乘，結果累加到Qe for(j=1;j<=N.tu;j+)if(M.datai.j=N.dataj.i)*(Qe+(M.datai.i-1)*l+N.dataj.j-1) +=M.datai.e * N.dataj.e;for(i=1;i<=M.mu;i+)for(j=1;j<=N.nu;j+)if(*(Qe+(i-1)*l+j-1)!=0)Qn+;(*Q).dataQn.e=*(Qe+(i-1)*l+j-1);(*Q).dataQn.i=i;(*Q).

11、dataQn.j=j;free(Qe);(*Q).tu=Qn;return 1;/ 算法5.1 P99/ 求稀疏矩陣M的轉置矩陣T。int TransposeSMatrix(TSMatrix M,TSMatrix *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.data

12、p.i;(*T).dataq.e=M.datap.e;+q;return 1;/ 算法5.2 P100/ 快速求稀疏矩陣M的轉置矩陣T。int FastTransposeSMatrix(TSMatrix M,TSMatrix *T) int p,q,t,col,*num,*cpot;num=(int *)malloc(M.nu+1)*sizeof(int);/ 生成數組（0不用） cpot=(int *)malloc(M.nu+1)*sizeof(int);/ 生成數組（0不用） (*T).mu=M.nu;(*T).nu=M.mu;(*T).tu=M.tu;if(*T).tu)for(col=

13、1;col<=M.nu;+col)numcol=0; / 設初值 for(t=1;t<=M.tu;+t) / 求M中每一列含非零元素個數 +numM.datat.j;cpot1=1;/ 求第col列中第一個非零元在(*T).data中的序號for(col=2;col<=M.nu;+col) cpotcol=cpotcol-1+numcol-1;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;+cp

14、otcol;free(num);free(cpot);return 1;int main()TSMatrix A,B,C;printf("創建矩陣A: ");CreateSMatrix(&A);PrintSMatrix(A);printf("由矩陣A復制矩陣B: ");CopySMatrix(A,&B);PrintSMatrix(B);DestroySMatrix(&B);printf("銷毀矩陣B后:n");PrintSMatrix(B);printf("重創矩陣B:(注意與矩陣A的行、列數相同，這

15、樣方便后面的測試""行、列分別為%d,%d)n", A.mu, A.nu);CreateSMatrix(&B);PrintSMatrix(B);printf("矩陣C1(A+B): ");AddSMatrix(A,B,&C);PrintSMatrix(C);DestroySMatrix(&C);printf("矩陣C2(A-B): ");SubtSMatrix(A,B,&C);PrintSMatrix(C);DestroySMatrix(&C);printf("矩陣C3(A的

16、轉置): ");TransposeSMatrix(A,&C);PrintSMatrix(C);DestroySMatrix(&A);DestroySMatrix(&B);DestroySMatrix(&C);printf("創建矩陣A2: ");CreateSMatrix(&A);PrintSMatrix(A);printf("創建矩陣B3:(行數應與矩陣A2的列數相同=%d)n",A.nu);CreateSMatrix(&B);PrintSMatrix(B);printf("矩陣C5(

17、A*B): ");MultSMatrix(A,B,&C);PrintSMatrix(C);DestroySMatrix(&A);DestroySMatrix(&B);DestroySMatrix(&C);printf("創建矩陣A: ");CreateSMatrix(&A);PrintSMatrix(A);FastTransposeSMatrix(A,&B);printf("矩陣B(A的快速轉置): ");PrintSMatrix(B);DestroySMatrix(&A);Destroy

18、SMatrix(&B);system("pause");return 0;/*輸出效果：創建矩陣A: 請輸入矩陣的行數,列數,非零元素個數：（逗號）3,3,3請按行序順序輸入第1個非零元素所在的行(13),列(13),元素值：(逗號)1,1,1請按行序順序輸入第2個非零元素所在的行(13),列(13),元素值：(逗號)1,3,2請按行序順序輸入第3個非零元素所在的行(13),列(13),元素值：(逗號)3,3,33行3列3個非零元素。 行 列 元素值 1 1 1 1 3 2 3 3 3由矩陣A復制矩陣B:3行3列3個非零元素。 行 列 元素值 1 1 1 1 3 2

19、 3 3 3銷毀矩陣B后:0行0列0個非零元素。 行 列 元素值重創矩陣B:(注意與矩陣A的行、列數相同，這樣方便后面的測試行、列分別為3,3)請輸入矩陣的行數,列數,非零元素個數：（逗號）3,3,3請按行序順序輸入第1個非零元素所在的行(13),列(13),元素值：(逗號)1,2,1請按行序順序輸入第2個非零元素所在的行(13),列(13),元素值：(逗號)2,1,2請按行序順序輸入第3個非零元素所在的行(13),列(13),元素值：(逗號)3,1,33行3列3個非零元素。 行 列 元素值 1 2 1 2 1 2 3 1 3矩陣C1(A+B):3行3列6個非零元素。 行 列 元素值 1 1 1 1 2 1 1 3 2 2 1 2 3 1 3 3 3 3矩陣C2(A-B):3行3列6個非零元素。 行 列 元素值 1 1 1 1 2 -1 1 3 2 2 1 -2 3 1 -3 3 3 3矩陣C3(A的轉置):3行3列3個非