资源预览内容
第1页 / 共27页
第2页 / 共27页
第3页 / 共27页
第4页 / 共27页
第5页 / 共27页
第6页 / 共27页
第7页 / 共27页
第8页 / 共27页
第9页 / 共27页
第10页 / 共27页
亲,该文档总共27页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
数据结构课程设计上机实习报告课 设 题 目Huffman编码和解码班 级学 生 姓 名学 号指 导 教 师时 间2015.12-2015.1一、设计目的1.进一步熟悉C语言开发环境,熟悉用C语言完成一个应用程序的设计过程,掌握有关编辑、调试和整合程序的方法和技巧。2.通过此设计,了解数据结构课程中霍夫曼编码的的有关内容,明确其操作,熟悉其设计,同时学习到有关位向量的内容,对文件掌握加深二、设计内容Huffman编码与解码 (必做)(Huffman编码、二叉树)问题描述对一篇英文文章(大于2000个英文字符),统计各字符出现的次数,实现Huffman编码,以及对编码结果的解码。基本要求(1) 输出每个字符出现的次数和编码,其中求最小权值要求用堆实现。(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 struct 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 /*操作函数声明*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 &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()函数进行单词权值记录,然后进入编码功能,值得一提的是,编码时我给堆排序设计了两种排序形式对权值的排序和对位置的排序,以达到选择两个最小的权值结点的最优时间复杂度的目的,此功能通过switch实现,但要给编码结构体中放置一个place空间,这也从侧面反映了时间和空间矛盾的地方(值得一提的是,有些编码并不可见且有特殊含义,如换行符,所以将字符放入文件中时,并不对其进行处理,读出是进行顺序读出)3. 编码结束后将编码结果,对应字符分别存放在文件中,然后对整篇文章进行编码4. 解码时依据霍夫曼编码的唯一性进行比较求解,遇到同样的字符即返回对应的字母并写入解码文件中五、调试与测试(测试数据:献给艾米莉的玫瑰)1. 首先打开文件进行字符权值统计并输出结果(有些符号不可见,所以无法显示)2. 然后对其进行堆排序3. 输出编码表,及其对应亲子关系(#号代表为父结点)4. 输出编码结果(可以轻易看出编码具备唯一性)5. 将编码写入文件,一下显示文件部分内容位域存储的bite编码文档编码对应的字符顺序存储(可以看到因为换行符的 存在,自动换行了)6. 解码(将文章在命令行显示,也写入了翻译文档(以doc格式保存))六、课程设计总结本次程序设计过程中遇到过许多大大小小的问题,也在设计思路上遇到过难题,但都在各方面的努力下得到了解决。一些问题如下:1. Bite形式保存由于以前没学到过位向量的内容,有一段时间无法实现这个功能,后来在网络上偶然接触到位域的内容,认识到其可行性,于是解决了此问题2. 选择最小的两个权值一开始我认识的这个可能很复杂,又联想到堆排序可以对其有序输出,但我又不想改变其位置,所以增设一个place记录一开始的编码表位置,进行编码时改变后可以轻易还原总结:霍夫曼编码在通信领域内是十分重要的内容,对其的掌握既能帮助我们理解二叉树的重要性,也能为我们未来工作提供一个更广阔的舞台七、附录/* *题目:Huffman编码的编码和解码 *作者:杨欢 *学号:161420325 *完成时间:2015-12-30 算法思想:以书上的霍夫曼算法为核心进行文章(所有内容,包括标点,换行符,所以命令行可能无法显示部分字符)编码和解码。 对于比特位的存储,我选择用位域进行简单方便的操作。文件的读写都以最基本的方式进行。 测试文章上,我选择艾米莉的玫瑰这一小说测试,数据量大,可以验证程序的正确性 */#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;/存放亲子节点位置 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 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 &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);/展示文章 /*主函数*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);
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号