하프 만 트 리 생 성 및 하프 만 인 코딩

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");
}

좋은 웹페이지 즐겨찾기