헤프만 트리 인코딩 문제 해독
결점의 리본 경로 길이는 이 결점에서 나무 뿌리 사이의 경로 길이와 결점 상권의 곱셈입니다.나무의 권한 경로 길이는 나무의 모든 잎사귀 결점의 권한 경로 길이의 합이다.n개의 권한이 있다고 가정하고 n개의 잎사귀 결점이 있는 두 갈래 나무를 만들어 보자. 각 잎사귀 결점대권은wi이다. 그 중에서 권한 경로의 길이가 가장 작은 두 갈래 나무를 가장 좋은 두 갈래 나무나 헤프만 나무라고 부른다.
헤프만 나무를 만드는 방법:
(1) 주어진 n개의 권한 값에 따라 {w1, w2, w3...}n그루의 두 갈래 나무를 구성하는 집합 F={T1, T2, T3, T4...},그 중 두 갈래 나무 Ti 중 하나는 와이의 뿌리 결점이고 좌우 나무는 모두 비어 있다.
(2) F에서 두 그루의 뿌리 결점의 값이 가장 작은 나무를 좌우 자수로 선택하여 새로운 두 갈래 나무를 구성하고 새로운 두 갈래 나무의 뿌리 결점의 값이 왼쪽, 오른쪽 자수의 뿌리 결점의 값의 합이다.
(3) F에서 이 두 나무를 삭제하고 새로 얻은 두 갈래 나무를 F에 추가합니다.
(4) F가 한 그루의 나무만 포함할 때까지 (2) 및 (3) 반복합니다.이 나무가 바로 헤프만 나무다.
코드 구현:
#include
#include
using namespace std;
struct HuffmanNode
{
unsigned int weight;
unsigned int parent,leftChild,rightChild;
HuffmanNode()
{
weight=0;parent=0;leftChild=0;rightChild=0;
}
};
void Select(const HuffmanNode* & nodelist,const int length,int & a, int &b)
{
int min=1000000,min2=1000000;
for(int i=0;i {
if(min>nodelist[i].weight&&nodelist[i].parent==0)
{
min=nodelist[i].weight;
a=i;
}
}
for(int j=0;j {
if(j!=a&&min2>nodelist[j].weight&&nodelist[j].parent==0)
{
min2=nodelist[j].weight;
b=j;
}
}
}
char ** HuffmanCoding(const int *w, const int n)
{
assert(w!=NULL);
int i,min1,min2;
int m = 2*n-1;
HuffmanNode * nodelist = new HuffmanNode[m]();
for(i=0;i {
nodelist[i].weight=w[i];
nodelist[i].parent=0;
}
for(i=n;i {
Select(nodelist,i,min1,min2);
nodelist[min1].parent=i;
nodelist[min2].parent=i;
nodelist[i].weight=nodelist[min1].weight+nodelist[min2].weight;
nodelist[i].rightChild=min2;
nodelist[i].leftChild=min1;
nodelist[i].parent=0;
}
char temp [20];
char ** code = new char * [n];
for(i=0;i {
int j=i;
int index=0;
while(j!=m-1)
{
if(j==nodelist[nodelist[j].parent].leftChild) temp[index++]='0';
else temp[index++]='1';
j=nodelist[j].parent;
}
temp[index]='\0';
code[i] = new char[index+1];
strcpy(code[i],temp);
}
delete nodelist;
return code;
}
int main()
{
const int size=6;
char word[size]={'A','B','C','D','E','F'};//
int w[size]={4,3,2,1,7,8};//
char ** code;
code=HuffmanCoding(w,size);
assert(code!=NULL);
for(int i=0;i {
cout< }
//
for(int j=0;j {
delete []code[j];
}
delete []code;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.