データ構造疎行列の三元群加算と高速回転アルゴリズム

48281 ワード

データ構造疎行列の三元群加算と高速回転アルゴリズム
ヘッダファイルh
#ifndef TSMATRIX_H_INCLUDED
#define TSMATRIX_H_INCLUDED
 status Initi_SMatrix(TSMatrix,int ***);
 status CreateSMatrix(TSMatrix *,int ***);
 status FastTransposeSMatrix(TSMatrix ,TSMatrix *);
 status AddSMatrix(TSMatrix,TSMatrix,TSMatrix *);
 status PrintSMatrix_T(TSMatrix);
 int comp(int,int);
 void PrintSMatrix(TSMatrix);
 #endif//TSMATRIX

main.hファイル
#include 
#include 
#define OK 1
typedef int status;
#define MAXSIZE 12500
typedef int ElemType ;//    
typedef struct
{
	int i,j;			//    ,   
	ElemType e; 		//      
}Triple;
typedef struct
{
	Triple data[MAXSIZE+1]; 	//        ,data[0]  
	int mu,nu,tu;				//      、        
}TSMatrix;

#include "TSMatrix.h"
 status scan_n_m(TSMatrix *);
int main()
{
    int **A,**B;
    srand((unsigned)time(NULL));
    TSMatrix M,N,T,Q;
    scan_n_m(&N);
    scan_n_m(&M);
    Initi_SMatrix(N,&B);
    CreateSMatrix(&N,&B);
    Initi_SMatrix(M,&A);
    CreateSMatrix(&M,&A);
    FastTransposeSMatrix(M,&T);
    AddSMatrix(M,N,&Q);
    printf("    A----------------
"
); PrintSMatrix_T(M); PrintSMatrix(M); printf(" B-----------------
"
); PrintSMatrix_T(N); PrintSMatrix(N); printf(" A T------
"
); PrintSMatrix_T(T); PrintSMatrix(T); printf("A,B Q----
"
); PrintSMatrix_T(Q); PrintSMatrix(Q); } // status scan_n_m(TSMatrix *M) { printf(" , :
"
); scanf("%d", &(*M).mu); scanf("%d",&(*M).nu); } // status Initi_SMatrix(TSMatrix M,int ***T) { *T = (int **)malloc(sizeof(int *) * (M.mu) );// for(int i = 0; i < M.nu ;i++) { *(*T + i) = (int *)malloc(sizeof(int) * M.nu);// } } // M status CreateSMatrix(TSMatrix *M,int ***T) { int k; int a=1; M->tu = 0; for(int i = 0;i < M->mu;i++) { for(int j = 0;j < M->nu;j++) { k= rand()%100; (*T)[i][j] = rand()%100 > 80 ? k : 0; if((*T)[i][j] != 0) { M->data[a].i = i + 1; // M->data[a].j = j + 1; // M->data[a].e = (*T)[i][j]; // M->tu ++; a++; } } } return OK; } // AddSMatrix int comp(int c1,int c2) { int i; if(c1<c2) i=1; else if(c1==c2) i=0; else i=-1; return i; } // Q=M+N status AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q) { Triple *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.data[1]; // Mp M , Np=&N.data[1]; // Np N , Me=&M.data[M.tu]; // Me M Ne=&N.data[N.tu]; // Ne N Qh=Qe=(*Q).data; // Qh、Qe Q while(Mp <= 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: *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 OK; } // M, void DestroySMatrix(TSMatrix *M) { (*M).mu=0; (*M).nu=0; (*M).tu=0; } // status FastTransposeSMatrix(TSMatrix M,TSMatrix *T) { int num[M.nu]; int cpot[M.nu]; T->mu = M.nu; T->nu = M.mu; T->tu = M.tu; if(T->tu) { for(int col = 1;col <= M.nu; ++col) { num[col] = 0; } for(int t = 1; t <=M.tu;t++)// M { ++num[M.data[t].j]; } cpot[1] = 1; // col T for(int col = 2;col <= M.nu;++col) { cpot[col] = cpot[col-1] + num[col - 1]; } for(int p = 1;p<=M.tu;p++) { int col = M.data[p].j; int q = cpot[col]; T->data[q].j = M.data[p].i; T->data[q].i = M.data[p].j; T->data[q].e = M.data[p].e; ++cpot[col]; }//for }//if return OK; }//FastTransporeSMatrix // M, void PrintSMatrix(TSMatrix M) { int i; printf("
%d , %d , %d 。
"
,M.mu, M.nu, M.tu); printf("======================
"
); printf("%4s %4s %8s
"
, "i", "j", "e"); printf("======================
"
); for(i=1;i<=M.tu;i++) printf("%4d %4d %8d
"
, M.data[i].i, M.data[i].j, M.data[i].e); printf("======================
"
); } // status PrintSMatrix_T(TSMatrix M) { int i , j,k = 1; for(i=1 ;i<=M.mu;i++) { for(j=1;j<=M.nu;j++) { if(M.data[k].i == i&&M.data[k].j == j) { printf("%2d ",M.data[k].e); k++; } else { printf("%2d ",0); } } printf("
"
); } } //--------------------------------------------------------------------- // /*status 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.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; }*/ // M T int CopySMatrix(TSMatrix M,TSMatrix *T) { (*T)=M; return 1; }

初めてブログを書いたので、あまり使えないかもしれません.