C)주어진 파일 문서에 포함된 각 단어별 빈도 수를 출력하는 프로그램 작성(이진트리 사용)

오늘은 파일을 불러와 이진트리에 저장하여 단어종류와 빈도수를 출력하는 알고리즘을 만들어볼 것입니다.

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <ctype.h>
#include <time.h>

#define MAX_NAME        100
#define MAX_WORDS       10000
#define MAX_WORD_SIZE   100
#define TRUE            1
#define FALSE           0

/// 데이터 형식
typedef struct {
char    word[MAX_WORD_SIZE];		/// 키필드
    int     count;
} element;
/// 노드의 구조
typedef struct TreeNode {
	element key;
	struct TreeNode *left, *right;
} TreeNode;

/// 만약 e1 > e2 -> -1 반환
/// 만약 e1 == e2 -> 0  반환
/// 만약 e1 < e2 -> 1 반환
int compare(element e1, element e2)
{
	return strcmp(e1.word, e2.word);
}
static int ko=0;
/// 디스크 파일로부터 한 개 단어를 읽어 배열 word에 저장
/// 성공적으로 읽었으면 TRUE, 그렇지 않으면(파일 끝) FALSE 리턴
int getword(FILE *fd, char *word)
{
    char    ch;
    int    i;

    do {
        ch = getc(fd);
        if (ch == EOF)
            return FALSE;
    } while (!isalpha(ch)); /// 첫번째 알파벳 문자가 나올때까지 읽는다.
    i = 0;
    do {    /// 단어 1개를 읽는다.
        ch = tolower(ch);   /// 소문자로 변환
        word[i++] = ch;
        ch = getc(fd);
    } while (isalpha(ch));  /// 알파벳 문자이면 계속 읽는다.
    word[i] = '\0';
    return TRUE;
    }

/// Binary Search Tree에 새 단어 추가 또는 기존 단어인 경우 빈도 갱신
TreeNode * update_BST(TreeNode **root, element key)
{
    TreeNode *p,*q;
    TreeNode *newnode;
    p=*root;
    q = NULL;
    while(p !=NULL)
    {
        if(compare(key,p->key)==0){ ///compare를 비교하여 0이면 값이똑같아 p의 count값을 1증가시켰습니다.
            p->key.count++;
            ko++;
            return p;
        }
        q = p;
        if(compare(key,p->key)<0){ ///나머지는 다른 값이여서 비교하여 p를 left랑 right로 옮겼습니다.
            p= p->left;
        }
        else
            p=p->right;
    }

    newnode= (TreeNode *)malloc(sizeof(TreeNode));  ///newnode라는 새로운 포인터에 treenode만큼 메모리를 할당해주었습니다.
    if(newnode == NULL)   ///null이면 다시 돌아가도록 했습니다.
        return newnode;
    newnode->key = key;     ///newnode의 값을 집어넣어줬습니다. right,left값에는 null을 넣어줬습니다.
    newnode->left = newnode->right =NULL;
    ///newnode에 아무것도 없다면 밑을 실행시켜줍니다.
    if(q !=NULL){
        if(compare(key,q->key)<0){  ///새로운 값이 들어온다면 newnode의 count값을 1증가시켜줍니다.
            q->left = newnode;
            newnode->key.count=1;
            ko++;
        }
        else{
            q->right = newnode;
            newnode->key.count=1;///새로운 값이 들어온다면 newnode의 count값을 1증가시켜줍니다.
            ko++;
        }
    }
    else{
        *root =newnode;
        newnode->key.count=1;   ///값이 아무것도 안들어있다면 newnode의 count값을 1증가시켜줍니다.
        ko++;
    }
};

/// inorder traversal
void inorder(TreeNode *t)  ///노드의 단어와 count를 출력해줍니다.
{
    if(t)
    {
        inorder(t->left); ///자기 자신의 함수를 부릅니다. 왼쪽 먼저 탐색합니다.
         printf("%s %d ",t->key.word,t->key.count); ///값을 출력해줍니다.
        inorder(t->right); ///다시 오른쪽을 탐색합니다.
    }
/// 방문한 노드의 단어와 count 출력
}

/// 노드 개수 세기
int get_node_count(TreeNode *node)
{
    int count = 0;
    if ( node != NULL ) ///node가 null이 아닐때까지
        count = 1 + get_node_count(node->left) + get_node_count(node->right); ///자기 자신의 함수를 불러  left,rihgt를 탐색하면서 카운트 값을 증가시킵니다.
    return count; ///count값을 반환시켜줍니다.
}

/// 최대값 return
int max(int a, int b)
{
    return (a>b)?a:b;  ///a와 b를 비교하여 참이면 a를 반환하고 거짓이면 b를 출력합니다.
}

/// 트리 높이 계산
int get_height(TreeNode *node)
{
    int height = 0;
    if(node != NULL) ///node가 null일 때까지
        height = 1 + max(get_height(node->left),get_height(node->right)); ///hegiht값에 다가 max함수를 호출하여 left,right 중 더 큰값을 재귀호출을 하면서 탐색하여 값을 증가합니다.
    return height;   ///hegiht값을 반환합니다.
}

/// Binary Search Tree를 사용하여 단어 빈도 파악
int main()
{
	FILE        *fd;
 	element     e;
	TreeNode    *root=NULL;
	TreeNode    *tmp;
	char        fname[MAX_NAME];    /// 파일 이름
	char        w[MAX_WORD_SIZE];   /// 읽어들인 단어
	int         flag;               /// 파일 끝이 아닌지 여부
    clock_t     start, finish;
    double      duration;

    printf("파일 이름: "); ///파일을 불러오는 곳입니다.
    scanf("%s",fname);
    if((fd =fopen(fname,"r"))==NULL){
        fprintf(stderr,"파일을 열수없습니다.\n");
        return 0;
    }

    start =clock(); ///프로그램총 실행 시간 시작
    do{
        flag = getword(fd,w);
        if(flag ==FALSE)      ///단어가 있다면
            break;
        strcpy(e.word,w);   ///strcpy를 사용하여 e.word에 w값을 넣었습니다.
        update_BST(&root,e);  ///root의 주소 값을 넣고 e를 받아갑니다.

    }while(1);

    finish = clock();  ///프로그램 실행시간
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    inorder(root);///프린트 함수

    printf("\n노드 개수 = %d\n",get_node_count(root));
    printf("트리 높이 = %d\n",get_height(root));
    printf("\n%.6f 초입니다.\n",duration);

}

각 함수별로 정리를 해보겠습니다.

​

int compare(element e1, element e2)

이함수는 element 객체를 받아와 strcmp를 통해 word를 비교해서 같으면 0,앞이 크면-1, 뒤가크면 1을 반환하는 함수이다.

 

int getword(FILE *fd, char *word)

이것은 파일을을 받아와 word를 가져오는 것이다. 첫 번째 알파벳 문자가 나올때까지 do while 문을 실행시키고 단어하나를 받아오면 소문자로 변환시켜 그값을 word에 집어넣는다.아니면 ‘\0’을 word에 넣어준다.

 

​

TreeNode * update_BST(TreeNode **root, element key)

TreeNode *p,*q,*newnode를 선언한다. p에다가 루트노드인 *root를 대입하고 q에는 null을 넣어준다. p가 null이 아닐 때 까지 if문으로 compare함수 반환값이 0일 때와 아닐떄를 구별한다. 입력받아온 key값과 p의 key값의 단어가 똑같으면 p의 key값의 count를 1을 증가시켜준다. q에다가 p를 대입시켜주고 compare값이 -1이면 p를 left로 한칸이동한다. 1이면 right로 한칸이동한다. newnode에 동적메모리를 할당해준다. 만약 newnode가 null이면 newnode를 리턴한다. newnode에 값을 집어넣어주고 left,right에 null값을 넣어준다. 다시 q에는 p위치가 들어있을 것이다. q가 null이 아닐때까지 if문으로 compare값을 비교하여 0보다 작으면 q->left에 newnode를 대입하고 count값을 1로 만든다. 나머지는 q->right에 newnode를 대입시키고 count값을 1로 만든다. 또한, 예외가있는데 q가 null이면 *root를 newnode에 대입하고 count값을 1로 만든다.

 

​

void inorder(TreeNode *t)

이 함수는 노드의 단어와 count값을 출력해주는 함수이다. inorder(t->left)를 통해 자기자신의 왼쪽을 먼저 불러온다. 왼쪽이 계속 재귀함수로 불러드리다가 마지막에도착하면 그때 단어와 카운트값을 출력한다. 그리고다시 inorder(t->left)를 통해 오른쪽을 탐색하고 없으면 다시 반복한다.

 

​

int max(int a, int b)

이 함수는 최대값을 반환해주는 것이다. a,b의 값을 받아온뒤 (a>b)?a:b 앞의 조건이 참이면 a를 반환, 아니면 b를 반환한다.

 

​

int get_node_count(TreeNode *node)

이 함수는 노드의 개수를 세어주는 것이다. 노드의 개수를 숫자로 나타내기위해 int count=0을 선언하고 node가 null이 아닐때까지

count = 1 + get_node_count(node->left) + get_node_count(node->right);를 실행시켜주면서 자기 자신의 왼쪽노드,오른쪽노드를 탐색한값을 더해서 count값에 누적시켜 최종적으로 count값을 반환시켜준다.

 

​

int get_height(TreeNode *node)

-이 함수는 트리의 높이를 구하는 것이다. 높이를 숫자로 나타내기위해 int height=0을 선안해준다. *node를 받아와 if문을 통해 node가 null이 아닐때까지

height=1+max(get_height(node->left),get_height(node->right));를 수행시킨다. max함수를 통해 get_height(node->left)를 탐색하여 왼쪽트리의 최대값 찾고, et_height(node->right)를 통해 오른쪽값을 찾아 비교하여 큰값을 반환해준다.

 

​

int main()

파일이름을 scanf로 받아와 fopen을 통해 비교해 만약 있으면 실행하고, 파일이 없으면 파일을 열 수 없습니다.를 출력해준다. 총 실행시간을 알기위해 start 변수에 clock()함수를 사용하였고 do while문을 통해 파일에서 단어 하나하나 받아와 update_BST(&root,e);로 노드에 넣어주었다. 만약 단어가 없으면 break문으로 빠져나온다. 빠져나온다음 finish 변수를 선언해 clock()함수를 사용해 끝난시점을 알려준다. duration변수에 (finish - start) / CLOCKS_PER_SEC;를 대입해 총 실행시간을 구한다. inorder(root)로 단어갯수와 단어를 출력해준다. get_node_count(root),get_height(root),duration을 출력하여, 노드개수, 트리높이, 총실행시간을 구하고 프로그램을 종료한다.