희소행렬

/* 100*100 MATRIX에서의 SIMPLE_TRANSPOS와 FAST_TRANSPOS의 시간 비교 */

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

#define MAX_TERMS 1000
#define MAX_COL 120

typedef struct {
int row;
int col;
int value;
} term;
term a, b;

void simple_transpose(term a[], term b[]);
void fast_transpose(term a[], term b[]);
void displayMatrix(term[]);

void main()
{
term a[MAX_TERMS+1];
term b[MAX_TERMS+1];

int i, x=1;
long double ct, tt;
clock_t start, end;

FILE *fp;

while(x) {
printf("Input Char (S = simple_transpos, F = fast_transpos, E = exit) : ");
scanf("%c", &x);

switch(x) {
case 'S' :
if( !(fp = fopen("rnd.txt", "r")) ) {
printf("error");
exit(1);
}
a[0].row = 120;
a[0].col = 120;
a[0].value = 1000;

for(i = 1 ; i < 1001 ; i++) {
fscanf(fp,"%d %d %d\n",&a[i].row, &a[i].col, &a[i].value);
}
fclose(fp);

start = clock();
simple_transpose(a, b);
printf("**simple_transpose**\n");
displayMatrix(b);
end = clock();

ct = (long double)(end - start) / (long double)CLK_TCK;
printf("SIMPLE_TRANSPOS SPEND TIME : %1fsec\n", ct);
break;
case 'F' :
if( !(fp = fopen("rnd.txt", "r")) ) {
printf("error");
exit(1);
}
a[0].row = 120;
a[0].col = 120;
a[0].value = 1000;

for(i = 1 ; i < 1001 ; i++) {
fscanf(fp,"%d %d %d\n",&a[i].row, &a[i].col, &a[i].value);
}
fclose(fp);

start = clock();
fast_transpose(a, b);
printf("\n**fast_transpose**\n");
displayMatrix(b);
end = clock();
tt = (long double)(end - start) / (long double)CLK_TCK;
printf("FAST_TRANSPOS SPEND TIME : %1fsec\n", tt);
break;
case 'E' :
exit(1);
}
}
b[MAX_TERMS] = a[MAX_TERMS];
}

void simple_transpose(term a[], term b[])
{
int n, i, j;
int currentb;


n = a[0].value;
b[0].row = a[0].col;
b[0].col = a[0].row;
b[0].value = n;

if(n > 0) {
currentb = 1;
for(i = 0 ; i < a[0].col ; i++)
for(j = 1 ; j <= n ; j++)
if(a[j].col == i) {
b[currentb].row = a[j].col;
b[currentb].col = a[j].row;
b[currentb].value = a[j].value;
currentb++;
}
}
}

void fast_transpose(term a[], term b[])
{
int row_terms[MAX_COL];
int starting_pos[MAX_COL];
int i, j;
int num_cols = b[0].row = a[0].col;
int num_terms = b[0].value = a[0].value;

b[0].col = a[0].row;

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++) {
j = starting_pos[a[i].col]++;
b[j].row = a[i].col;
b[j].col = a[i].row;
b[j].value = a[i].value;
}
}
}

void displayMatrix(term b[])
{
int i;

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