1 / 24 일 모각코 제 8회 결과

10 주차 : Huffman 코드 

10 주차는 복습은 하되 정리할 부분이 너무 많아 코드 정리부분은 생략 

구현내용 : 

텍스트 파일을 읽어 information 클래스를 이용하여 문자와 빈도수를 저장한다

( 만약 문자가 이미 있다면 그 문자의 빈도수를 1씩증가하는 방식)

저장한 information 배열을 Minheap 을 이요한 priority queue 에 삽입한다 

지금까지 텍스트 파일을 빈도수로 정리한 우선순위큐가 생성되었다 

이 우선순위 큐를 이용하여 허프만 트리를 생성한다 

허프만 트리 클래스 안에서 setBitCode 메소드를 통해서 허프만의 루트로 부터 순환적으로 경로를 탐색하여 왼쪽 자식이면 0 오른쪽 자식이면 1로 인코딩 하며 허프만 코드를 생성한다 

결과화면 :

발생빈도                                                             허프만 코드 

                         

11 주차 :  Deap 구현

Deap의 크기를 i로 증가시키고 기존의 원소를 복사하는 increaseheap 메소드 

private void increaseheap(int i){ //deap의 크기를 i로 증가시키고 기존의 원소를 복사       

int [] aa = new int [i];

System.arraycopy(deap, 0, aa, 0, deap.length);

deap = aa;       

}

인덱스 i가 min-heap에 위치해 있으면 true를 리턴하고, 그렇지 않으면 false를 리턴하는 inMinHeap 메소드  

private boolean inMinHeap(int i) { //인덱스 i가 min-heap에 위치해 있으면 true를 리턴하고, 그렇지 않으면 false를 리턴

while( i > 2 ) { // i 부터 부모를 타고 계속해서 올라감 -> 최종 부모가 1이면 min 2이면 max 

i = (i-1)/2 ;

}

if(i==1)

return true;

else

return false;

}

인덱스 i가 min-heap에 위치해 있을 때 max partner의 인덱스를 리턴하는 maxPartner 메소드 

private int maxPartner(int i) { //인덱스 i가 min-heap에 위치해 있을 때 max partner의 인덱스를 리턴

int j = i + (int)Math.pow(2, Math.floor(Math.log10(i+1)/Math.log10(2))-1);

if (j > n-1)

j = (j-1)/2;

return j;

}

인덱스 i가 max-heap에 위치해 있을 때 min partner의 인덱스를 리턴하는 minPartner 메소드 

private int minPartner(int i) { //인덱스 i가 max-heap에 위치해 있을 때 min partner의 인덱스를 리턴

int j = i - (int)Math.pow(2, Math.floor(Math.log10(i+1)/Math.log10(2))-1);

return j;

}

min-heap에 있는 인덱스 at 위치에 key를 삽입하는 minInsert 메소드 

private void minInsert(int at, int key) { //min-heap에 있는 인덱스 at 위치에 key를 삽입

deap[at] = key;

int parent =(at-1)/2;

boolean bool = false;

while(bool == false && parent!=0) { // 일단 at 자리에 넣은후 부모와 비교하며 재정비 

if(deap[parent] > deap[at]) {

int temp = deap[parent];

deap[parent] = deap[at];

deap[at] = temp;

}

else 

bool = true;

at = parent;

parent = (at-1)/2;

}

}

max-heap에 있는 인덱스 at 위치에 key를 삽입하는 maxInsert 메소드 

private void maxInsert(int at, int key) { // max-heap에 있는 인덱스 at 위치에 key를 삽입

deap[at] = key;

int index = (at-1)/2;

boolean bool = false;

while(bool == false && index!=0) { // 일단 at 자리에 넣은후 부모와 비교하며 재정비 

if(deap[index] < deap[at]) {

int temp = deap[index];

deap[index] = deap[at];

deap[at] = temp;

}

else 

bool = true;

at = index;

index = (at-1)/2;

}

}

max 값을 삭제하여 리턴하는 deleteMax 메소드 

public int deleteMax() { //max 값을 삭제하여 리턴

int temp = deap[n--];

int remove = deap[2];

int parent = 2;

while(2*parent+1 <= n) { // max 힙의 루트를 삭제후 자식중에 큰수를 루트에 넣으며 리프노드에 도달할때 까지 반복 

int leftchild = 2*parent+1;

int rightchild = 2*parent+2;

if(deap[leftchild] < deap[rightchild]) {

deap[parent] = deap[rightchild];

parent = rightchild;

}

else {

deap[parent] = deap[leftchild];

parent = leftchild;

}

}

int index = minPartner(parent); 

// 최종 리프노드에 대응되는 min 힙을 찾고 그 자식들과 비교하며 가장큰 수를 찾아 최종 리프노드와 비교

if( index*2+1 <= n ) {

if(deap[index*2+1] < deap[index*2+2])

index = index*2+2;

else

index = index*2+1;

}

if(temp < deap[index]) {

deap[parent] = deap[index];

minInsert(index,temp);

}

else 

maxInsert(parent,temp);

return remove;

}

min 값을 삭제하여 리턴하는 deleteMin 메소드 

public int deleteMin() { //min 값을 삭제하여 리턴한다

int temp = deap[n--];

int remove = deap[1];

int parent = 1;

while(2*parent+1 <= n) { // min 힙의 루트를 삭제후 자식중에 작은수를 루트에 넣으며 리프노드에 도달할때 까지 반복 

int leftchild = 2*parent+1;

int rightchild = 2*parent+2;

if(deap[leftchild] < deap[rightchild]) {

deap[parent] = deap[leftchild];

parent = leftchild;

}

else {

deap[parent] = deap[rightchild];

parent = rightchild;

}

}

int index = maxPartner(parent); //최종 리프노드에 대응되는 수를 max 힙에서 찾고 temp 와 비교하여 삽입

if(temp > deap[index]) {

deap[parent] = deap[index];

maxInsert(index,temp);

}

else 

minInsert(parent,temp);

return remove;

}