[공학]색인관리시스템(index)

소개

공대학생입니다.
엔지니어링DB수업을 들으면서 말들었던 레포트입니다.
학점 잘 나왔습니다.

이진 탐색트리와 단순 링크드 리스트 자료구조를 이용하여, 색인 관리 프로그램을
만들 수 있다.

목차

(1) 문제 정의
(2) 해결 아이디어
[1] 자료구조 모형화 (레포트본문에 그림첨가)
[2] 입력, 삭제, 검색, 오름차순 출력 등의 기능

(3) 프로그램 테스트 결과
(4) 주석이 달린 소스코드
(5) 결론 및 느낀 점

본문내용

(1) 문제 정의
이진 탐색트리와 단순 링크드 리스트 자료구조를 이용하여, 색인 관리 프로그램을
만들 수 있다.

=> 색인용 단어는 이진 탐색 트리를 이용하여 삽입과 삭제를 하며,
페이지는 단순 링크드 리스트를 이용하여 삽입, 삭제한다.
Index 노드에 page노드를 추가하여 참조하도록 구현한 것이 포인트이다.

[2] 입력, 삭제, 검색, 오름차순 출력 등의 기능
(i) 입력기능
삽입하고자 하는 index값과 page값을 받아들이고,
index 트리가 비어 있다면, head노드의 주소값에 입력한 index의 주소값을 넣는다.

만약, 비어있지 않다면, head노드와 삽입한 index값을 비교하여

(1) head노드 값 < 입력 index값 이면,
head노드의 right child 값 과 입력 index 값을 비교하여 작다면, left child 값과 비교한다.
(ii) 삭제기능
(1) 삭제하려고 입력 받은 index값이 존재하지 않을 경우, 없다고 출력함
(2)-1 삭제하려는 index값이 child중에서도 terminal 노드일 때
: 위의 parents 노드 와의 연결을 끊으면 된다.
(2)-2 삭제하려는 index값이 parents 노드 – 삭제하고자 하는 노드 - child노드
순으로 되어 있을 때, 양쪽 link 를 모두 없애고,
parents 노드 – child 노드 로 바로 연결한다
(iii) 검색기능 : 입력기능과 유사
(iv) 출력기능
key값이 작은 것부터 출력(중위순회방식이용)
page 또한 오름차순으로 출력 (입력기능에 알고리즘이 들어있음

참고자료

· 인터넷 및 관련서적