6.5 자기참조 구조체(Self-referential Structures)

어떤 입력에서 발생 할수 있는 모든 단어의 발생 횟루를 셀수 있는 좀더 일반적인 문제를 다루기 원한다고 가정해 보자 단어의 목록을 미리 할수 없기 때문에 쉽게 정렬 시켜 이진탐색을 사용할 수가 없다. 또한 단어가 나올때 마다 그 단어가 이미 나타났던 것인지를 알기 위해 모든 단어를 뒤져볼 수도 없다. 왜냐하면 프로그램이 너무 느려지기 때문이다.(정확하게 말하면,실행시간은 입력단어 수의 제곱의 형태로 증가한다)그러면 임의의 단어가 올떄 그 단어를 빨리 찾을수 있도록 하려면 자료을 어떻게 구성해야 하는가?

한가지 방법은 새로운 단어가 들어올때마다 적당한 위치에 그 단어가 위치하도록 함으로써 그때까지 들어온 단어들을 항상 정렬시켜 두는 것이다. 이것을 지금까지 해왔던 방식으로 단어 순서를 바꾸면 시간이 걸리기 때문에 이진트리라고 불리는 자료구조를 대신 사용하기로한다.

트리는 서로 다른 각 단어마다 하나의 node를 갖는데 각 마디는 다음과 같은 정보를 가진다.

단어에 대한 포인터     (a pointer to the text of the word)

발견된 횟수          (a count of the number of occurrence)

왼쪽 가지에 대한 포인터 (a pointer to the left child node)

오른쪽 가지에 대한 포인터(a pointer to the right child node)

어떤 마디도 두개 이상의 가지를 가질 수 없으며, 가지의 번호는 0과 1로 표현된다. 각 마디의 왼쪽 가지에는 그 마디보다 작은 갖을 갖는 마디만 있고 오른쪽 가지에는 그 마디의 가지보다 큰값을 갖는 마디만 오게 된다 다음은 "now is the time for all good men to come to the aild of their party"라는 문장의 트리이다.

새로운 단어가 그 트리에 있나 없나를 알기 위해서는 가장 위의 마디부터 시작하여 그 마디에 저장된 것과 새로운 단어를 비교한다. 두 단어가 일치하면 그 단어는 트리에 있는 것이고 만약 그 단어가 트리의 단어보다 작으면(ASCII 값이 작으면) 왼쪽 마디에 비교하고 그렇지 않으면 오른쪽 마디와 비교한다. 비교된 방향으로 맞는 단어가 없으면 새로운 단어는 트리에 없는 것이고 새로운 단어를 추가하기 위한 적당ㅇ한 빈 공간이 마련된다. 이러한 탐색 과정은 어떤 마디에 대해 일치하지 않으면 그 가지에 대해 똑같은 과정을 하게 되므로 순환(recursive)과정이 된다. 각 마디를 다시 살펴보면 다음 4개의 요소로 구성되어있다.

struct tnode {           /* the tree node: */

    char *word;          /* points to the text */

    int count;           /* number of occurrences */

    struct tnode *left;  /* left child */

    struct tnode *right; /* right child */

};

이렇게 마드를 순환적으로 선언하는 것이 이상하게 생각될지도 모르지만 사실상은 아주 합당한 구조이다. 구조체가 자기 자신을 포함하게 되면 틀리게 되지만 다음과 같은 경우는 left가 마디 자체가 아니라 마디에 대한 포인터라는 것을 선언하는 것이다.

struct tnode *left;

때때로 자기참조의 구조를 가진 구조체 변수가 필요한 경우가 생긴다 이는 두개의 구조가 상대를 각각 참조함으로써 다음과 같은 방법으로 구현될수 있다.

struct t {         

...         

    struct s *p; /* p point to an s */

...

};

struct s {         

...         

    struct s *q; /* q point to an t */

...

};

지금까지 설명했던 동작을 하는 프로그램은 다음과 같은데, 이는 이미 우리가 썻던 getword와 같은 보조루틴들을 가지고있다. main루틴은 getword로 단어를 읽어들이고, addtree로 트리에 단어를 저장시킨다.

#include <stdio.h> 

#include <ctype.h> 

#include <string.h>

#define MAXWORD 100

struct tnode *addtree(struct tnode *, char *);

void treeprint(struct tnode *);

int getword(char *, int);

/* word frequency count */

int main()

{

    struct tnode *root;

    char word[MAXWORD];

    

    root = NULL;

    while (getword(word, MAXWORD) != EOF)

        if (isalpha(word[0]))

            root = addtree(root, word);

    treeprint(root);

    return 0;

}

addtree 루틴은 순환적이다. main에서 읽어 들인 한 단어는 트리의 맨 위에 놓인다. 각 단계마다 그단어는 그 마디에 있는 단어와 비교되어서 결과에 따라 왼쪽이나 오른쪽 가지로 가서 트리를 recursive으로 호출하게 된다.

결국 그 단어는 그 트리에 있는 어떤 단어와 일치해서 카운트를 하나 증가시키든지 또는 일치하지 않아서 nill포인터를 만나 그 마디가 트리에 첨가되어야함을 나타내게 된다. 만일 새로운 마디가 만들어지면 addtree는 그 마디에 대한 포인터를 리턴시키고 그 포인터를 해당되는 바로위의 마디(parent node)에 기록한다.

struct tnode *talloc(void);

char *strdup(char *);

/* addtree: add a node with w, at or below p */

struct treenode *addtree(struct tnode *p, char *w)

{

    int cond;

    if (p == NULL) { /* a new word has arrived */

        p = talloc(); /* make a new node */

        p->word = strdup(w);

        p->count = 1;

        p->left = p->right = NULL;

    } else if ((cond = strcmp(w, p->word)) == 0)

        p->count++; /* repeated word */

    else if (cond < 0) /* less than into left subtree */

        p->left = addtree(p->left, w);

    1

    else /* greater than into right subtree */

        p->right = addtree(p->right, w);

    return p;

}

새로운 node에 대한 기억장소는 node를 기억할 수 이쓴 적당한 기억공간에 대한 포인터를 리턴시키는 talloc 이라는 함수에 의해 배당된다. 조만간 언급하게될 strdup에 의해 새로운 단어는 숨겨진 장소로 복사된다. 카운트는 초기화 되고 두개의 아래 마디는 NULL 값을 갖게 된다. 프로그램 중 이 부분은 트리의 가장 아래로 새로운 마디가 첨가될 경우에만 실행된다 여기서는 strdup와 talloc에서 리턴되는 값에 대한 에러 검사 부분을 생력했다 treepirnt는 정렬된 순서로 트리를 출력한다. 각각의 마디에서 먼저 왼쪽 가지(그 단어보다 순위가 낮다)를 출력한 후 그 단어를 출력하고 다음에 오른쪽 가지 (그단어보다 순위가 높다)를 출력 한다. 순환 루틴이 어떻게 동작하는 잘 이해가 안되면 다음에 보이틑 트리를 다루는 treeprint를 실행시켜 보라.

/* treeprint: in-order print of tree p */

void treeprint(struct tnode *p)

{

    if (p != NULL) {

        treeprint(p->left);

        printf("%4d %s\n", p->count, p->word);

        treeprint(p->right);

    }

}

단어가 고루 퍼진 순서로 오지 않아서 트리가 불균형을 이루게 되면 프로그램 수행시간은 굉장히 길어질 수있다. 최악의 경우이 프로그램의 수행시간은 뒤섞인 단어를 정렬하는 것과 비슷하게 된다. 이러한 이진트리의 단점을 보완한 일반적인 형태의 이진 트리가 있으나 여기서는 더 이상 설명하지 않기로 한다.

이 ㅇ쪠를 끝내기 전에 잠시 기억장소 배당에 관해 살펴보자. 한 프로그램에서는 기억장소를 배당하는 함수가 한 개인 것이 가장 바람직하다. 그러나 char 에 대한 포인터와 struct tnode 에 대한 포인터를 요구하는 것을 하나의 기억장소 배당함수가 처리할 경우 두가지의문이 발생한다.

첫째 대부분의 컴퓨터에서 요구하는 특정한 형태의 alignment restiction)문제를 어떻게 만족시킬 것인가.(예:정수는 기억장소의 짝수 주소에 저장되어야 된다는 것)

둘째 메모리 할당 프로그램이 여러 형태의 포인터를 리턴하도록 하려면 함수를 어떻게 선언해야 하는가?

정렬문제는 기억장소를 조금 낭비해서 항상 모든 제한사항을 만족하는 포인터를 리턴하게 되면 일반적으로는 쉽게 해결할 수가 있다. 제 5장의 alloc는 어느 늑정한 배열에는 적당하지 못하므로 표준 라이브러리 함수 malloc를 사용하겠다. alloc를 사용하는 방법은 8장에서 보여주겠다.

malloc의 형 서천과 같은 문제는 형 검사(type-checking)를 엄밀히 하는 어떤 언어에서도 힘든 문제이다. C에서는 malloc가 void형의 포인터를 리턴하도록 선언하고 그 다음에 원하는 형으로 포인터를 바꾸게 하는것이 가장 적절한 방법이다.malloc와 그와 관계된 루틴들은 표준헤더인 <stdlib.h> 에 선언되어 있다. 따라서 talloc는 다음과 같이 쓸수 있다

#include <stdlib.h>

/* talloc: make a tnode */

struct tnode *talloc(void)

{

  

    return (struct tnode *) malloc(sizeof(struct tnode));

}

strdup은 malloc의 호출로 얻어진 장소이자 인자(argument)에 의해 주어진 문자열을 단순히 복사하기만 한다.

char *strdup(char *s) /* make a duplicate of s */

{

    char *p;

    p = (char *) malloc(strlen(s)+1); /* +1 for '\0' */ i

    f (p != NULL)

        strcpy(p, s);

    return p;

}

malloc는 더이상 공간이 없으면 NULL을 리턴한다 strdup는 strdup을 호출한 함수가 에러를 처리할수 있도록 값을 리턴한다 malloc를 부름으로써 사용된 공간은 제 7장과 제8장에서 소개될 free라는 함수를 사용함으로써 재사용 할 수가있다.

예제 6-2 C프로그램을 읽어서 처음 여섯 자가 같고 나머지가 다른 변수명을 각 그룹별로 알파벳순서로 프린트하는 프로그램을 작성하라 문자열이나 설명문 안에 있는 단어는 세지 않기도한다. 명령어 라인에서 검사할 문자수를 정해 줄수 있도록 6을 매개변수로 할것.

예제 6-3 문장 안에 있는 모든 단어의 리스트를 출력하고 각 단어에 대해 그단어가 나타나는 문장번호를 출력하는 전후참조(cross-reference)를 작성하라  단 "the"나"and"같은 단어는 제외할것.

예제 6-4 입력에 있는 서로 다른 각 단어에 대해 그단어가 나타나는 횟수가 많은 것부터 차례대로 그단어가 나타난 횟수와 함꼐 출력하는 프로그램을 작성하라.