AVL Tree, Hash Table, Linked List를 이용한 패턴 매칭 프로그램

목차

1. Program Design
가. HashTable의 구현
나. AVl Tree의 구현
다. Linked List의 구현
라. 프로그램의 흐름
마. AVL Tree의 조작

2. Source Code설명
가. HashTable Class
나. HashCode function
다. AVLTree Class
라. AddToTree function
마. LinkedList Class
바. main function

3. 실행화면
가. 텍스트파일 내용
나. 사용자 입력
다. 출력 내용

4. Conclusion

본문내용

라. 프로그램의 흐름
main()함수 밖에서 CHashTable 클래스의 인스턴스 ht를 먼저 선언한다. 프로그램 전체를 통틀어 hashtable은 단 한 개만 사용하게 된다. 사용자로부터 처음 입력받는 것은 검색할 문자열들이 담겨있는 텍스트 파일의 파일명이다. 다음으로는 검색의 대상이 되는 패턴을 파일이 아닌 키보드로부터 직접 입력받게 된다.
입력이 끝나면 사용자가 지정해 준 텍스트 파일을 읽어 들인다. 한 줄씩 내려가면서 string을 얻고, 이 string은 또 각각의 substring으로 분할한다. substring의 크기는 본 프로젝트에서 (K=6)으로 고정되어 있으며, 이렇게 나눈 각각의 substring은 hashCode()를 통해 hash value로 전환시킨다.
이제 hashvalue는 hash table상의 index로 사용하게 된다. 단순히 table에 substring 자체를 저장하면 collision 때문에 제대로 된 결과를 기대하기 힘들다. 따라서 table에 내용으로 들어가는 것은 AVL Tree의 포인터로 지정해 주도록 한다. table[index]가 비어있으면 이 포인터를 위한 공간을 할당하고 여기에 AVL Tree의 root를 연결시켜 준다. 비어있지 않으면 이미 지금 처리하고 있는 substring과 같은 hash value를 갖는 key가 있었다는 의미이다. AVL Tree를 검색하여 이미 같은 substring이 저장되어 있지 않은지를 검사하고, BST의 정의에 따라 새로운 node를 Tree에 추가한다. node를 추가하면 AVL Tree의 정의를 만족하지 않는 Tree가 되었는지 여부를 검사하고 이 정의를 위반하였을 경우 Restructure()를 호출하여 Tree를 재정렬 시키도록 한다.
만약 이미 지금 저장하고자 하는 substring이 AVL Tree상에 존재한다면 똑같은 substring이 이전에 있었다는 의미이므로 해당하는 위치에 있는 노드에, 현재 substring의 index만을 새로운 Linked List item으로서 저장한다.
이렇게 자료구조를 생성하는 작업이 모두 끝나면 이제 마지막으로 사용자가 입력한 패턴을 다시 가져와서 전체 자료구조상에서 이를 검색한다. 검색하여 발견된 index값을 출력하고 프로그램을 종료한다. 검색하고자 하는 패턴이 없을 경우 없다는 찾을 수 없다는 메시지를 출력한다.

................... (중략) ..................................

라. AddToTree() function
기본적으로, 새로운 node의 추가는 Binary Search Tree의 정의에 따라 key(leftchild) < key(parent) < key(rightchild)를 만족하도록 하며 수행한다. root에서부터 위 관계식을 만족하도록 차례대로 child node를 방문하고, node의 pointer가 NULL에 해당하는 external node에 도달하면 여기에 새로운 node를 위한 공간을 할당하고, 내용(문자열, 링크드 리스크의 아이템)을 채워 넣는다. node들을 방문(검색)하는 과정에서 현재 추가하고자 하는 substring과 똑같은 element를 가진 node를 만나면, 기존에 해당 substring이 string전체에서 이미 한 번 이상 발견되었다는 의미이므로, 이러한 경우에는 tree의 node는 추가하지 않은 상태에서 linked list의 node만을 추가하도록 한다.

참고 자료

없음

압축파일 내 파일목록

PatterMatching/
PatterMatching/debug/
PatterMatching/debug/input.txt
PatterMatching/debug/PatterMatching.ilk
PatterMatching/debug/PatterMatching.pdb
PatterMatching/PatterMatching/
PatterMatching/PatterMatching/CAVLTree.cpp
PatterMatching/PatterMatching/CAVLTree.h
PatterMatching/PatterMatching/CHashTable.cpp
PatterMatching/PatterMatching/CHashTable.h
PatterMatching/PatterMatching/CLinkedList.cpp
PatterMatching/PatterMatching/CLinkedList.h
PatterMatching/PatterMatching/Debug/
PatterMatching/PatterMatching/Debug/BuildLog.htm
PatterMatching/PatterMatching/Debug/CAVLTree.obj
PatterMatching/PatterMatching/Debug/CHashTable.obj
PatterMatching/PatterMatching/Debug/CLinkedList.obj
PatterMatching/PatterMatching/Debug/main.obj
PatterMatching/PatterMatching/Debug/PatterMatching.exe.embed.manifest.res
PatterMatching/PatterMatching/Debug/vc80.idb
PatterMatching/PatterMatching/Debug/vc80.pdb
PatterMatching/PatterMatching/input.txt
PatterMatching/PatterMatching/main.cpp
PatterMatching/PatterMatching/PatterMatching.vcproj
PatterMatching/PatterMatching/PatterMatching.vcproj.E6300.Administrator.user
PatterMatching/PatterMatching/PatterMatching.vcproj.P7010.Karon.user
PatterMatching/PatterMatching/Release/
PatterMatching/PatterMatching/Release/BuildLog.htm
PatterMatching/PatterMatching/Release/CAVLTree.obj
PatterMatching/PatterMatching/Release/CHashTable.obj
PatterMatching/PatterMatching/Release/CLinkedList.obj
PatterMatching/PatterMatching/Release/main.obj
PatterMatching/PatterMatching/Release/vc80.idb
PatterMatching/PatterMatching/Release/vc80.pdb
PatterMatching/PatterMatching.ncb
PatterMatching/PatterMatching.sln
PatterMatching/PatterMatching.suo
PatterMatching/PattrernMatching.hwp
PatterMatching/release/
PatterMatching/release/input.txt
PatterMatching/release/PatterMatching.pdb

전체 목록 보기