하프 만 인 코딩 과 디 코딩

title:         
date: 2018-11-21 12:01:27
tags: [    ]
categories:     

실험 2 하프 만 인 코딩 과 디 코딩
실험 목적
1. 이 진 트 리 의 순서 저장 구 조 를 잘 알 고 있다.
2. 이 진 트 리 의 순서 저장 구조 와 구체 적 인 실현 에 익숙 하 다.
3. 하 프 만 인 코딩 과 디 코딩 을 잘 알 고 순서 저장 구조 에서 의 실현
실험 요구:
1. 입력 에 따라 하프 만 나 무 를 구성 하고 이 하프 만 나무의 왼쪽 나 무 는 오른쪽 나무 보다 작 아야 한다.
2. 구조의 하 프 만 나무 에 따라 해당 하 는 인 코딩 을 한다.왼쪽 트 리 의 인 코딩 은 0 이 고 오른쪽 트 리 의 인 코딩 은 1 입 니 다.
3. 각 문자 에 대응 하 는 인 코딩 과 평균 인 코딩 길 이 를 출력 합 니 다.
4. 입력 한 인 코딩 에 따라 구조의 하 프 만 트 리 와 결합 하여 해당 하 는 디 코딩 을 제시한다.
5. 서로 다른 가중치 가 있 는 문 자 를 인 코딩 합 니 다.자신 이 실현 한 인 코딩 표를 사용 하여 입력 한 '0', '1' 코드 를 디 코딩 하 다.
데이터 입 출력 요구 사항
예제 입력
5
A 8
B 20
C 30
D 15
E 27
0101101110#
(설명: 첫 번 째 데이터 5 는 모두 5 개의 문 자 를 인 코딩 해 야 한 다 는 것 을 나타 내 고 뒤의 'A 8' 은 A 의 권 리 를 8 로 나타 내 며 문자 의 개 수 는 20 개 를 초과 하지 않 습 니 다. 데이터 0101101110 # 디 코딩 할 데이터 이 고 마지막 으로 # 로 끝 납 니 다)
출력 예시
인 코딩: A 010
B 00
C 11
D 011
E 10
평균 인 코딩 길이: 2.23
대응 하 는 디 코딩 은: ACDE
코드

#include 
#include 
#include 
#include 
#include 
const int INF=0x3f3f3f3f;
using namespace std;
typedef struct
{
    char ch;                     //     
    int weight;                  //  
    int parent, lchild, rchild;   //       
}HTNode, *HuffmanTree;
typedef char **HuffmanCode;
int Floor[25];
​
//         
void   CreateHuffmanTree(HuffmanTree &HT, int w[], char ch[], int n);//  HuffmanTree
void   Select(HuffmanTree HT, int  n, int &s1, int &s2); //               
void   HTCoding(HuffmanTree HT, HuffmanCode &HC, int n); //  HuffmanTree     
void   PrintCode(HuffmanCode HC, int n, char ch[]);//    
double AverageLenght(HuffmanTree HT, HuffmanCode HC, int n); //       
void   DeCode(HuffmanTree HT, int n);//  
​
int main()
{
    int n;
    int i;
    char arrch[20];
    int arrweight[20];
    double avlength;
    char ch;
    HuffmanTree HT; //HT       ，    HuffmanTree
    HuffmanCode HC; //HC       ,           
    scanf("%d",&n);//      
    while((ch=getchar())!='
');
    if(n>20||n<2)   exit(0); //              ；
    for(i=0;i0)，      HT，
    int i, m,s1, s2;
    m = 2 * n - 1;
    HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));  // 0     
    //           w[] ，        ch[] 
    for (i=1; i<=n; i++)
    {
        HT[i].weight=w[i-1];
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
       HT[i].ch =ch[i-1];
     }
     //  HT n-1      
    for (i=n+1; i<=m; i++)
    {
        HT[i].weight=0;
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
        HT[i].ch='\0';
     }
    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;
    }
}
​
void Select(HuffmanTree HT, int  n, int &s1, int &s2)
{      //    
    int t1=INF;
    int t2=INF;
    for(int i=1;i<=n;i++)
    {
        if(HT[i].parent==0)//    
        {
            if(HT[i].weight

​
주의 하 다.
통계 층 수 는 전역 변수 그룹 을 사 용 했 기 때문에 좋 지 않 습 니 다. strlen (HC [I]) 으로 대체 해 야 합 니 다.