哈夫曼编/译码器

任务：建立最优二叉树函数。

要求：可以建立函数输入二叉树，并输出其哈夫曼树。

在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。

一个完整的系统应具有以下功能：

（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

（3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。

（4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。

（5）T：印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

题目不分析了，说一下我的代码

0. 假定你看这篇文章的时候已经掌握哈夫曼树原理

1. 原文两种输入方式：手动输入和随机输入

2. 创建哈夫曼树两种方式：通过输入的字符创建或者从文件读取

3. Dict数据结构：以键值对的形式存储编码字符和其对应的权值

4. 哈夫曼树以结构体数组形式存储

5. 哈夫曼编码表以二维字符数组形式存储

6. 凹凸打印哈夫曼树使用递归方法，

7. plaintext.txt ：原文 ciphertext.txt ：密文 DecodingResults.txt ：解码结果

注意：哈夫曼数组的零号地址不使用

Code，环境codeblocks17 通过

//@ChenYe 2019/2/1#include
   
    #include
    
     #include
     
      #include
      
       #include 
       
        #define MAXSIZE 10000#define green SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_GREEN|FOREGROUND_INTENSITY)#define white SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FOREGROUND_BLUE|FOREGROUND_GREEN)#define red SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FOREGROUND_INTENSITY)#define yellow SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_INTENSITY)// 类似green; red; white;的语句为颜色控制语句const int INF = 0x3f3f3f3f;const int NINF = 0xc0c0c0c0;//1061109567 -1061109567	最大最小值typedef struct{    char a;    int weight;} Dict; // Dict以键值对得形式存储编码字符和对应的权值typedef struct{    int weight;    int parent,lchild,rchild;    char data;} HTNode,*HuffmanTree;typedef char **HuffmanCode;void RandomGenerate(char *a, int n){    // 随机生成字符串    char all[]="ABCDEFGHIJKLMNOPQRSTUVDictXYZabcdefghijklmnopqrstuvwxyz0123456789";    srand(time(0));    for (int i=0; i
        
         i) // 不在w中 { i++; w[i].a=*p; w[i].weight++; } p++; } n=i+1; for(int x=n; x>0; x--) // w[0]空出来 { w[x] = w[x-1]; } printf("编码字符及其权值：\n"); for(i=1; i<=n; i++) // 打印权值 printf("%c",w[i].a); printf("\n"); for(i=1; i<=n; i++) printf("%d",w[i].weight); printf("\n");}void Select(HuffmanTree HT,int n,int &s1,int &s2){ //在HuffmanTree中筛选权值最小的两个节点下标赋值给s1、s2 int i=1; int min1=INF,min2=INF;//INF = 1061109567 s1=s2=0; while(i<=n) // min1
         
          
           HT[i].weight) { min2=min1; s2=s1; min1=HT[i].weight; s1=i; } else if(min2>HT[i].weight) { s2=i; min2=HT[i].weight; } }// 
           
             i++; }// 
            
             }void CreateHuffman(HuffmanTree &HT,Dict w[],int n){ // 创建哈弗曼树并存储在HuffmanTree文件中，n为长度 int i,s1,s2; int m=2*n-1; if(n<=1) return ; HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(i=0; i<=n; i++) { HT[i].weight=w[i].weight; HT[i].data=w[i].a; HT[i].lchild=0; HT[i].parent=0; HT[i].rchild=0; } for(; i<=m; ++i) { HT[i].weight=0; HT[i].lchild=0; HT[i].parent=0; HT[i].rchild=0; } for(i=n+1; i<=m; i++) //建立哈夫曼树 { s1=s2=0; 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; } // 写入文件 FILE *fp = fopen("HuffmanTree","wb"); fwrite((HuffmanTree)&HT, sizeof(HTNode), m+1, fp); fclose(fp);}void Huffman_CodeTable(HuffmanTree HT,HuffmanCode &HC,int n){//得到并打印哈夫曼树的编码表 //求出n个字符的哈夫曼编码HC if(n<=1) return ; printf("编码表：\n"); int i; HC = (HuffmanCode)malloc((n+1)*sizeof(char*)); char *cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1; i<=n; ++i)//倒序求编码字符的哈夫曼编码 { int start=n-1; for(int 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'; HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],cd+start); } for(i=1; i<=n; i++) { printf("%c %d的编码为: %s\n",HT[i].data,HT[i].weight,HC[i]); } free(cd);}void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n,char a[]){ FILE *fp; fp=fopen("ciphertext.txt","w"); // 向文件中写入编码后的字符串 green; printf("\nThe cipher code is:\n"); int len = strlen(a); for(int i=0; i

转载地址：http://ajoen.baihongyu.com/

你可能感兴趣的文章