희소 행렬 쾌속 전환

제목 설명
희소 행렬 의 저장 소 는 2 차원 배열 로 모든 요 소 를 저장 하 는 것 이 좋 지 않다. 그러면 많은 저장 공간 을 낭비 할 것 이다.그래서 1 차원 배열 로 0 이 아 닌 요 소 를 저장 할 수 있 습 니 다.이 1 차원 배열 의 요소 유형 은 3 원 그룹 으로 0 요소 가 아 닌 이 희소 행렬 의 위치 (줄 번호 와 열 번호 쌍) 와 이 원 그룹의 값 으로 구성 된다.
행렬 전환 은 행렬 줄 과 열 에 있 는 요 소 를 바 꾸 는 것 이다.알고리즘 5.1 의 구체 적 인 방법 을 참고 하여 mu 와 nu 는 각각 희소 행렬 의 줄 수 와 열 수 를 대표 하고 그 시간 복잡 도가 O (mu) 인 것 을 발견 하기 어렵 지 않다.×nu)。0 원 이 아 닌 개수 tu 와 mu×nu 동 수량 급 시 알고리즘 5.1 의 시간 복잡 도 는 O (mu) 로 상승 합 니 다.×nu
2)。따라서 빠 른 희소 행렬 변환 알고리즘 을 사용 해 야 한다.
지금 은 희소 행렬 을 빠르게 전환 하 는 알고리즘 을 실현 하 세 요.다음은 희소 행렬 의 빠 른 전환 알고리즘 설명 입 니 다.
입력
입력 한 첫 번 째 줄 은 두 개의 정수 r 와 c (r < 200, c < 200, r * c < = 12500) 로 각각 0 이 많은 희소 행렬 을 포함 하 는 줄 수 와 열 수 를 나타 낸다.다음은 r 줄 이 있 고 줄 마다 c 개의 정수 가 있 으 며 빈 칸 으로 구분 하여 이 희소 행렬 의 각 요 소 를 나타 낸다.
출력
읽 기 전용 희소 행렬 의 변환 행렬 을 출력 합 니 다.출력 은 모두 c 줄 이 있 고 줄 마다 r 개의 정수 가 있 으 며 정수 마다 빈 칸 을 출력 합 니 다.줄 끝 출력 줄 바 꾸 기 에 주의 하 세 요.
샘플 입력

6 7

0 12 9 0 0 0 0

0 0 0 0 0 0 0

-3 0 0 0 0 14 0

0 0 24 0 0 0 0

0 18 0 0 0 0 0

15 0 0 -7 0 0 0

샘플 출력

0 0 -3 0 0 15 

12 0 0 0 18 0 

9 0 0 24 0 0 

0 0 0 0 0 -7 

0 0 0 0 0 0 

0 0 14 0 0 0 

0 0 0 0 0 0 

제시 하 다.
힌트 거두 기 [-]
알림: 이 알고리즘 은 알고리즘 5.1 보다 두 개의 보조 벡터 만 더 사 용 했 습 니 다.이 알고리즘 의 시간 복잡 도 에 대해 알고리즘 중 4 개의 병렬 된 단일 순환 이 있 고 순환 횟수 는 각각 nu 와 tu 이기 때문에 전체적인 시간 복잡 도 는 O (nu + tu) 이다.희소 행렬 의 비 0 원 개수 tu 와 mu×nu 의 수량 등급 과 동시에 그 시간 복잡 도 는 O (mu) 이다.×nu) 고전 알고리즘 과 시간 복잡 도가 같 습 니 다.왜 전환 알고리즘 에서 열 로 어 릴 때 부터 큰 것 으로 전환 하 는 지 이해 하 세 요.실제로 하나의 순환 만 있 으 면 전 치 를 완성 할 수 있 고 열 을 어 릴 때 부터 크게 처리 하지 않 아 도 된다. 전 치 된 행렬 은 내용 이 정확 하지만 요소 의 순서 가 달라 져 후속 적 인 각종 처리 작업 에서 복잡 도 를 높 일 수 있다.한편, 본 문제 에서 열 에 따라 작은 것 부터 큰 것 까지 순서대로 처리 하지 않 으 면 수출 이 어렵 고 수출 의 복잡 도 를 크게 증가 할 것 이다.요약: 희소 행렬 은 행렬 응용 에서 매우 중요 한 부분 으로 그 요소 가 희소 한 특수성 으로 인해 우 리 는 전통 적 인 행렬 알고리즘 보다 더욱 빠 른 특수 알고리즘 을 얻 을 수 있다.이것 도 이 장 뒤의 제목 에서 구 현 될 것 이다.

#include
#define MAXSIZE 12500
int num[MAXSIZE+1],cpot[MAXSIZE+1];
typedef struct
{
    int i,j;//       ，  
    int e;//      
}Triple;
typedef struct
{
    Triple data[MAXSIZE+1];//       ，data[0]  
    int mu,nu,tu;//     ，  ，       
}TSMatrix;

TSMatrix TransposeSMatrix(TSMatrix M,TSMatrix T);
TSMatrix CreatSMatrix(TSMatrix M);

TSMatrix CreatSMatrix(TSMatrix M)
{
    int p,q,k,a;
    M.tu=0,k=1;
    for( p=1;p<=M.mu;p++)
        for( q=1;q<=M.nu;q++)
        {
            scanf("%d",&a);
            if(a!=0)
            {
                M.data[k].i=p;
                M.data[k].j=q;
                M.data[k].e=a;
                k++;
                M.tu++;
            }
         }
         return M;
}
TSMatrix TransposeSMatrix(TSMatrix M,TSMatrix T)
{
    int col,t,p,q;
    T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
    if(T.tu)
    {
        for(col=1;col<=M.nu;++col) num[col]=0;
        for(t=1;t<=M.tu;t++)  ++num[M.data[t].j];
        cpot[1]=1;
        for(col=2;col<=M.tu;col++)  cpot[col]=cpot[col-1]+num[col-1];
        for(p=1;p<=M.tu;p++)
        {
            col=M.data[p].j;
            q=cpot[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;
            ++cpot[col];
        }

    }
    return T;
}
int main()
{
    int k=1,p,q;
    TSMatrix M,T;
    scanf("%d%d",&M.mu,&M.nu);
    M=CreatSMatrix(M);
    T=TransposeSMatrix(M,T);
    for(p=1;p<=T.mu;p++)
    {
        for(q=1;q<=T.nu;q++)
        {
           if(T.data[k].i==p&&T.data[k].j==q)
           {
                printf("%d ",T.data[k].e);
                k++;
           }
           else
                printf("0 ");
        }
        printf("
");
    }
    return 0;
}