자료구조론 프로젝트2 기말프로젝트 인하대

소개글

"자료구조론 프로젝트2 기말프로젝트 인하대"에 대한 내용입니다.

목차

Ⅰ. Problem

Ⅱ. Solutions(Source code and results)
1. 헤더 file (huff.h)
2. 구현 file (huff.cpp)

Ⅲ. Discussions

본문내용

1. 헤더 file (huff.h)

우선 헤더파일부터 살펴보자. 문제의 조건대로 huff라는 클래스를 사용해서 구현했다. 허프만 트리를 위해 HFNode구조와 각 원소들 element 그리고 heap구조를 이용하기 위해 Heap을 선언했다. huff클래스의 public에는 허프만 코드 작성을 위한 멤버함수들을 선언해주었다. 각각의 기능은 코드의 주석으로 작성해놓았다.

2. 구현 file (huff.cpp)

이제 구현부를 살펴보자. 우선 헤더파일을 include했다. Newheap 함수는 새로운 heap 메모리를 할당한다. initializeHeap 함수는 입력 받은 heap을 초기화한다. insert 함수는 heap에 새로운 element e를 삽입하는 함수인데, min heap으로 구현했기 때문에 최상단에 가장 작은 값이 들어가야한다. 따라서 트리를 거슬러 올라가며 부모 노드와 key(빈도수)를 비교한다. while 루프를 돌면서 부모 노드의 key와 비교하며 더 작은 값이면 부모 노드로 올라간다. 루프를 빠져나오면 현재 위치에 삽입하려는 e를 넣는다.

Removemin 함수는 heap에서 가장 작은 원소를 삭제하는 함수로 삭제하는 동시에 그 원소를 반환한다. heap의 최소값 삭제 알고리즘을 살펴보면 최상단에 최하위 노드의 값을 저장하는 동시에 최하위 노드를 삭제하며 down heap을 진행한다. min heap이기 때문에 최상단에 최소값이 있고 따라서 반환할 최상단의 값을 e에 저장해두고 최하위의 가장 큰 값을 temp에 저장한다. temp가 최상단에 있다고 가정하고 비교할 child를 설정한다. 왼쪽 오른쪽 child중 작은 자식과 비교해야 한다. parent를 1로 child를 2로 설정했기 때문에 child는 왼쪽 자식을 가리키게 된다. 32번 라인을 보면 우선 child가 heap크기보다 클 수 없기 때문에 while문의 조건으로 32번 라인을 넣었고 33번은 오른쪽 자식이 있을 경우를 위해 작성한 라인이다.

참고 자료

없음