데이터 구조 (C 언어) 과목 설정 3 - 하프 만 트 리 (인 코딩 디 코딩)

데이터 구조 (C 언어) 과목 설정 3 - 하프 만 트 리 (인 코딩 디 코딩)

#include 
#include 
#include 
using namespace std;
typedef struct
{
    char ch;//    
    int weight;
    char shu[1000];//    
    int parent, lchild, rchild;
}HTNode, *HuffmanTree;
//int S[1005];
void Select(HuffmanTree &HT, int n, int &l, int &r)
{
    int MIN = 10000;
    for(int i = 0; i <= n; i++) {
        if(HT[i].parent == 0)
            if(HT[i].weight < MIN) {
                MIN = HT[i].weight; l = i;
            }
    }
    MIN = 10000;
    for(int i = 0; i <= n; i++) {
        if(HT[i].parent == 0)
            if(HT[i].weight < MIN && i != l) {
                MIN = HT[i].weight; r = i;
            }
    }
}

int CreatHuffmanTree(HuffmanTree &HT, char ch[])
{
    int i, j, n1 = strlen(ch), n2 = 0;
    int *a = new int[n1];
    char *c = new char[n1];
    for(i = 0; i < n1; i++) {
        for(j = 0; j < n2 && ch[i] != c[j]; j++);
        if(j == n2) {
            c[n2] = ch[i]; a[j] = 1; n2++;
        }
        else a[j]++;
    }
    //cout << c << endl;

    /*for(i = 0; i < n2; i++) {
        cout << a[i] << endl;
    }*/
    if(n2 <= 1)
        return 0;
    int m = 2 * n2 - 1, l, r;
    HT = new HTNode[m + 1];
    for(i = 0; i < m; i++)
    {
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
        if(i < n2)
        {
           HT[i].ch = c[i];
           HT[i].weight = a[i];
           //cout << c[i] << " "<}
}
for(i = n2; i < m; i++)
{
Select(HT, i-1, l, r);
HT[l].parent = i; HT[r].parent = i;
HT[i].lchild = l; HT[i].rchild = r;
HT[i].weight = HT[l].weight + HT[r].weight;
}
delete c;
delete a;
return n2;
}
void BianMa(HuffmanTree &H, int n)
{
int i, start, c, f;
char *cd;
cd = new char[n];
cd[n - 1] = '\0';
for(i = 0; i < n; i++)
{
start = n - 1; / 포 지 셔 닝
c = i;
f = H[i].parent;
while(f != 0)
{
--start;
if(H[f].lchild == c)
cd[start] = '0';
else
cd[start] = '1';
c = f;
f = H[f].parent;
}
strcpy (H [i]. shu, & cd [start]); / start 인 코딩 길이
}
delete cd;
}
int Long (HuffmanTree & H, int n) / / 계산 코딩 총 길이
{
int i, x = 0;
for(i = 0; i < n; i++)
x += H[i].weight * (strlen(H[i].shu));
return x;
}
void TranSlate (Huffman Tree & H, char p [], int n) / p 인 코딩 배열
{
int x = strlen(p);
//cout << p <
char *o = new char[x];
int c = 0, i = 2 * n - 2, k = 0; / / i 뿌리
while(p[c] != '\0')
{
if(p[c] == '0')
{
i = H[i].lchild;
}
else
{
i = H[i].rchild;
}
if (H [i]. lchild = = 0 & H [i]. rchild = = 0) / / 좌우 아이들 이 모두 비어 있다 는 것 은 잎 이라는 뜻 이다.
{
o [k + +] = H [i]. ch; / / 번호 가 i 인 문 자 를 배열 에 부여 합 니 다.
//cout << H[i].ch << endl;
i = 2 * n - 2;
}
c++;
}
//o[x] = '\0';
//cout << o <
o[k] = '\0';
cout << k <<endl;
//cout << strlen(o) <
}
int main()
{
char ch[1005]; cin >> ch;
HTNode *H;
int m = CreatHuffmanTree(H, ch);
BianMa(H, m);
int x = Long(H, m);
cout << x << endl;
char *p = new char[x];
for(int i = 0; i < strlen(ch); i++)
{
for(int j = 0; j < m; j++)
if(ch[i] == H[j].ch)
{
//cout << H[j].shu << endl;
if(i == 0)
strcpy(p, H[j].shu);
else
p = strcat(p, H[j].shu);
}
}
p[x] = '\0';
TranSlate(H, p, m);
return 0;
}
/*
hailhydra*/

이 박문 은 블 로 거들 이 학습 과정 을 기록 하 는 데 만 사용 된다 (문제 가 있 으 면 평론 할 수 있다).