초급편 9. 이진수

포인터 토대가 된 책

이진수

목록 구조의 응용으로

목록 구조를 기초로 다양한 데이터 구조가 만들어진다. 이 예제 중 하나가 "양방향 목록」이지만, 이렇게 2 개의 자기 참조 포인터를 가지고있다 셈이다.

struct DList {
    int data;
    struct DList * prev;
    struct DList * next;
};

이 양방향 목록의 경우에는 "하나 앞을 나타내는 포인터 '와'다음을 나타내는 포인터」의 2 개를 가지고있다. 그래서 삽입과 삭제의 경우에는 간단한 목록보다 약간 불편하지만, 어느 방향에서도 체인을 추적 할 수있어 편리하다. 이른바 "관계형 데이터베이스"데이터 구조로 매우 일반적으로 이용되고있다. 즉, 각 행의 데이터 (횡 방향)이 이것으로 표현 된 모든 행에 대한 수직 체인 역시 양방향 목록에서 표현하고 다른 갖게하면되는 것이다.

    / * 삭제 * / 
    / * at가 삭제되는 데이터 항목 * /
    at-> prev-> next = at-> next;
    at-> next-> prev = at-> prev;

    / * 삽입 * / 
    / * at 전에 ins를 삽입한다. * /
    ins-> prev = at-> prev;
    ins-> next = at;
    at-> prev-> next = ins;
    at-> prev = ins;

이처럼 자기 참조 구조체에 여러 포인터를 갖게 데이터 구조는 응용 범위가 넓다. 컴파일러와 인터프리터 소스 프로그램을 더 다루기 쉬운 데이터 구조로 변환 할 때도 이런 복잡한 목록 구조를 이용한다.

이진수 정렬

자기 참조 구조체에 여러 포인터를 갖게 응용 예로서 중요한 것이 "이진수 '가있다. 이것은 2 개의 포인터 " left, right "를 가지고"오른쪽 "과"왼쪽 "잘 데이터를 분산하여 검색 및 정렬의 편의를 도모한다는 것이다. 즉, 이진 검색과 빠른 정렬이 "두 분할"을 잘 사용하여 O (log n) 와 O (n log n) 과 같은 빠른 알고리즘을 실현했던 것과 마찬가지로, 이진수를 이용하면 이러한 빠른 알고리즘을 실현할 수있다.

struct BTree {
    int data;
    struct BTree * left;
    struct BTree * right;
};
struct BTree BTree [128];

이 이진수의 된장은 " BTree [i] .data "값에 대해서, 그것보다 작은 값을 가지는 데이터는 모두" BTree [i] .left "로 추적된다 노드 (절)에 있으며, 그것보다 큰 값을 가지는 데이터는 모두 " BTree [i] .right "로 추적된다 노드 (절)에있는 것이다. 그래서 재귀 프로그램을 잘 사용하여 데이터를 읽어 들여 가면 자연과 정렬이 이루어진다. 이를 '이진수 정렬'이라고 부른다.

void insertBTree (struct BTree * at, struct BTree * ins)
{
    / * 재귀 함수이므로주의! * / 
    / * ins는 left, right 함께 NULL이기 때문 * / 
    / * 정지 조건에 문제가 없다. * /
    if (ins-> data> at-> data) {
        if (at-> right == NULL) {
            at-> right = ins;
        } else {
            insertBTree (at-> right, ins);
        }
    } else {
        if (at-> left == NULL) {
            at-> left = ins;
        } else {
            insertBTree (at-> left, ins);
        }
    } 
}

void createBTree (void)
{
    struct BTree * ins;
    int val;
    int cnt;

    / * 파일 등의 데이터를 하나씩 읽어 * / 
    / * 이진수를 구축한다. * / 
    / * 첫 번째 노드 (루트 뿌리)은 특별 취급하여 설정한다. * /
    BTree [0] .data = readData ();
    BTree [0] .left = BTree [0] .right = NULL;
    cnt = 1;
    while ((val = readData ())! = EOF) {
        ins = & BTree [cnt ++;
        ins-> data = val;
        ins-> left = ins-> right = NULL;
        / * 재귀 함수 호출 * /
        insertBTree (& BTree [0], ins);
    }
}

void chaseBTree (struct BTree * at)
{
    / * at가 NULL 인을 종료 조건으로하고있다 * /
    if (at == NULL) {
        return;
    }
    / * 그래서 at-> left 등이 NULL이라면, * / 
    / * 재귀 불리고에서 돌아온다. 이것은 다소 효율이 나쁘다. * /
    chaseBTree (at-> left);
    printf ( "% d \ n", at-> data);
    chaseBTree (at-> right);
}

void showBTree (void)
{
    chaseBTree (& BTree [0]);
}

이진수 검색

이 때, 충분히 무작위 데이터라면 BTree [0] 루트 (뿌리)로한다 (거꾸로 방향) 나무의 높이는 총 노드 수 n에 대해 log (n) 이된다. 그러므로 빠른 검색이 가능하게도된다.

반대로 말하면 미리 정 순서 또는 역순으로 갖추어져있는 경우가 최악이며, 이때에는 간단한 삽입 정렬 선형 탐사와 같게되어 버린다.

검색 알고리즘은 다음과 같다.

/ * 발견되면 1을, 없으면 0을 반환 값으로 반환 * /
int searchBTree (int val, struct BTree * at)
{
    int ret;
    if (at == NULL) {
        printf ( "% d는 없습니다! \ n", val);
        return 0;
    }
    if (val> at-> data) {
        ret = searchBTree (val, at-> right);
    } else if (val <at-> data) {
        ret = searchBTree (val, at-> left);
    } else {
        printf ( "found! % d == % d \ n", val, at-> data);
        ret = 1;
    }
    return ret;
}

void search (int n)
{
    sea​​rchBTree (n & BTree [0]);
}

이와 같이 이진수 서치는 효율적인 검색 알고리즘이지만, 일반적으로 고속 알고리즘은 속도를 벌기 위해 재귀가 스택을 낭비하는 경향이 있음을주의하고.

또한 이진수에 의한 분류 및 검색은 이미 데이터가 정순 · 역순으로 갖추어져있는 경우, 삽입 정렬과 선형 탐사와 같게되어 버린다. 이 약점을 피하기 위해는 B 트리 (균형 목) 같은 더 복잡한 데이터 구조가 필요하게된다. 즉, 이진수를 구축 할 때, 좌우의 깊이의 균형이 무너지지 않도록하는 알고리즘이 필요하다는데 이것은 초급의 범위를 크게 초과 위에 포인터 해설 취지에서 일탈 그래서 각자 알고리즘 설명서를 참조 해 주었으면한다.