교재에 나온 mmult가 틀린 점이 있어 이를 수정하여 동작시킨 코드입니다.

'2008년 2학기 자료구조 - Flow Chart - mmult'

#include "stdio.h"
#include "stdlib.h"
#define MAX_TERMS 101 // 최대 항의 수 + 1
#define MAX_COL 50 // 최대 열의 수 + 1
#define COMPARE(x, y) (((x) < (y)) ? -1 : ((x) == (y))? 0 : 1)

// global 변수
typedef struct {
          int col;
          int row;
          int value;
} term;

int pos = 0;

// 함수의 선언
void fast_transpose(term a[], term b[]);
void insert(int col, int row, int value, term a[]);
//void sparse_matrix(int row, int col, int matrix[][3], term a[]);
void sparse_matrix(int matrix[][3], term a[]);
void print_matrix(int row, int col);
void storeSum(term d[], int *totalD, int row, int column, int *sum);
void my_print_matrix(term b[]);
void mmult(term a[], term b[], term d[]);

int main(void)
{
// 입력값
    int matrix[][3] = {
        {6,6,8},{0,0,15},{0,4,91},{1,1,11},
        {2,1,3},{2,5,28},{3,0,22},{3,2,-6},
        {5,0,-15}
    };
/*
    int matrix1[][3] = {
        {3,3,4},{0,0,1},{0,2,2},{1,2,3},
        {2,1,4}
    };

    int matrix2[][3] = {
        {3,2,4},{0,0,1},{0,1,2},{1,0,3},
        {2,1,4}
    };*/
    term a[MAX_TERMS], b[MAX_TERMS], d[MAX_TERMS];

    sparse_matrix(matrix, a);
          //sparse_matrix(matrix1, a);
          //sparse_matrix(matrix2, b);
          // 초기에 입력된 행렬을 보여준다
//          print_matrix(row, col, a);

          // 행렬을 원소쌍으로 바꾼다
          //sparse_matrix(row, col);
            my_print_matrix(a);
          // 행렬의 빠른전치
          fast_transpose(a, b);

          my_print_matrix(b);
          // 전치행렬의 원소를 보여준다

          mmult(a, b, d);

            my_print_matrix(d);
          //for (i = 0; i <= b[0].value; i++)
          //        printf("row = %d col = %d value = %d \n", b[i].row, b[i].col, b[i].value);

    return 0;
}

void my_print_matrix(term b[])
{
    int i;
    for (i = 0; i <= b[0].value; i++)
                  printf("row = %d col = %d value = %d \n", b[i].row, b[i].col, b[i].value);

    printf("\n\n");
}
/*
void print_matrix(int row, int col)
{
          int i, j;

          printf("\n %d x %d Matrix \n", row, col);

          for (i = 0; i < row; i++)
          {
                    putchar('[');

                    for (j = 0; j < col; j++)
                              printf("%4d", matrix[i][j]);

                    putchar(']');
                    putchar('\n');
          }
          putchar('\n');
}*/

void sparse_matrix(int matrix[][3], term a[])
{
          int i, j = matrix[0][2], count = 0;

          /*
          for (i = 0; i < row; i++)
          {
                    for (j = 0; j < col; j++)
                    {
                              if (matrix[i][j] == 0)
                                        continue;

                              insert(i, j, matrix[i][j], a);
                              count++;
                    }
          }
          */
          for(i = 0 ; i <= j ; i++)
          {
              insert(matrix[i][1], matrix[i][0], matrix[i][2], a);
          }
          // 0이 아닌 항의 총 갯수를 저장한다
          //a[0].value = count;
          pos = 0;
}

void fast_transpose(term a[], term b[])
{
          // a를 전치시켜 b에 저장
          int row_terms[MAX_COL];
          int starting_pos[MAX_COL];
          int num_cols = a[0].col;
          int num_terms = a[0].value;
          int i, sp;

          b[0].row = num_cols;
          b[0].col = a[0].row;
          b[0].value = num_terms;
                    // 0 이 아닌 행렬         
          if ( num_terms > 0 )
          {
                    for (i = 0; i <= num_cols; i++)
                              row_terms[i] = 0;

                    for (i = 1; i <= num_terms; i++)
                              row_terms[a[i].col]++;

                    starting_pos[0] = 1;

                    for (i = 1; i < num_cols; i++)
                              starting_pos[i] = starting_pos[i - 1] + row_terms[i - 1];

                    for (i = 1; i <= num_terms; i++)
                    {
                              sp = starting_pos[a[i].col]++;

                              b[sp].row = a[i].col;
                              b[sp].col = a[i].row;
                              b[sp].value = a[i].value;
                    }
          }
}

void insert(int col, int row, int value, term a[])
{
          a[pos].col = col;
          a[pos].row = row;
          a[pos].value = value;

          pos++;
}

void mmult(term a[], term b[], term d[])
{
int i, j, column, totalB = b[0].value, totalD = 0;
int rowsA = a[0].row, colsA = a[0].col, totalA = a[0].value;
int colsB = b[0].col, rowBegin = 1, row = a[1].row, sum = 0;
term newB[MAX_TERMS];
if (colsA != b[0].row)
{
fprintf(stderr, "Incompatible matrices\n");
exit(EXIT_FAILURE);
}
fast_transpose(b, newB);

a[totalA+1].row = rowsA;
newB[totalB+1].row = colsB;
//newB[totalB+1].col = 0;

for (i = 1 ; i <= totalA ; )
{
    column = newB[1].row;
    for (j = 1 ; j <= totalB+1; )
    {
        if (a[i].row != row)
        {
            storeSum(d, &totalD, row, column, &sum);
            i = rowBegin;
            for (; newB[j].row == column ; j++)
                ;
            column = newB[j].row;
        }
        else if (newB[j].row != column)
        {
            storeSum(d, &totalD, row, column, &sum);
            i = rowBegin;
            column = newB[j].row;
        }
        else switch (COMPARE(a[i].col, newB[j].col))
        {
            case -1:
                i++; break;
            case 0:
                sum += (a[i++].value * newB[j++].value);
                break;
            case 1:
                j++;
        }
    }
    for (; a[i].row == row ; i++)
        ;
    rowBegin = i; row = a[i].row;
}
d[0].row = rowsA;
d[0].col = colsB;
d[0].value = totalD;
}

void storeSum(term d[], int *totalD, int row, int column, int *sum)
{
    if (*sum)
        if (*totalD < MAX_TERMS)
        {
            d[++*totalD].row = row;
            d[*totalD].col = column;
            d[*totalD].value = *sum;
            *sum = 0;
        }
        else
        {
            fprintf(stderr, "Numbers of terms in product exceeds %d\n", MAX_TERMS);
            exit(EXIT_FAILURE);
        }
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.