본문 바로가기

자료구조12

프로젝트) 간단한 검색 엔진 구현 주어진 영문 문서에서 검색하고자 하는 문서의 단어들이 어느 문서에 몇 번이나 나타나는지에 대한 정보를 자료구조를 이용하여 저장하는 색인과정을 거치고 각 문서에 대해 사용자가 입력한 단어에 대해서 문서 각각에서 검색된 횟수와 함께 그 단어가 들어간 전후 3단어를 출력하는 검색과정을 하는 검색엔진을 구현한다. 검색 대상이 될 문서 파일의 내용은 ASCII코드의 영문자, 개행문자 및 문장부호들로 이루어져 있고, 단어와 단어 사이는 ' '(공백)으로 구분된다. 검색 단어가 포함된 파일에서 가장 많이 포함된 파일의 이름이 먼저 나오도록 정렬한다. 체이닝 해시를 이용해 구현 #pragma once #pragma warning(disable:4996) #include #include #include #include .. 2016. 8. 12.
(9) Sort Insertion sort Quick sort Merge sort 구현 #pragma once #defineMAX_SIZE 10 #definebooleanunsigned char #definetrue1 #definefalse0 // 정렬할 테스트 데이터 intoriginal[] = { 25, 5, 37, 1, 61, 11, 59, 15, 48, 19 }; // 키값 비교회수 카운트를 위한 변수 intnum_compare; // insertion sort void insertion_sort(int list[], int n); // quick sort void quick_sort(int list[], int left, int right); // merge sort void merge_sort(int list.. 2016. 8. 12.
(8) Hash Hash : 해싱 함수를 통해서 얻어낸 데이터의 해시 값을 해시 테이블의 주소로 이용하는 자료구조 - 해싱 함수 : 데이터로부터 해시 테이블의 주소를 산출해낼 수 있는 수식 - 제산법(division) : 나머지 연산자를 사용해 테이블 주소를 구하는 방법 ex) x = 127, M = 7 -> 127 % 7 = 1 -> 1번째 버킷으로 - 접지법(folding) : 키를 여러 부분으로 나누어 더하는 방법 ex) x = 12320324111220 -> 123 + 203 + 241 + 112 + 20 = 699 - 해시 테이블 : 데이터의 저장을 위한 자료구조. 버킷과 슬롯으로 구성 - 동의어(synonyms) : 같은 주소를 갖는 데이터들의 집합 주의할 점 - 충돌 : 서로 다른 키가 같은 주소를 가지는 .. 2016. 8. 12.
(7) DFS, BFS DFS(Depth First Search) : 깊이 우선 탐색 - 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 방문 - 스택(Stack) 이용 - V0 -> V1 -> V3 -> V7 -> V4 -> V5 -> V2 -> V6 BFS(Breadth First Search) : 너비 우선 탐색 - 한 노드를 시작으로 인접한 모든 정점 우선 방문 - 큐(Queue) 이용 - V0 -> V1 -> V2 -> V3 -> V4 -> V5 -> V6 -> V7 인접 행렬로 BFS, DFS 구현 #pragma once #defineMAX_VERTICES 100 #definebooleanunsigned char #definetrue1 #definefalse0 // Adjacency matrix for a grap.. 2016. 8. 9.
(6.1) priority queue simulation min heap을 이용한 priority queue simulation 구현#pragma once // 시뮬레이션 설정 상수 #defineMAX_SIMUL_TIME20// 시뮬레이션 진행 시간 #defineMAX_PRINTING_TIME10// 각 Job의 가능한 최대 프린트 시간 #defineJOB_ARRIVAL_PROB0.5// 매 시각 새로운 Job의 도착 확률 #definebooleanunsigned char #definetrue1 #definefalse0 #defineMAX_PQ_SIZE 1000 // Priority queue size // 시뮬레이션을 위한 global variables int current_time = 0;// 현재 시각 int new_job_id = 0;// 새로운 Job.. 2016. 8. 9.
(6) Heap Heap : 완전 이진 트리 구조를 가진 자료구조 (max heap : 각 노드의 키 값이 자식의 키 값보다 큰 완전 이진 트리) 삽입 과정 : 완전 이진 트리가 깨지지 않도록 가장 마지막 노드에 추가 -> 각 노드 비교 삭제 과정 : 제일 큰 값 삭제 -> 완전 이진 트리가 깨지지 않도록 가장 마지막 노드를 위로 올림 -> 각 노드 비교 max heap 구현#pragma once #defineMAX_SIZE 100 #definebooleanunsigned char #definetrue1 #definefalse0 typedef struct { intkey; chardata; } Element; // Global heap Element heap[MAX_SIZE]; int heap_size = 0; // 히.. 2016. 8. 9.

티스토리툴바