데이터구조 : Hash, Separate Chaining, List (문서 비교)

소개

주어진 문서를 서로 비교하면서 같은 단어, 다른 단어등을 분류 및 비교하는 과정을 통해 데이터 구조에 대한 개념을 알 수 있도록 한 과제에 대한 보고서이다. Hash, Separate Chaining, List 등에 관련된 데이터 구조를 자세히 알 수 있도록 설명이 되어 있으며 또한 소스코드도 첨부되어 있다. C++로 데이터 구조를 코딩해야 하는 사람들에게 큰 도움이 될 것이다. 또한 문자열 처리를 하는 과정이 자세히 기술 되어 있으므로 문자열 처리에 대한 보고서를 써야 하는 사람또한 도움이 될 것이다. Yonsei 대학교 데이터 구조를 수강하면서 만들어진 보고서 이다.

목차

1. Definition of Problem.
2. Consideration for this Project.
1. 문자열의 처리
2. ASC code
3. 연속되는 문자열을 처리하는 방법 (실제적인 이번 프로젝트의 핵심)
3. Consideration for Hash & List.
1. Hash의 기본 개념
2. Separate Chaining
3. List
◑ Double side linked list
4. The step of project.
5. Anything for this project.
6. Reference.

본문내용

1. Definition of Problem.

이번 프로젝트는 세 번째 프로젝트에 이어 영어 단어를 아스키코드를 통해 비교를 하는 것이라 할 수 있다. 좀 더 세부적으로 말하면 어떠한 두 개의 문서가 주어지면 그 문서가 얼마나 일치하는지를 비교하는 것이다. 이는 세 번째 프로젝트에서 사용한 Hash와 문자열에 대한 지식뿐만 아니라 연속적으로 일치하는 단어를 찾아 출력하고 그 수를 셈하는 것을 구현하는 방법 또한 알아야 한다. 지난 프로젝트에서 대부분의 것을 설명 했기 때문에 이번 프로젝트에서는 세 번째 프로젝트에서 설명한 부분은 간단하게 설명하고 일치하는 단어를 찾아 출력하는 부분에 중점을 두어 논하도록 하겠다.

2. Consideration for this Project.
그림 1. 비교 기준이 되는 문서 -
지난 프로젝트와 마찬가지로 공백과 줄 넘김으로 단어가 나뉘게 처리함


위 그림에서와 같이 저번 프로젝트에서 다양성을 높이기 위하여 단어들을 공백과 줄 넘김 둘 다로 구분을 했던 것을 이용하여 위와 같은 문서를 인터넷에서 가져왔다. 이번 프로젝트에서는 단어의 개수에 따른 제한이 없었기 때문에 단순히 그냥 기사화된 자료들을 가져와서 위와 같이 저장을 해두었다.
그림 2. 비교 대상이 되는 문서 - 마찬가지로 공백과 줄 넘김으로 단어가 나뉘게 처리함


위의 문서와 비교할 대상이 될 문서를 다음과 같이 준비하였다. 대소문자는 당연히 소문자로 처리 되어 비교가 시행되며 이 대부분의 것은 지난 세 번째 프로젝트에서 구현하였던 함수들을 그대로 이용하였다.

참고자료

· 1. Data structures and algorithm analysis in c, M.A. Weiss
· 2. Print material, 강홍구
· 3. Web site
· http://en.wikipedia.org/wiki/Hash_function
· http://msdn2.microsoft.com/en-us/library/aa376217.aspx
· http://www.cs.fiu.edu./~weiss/dsaa_c2e/files.html