Data Structure Chapter 3 - 순차 자료구조.md

Data Structure Chapter 3

순차 자료구조

• 순차 자료구조와 연결 자료구조의 비교

구분	순차 자료구조	연결 자료구조
메모리 저장 방식	논리순서에 맞추어 메모리에 빈틈없이 나열	논리순서에 따라 링크로 연결
연산 특징	삽입, 삭제 연산시에 비용이 선형으로 증가	삽입, 삭제 연산시에도 링크 정보만 변경
선호 연산	읽기, 쓰기, 순차접근
오버헤드	삽입, 삭제: 물리적 이동이 야기됨
프로그램 기법	배열	포인터
액세스	인덱스로 주소를 쉽게 액세스

• C는 다차원 배열을 행 우선으로 메모리에 저장.

• 3-5, 희소행렬의 전치 연산하기

#include <stdio.h>

typedef struct {
    int row;
    int col;
    int value;
} term;

/* term smTranpose~ 와 같이 작성하지 않는 이유는 함수 안에서 정의된 배열은
 * 함수가 종료되면서 메모리에서 반환되기 때문인 것 같다.
 * 그럴 경우에는 malloc으로 수동 할당 후 그 포인터를 반환하면 되는 모양
 */
void smTranspose(term a[], term b[]) {

    int m, n, v, i, j, p;
    /* term 배열의 첫 번째 요소는 행렬의 행과 열, 0이아닌 값의 개수 */
    m = a[0].row;
    n = a[0].col;
    v = a[0].value;
    b[0].row = n;
    b[0].col = m;
    b[0].value = v;
    /* 애초에 전처리되어 들어오는데 불필요한 조건식  */
    if (v>0) {
        p=1;
        for (i=0; i<n; i++)
            for (j=1; j<=v; j++)
                if (a[j].col == i) {
                    b[p].row = a[j].col;
                    b[p].col = a[j].row;
                    b[p].value = a[j].value;
                    p++;
                }
    }
}


int main () {

    int a[10][8] = { 0, }, b[8][10] = { 0, }, i=0, j=0;
    int k = 0;
    term za[10], zb[10];
    za[0].row = 10;
    za[0].col = 8;
    za[0].value = 9;

    /*  init matrix a */
    for (i=0; i<10; i++) {
        for (j=0; j<8; j++) {
            a[i][j] = (i==j?i:0);
        }
    }

    /*  print matrix a */
    for (i=0; i<10; i++) {
        for (j=0; j<8; j++) {
            printf("%d ", a[i][j]);
            printf("%c", (j!=7?' ':'\n'));
        }
    }

    /*  make zipped array,  */
    for (i=0; i<10; i++) {
        for (j=0; j<8; j++) {
            if (a[i][j] != 0) {
                za[++k].row = i;
                za[k].col = j;
                za[k].value = a[i][j];
            }
        }
    }

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

    printf("\n");
    smTranspose(za, zb);

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

    /*  init matrix b */
    for (i=0; i<8; i++) {
        for (j=0; j<10; j++) {
            printf("%d ", b[i][j]);
            printf("%c", (j!=9?' ':'\n'));
        }
    }

    return 0;
}

0  0  0  0  0  0  0  0
0  1  0  0  0  0  0  0
0  0  2  0  0  0  0  0
0  0  0  3  0  0  0  0
0  0  0  0  4  0  0  0
0  0  0  0  0  5  0  0
0  0  0  0  0  0  6  0
0  0  0  0  0  0  0  7
0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0
< 10 8 9 >
< 1 1 1 >
< 2 2 2 >
< 3 3 3 >
< 4 4 4 >
< 5 5 5 >
< 6 6 6 >
< 7 7 7 >

< 8 10 9 >
< 1 1 1 >
< 2 2 2 >
< 3 3 3 >
< 4 4 4 >
< 5 5 5 >
< 6 6 6 >
< 7 7 7 >
0  0  0  0  0  0  0  0  0  0
0  1  0  0  0  0  0  0  0  0
0  0  2  0  0  0  0  0  0  0
0  0  0  3  0  0  0  0  0  0
0  0  0  0  4  0  0  0  0  0
0  0  0  0  0  5  0  0  0  0
0  0  0  0  0  0  6  0  0  0
0  0  0  0  0  0  0  7  0  0