《数据结构》课程设计报告%设计题目?学院名称信息工程学院专业班级12 计本 2姓名张翠翠学号17 ______$题目：哈夫曼(Huffman)编/译码器一、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。
对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
试为这样的信息收发站写一个哈夫曼码的编/译码系统。
二、设计目标帮助学生熟练掌握树的应用和基本操作，重点掌握二叉树的存储，这里以哈夫曼树为设计目标进一步提高学生的设计能力及对树的理解。
三、任务要求；一个完整的系统应具有以下功能：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中。
四、需求分析~利用哈夫曼树(Huffman)编/译码（一）、初始化哈夫曼树（二）、建立哈夫曼树（三）、对哈夫曼树进行编码（四）、输出对应字符的编码（五）、译码过程五、概要设计哈夫曼树的存储结构描述~typedef struct{unsigned int weight;unsigned int parent, lchild, rchild;}HTNode, *HuffmanTree;哈弗曼树的算法void CreateHT(HTNode ht[],int n)arent=ht[i].lchild=ht[i].rchild=-1; arent==-1) eight<min1) eight;lnode=k;}}else if (ht[k].weight<min2){min2=ht[k].weight;rnode=k;}}}ht[lnode].parent=i;ht[rnode].parent=i;eight=ht[lnode].weight+ht[rnode].weight;child=lnode;ht[i].rchild=rnode; arent;while (f!=-1) child==c) arent;、}++; ata);for (k=hcd[i].start;k<=n;k++) d[k]); }printf("\n");}}#void editHCode(HTNode ht[],HCode hcd[],int n) ata)tart;k<=n;k++){printf("%c",hcd[j].cd[k]);}break; tart,j=0;k<=n;k++,j++)d[k]) ata);for(x=0;code[x-1]!='#';x++) ata=str[i];ht[i].weight=fnum[i];}（while (flag) .");getch();system("cls");break;case 'b':case 'B':system("cls");printf("请输入要进行编码的字符串(以#结束):\n"); &editHCode(ht,hcd,n);printf("\n按任意键返回...");getch();system("cls");break;case 'c':case 'C':system("cls");！DispHCode(ht,hcd,n);printf("请输入编码(以#结束):\n");deHCode(ht,hcd,n);printf("\n按任意键返回...");getch();system("cls");break;case 'd':<case 'D':flag=0;break;default:system("cls");}}}字符（空格A B C D E F G&HI J K L M频度186【64132232103211547—57153220由上表画出哈夫曼树：…由哈夫曼树得出各字符的编码：字符编码字符编码空格10|0001DA010E111111001 B011111%FC0000G01110关系调用：；该程序的流程图：`【开始结点数是否大于1将data 和权值赋给ht输出根结点和权值调用selectmin 函数 计算根结点函数父结点为两子结点之和"是否为根结点左子是否为空此时编码为0i<=2*ni++编码为1结束、否否右子是否为空是是否否|是是七、测试分析白盒：查看代码完整性￥白盒测试也称结构测试或逻辑驱动测试，它是按照程序内部的结构测试程序，通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行，检验程序中的每条通路是否都能按预定要求正确工作。
这一方法是把测试对象看作一个打开的盒子，测试人员依据程序内部逻辑结构相关信息，设计或选择测试用例，对程序所有逻辑路径进行测试，通过在不同点检查程序的状态，确定实际的状态是否与预期的状态一致。
黑盒：测试是否可以正确的创建，删除，插入，打印，查找等操作黑盒测试也称功能测试，它是通过测试来检测每个功能是否都能正常使用。
在测试中，把程序看作一个不能打开的黑盒子，在完全不考虑程序内部结构和内部特性的情况下，在程序接口进行测试，它只检查程序功能是否按照需求规格说明书的规定正常使用，程序是否能适当地接收输入数据而产生正确的输出信息。
黑盒测试着眼于程序外部结构，不考虑内部逻辑结构，主要针对软件界面和软件功能进行测试。
八、使用说明:1) 输入n个字符的权值2) 输入对应的字符3) 得出各字符的编码九、测试数据用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。
字符空格 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 20|字符 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注：学生在测试数据时，需要写出测试用例和截图十、该程序的源代码#include <>#include <> arent=ht[i].lchild=ht[i].rchild=-1; arent==-1) eight<min1) eight;lnode=k;};else if (ht[k].weight<min2){min2=ht[k].weight;rnode=k;}}}ht[lnode].parent=i;ht[rnode].parent=i;eight=ht[lnode].weight+ht[rnode].weight;child=lnode;ht[i].rchild=rnode; arent;while (f!=-1) child==c) arent;}}++; ata);for (k=hcd[i].start;k<=n;k++) d[k]); }printf("\n");}}—void editHCode(HTNode ht[],HCode hcd[],int n) ata)tart;k<=n;k++){printf("%c",hcd[j].cd[k]);}break; tart,j=0;k<=n;k++,j++)d[k]) ata);for(x=0;code[x-1]!='#';x++) ata=str[i];ht[i].weight=fnum[i];}；while (flag) .");getch();system("cls");break;case 'b':case 'B':system("cls");printf("请输入要进行编码的字符串(以#结束):\n");`editHCode(ht,hcd,n);printf("\n按任意键返回...");getch();system("cls");break;case 'c':case 'C':system("cls");,DispHCode(ht,hcd,n);printf("请输入编码(以#结束):\n");deHCode(ht,hcd,n);printf("\n按任意键返回...");getch();system("cls");break;case 'd':、case 'D':flag=0;break;default:system("cls");}}}：该程序的截图：初始化界面截图如下选A时的显示结果截图如下选择B时的显示结果截图如下选C时的显示结果截图如下十一、使用说明（给出软件如何使用，使用时的注意事项）VC++编程环境使用1、VC++程序启动2、新建工程Project3、设定工程Project名称、保存位置4、设定工程Project的类型5、工程Project的描述信息生成6、空工程Project建立完毕7）向工程Project中添加(新建)源代码文件的类型、名称、保存位置8、设定源代码文件的类型、名称9、源代码文件被添加到工程中10、在源代码文件中添加程序代码11、程序代码编译完成后编译、链接过程注意事项：（1）一个工程project中可以有多个源文件(.cpp)、多个头文件（.h）；但这些源代码文件中只能出现一个main函数，作为整个程序运行的入口；（2）必须关闭前一次程序运行结果窗口，才能进行下一次程序运行；（3）书写标识符时，忽略了大小写字母的区别。