[DS] 트리를 이용한 희소행렬 전치 프로그램

#include <stdio.h>
#include <stdlib.h>

#define STDNUM 8                        //학번을 구성하는 숫자수
#define STDNUMCNT 6                 //학번 갯수

typedef struct _NODE{       
        int row;                                //열
        int col;                                 //행
        int data;                               //데이터
        struct _NODE *left;               //트리왼쪽노드주소
        struct _NODE *right;            //트리오른쪽노드주소
} NODE;

void setting();                              // 초기값 세팅
void outputM2();                          // 전치전 결과값 출력
void inorder(NODE*);                  // 만들어진 트리 inorder방식 탐색
NODE* insertNode(NODE*,int,int,int);        // 노드생성

int spar[STDNUM*STDNUMCNT][3];        // 희소행렬 출력
int outputM[100][100];                              // 완성된 전치희소행렬 출력 배열

void main(){
       
        int i,j, cnt = 0;               
        char stdnum[STDNUMCNT][STDNUM];
        NODE *tree = NULL;
       
        printf("학번 %d개를 차례로 임력해주세요.\n",STDNUMCNT);
       
        for(i=0;i<STDNUMCNT;i++){
                scanf("%s",&stdnum[i][0]);        //학번입력받기
        }
       
        //희소행렬을 일차원행열에 저장
        for(i=0;i<STDNUMCNT;i++){
                for(j=0;j<STDNUM;j++){
                        // 0과 NULL을 제외한 모든 수를 트리에 넣는다.
                        if((0!=(int)stdnum[i][j]-48) && (NULL!=(int)stdnum[i][j]-48)){
                                tree = insertNode(tree,(int)stdnum[i][j]-48,i,j);
                        }
                }
        }

        setting();                // 출력배열 초기값 세팅
        inorder(tree);        // 생성된 트리를 inorder방식 탐색과 전치
        printf("\n\n");
        outputM2();                // 전치된 희소행렬 출력
       
}

NODE* insertNode(NODE *t, int data, int row, int col){ //트리에 노드 생성
       
        NODE *root;
        if(t==NULL){                //root 노드 생성
                root = (NODE*)malloc(sizeof(NODE));
                root->left = NULL;
                root->right = NULL;
                root->row = row;
                root->col = col;
                root->data = data;
               
                return root;
        }
       
        if(col < t->col){        //먼저 들어간 열을 바교해 값이 적으면 왼쪽으로 간다
                t->left = insertNode(t->left,data,row,col);
                return t;
        }else{                                // 반대의 경우 오른쪽으로 데이터가 들어간다.
                t->right = insertNode(t->right,data,row,col);
                return t;
        }
}

void inorder(NODE *t){        //inorder
       
        if(t!=NULL){
                inorder(t->left);
                // 트리를 inoreder방식으로 순차적 방문 후
                // 희소행렬의 데이터를 순서쌍으로 출력
                outputM[t->col][t->row] = t->data;
                inorder(t->right);
        }
}

void setting(){                        // 출력 행렬을 위한 세팅
        int i,j;
        for(i=0;i<STDNUM;i++){
                for(j=0;j<STDNUMCNT;j++){
                        outputM[i][j] = 0;
                }
        }
}

void outputM2(){                        //결과값출력 - 전치행렬
       
        int i,j;
        for(i=0;i<STDNUM;i++){       
                for(j=0;j<STDNUMCNT;j++){
                        printf("%d",outputM[i][j]);                       
                }
                printf("\n");
        }       
}