데이터 구조 실습-허프맨(Huffman) 컴파일러/디코더

제목 4, 하프만(Huffman) 컴파일러/디코더(1인 완성 가능)
[문제 설명]
하프만 인코딩을 이용하여 통신을 하면 채널 이용률을 크게 높일 수 있고 정보 전송 시간을 단축하며 전송 원가를 낮출 수 있다.그러나 이것은 송신단에서 하나의 인코딩 시스템을 통해 전송된 데이터를 미리 인코딩하고 수신단에서 전송된 데이터를 인코딩(복원)해야 한다.이중 채널(즉 정보를 양방향으로 전송할 수 있는 채널)에 대해 모든 단말기는 완전한 컴파일/코딩 시스템이 필요하다.이런 정보 수신소를 위해 하프만 코드의 컴파일링/디코딩 시스템을 써 보세요.먼저 27개의 문자 (빈칸 포함) 를 포함하는 문자 (한 파일에 존재할 수 있음) 를 입력한 다음, 각 문자의 출현 횟수를 통계하고, 각 문자의 출현 횟수를 권한값으로 하프만 트리를 구성하여 하프만 인코딩을 구한다.
[기본 요구]
하나의 완전한 시스템은 다음과 같은 기능을 갖추어야 한다. 1. O: 파일chartexfile에 문자(27자 포함)를 입력하여 각 문자가 나타나는 횟수를 통계하고 표 형식으로 파일charsumfile에 저장한다.예를 들면 다음과 같습니다.
문자
스페이스 바
A
B
C
D
E
F
G
H
I
J
K
L
M
빈도
186
64
13
22
32
103
21
15
47
57
1
5
32
40
문자
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
빈도
57
63
15
1
48
51
80
23
8
18
1
16
1
2. I: 초기화(Initialization)터미널에서 문자 집합 크기 n, n 문자, n 값을 읽고 하프만 트리를 만들어서 파일 hfmTree에 저장합니다.3, E: 인코딩(Encoding)만들어진 하프만 트리(메모리에 없으면 파일 hfmTree에서 읽기)를 이용하여 파일 ToBetran의 본문을 인코딩한 다음 결과를 파일 CodeFile에 저장합니다.4. D: 디코딩.만들어진 하프만 트리를 이용하여 파일 CodeFile의 코드를 디코딩한 결과 파일TextFile에 저장됩니다.5. P: 코드 파일 인쇄(Print)파일CodeFile을 행 당 50개의 코드로 축소된 형식으로 터미널에 표시합니다.또한 이 문자 형식의 인코딩 파일을 파일 CodePrin에 씁니다.4, T: 하프만 트리(Tree Printing)를 인쇄합니다.메모리에 있는 하프만 트리를 터미널에 직관적으로 (트리나 오목한 테이블 형식) 표시하고, 이 문자 형식의 하프만 트리를 파일 TreePrint에 기록합니다.[테스트 데이터] 파일charsumfile에서 제시한 문자 집합과 빈도의 실제 통계 데이터로 하프만 트리를 구축하고 다음 메시지의 인코딩과 디코딩을 실현한다.'THIS PROGRAM IS MY FAVORITE'.테스트 데이터 요구: 1. 모든 합법적인 데이터를 사용해야 한다.2. 전체 불법 데이터;3. 부분적인 불법 데이터.프로그램 테스트를 실시하여 프로그램의 안정을 확보하다
부착된 코드:

#include 
#include 
#include 
#include 

struct HuffmanTree
{
     
    int weight;                 //     
    int Lchild, Rchild, Parent; //      ,     
    char letter;                //        
};

struct code
{
     
    char col[28]; //    
    char letter;  //        
} HC[28];         //0     

struct HuffmanTree *HT = NULL; //      
int N;                         //         

void Input();                         //        
void Init();                          //       
void CreateHTree(char a[], int w[]);  //        
void Select(int n, int *s1, int *s2); // 1-n             
void PutHuffmanTree();                //       
void CreateHuffmanCode();             //     
void Puteverycode();                  //           
int FILEhfmtree();                    //          
void Codetxt();                       //    
void DeCodetxt();                     //    
void Printcodetxt();                  //         
void Printhftree();                   //       

int main()
{
     
    int i, j;
    char command;
    system("color 0f");
    while (1)
    {
     
        printf("       

");
        printf("O:       (  26        ),            

");
        printf("I：   ,      

");
        printf("E：  (Encoding)

");
        printf("D：  (Decoding)

");
        printf("P：      (Print)

");
        printf("T：      (Tree Printing)

");
        printf("Q：    

");
        printf("           :");
        scanf("%c", &command);
        fflush(stdin);
        if ('Q' == command || 'q' == command)
            break;
        switch (command)
        {
     
        case 'o':
        case 'O':
            Input();
            break;
        case 'i':
        case 'I':
            Init();
            break;
        case 'e':
        case 'E':
            Codetxt();
            break;
        case 'd':
        case 'D':
            DeCodetxt();
            break;
        case 'p':
        case 'P':
            Printcodetxt();
            break;
        case 't':
        case 'T':
            Printhftree();
            break;
        default:
            printf("       ！
");
            system("pause");
            system("cls");
            break;
        }
    }
    system("pause");
    return 0;
}
void Input()
{
      //       
    char str[1024], a[27] = " ";
    int Alph[27], i, j, flag = 1;
    FILE *fp;
    memset(Alph, 0, 27 * sizeof(int));
    printf("         26              
");
    printf("Tip:       
");
    gets(str);
    i = 0;
    while (str[i])
    {
     
        if ('A' <= str[i] && str[i] <= 'Z')
            Alph[str[i] - 'A' + 1] += 1;
        else if (str[i] == ' ')
            Alph[0] += 1;
        else
        {
     
            flag = 0;
            printf("             ,      ！
");
            break;
        }
        i++;
    }
    if (flag)
    {
     
        if (!Alph[0])
        {
     
            flag = 0;
            printf("             
");
        }
        for (i = 1; i < 27; i++)
            if (!Alph[i])
            {
     
                flag = 0;
                printf("           %c
", i + 64);
            }
        if (!flag)
            printf("        
");
    }
    if (flag)
    {
     
        fp = fopen("chartexfile.txt", "w");
        if (fp == NULL)
        {
     
            printf("    chartexfile.txt  
");
            system("pause");
            system("cls");
            return;
        }
        fputs(str, fp);
        fclose(fp);
        printf("
       chartexfile.txt  

");
        fp = fopen("charsumfile.txt", "w");
        if (fp == NULL)
        {
     
            printf("    charsumfile.txt  
");
            system("pause");
            system("cls");
            return;
        }
        fprintf(fp, "%c%d", '@', Alph[0]); // @           
        printf("      ");
        for (i = 1; i < 27; i++)
            printf("%3c", i + 64);
        printf("
    %4d", Alph[0]);
        for (i = 1; i < 27; i++)
        {
     
            fprintf(fp, "
%c%d", i + 64, Alph[i]);
            printf("%3d", Alph[i]);
        }
        printf("

           charsumfile.txt  
");
        fclose(fp);
        printf("
                  ?(Y/N)");
        if ('Y' == fgetc(stdin))
        {
     
            for (i = 1; i < 27; i++)
                a[i] = i + 64;
            N = 27;
            CreateHTree(a, Alph);
            PutHuffmanTree();
            CreateHuffmanCode();
            Puteverycode();
        }
    }
    system("pause");
    system("cls");
    fflush(stdin);
}

void Init()
{
      //     
    int i, flag, com;
    FILE *fp;
    char ABC[27], temp;
    int ABCnums[27];
    int filenums[27];
    system("cls");
    printf("1.     charsumfile.txt     

");
    printf("2.       

");
    printf("         :");
    flag = scanf("%d", &com);
    while (flag != 1 || com > 2 || com < 1)
    {
     
        printf("      ，     
");
        fflush(stdin);
        flag = scanf("%d", &com);
    }
    printf("
        N, 1<= N <=27
");
    flag = scanf("%d", &N);
    while (flag != 1 || N < 1 || N > 27)
    {
     
        printf("      ，     
");
        fflush(stdin);
        flag = scanf("%d", &N);
    }
    if (com == 1)
    {
     
        fp = fopen("charsumfile.txt", "r");
        if (fp == NULL)
        {
     
            printf("charsumfile.txt    
");
            system("pause");
            system("cls");
            return;
        }
        for (i = 0; i < 27; i++)
            fscanf(fp, "%c%d
", &temp, &filenums[i]);
        fclose(fp);
        printf("
   N           ,         
");
        for (i = 0; i < N; i++)
        {
     
            fflush(stdin);
            ABC[i] = getc(stdin);
            while ((ABC[i] > 'Z' || ABC[i] < 'A') && ABC[i] != ' ')
            {
     
                printf("            ,     
");
                fflush(stdin);
                ABC[i] = getc(stdin);
            }
            if (ABC[i] == ' ')
                ABCnums[i] = filenums[0];
            else
                ABCnums[i] = filenums[ABC[i] - 64];
        }
    }
    else if (com == 2)
    {
     
        printf("
              
A12
C23

");
        for (i = 0; i < N; i++)
        {
     
            fflush(stdin);
            ABC[i] = getc(stdin);
            scanf("%d", &ABCnums[i]);
        }
    }
    printf("    ");
    for (i = 0; i < N; i++)
    {
     
        if (ABC[i] == ' ')
            printf("   ");
        else
            printf("%-4c ", ABC[i]);
    }
    printf("
    ");
    for (i = 0; i < N; i++)
        printf("%-4d ", ABCnums[i]);
    printf("
");
    CreateHTree(ABC, ABCnums); //      
    PutHuffmanTree();          //       
    fp = fopen("hfmTree.txt", "w");
    if (fp == NULL)
    {
     
        printf("hfmTree.txt      
");
        system("pause");
        system("cls");
        return;
    }
    fprintf(fp, "%-6s%-6s%-6s%-8s%-8s%-6s
", "  ", "  ", "  ", "   ", "   ", "  ");
    for (i = 1; i <= N; i++)
    {
     
        if (HT[i].letter == ' ') //   @  ,     
            fprintf(fp, "%-6d%-6c%-6d%-8d%-8d%-6d
", i, '@', HT[i].weight, HT[i].Lchild, HT[i].Rchild, HT[i].Parent);
        else
            fprintf(fp, "%-6d%-6c%-6d%-8d%-8d%-6d
", i, HT[i].letter, HT[i].weight, HT[i].Lchild, HT[i].Rchild, HT[i].Parent);
    }
    for (i; i <= 2 * N - 1; i++)
        fprintf(fp, "%-6d%-6c%-6d%-8d%-8d%-6d
", i, HT[i].letter, HT[i].weight, HT[i].Lchild, HT[i].Rchild, HT[i].Parent);
    fclose(fp);
    printf("
         hfmTree.txt 
");
    CreateHuffmanCode(); //     
    Puteverycode();      //           
    system("pause");
    system("cls");
    fflush(stdin);
}

void CreateHTree(char a[], int w[])
{
      //      
    struct HuffmanTree *pt;
    int m, i, s1, s2;
    m = 2 * N - 1;
    s1 = 1;
    s2 = 2;
    HT = (struct HuffmanTree *)malloc(sizeof(struct HuffmanTree) * (m + 1));
    //0      
    pt = HT;                                 /*HT  0   */
    pt++;                                    //pt     1   
    for (i = 1; i <= N; i++, pt++, w++, a++) //  1-n     
    {
     
        pt->weight = *w;
        pt->Lchild = 0;
        pt->Rchild = 0;
        pt->Parent = 0;
        pt->letter = *a;
    }
    for (i; i <= m; i++, pt++) //  n+1~2n-1     
    {
     
        pt->weight = 0;
        pt->Lchild = 0;
        pt->Rchild = 0;
        pt->Parent = 0;
        pt->letter = 0;
    }
    for (i = N + 1; i <= m; i++) //      
    {
     
        Select(i - 1, &s1, &s2); // HT[1..i-1]   parent 0 weight       ,   s1,s2
        HT[i].Lchild = s1;
        HT[i].Rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
        HT[s1].Parent = i;
        HT[s2].Parent = i;
    }
}

void Select(int n, int *s1, int *s2)
{
      // 1~n               
    int i = 1, temp;
    while (HT[i].Parent != 0 && i <= n) //             
        i++;
    if (i == n + 1)
        return;
    *s1 = i++;
    while (HT[i].Parent != 0 && i <= n) //             
        i++;
    if (i == n + 1)
        return;
    *s2 = i++;
    if (HT[*s1].weight > HT[*s2].weight)
    {
     
        temp = *s1;
        *s1 = *s2;
        *s2 = temp;
    }
    for (; i <= n; i++) //        
    {
     
        if (HT[i].Parent == 0)
        {
     
            if (HT[i].weight < HT[*s1].weight)
            {
     
                *s2 = *s1;
                *s1 = i;
            }
            else if (HT[i].weight < HT[*s2].weight)
                *s2 = i;
        }
    }
}

void PutHuffmanTree()
{
      //       
    int i, m = 2 * N - 1;
    printf("
       
");
    printf("
%-6s%-6s%-6s%-8s%-8s%-6s
", "  ", "  ", "  ", "   ", "   ", "  ");
    for (i = 1; i <= N; i++)
    {
     
        if (HT[i].letter == ' ')
            printf("%-6d%-6s%-6d%-8d%-8d%-6d
", i, "  ", HT[i].weight, HT[i].Lchild, HT[i].Rchild, HT[i].Parent);
        else
            printf("%-6d%-6c%-6d%-8d%-8d%-6d
", i, HT[i].letter, HT[i].weight, HT[i].Lchild, HT[i].Rchild, HT[i].Parent);
    }
    for (i; i <= m; i++)
        printf("%-6d%-6c%-6d%-8d%-8d%-6d
", i, HT[i].letter, HT[i].weight, HT[i].Lchild, HT[i].Rchild, HT[i].Parent);
    printf("
");
}

void CreateHuffmanCode()
{
      //     
    int start, i, p, f;
    char col[28];
    memset(HC, 0, sizeof(struct code) * 28);
    for (i = 1; i <= N; i++) //       
    {
     
        memset(col, 0, sizeof(col));
        start = N - 1; //       
        p = f = i;
        while (HT[f].Parent != 0) //          
        {
     
            f = HT[f].Parent;
            if (HT[f].Lchild == p)
                col[--start] = '0';
            else if (HT[f].Rchild == p)
                col[--start] = '1';
            p = f;
        }
        HC[i].letter = HT[i].letter;
        strcpy(HC[i].col, col + start);
    }
}

void Puteverycode()
{
      //           
    int i;
    printf("%-6s%-8s
", "  ", "  ");
    for (i = 1; i <= N; i++)
    {
     
        if (HC[i].letter == ' ')
            printf("%-6s%-8s
", "  ", HC[i].col);
        else
            printf("%-6c%-8s
", HC[i].letter, HC[i].col);
    }
}

int FILEhfmtree()
{
      //          
    FILE *fp;
    int i, temp;
    char a;
    fp = fopen("hfmTree.txt", "r");
    if (fp == NULL)
        return 0;
    getc(fp);
    if (feof(fp))
        return 0;
    i = 1;
    while (1)
    {
     
        fseek(fp, 42 * i + 6, SEEK_SET);
        a = fgetc(fp);
        if (!a)
            break;
        i++;
    }
    N = i - 1;
    HT = (struct HuffmanTree *)malloc(sizeof(struct HuffmanTree) * (2 * N));
    for (i = 1; i <= 2 * N - 1; i++)
    {
     
        fseek(fp, 42 * i + 6, SEEK_SET);
        a = fgetc(fp);
        fscanf(fp, "%d%d%d%d", &HT[i].weight, &HT[i].Lchild, &HT[i].Rchild, &HT[i].Parent);
        if (a == '@')
            HT[i].letter = ' ';
        else
            HT[i].letter = a;
    }
    fclose(fp);
    return 1;
}

void Codetxt()
{
      //    
    char str[1024];
    char codehf[2048];
    int i, j;
    FILE *fp;
    system("cls");
    if (NULL == HT)
    {
     
        printf("
           ,   hfmTree.txt    (Y/N)
");
        fflush(stdin);
        if ('Y' == getc(stdin))
        {
     
            if (FILEhfmtree() == 0)
            {
     
                printf("
hfmTree.txt       ,     I   
");
                system("pause");
                system("cls");
                fflush(stdin);
                return;
            }
        }
        else
        {
     
            printf("
        ,      
");
            system("pause");
            system("cls");
            fflush(stdin);
            return;
        }
    }
    CreateHuffmanCode();
    if (NULL == (fp = fopen("ToBeTran.txt", "w")))
    {
     
        printf("
ToBeTran.txt      
");
        system("pause");
        system("cls");
        return;
    }
    printf("
       ：  ");
    for (i = 1; i <= N; i++)
    {
     
        if (HC[i].letter == ' ')
            printf("%-5s", "  ");
        else
            printf("%-5c", HC[i].letter);
    }
    printf("

           
");
    fflush(stdin);
    gets(str);
    fputs(str, fp);
    fclose(fp);
    printf("
         ToBeTran.txt  
");
    memset(codehf, 0, sizeof(codehf));
    for (i = 0; str[i]; i++)
    {
     
        for (j = 1; j <= N; j++)
            if (str[i] == HC[j].letter)
            {
     
                strcat(codehf, HC[j].col);
                break;
            }
        if (j == N + 1)
        {
     
            printf("
        :%c
     
", str[i]);
            system("pause");
            system("cls");
            return;
        }
    }
    printf("
    ：
");
    for (i = 0; codehf[i]; i++)
    {
     
        printf("%c", codehf[i]);
        if (i % 50 == 49)
            printf("
");
    }
    if (NULL == (fp = fopen("CodeFile.txt", "w")))
    {
     
        printf("
CodeFile.txt      
");
        system("pause");
        system("cls");
        return;
    }
    fputs(codehf, fp);
    fclose(fp);
    printf("
        CodeFile.txt  
");
    system("pause");
    system("cls");
    fflush(stdin);
}

void DeCodetxt()
{
      //    
    char str[1024];
    char codehf[2048];
    int i, j, start, temp;
    FILE *fp;
    system("cls");
    if (NULL == HT)
    {
     
        printf("
           ,   hfmTree.txt    (Y/N)
");
        fflush(stdin);
        if ('Y' == getc(stdin))
        {
     
            if (FILEhfmtree() == 0)
            {
     
                printf("
hfmTree.txt       ,     I   
");
                system("pause");
                system("cls");
                fflush(stdin);
                return;
            }
        }
        else
        {
     
            printf("
        ,      
");
            system("pause");
            system("cls");
            fflush(stdin);
            return;
        }
    }
    CreateHuffmanCode();
    printf("
        :
");
    Puteverycode();
    if (NULL == (fp = fopen("CodeFile.txt", "r")))
    {
     
        printf("
CodeFile.txt      
");
        system("pause");
        system("cls");
        return;
    }
    fgets(codehf, 2048, fp);
    fclose(fp);
    printf("
CodeFile.txt     : 
");
    for (i = 0; codehf[i]; i++)
    {
     
        printf("%c", codehf[i]);
        if (i % 50 == 49)
            printf("
");
    }
    memset(str, 0, sizeof(str));
    i = 0;
    for (j = 0;; j++)
    {
     
        start = 2 * N - 1;
        for (i; codehf[i]; i++)
        {
     
            if (codehf[i] == '0')
                temp = HT[start].Lchild;
            else if (codehf[i] == '1')
                temp = HT[start].Rchild;
            start = temp;
            if (HT[start].Lchild == 0 && HT[start].Rchild == 0)
            {
     
                i++;
                break;
            }
        }
        str[j] = HT[start].letter;
        if (codehf[i] == 0)
            break;
    }
    printf("

    ：
");
    for (i = 0; str[i]; i++)
    {
     
        printf("%c", str[i]);
        if (i % 50 == 49)
            printf("
");
    }
    if (NULL == (fp = fopen("TextFile.txt", "w")))
    {
     
        printf("
TextFile.txt      
");
        system("pause");
        system("cls");
        return;
    }
    fputs(str, fp);
    fclose(fp);
    printf("

        TextFile.txt   
");
    system("pause");
    system("cls");
    fflush(stdin);
}

void Printcodetxt()
{
     //      
    char codehf[2048];
    int i;
    FILE *fp;
    if (NULL == (fp = fopen("CodeFile.txt", "r")))
    {
     
        printf("
CodeFile.txt      
");
        system("pause");
        system("cls");
        return;
    }
    fgets(codehf, 2048, fp);
    fclose(fp);
    if (NULL == (fp = fopen("CodePrin.txt", "w")))
    {
     
        printf("
CodePrin.txt      
");
        system("pause");
        system("cls");
        return;
    }
    printf("
CodeFile.txt    ：
");
    for (i = 0; codehf[i]; i++)
    {
     
        fputc(codehf[i], fp);
        printf("%c", codehf[i]);
        if (i % 50 == 49)
        {
     
            printf("
");
            fputc('
', fp);
        }
    }
    fclose(fp);
    printf("

  50          CodePrin.txt  
");
    system("pause");
    system("cls");
}

void Printhftree()
{
      //         
    int i, m = 2 * N - 1;
    FILE *fp;
    if (HT == NULL)
    {
     
        printf("
           
");
        system("pause");
        system("cls");
        return;
    }
    printf("
       
");
    printf("
%-6s%-6s%-6s%-8s%-8s%-6s
", "  ", "  ", "  ", "   ", "   ", "  ");
    for (i = 1; i <= N; i++)
    {
     
        if (HT[i].letter == ' ')
            printf("%-6d%-6s%-6d%-8d%-8d%-6d
", i, "  ", HT[i].weight, HT[i].Lchild, HT[i].Rchild, HT[i].Parent);
        else
            printf("%-6d%-6c%-6d%-8d%-8d%-6d
", i, HT[i].letter, HT[i].weight, HT[i].Lchild, HT[i].Rchild, HT[i].Parent);
    }
    for (i; i <= m; i++)
        printf("%-6d%-6c%-6d%-8d%-8d%-6d
", i, HT[i].letter, HT[i].weight, HT[i].Lchild, HT[i].Rchild, HT[i].Parent);
    printf("
");

    if (NULL == (fp = fopen("TreePrint.txt", "w")))
    {
     
        printf("TreePrint.txt      
");
        system("pause");
        system("cls");
        return;
    }
    fprintf(fp, "%-6s%-6s%-6s%-8s%-8s%-6s
", "  ", "  ", "  ", "   ", "   ", "  ");
    for (i = 1; i <= N; i++)
    {
     
        if (HT[i].letter == ' ') //   @  ,     
            fprintf(fp, "%-6d%-6c%-6d%-8d%-8d%-6d
", i, '@', HT[i].weight, HT[i].Lchild, HT[i].Rchild, HT[i].Parent);
        else
            fprintf(fp, "%-6d%-6c%-6d%-8d%-8d%-6d
", i, HT[i].letter, HT[i].weight, HT[i].Lchild, HT[i].Rchild, HT[i].Parent);
    }
    for (i; i <= 2 * N - 1; i++)
        fprintf(fp, "%-6d%-6c%-6d%-8d%-8d%-6d
", i, HT[i].letter, HT[i].weight, HT[i].Lchild, HT[i].Rchild, HT[i].Parent);
    fclose(fp);
    printf("
         TreePrint.txt 
");
    system("pause");
    system("cls");
}