《huffman编码报告》由会员分享，可在线阅读，更多相关《huffman编码报告（27页珍藏版）》请在金锄头文库上搜索。
1、 数据结构课程设计上机实习报告课 设 题 目Huffman编码和解码班 级学 生 姓 名学 号指 导 教 师时 间2015.12-2015.1一、设计目的1.进一步熟悉C语言开发环境，熟悉用C语言完成一个应用程序的设计过程，掌握有关编辑、调试和整合程序的方法和技巧。2.通过此设计，了解数据结构课程中霍夫曼编码的的有关内容，明确其操作，熟悉其设计，同时学习到有关位向量的内容，对文件掌握加深二、设计内容Huffman编码与解码 (必做)（Huffman编码、二叉树）问题描述对一篇英文文章（大于2000个英文字符），统计各字符出现的次数，实现Huffman编码，以及对编码结果的解码。基本要求（1）
2、输出每个字符出现的次数和编码，其中求最小权值要求用堆实现。（2） 在Huffman编码后，要将编码表和英文文章编码结果保存到文件中，编码结果必须是二进制形式，即0 1的信息用比特位表示，不能用字符0和1表示。（3） 提供读编码文件生成原文件的功能。三、数据结构说明在该程序中我仅仅使用了两个结构体来完成编码，用位域来实现bite流存储：const int MAXSIZE=300;/定义一次分配的Huffman储存单词最大量为500 const int OVERFLOW = 0;const int ERROR = 0;const int LineCountNum=500;typedef struc
3、t WordCountchar Word;/存放字符 int freq; int parent , lchild , rchild;/存放亲子节点位置 int place;/用来保存第一次堆排序后，建立霍夫曼表前的相对位置 char *HuffmanCode;/存放霍夫曼编码 WordCount , *WC;/存放单词结点的结构体typedef struct HuffmanTreeWC w;int Number;/存储有多少数据存入 HuffmanTree , *HTree; typedef struct unsigned int a:1;bite;/设置位段，存储一个bite /*操作函数声
4、明*void InitHuffmanTree(HTree &H);/初始化霍夫曼树 void HeapSort(WC &W , int Number , int choice);/堆排序核心函数void HeapAdjust(WC &W , int down , int up , int choice);/堆排序调整函数,实现两种排序 void HuffmanCoding(HTree &H , WC &HT); /求霍夫曼树和霍夫曼编码表void ShowHuffmanTree(HTree H);/输出霍夫曼树 void Select(WC &W , int i , int &s1 , int
5、 &s2);/选择1-i-1之间最小的两个数，且parent为0，用s1,s2返回 void GetTheDeCode(HTree H);/将编码结果写入函数 void PutTheDeCode(FILE *fp1 , FILE *fp2);/将编码结果解码得到文章 void CountTheWord(HTree &H , FILE *fp);/记录单词权值 void ShowTheEassy(FILE *wp);/展示文章四、详细设计1. 首先我给出了编码和解码的菜单供其选择2. 在编码功能中，我先通过CountTheWord（）函数进行单词权值记录，然后进入编码功能，值得一提的是，编码时我
6、给堆排序设计了两种排序形式对权值的排序和对位置的排序，以达到选择两个最小的权值结点的最优时间复杂度的目的，此功能通过switch实现，但要给编码结构体中放置一个place空间，这也从侧面反映了时间和空间矛盾的地方(值得一提的是，有些编码并不可见且有特殊含义，如换行符，所以将字符放入文件中时，并不对其进行处理，读出是进行顺序读出)3. 编码结束后将编码结果，对应字符分别存放在文件中，然后对整篇文章进行编码4. 解码时依据霍夫曼编码的唯一性进行比较求解，遇到同样的字符即返回对应的字母并写入解码文件中五、调试与测试(测试数据：献给艾米莉的玫瑰)1. 首先打开文件进行字符权值统计并输出结果（有些符号不
7、可见,所以无法显示）2. 然后对其进行堆排序3. 输出编码表，及其对应亲子关系(#号代表为父结点)4. 输出编码结果（可以轻易看出编码具备唯一性）5. 将编码写入文件，一下显示文件部分内容位域存储的bite编码文档编码对应的字符顺序存储（可以看到因为换行符的 存在，自动换行了）6. 解码（将文章在命令行显示，也写入了翻译文档(以doc格式保存)）六、课程设计总结本次程序设计过程中遇到过许多大大小小的问题，也在设计思路上遇到过难题，但都在各方面的努力下得到了解决。一些问题如下：1. Bite形式保存由于以前没学到过位向量的内容，有一段时间无法实现这个功能，后来在网络上偶然接触到位域的内容，认识到
8、其可行性，于是解决了此问题2. 选择最小的两个权值一开始我认识的这个可能很复杂，又联想到堆排序可以对其有序输出，但我又不想改变其位置，所以增设一个place记录一开始的编码表位置，进行编码时改变后可以轻易还原总结：霍夫曼编码在通信领域内是十分重要的内容，对其的掌握既能帮助我们理解二叉树的重要性，也能为我们未来工作提供一个更广阔的舞台七、附录/* *题目：Huffman编码的编码和解码 *作者：杨欢 *学号：161420325 *完成时间：2015-12-30 算法思想：以书上的霍夫曼算法为核心进行文章（所有内容，包括标点，换行符，所以命令行可能无法显示部分字符）编码和解码。 对于比特位的存储，
9、我选择用位域进行简单方便的操作。文件的读写都以最基本的方式进行。 测试文章上，我选择艾米莉的玫瑰这一小说测试，数据量大，可以验证程序的正确性 */#include#include#includeconst int MAXSIZE=300;/定义一次分配的Huffman储存单词最大量为500 const int OVERFLOW = 0;const int ERROR = 0;const int LineCountNum=500;typedef struct WordCountchar Word;/存放字符 int freq; int parent , lchild , rchild;/存放亲子
10、节点位置 int place;/用来保存第一次堆排序后，建立霍夫曼表前的相对位置 char *HuffmanCode;/存放霍夫曼编码 WordCount , *WC;/存放单词结点的结构体typedef struct HuffmanTreeWC w;int Number;/存储有多少数据存入 HuffmanTree , *HTree; typedef struct unsigned int a:1;bite;/设置位段，存储一个bite /*操作函数声明*void InitHuffmanTree(HTree &H);/初始化霍夫曼树 void HeapSort(WC &W , int Num
11、ber , int choice);/堆排序核心函数void HeapAdjust(WC &W , int down , int up , int choice);/堆排序调整函数,实现两种排序 void HuffmanCoding(HTree &H , WC &HT); /求霍夫曼树和霍夫曼编码表void ShowHuffmanTree(HTree H);/输出霍夫曼树 void Select(WC &W , int i , int &s1 , int &s2);/选择1-i-1之间最小的两个数，且parent为0，用s1,s2返回 void GetTheDeCode(HTree H);/将
12、编码结果写入函数 void PutTheDeCode(FILE *fp1 , FILE *fp2);/将编码结果解码得到文章 void CountTheWord(HTree &H , FILE *fp);/记录单词权值 void ShowTheEassy(FILE *wp);/展示文章 /*主函数*int main()FILE *fp , *wp; HTree H;WC HT;/存放编码表 printf(*菜单*n) ;printf(*1.编码文档*n); printf(*2.解码文档*n);printf(*0.退出*n);printf(请输入您的选择:);int choice;scanf(%d ,&choice); getchar();while(choice != 0) switch(choice)case 1: InitHuffmanTree(H);if(!(fp = fopen(献给艾米莉的玫瑰.txt , r) /以文本文件形式打开文件 printf(此文件不存在n); exit(ERROR); printf(文件打开成功n); CountTheWord(H , fp);
