보충 강의) 이진 검색 트리 & 인접 리스트 구현하기

권오흠 교수님의 유튜브 강의 영리한 프로그래밍을 위한 알고리즘 강좌 를 듣고 정리한 필기입니다. 😀

주, 지명, 위도, 경도, 수도로부터의 거리 데이터를 가진 지역 들을 이진 검색 트리에 저장할 것

서로 거리가 10km 이내의 지역들 사이엔 그래프 edge가 있다고 가정. 인접 리스트

📜place.h

typedef struct place 
{
    int index;
    char *state;            // 주
    char *name;             // 지명
    double lon, lat;        // 위도, 경도
    double distFromCapital; // 수도로부터의 거리
} Place;

int compareTo(Place * p, Place * q);  // 두 place의 크기 비교 함수

📜place.cpp

int compareTo(Place * p, Place * q)  // name 을 기준으로 크기를 비교할 것.
{
    return strcmp(p->name, q->name);
}

📜bst.h

이진 검색 트리 Binary Search Tree

typedef Place * Item;  // Place * 데이터 타입을 Item 으로 명명
typedef int (*CompareFtnType) (Item, Item);  // int (*f) (Item, Item) 형식의 함수 포인터 타입을 CompareFtnType 이라고 명명

struct tnode  // 트리 노드
{
    Item data;
    struct tnode *left, *right;  // 왼쪽 자식, 오른쪽 자식
};

typedef struct tnode Node; // tnode를 Node로 명명

typedef struct bst // BST. 이진 검색 트리
{
    Node * root;  // 루트만 있으면 이진 검색 트리들을 구분할 수 있는 정보가 됨
    CompareFtnType compareFtn;  // 비교 함수 포인터
} BST;

BST * create_bst(CompareFtnType f);  // 트리 생성. 노드 크기 비교 기준이 되는 함수 포인터를 인수로 받음.
Item search(BST * tree, Item item);  // 해당 트리에 이 아이템이 있는지 검색
bool insert(BST * tree, Item item); // 해당 트리에 아이템 삽입. bool인 이유는 이미 트리에 있는 데이터면 false 리턴하게끔.
Item remove(BST * tree, Item item);  // 해당 트리에 아이템 삭제

📜bst.cpp

이진 검색 트리에 필요한 함수들 구현

BST * create_bst(CompareFtnType f)  // 트리 생성. 노드 크기 비교 기준이 되는 함수 포인터를 인수로 받음.
{
    BST * tree = (BST *)malloc(sizeof(BST));
    tree->root = NULL;
    tree->compareFtn = f;
    return tree;
}

Item search(BST * tree, Item item)  // 해당 트리에 이 아이템이 있는지 검색
{
    Node * p = tree->root;
    while(p != NULL)
    {
        int result = tree->compareFtn(p->data, item); // 트리가 가지고 있는 비교 함수 포인터를 사용하여 비교 
        if (result == 0)   // 일치. 즉 찾았다면
            return p->data;
        else if (result > 0) // 찾으려는 아이템보다 더 크다면 왼쪽 자식 노드로 내려감
            p = p->left;
        else  // 찾으려는 아이템보다 더 작다면 오른쪽 자식 노드로 내려감
            p = p->right;
    }

    return NULL;  // 끝까지 돌아도 못 찾았다면
}

bool insert(BST * tree, Item item) // 해당 트리에 아이템 삽입. bool인 이유는 이미 트리에 있는 데이터면 false 리턴하게끔.
{
    Node *p = tree->root, *q = NULL;  // 순회 포인터가 하나 더 필요함

    // 중복 검사
    while(p != NULL)  // leaf 노드까지 내려 감
    {
        int result = tree->compareFtn(p->data, item); // 트리가 가지고 있는 비교 함수 포인터를 사용하여 비교 
        q = p;  // 내려가기전에 q를 현재의 p로 업데이트. 항상 이전 노드를 가리키게
        if (result == 0)   // 일치. 즉 트리에 중복되는 값이 있다면
            return false;
        else if (result > 0) // 찾으려는 아이템보다 더 크다면 왼쪽 자식 노드로 내려감
            p = p->left;
        else  // 찾으려는 아이템보다 더 작다면 오른쪽 자식 노드로 내려감
            p = p->right;
    }

    // while 을 빠져 나왔다는 것은 중복되는 것이 없으니까 삽입 해도 된단느 것

    Node * tmp = (Node *)malloc(sizeof(Node));  // 추가할 노드
    tmp->data = item;
    tmp->left = NULL;
    tmp->right = NULL;

    if (q == NULL)  // 트리가 빈 트리라는 것. 루트 노드로서 추가해주면 됨.
    {
        tree->root = tmp;
        return true;
    } 

    // 적절한 위치에 삽입. q 와 비교하여 q의 왼쪽 자식으로 넣을지 오른쪽 자식으로 넣을지.
    int result = tree->compareFtn(q->data, item);
    if (result > 0) 
        q->left = tmp;
    else
        q->right = tmp;
    return true;
}

Item remove(BST * tree, Item item)  // 해당 트리에 아이템 삭제
{

}

📜graph.h

인접 리스트 구현

서로 거리가 10km 이내의 지역들 사이엔 그래프 edge가 있다고 가정.

struct node 
{
    int end;  // edge의 끝
    struct node *next;
};
typedef struct node Edge;

typedef struct graph
{
    Edge **vertices;  // 정점
    int nbrNode;    // 노드 개수
} Graph;

Graph *create_graph(int n);  // 노드 개수를 인수로 받음
void addEdge(Graph *graph, ins s, int t);  // 두 노트끼리 edge 연결. 인수론 시작점, 끝점 넘김

📜graph.cpp

Graph *create_graph(int n)
{
    Graph *g = (Graph *)malloc(sizeof(Graph));
    g->vertices = (Edge **)malloc(n * sizeof(Edge *));
    g->nbrNode = n;
    for (int i = 0; i < n; i++) g->vertices[i] = NULL;
    return g;
}

void addEdge(Graph *graph, ins s, int t)  // 엣지 추가. s는 시작점, t는 끝점.
{
    Edge * edge = (Edge *)malloc(sizeof (Edge));  // edge 생성
    edge->end = t;
    edge->next = graph->vertices[s];  // 시작점 노드
    graph->vertices[s] = edge;
}

📜main.cpp

• “Alabama AL Distances.TXT” 파일. ‘\t’ 을 기준으로 주, 지명, 위도, 경도, 수도로부터의 거리 분류가 되어있다.
  • 
• 최종 결과
  • 지역 이름과 중복 갯수와 함께 그 지역의 10km내에 있는 타 지역들을 보여주게 된다.
    • 

#include <stdio.h>
#include <cstring>
#include <cstdlib>
#include "place.h"
#include "bst.h"
#include "graph.h"
#include "geolocation.h"

#define MAX 40000
#define BUFFER_SIZE 1000

Place * places[MAX];        // 트리가 될 배열. 크기는 40000
int n = 0; 
char * fileName = "Alabama AL Distances.TXT";   // 주, 지명, 위도, 경도, 수도로부터의 거리를 담은 각각의 지역 데이터들이 담긴 txt 파일. 위 사진과 같이 생김
BST * theTree;
Graph *theGraph;

void inorder(Node *p);
void readData(char * name);
void rename(Place *p);
void makeGraph();
void printGraph(Graph *graph);

int main()
{
    theTree = create_bst(compareTo);  // compareTo 함수 포인터를 넘김
    readData(fileName);
    makeGraph();
    printGraph(theGraph);

    /*
    inorder(theTree->root);  // 중위 표기 방식으로 순회하며 트리의 노드들 출력
    */

    return 0;
}

void makeGraph()
{
    theGraph = create_graph(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // caldDist 함수는 "geolocation.h"에 있는 두 지역의 위치(위도,경도)를 통해 거리를 리턴한느 함수다.
            if (caldDist(places[i]->lat, places[i]->lon, places[j]->lat, places[j]->lon) < 10000.0)  // 10km 이내면
            {
                addEdge(theGraph, i, j);  // 인접 리스트 에지를 이어 줌
                addEdge(theGraph, j, i);  // 인접 리스트 에지를 이어 줌
            }
        }
    }
}

void printGraph(Graph *graph)
{
    for(int i = 0; i < graph->nbrNode; i++)
    {
        printf("%s\n", places[i]->name);
        Edge *edge = graph->verticles[i];
        while(edge != NULL)
        {
            printf("    --- %s\n", places[edge->end]->name);
            edge = edge->next;
        }
    }
}

void inorder(Node *p)
{
    if (p == NULL)
        return;
    inorder(p->left);  
    printf("%s\n", p->data->name);
    inorder(p->right);  
}

void readData(char * name)  // Tab 으로 구분되어 있는 파일의 데이터들을 읽기
{
    char buffer[BUFFER_SIZE];
    FILE * fp = fopen(fileName, "r");
    while(fgets(buffer, BUFFER_SIZE, fp) != NULL)
    {
        Place *place = (Place *)malloc(sizeof(Place));

        char *p = strtok(buffer, "\t"); // tokenizing
        place->state = strdup(p);

        p = strtok(NULL, "\t");
        place->name = strdup(p);

        p = strtok(NULL, "\t");
        place->lon = (double)atof(p);

        p = strtok(NULL, "\t");
        place->lat = (double)atof(p);

        p = strtok(NULL, "\t");
        place->distFromCapital = (double)atof(p);

        place->index = n;

        rename(place);

        places[n++] = place;
        insert(theTree, place);
    }

    fclose(fp);
}

void rename(Place *p)  // 중복인 지명은 지명 뒤에 중복 갯수를 붙여준다.
{
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        if (strncmp(p->name, places[i]-> name, strlen(p->name)) == 0)
            count++;
    }
    if (count > 0)
    {
        char namebuffer[BUFFER_SIZE];
        sprintf(namebuffer, "%s%d", p->name, (count + 1));
        free(p->name);
        p->name = strdup(namebuffer);
    }
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Algorithm Lesson 1 카테고리 내 다른 글 보러가기