[데이터 구조의 여행] 희소 행렬 의 빠 른 전환

설명:
    희소 행렬 의 빠 른 전환 알고리즘 의 핵심 은 하나의 배열 num 으로 원래 행렬 의 각 열 에 0 원 이 아 닌 개 수 를 기록 하고 다른 배열 cpos 로 원 행렬 의 첫 번 째 비 0 원 이 새 행렬 에 있 는 위 치 를 기록 하여 빠 른 전환 의 목적 을 달성 하 는 것 이다.
    이런 방법 으로 주로 희망 이다. 행렬 이 전 환 된 후에 도 저장 순 서 는 줄 에 따라 저장 된다.
1. 구현 및 코드 설명
    위의 핵심 알림 에 따 르 면 다음 과 같은 코드 가 있 을 수 있 습 니 다. 아래 코드 의 주석 은 이미 매우 상세 하기 때문에 모든 부분 이 실현 하 는 기능 을 독립 시 키 지 않 습 니 다.

#include
#include
#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define TRUE 2
#define FALSE -2

typedef int ElemType;
typedef int Status;

typedef struct{ //            
	int i, j;	//        
	ElemType e;	//      
} Triple;		//                

typedef struct{		//        
	Triple *data;	//data ，               
	int mu, nu, tu;	//     、         
} TSMatrix;			//            

 /*
 	0	14	0	0	-5
 	0	-7	0	0	0
 	36	0	0	28	0
 	
 	mu = 3; nu = 5; tu = 5
*/

Status CreateSMatrix(TSMatrix &M){	//         
	M.tu = 5;
	
	M.data = (Triple*)malloc(sizeof(Triple) * (M.tu + 1)); //data                    1，   data[0]    
	if(NULL == M.data)
		return OVERFLOW;
	M.data[1].i = 1;
	M.data[1].j = 2;
	M.data[1].e = 14;
	
	M.data[2].i = 1;
	M.data[2].j = 5;
	M.data[2].e = -5;
	
	M.data[3].i = 2;
	M.data[3].j = 2;
	M.data[3].e = -7;
	
	M.data[4].i = 3;
	M.data[4].j = 1;
	M.data[4].e = 36;
	
	M.data[5].i = 3;
	M.data[5].j = 4;
	M.data[5].e = 28;
	
	M.mu = 3;
	M.nu = 5;
	
	return OK;
}

Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){ //         ，     M     T 
	int j, p, q, t;	
	/*j         ，cops[j]，                             （cops[j]++），      ； 
	p           ，      ； 
	q  cops[j]，       ，       ；
	t       。 
	*/
	int *num;	//            
	int *cpos;	//              T      
				//cops[j]++           ，       
	
	T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;	//     T 
	
	T.data = (Triple*)malloc(sizeof(Triple)*(T.nu + 1));
	
	num = (int*)malloc((M.nu + 1)*sizeof(int));	//num cpos           1，      0    
	cpos = (int*)malloc((M.nu + 1)*sizeof(int));
	
	if(num == NULL || cpos == NULL)
		return OVERFLOW;
	
	if(T.tu != 0){
		for(j = 1; j <= M.nu; j++)	//   num   
			num[j] = 0;
		for(t = 1;t <= M.tu; t++)	// M             
			num[M.data[t].j]++;		//     num[1]~num[5]，    num       0 
		
		cpos[1] = 1;	//       
		for(j = 2;j <= M.nu; j++)	//           T.data      
			cpos[j] = cpos[j-1] + num[j-1];	//             
		
		for(p = 1; p <= M.tu; p++){		//       ，         
			j = M.data[p].j;	//j            ，  cops   
			q = cpos[j];		//       ，        cpos[j] 
			T.data[q].i = M.data[p].j;	//    
			T.data[q].j = M.data[p].i;	//    
			T.data[q].e = M.data[p].e;	//   ，      ，             
										
			cpos[j]++;	//cops[j]++           ，      ，           
		}				//     for   ，     ， j   ，cpos[j]         
	} 
	free(num);
	free(cpos);
	return OK;
}

int main(void){
	int i,j;
	
	TSMatrix M;
	TSMatrix T;
	CreateSMatrix(M);	
	FastTransposeSMatrix(M, T);
	
	printf("
");
	return 0;
}

    C free 등 컴 파 일 러 로 컴 파 일 러 를 실행 할 수 있 으 나 시간 관계 상 위 코드 에는 전 환 된 매트릭스 로 인쇄 된 코드 가 제시 되 어 있 지 않 아 스스로 추가 할 수 있 으 며, 물론 새로운 매트릭스 T 의 data 필드 의 수치 변 화 를 디 버 깅 하 는 방법 으로 감시 할 수도 있다.
2. 테스트
    테스트 는 위의 제시 에 따라 하면 됩 니 다. 시간 관계 입 니 다. 여 기 는 테스트 를 하지 않 고 다음 에 시간 이 있 으 면 다시 보충 합 시다.