2018.03.14의 자료구조 첫 과제

새 학기가 시작됐고, 매우 바쁘게 살고 있다. 학생회 부장을 맡게 되어 매우 귀찮게 되었고, 동아리 임원 까지 맡게 되었다. 군대 전에 마지막으로 불태우는 것 같기도 하다. 뭐 어쨌든 문제는 이거다.

 

이 문제는 file open을 사용한 입력법과 선택정렬, 문장부호 제거(텍스트 제외한 모든 것), 중복 제거 그리고 마지막으로 이진 탐색의 구현을 요구하고 있다. 그리하여 작성자가 구현한 함수는 strcmp_r(O(n^2)), test(O(n)), GetWord(O(n)), sort_r(선택정렬,O(n^2)), binSearch(logn) 이다.

아래의 그림은 큰 범위의 함수와 사용된 함수들이다.

1. strcmp_r(char *a, char *b) : a와 b를 비교(소문자로 변환하여)하여 a가 크면 1, b가 크면 -1, 같으면 0을 return 하는 함수

2. test(char *a) : 현재 저장되어 있는 단어 중 현재 입력 받은 단어와 같은 것이 있는지 탐색하는 함수(strcmp_r사용)

3. int GetWord(int len, char *line) : fscanf로 받은 한 char덩어리들 중에서 특수부호(“”, . , * , ! 등)들을 걷어내고, test함수를 이용하여 중복검사를 실시하는 함수(test 사용)

4. sort_r() : 입력이 끝난 단어들의 배열을 선택 정렬 알고리즘을 사용해 정렬하는 함수(strcmp_r 사용)

5. binSearch(char **a,char *b, const int left, const int right) : 이진 탐색 알고리즘을 사용하여 사용자가 원하는 단어의 위치를 탐색하는 함수(strcmp_r 사용)

예외처리를 해야 했기 때문에 모든 함수를 손으로 작성해야 해서 매우 귀찮은 문제였다. 시간 복잡도도 많이 나오고.

HW1.cpp

input.txt