하프 만 트 리 생 성 및 하프 만 인 코딩
6873 단어 데이터 구조
#include"stdio.h"
#include"string.h"
#include"malloc.h"
#include"iostream"
using namespace std;
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffTree;
typedef char **HuffCode;
void Select(HuffTree &Ht, int m, int &S1, int &S2)
{/*
Select , 2 (weight ) ,
s1,s2
*/
int j;
S1 = 0;
S2 = 0;
for (j = 1; j <= m; j++)
{
if (Ht[j].parent == 0 && Ht[j].weight != 0)
{
if (Ht[j].weightfor (j = 1; j <= m; j++)
{
if (Ht[j].parent == 0 && j != S1&&Ht[j].weight != 0)
{
if (Ht[j].weightvoid HuffmanCoding(HuffTree &Ht,HuffCode &Hc,int n){ //
if(n<=1)return;
int m,i,s1, s2;
HuffTree p;
m =2*n-1;
Ht = (HuffTree)malloc((m + 1) * sizeof(HTNode));
char ch[100];
for (p = Ht + 1, i = 1; i <= m; ++i, ++p) { //
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
cin >> ch; //
for (int i = 0; ch[i] !='\0'; i++) {
Ht[ch[i] - 'a'+1].weight++; // ,
}
for(i=n+1;i<=m;++i){ //
Select(Ht,i-1,s1,s2);
Ht[s1].parent=i;Ht[s2].parent=i;
Ht[i].lchild=s1;Ht[i].rchild=s2;
Ht[i].weight=Ht[s1].weight+Ht[s2].weight;
}
//
Hc=(HuffCode)malloc((n+1)*sizeof(char*));
char * cd=(char*)malloc((n)*sizeof(char));
int c,f;
cd[n-1]='\0'; //
int start;
for(i=1;i<=n;++i){
start=n-1;
for(c=i,f=Ht[i].parent;f!=0;c=f,f=Ht[f].parent)
{if(Ht[f].lchild==c)cd[--start]='0';
else cd[--start]='1';
}
//cd[n-1]='\0';
Hc[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(Hc[i],&cd[start]);
}
free(cd);
}
void show(HuffCode &Hc, int n)//
{
int i, k;
cout<<" :
"; //
for (i = 1; i<=n; i++)
{
cout<< Hc[i];
cout<<"
";
}
}
그리고 주 함수 에서 호출 하여 입 출력 문 구 를 넣 으 면 됩 니 다.
#include"1.h"
using namespace std;
int main()
{
HuffTree ht;
HuffCode hc;
int n;
cout << " ";
HuffmanCoding(ht,hc,26);
show(hc,26);
system("pause");
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.