Huffman编码报告

《数据结构》课程设计上机实习报告课设题目Huffman编码和解码班级学生姓名学号指导教师时间2015.12-2015.1第2页（共27页）一、设计目的1.进一步熟悉C语言开发环境，熟悉用C语言完成一个应用程序的设计过程，掌握有关编辑、调试和整合程序的方法和技巧。2.通过此设计，了解《数据结构》课程中霍夫曼编码的的有关内容，明确其操作，熟悉其设计，同时学习到有关位向量的内容，对文件掌握加深二、设计内容Huffman编码与解码(必做)（Huffman编码、二叉树）[问题描述]对一篇英文文章（大于2000个英文字符），统计各字符出现的次数，实现Huffman编码，以及对编码结果的解码。[基本要求]（1）输出每个字符出现的次数和编码，其中求最小权值要求用堆实现。（2）在Huffman编码后，要将编码表和英文文章编码结果保存到文件中，编码结果必须是二进制形式，即01的信息用比特位表示，不能用字符’0’和’1’表示。（3）提供读编码文件生成原文件的功能。三、数据结构说明在该程序中我仅仅使用了两个结构体来完成编码，用位域来实现bite流存储：constintMAXSIZE=300;//定义一次分配的Huffman储存单词最大量为500constintOVERFLOW=0;constintERROR=0;constintLineCountNum=500;typedefstructWordCount{第3页（共27页）charWord;//存放字符intfreq;intparent,lchild,rchild;//存放亲子节点位置intplace;//用来保存第一次堆排序后，建立霍夫曼表前的相对位置char*HuffmanCode;//存放霍夫曼编码}WordCount,*WC;//存放单词结点的结构体typedefstructHuffmanTree{WCw;intNumber;//存储有多少数据存入}HuffmanTree,*HTree;typedefstruct{unsignedinta:1;}bite;//设置位段，存储一个bite//**************操作函数声明***********voidInitHuffmanTree(HTree&H);//初始化霍夫曼树voidHeapSort(WC&W,intNumber,intchoice);//堆排序核心函数voidHeapAdjust(WC&W,intdown,intup,intchoice);//堆排序调整函数,实现两种排序voidHuffmanCoding(HTree&H,WC&HT);//求霍夫曼树和霍夫曼编码表voidShowHuffmanTree(HTreeH);//输出霍夫曼树voidSelect(WC&W,inti,int&s1,int&s2);//选择1-i-1之间最小的两个数，且parent为0，用s1,s2返回voidGetTheDeCode(HTreeH);//将编码结果写入函数voidPutTheDeCode(FILE*fp1,FILE*fp2);//将编码结果解码得到文章voidCountTheWord(HTree&H,FILE*fp);//记录单词权值voidShowTheEassy(FILE*wp);//展示文章四、详细设计1.首先我给出了编码和解码的菜单供其选择2.在编码功能中，我先通过CountTheWord（）函数进行单词权值记录，然后进入编码功能，值得一提的是，编码时我给堆排序设计了两种排序形式——对权值的排序和对位置的排序，以达到选择两个最小的权值结点的最优时间复杂度的目的，此功能通过switch实现，但要给编码结构体中放置一个place空间，这也从侧面反映了时间和空间矛盾的地方(值得一提的是，有些编码并不可见且有特殊含义，如换行符，所以将字符放入文件中时，并不对其进行处理，读出是进行顺序读出)3.编码结束后将编码结果，对应字符分别存放在文件中，然后对整篇文章进行编码第4页（共27页）4.解码时依据霍夫曼编码的唯一性进行比较求解，遇到同样的字符即返回对应的字母并写入解码文件中第5页（共27页）五、调试与测试(测试数据：献给艾米莉的玫瑰)1.首先打开文件进行字符权值统计并输出结果（有些符号不可见,所以无法显示）2.然后对其进行堆排序第6页（共27页）3.输出编码表，及其对应亲子关系(#号代表为父结点)第7页（共27页）第8页（共27页）第9页（共27页）4.输出编码结果（可以轻易看出编码具备唯一性）第10页（共27页）5.将编码写入文件，一下显示文件部分内容第11页（共27页）位域存储的bite编码文档第12页（共27页）编码对应的字符顺序存储（可以看到因为换行符的存在，自动换行了）6.解码（将文章在命令行显示，也写入了翻译文档(以doc格式保存)）第13页（共27页）六、课程设计总结本次程序设计过程中遇到过许多大大小小的问题，也在设计思路上遇到过难题，但都在各方面的努力下得到了解决。一些问题如下：1.Bite形式保存由于以前没学到过位向量的内容，有一段时间无法实现这个功能，后来在网络上偶然接触到位域的内容，认识到其可行性，于是解决了此问题2.选择最小的两个权值一开始我认识的这个可能很复杂，又联想到堆排序可以对其有序输出，但我又不想改变其位置，所以增设一个place记录一开始的编码表位置，进行编码时改变后可以轻易还原总结：霍夫曼编码在通信领域内是十分重要的内容，对其的掌握既能帮助我们理解二叉树的重要性，也能为我们未来工作提供一个更广阔的舞台七、附录/**题目：Huffman编码的编码和解码*作者：杨欢*学号：161420325*完成时间：2015-12-30算法思想：以书上的霍夫曼算法为核心进行文章（所有内容，包括标点，换行第14页（共27页）符，所以命令行可能无法显示部分字符）编码和解码。对于比特位的存储，我选择用位域进行简单方便的操作。文件的读写都以最基本的方式进行。测试文章上，我选择艾米莉的玫瑰这一小说测试，数据量大，可以验证程序的正确性*/#includestdio.h#includestdlib.h#includestring.hconstintMAXSIZE=300;//定义一次分配的Huffman储存单词最大量为500constintOVERFLOW=0;constintERROR=0;constintLineCountNum=500;typedefstructWordCount{charWord;//存放字符intfreq;intparent,lchild,rchild;//存放亲子节点位置intplace;//用来保存第一次堆排序后，建立霍夫曼表前的相对位置char*HuffmanCode;//存放霍夫曼编码}WordCount,*WC;//存放单词结点的结构体typedefstructHuffmanTree{WCw;intNumber;//存储有多少数据存入}HuffmanTree,*HTree;typedefstruct{unsignedinta:1;}bite;//设置位段，存储一个bite//**************操作函数声明***********voidInitHuffmanTree(HTree&H);//初始化霍夫曼树voidHeapSort(WC&W,intNumber,intchoice);//堆排序核心函数voidHeapAdjust(WC&W,intdown,intup,intchoice);//堆排序调整函数,实现两种排序voidHuffmanCoding(HTree&H,WC&HT);//求霍夫曼树和霍夫曼编码表voidShowHuffmanTree(HTreeH);//输出霍夫曼树voidSelect(WC&W,inti,int&s1,int&s2);//选择1-i-1之间最小的两个数，且第15页（共27页）parent为0，用s1,s2返回voidGetTheDeCode(HTreeH);//将编码结果写入函数voidPutTheDeCode(FILE*fp1,FILE*fp2);//将编码结果解码得到文章voidCountTheWord(HTree&H,FILE*fp);//记录单词权值voidShowTheEassy(FILE*wp);//展示文章//************主函数***************intmain(){FILE*fp,*wp;HTreeH;WCHT;//存放编码表printf(*************菜单**************************\n);printf(*********1.编码文档********\n);printf(*********2.解码文档********\n);printf(*********0.退出****************************\n);printf(请输入您的选择:);intchoice;scanf(%d,&choice);getchar();while(choice!=0){switch(choice){case1:InitHuffmanTree(H);if(!(fp=fopen(献给艾米莉的玫瑰.txt,r))){//以文本文件形式打开文件printf(此文件不存在\n);exit(ERROR);}printf(文件打开成功\n);CountTheWord(H,fp);printf(按任意键统计该文章各字符出现的频率为\n);getchar();ShowHuffmanTree(H);printf(按任意键开始堆排序\n);getchar();第16页（共27页）HeapSort(H-w,H-Number,1);//对频率排序printf(按任意键输出堆排序后的情况\n);getchar();ShowHuffmanTree(H);printf(现在开始进行霍夫曼树的构建和霍夫曼编码的构建\n);HuffmanCoding(H,HT);printf(输入任意键输出霍夫曼编码表：);getchar();printf(字符位置权值左孩子右孩子父亲\n);for(inti=1;i=2*H-Number;++i){printf(%c%d%d%d%d%d\n,HT[i].Word,i,HT[i].freq,HT[i].lchild,HT[i].rchild,HT[i].parent);}printf(按任意键输出构建的霍夫曼编码结果:);getchar();for(inti=1;i=H-Number;++i){printf(%c对应的编码为%s\n,H-w[i].Word,H-w[i].HuffmanCode);}printf(按任意键将结果写入文件\n);getchar();GetTheDeCode(H);free(H);//释放空间，避免影响break;case2:PutTheDeCode(fp,wp);printf(该英文文章为\n);ShowTheEassy(wp);第17页（共27页）printf(\n);fclose(fp);break;case0:break;}printf(请输入您的选择:);scanf(%d,&choice);getchar();}return0;}//*********操作函数实现**********voidInitHuffmanTree(HTree&H){if(!(H=(HuffmanTree*)malloc(sizeof(HuffmanTree))))exit(OVERFLOW);if(!(H-w=(WC)malloc(sizeof(WordCount)*MAXSIZE)))exit(OVERFLOW);//创建结点H-Number=0;}//****************将结果写入文件********************voidGetTheDeCode(HTreeH){FILE*fp,*wp;//******