《赫夫曼编码(实验报告)》由会员分享，可在线阅读，更多相关《赫夫曼编码(实验报告)（7页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计实验报告 编号 实验一 实验项目名称 赫夫曼编码 学时数 6 指导教师 冯韵 班 级 08计科系2 班 学 号 13 姓 名 周枚 实验日期 2010-9-30至2010-10-14 成 绩 一、实验目的： 掌握赫夫曼编码的存储，理解赫夫曼树的算法。通过赫夫曼树的建立，完成赫夫曼编码的 生成，并实现编码文件的译码。 二、内容与设计思想：（设计思想、主要数据结构、主要代码结构、主要代码段分析） 1、设计思想 输入一串电文字符：LINEARALGEBRAINTRODUCTIONOFCOMPUTERPASCALLANGUGEMTCROCOMPUTER,实 现字符的赫夫曼编码，再对赫夫
2、曼编码生成的字符串进行译码，输出电文字符串。 2、主要数据结构 1）赫夫曼树的存储结构定义： #define n 100/叶子结点数 #define m 2*n-1/赫夫曼树中结点总数 typedef structint weight;/权值int lchild,rchild,parent;/左右孩子及双亲指针 HTNode;/树中结点类型 typedef HTNode HuffmanTreem+1;/零号单元不用 2）选择parent为0且权值最小的两个根结点的算法的定义： void select(HuffmanTree T,int k,int int minl=101; for(i=1;i
3、=A c=p; strcpy(HCi.bits, HCi.len=num-start; 3）建立正文的编码文件 建立正文的编码文件的基本思想是：将要编码的字符串中的字符逐一与预先生成赫夫曼树 是保存的字符编码对照表进行比较，找到之后，对该字符的编码写入代码文件，直至所有 的字符处理完为止。具体实现算法如下： void coding(HuffmanCode HC,char*str) int i,j; FILE *fp; fp=fopen(“codefile.txt“,“w“); while(*str) for(i=1;i0)/直至上溯到HTc是树根为止 /若HTc是HTp的左孩子，则生成0；否则
4、生成代码1 cd-start=(HTp.lchild=c) ?0:1; c=p; strcpy(HCi.bits, HCi.len=num-start; /end of for 三、调试过程（测试数据设计与测试结果分析） 输入一串电文字符 LINEARALGEBRAINTRODUCTIONOFCOMPUTERPASCALLANGUGEMTCROCOMPUTER，得到进行译码后的 结果如下： 四、总结 1、设计中遇到的问题及解决过程 在生成赫夫曼树的过程中，对树中成员函数的定义没有定义清楚，导致编译过程中不能识 别，主要错误如下中的黑体部分所示： void HuffmanEncoding(Huf
5、fmanTree HT,HuffmanCode HC) int c,p,i;/c和p分别指示T中的孩子和双亲的位置 char cdn;/临时存放编码串 int start;/指示编码在cd中的起始位置 cdnum=0;/最后一位放上串结束符for(i=1;i0)/直至上溯到tc是树根为止 /若Tc是Tp的左孩子，则生成0；否则生成代码1 cd-start=(Tp.lchild=c) ?0:1; c=p; strcpy(Hi.bits, Hi.len=num-start; 正确的描述如下： void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC) i
6、nt c,p,i; char cdn; int start; cdnum=0; for(i=1;i0) cd-start=(HTp.lchild=c) ?0:1; c=p; strcpy(HCi.bits, HCi.len=num-start; 如上的黑体部分，在程序编译的过程中存在的主要错误就是函数不能识别Tc.parent 、Tp.lchild和Hi.bits、 Hi.len这几个函数，因为我们在定义时是定义的 HT、HC，所以我们应该把其改正，这样程序才能够进行识别。 还存在的错误就是输入的错误，这是每次实验过程中都存在的问题，我们只需在编译过程 中便可以发现并轻松的解决。 2、设计中产生的错误及原因分析 设计过程中，我们对函数的定义总会遗漏或者定义的时候前后不一致，就像上述的错误， 这些错误需要我们对整个函数的定义有一个很清晰的认识，知道每个算法在定义过程中需 要什么函数，需要什么变量。在函数的编写过程中，我们还应该细心，很多错误都是我们 在输入的过程中造成的。 3、设计体会和收获 本次实验，让我们对赫夫曼编码有了一个很好的掌握，了解了赫夫曼编码在算法中的应用， 实现了电文字符的赫夫曼编码的转换并输出。
