보충 강의) 이진 검색 트리 & 인접 리스트 구현하기
카테고리: Algorithm Lesson 1
권오흠 교수님의 유튜브 강의 영리한 프로그래밍을 위한 알고리즘 강좌 를 듣고 정리한 필기입니다. 😀
주, 지명, 위도, 경도, 수도로부터의 거리 데이터를 가진 지역 들을
이진 검색 트리에 저장할 것
서로 거리가 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내에 있는 타 지역들을 보여주게 된다.
- 지역 이름과 중복 갯수와 함께 그 지역의 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);
}
}
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글남기기