1、哈夫曼编码译码实训报告实训报告题 目： 哈夫曼编码和译码 院 系： 信息科技学院专 业： 计算机科学与技术姓 名： 吴 平 学 号： * *日 期：2016年6月29日 桂林电子科技大学信息科技学院哈夫曼编码译码一、设计目的 通过对哈夫曼编码译码系统的设计编写原代码，深刻掌握C+语言中各个语法以及数据结构与C+的联系与结合，其中还应用了C语言的结构体的知识。函数的应用，使我们对结构体，链表，文件以及程序的操作更加熟悉。初步掌握中，大型程序设计中的各个步骤，流程，以及开发过程中遇到问题的处理方法，为以后的学习打下基础。并且通过课程设计，将上学期所学的C+程序设计以及这学期所学的数据结构的知识联系
2、结合，培养自己的动手能力，加强相关学科之间的联系。二、设计内容 本系统以哈夫曼编码译码为主要背景，设计和实现了一个小型哈夫曼编码译码器系统。主要有以下功能：1.系统以Dos界面显示来运行工作，界面清晰直观，便于用户操作。2.哈夫曼树的创建，包括双亲，左孩子、右孩子和权值。3.创建哈夫曼编码，输入一段字符和对应字符的权值并以.txt的形式保存在文件中。4.哈夫曼译码，对之前创建的编码进行译码。程序运行效果图如下图所示：三、概要设计 采用模块化的程序设计方法，即将较大的任务按照一定的原则分为一个个较小的任务，然后分别设计各个小任务。需要注意的是划分出来的模块应该相对独立但又相关，且容易理解。可以用
3、模块化层次结构图（即模块图）来分析其任务的划分，一般从上到下进行，最上面一层是主模块，下面各层是其上一层模块的逐步细化描述。 本哈夫曼编码译码要求用c+语言编写实现，如图2.1所示，它由如下四大模块构成：.创建哈夫曼树：创建一个新的哈夫曼树，完成将字符初始化的操作。然后编码译码就可以读出相应的字符并进行编码译码。.创建哈弗曼编码：在新建的哈夫曼树的基础下，对字符进行编码并保存到文件。.进行哈夫曼译码：对之前已经进行好编码的字符进行译码。.退出程序。四、详细设计4.1、头文件的定义：#include /程序中要用到文件流类ofstream，ofstream是在这个中定义的#include #in
4、clude#include /系统自带的字符串库函数 ，strcpy包含在这个头文件中4.2、模块接口设计：class LinkList 定义一个链表类class HuffmanTree 定义一个哈夫曼树void HuffmanTree:CreatHuffmanTree(char ch, int w, int n) 创建哈夫曼树string HuffmanTree:Encode(char ch) 哈弗曼编码LinkList HuffmanTree:Decode(string strCode) 哈夫曼译码4.3、主函数main()：main()函数主要实现了对整个程序的运行控制，以及相关功能模块
5、的调用。int main() char *ch; int *w,n=0; int *p=&n; ch=new char100; w=new int100; int x; do switch(x=actmenu() case 1:f1(ch,w,p);break; case 2:f2(ch,w,n);break; case 3:f3(ch,w,n);break; case 4:f4(ch,w,n);break; while(x); coutendlendl; return 0;4.4、主菜单界面：用户进入哈夫曼编码译码系统时，需要显示主菜单，提示用户进行选择，完成相应任务。此代码被main()函
6、数调用。int actmenu() /主菜单 system(cls); /清屏函数 int k=0; coutnnnnnnt哈夫曼编码译码系统; coutnn* 主菜单 *endl; coutnn* 0.退出 *endl; coutnn * 1.建树 *endl; coutnn * 2.编码 *endl; coutnn * 3.译码 *endl; coutn*请选择系统功能（0-3）：k; return k;4.5、功能的执行过程：用户进入系统时，对每个功能进行操作，需要按这些条件输入，才能得到相应的正确的结果。/每个功能的执行过程void f1(char ch,int w,int *p) c
7、har *ch1; int *w1,n1,i; cout输入字符集中字符的个数：n1; *p=n1; ch1=new charn1; w1=new intn1; cout输入字符集中的字符：endl; for(i=0;ich1i; strcpy(ch,ch1); /将ch1复制给ch strcpy(ch+sizeof(char)*n1,0); /将括号里的内容复制给ch cout输入字符集中的字符的权值：endl; for(i=0;iw1i; HuffmanTree hmTree(ch1,w1,n1); system(PAUSE);void f2(char ch,int w,int n) Hu
8、ffmanTree hmTree(ch,w,n); string strText,strCode; coutstrText; cout文本串strText.c_str() 编码为：; ofstream ofile1(texrfile.txt); /定义文件流对象，打开磁盘文件“texrfile.txt” if(!ofile1) /如果打开失败，ofile1返回0值 coutcannot open texrfile.txtn; return; ofile1strText.c_str(); /向磁盘文件“texrfile.txt”输出数据 ofstream ofile2(codefile.txt)
9、; /定义文件流对象，打开磁盘文件“codefile.txt” if(!ofile2) /如果打开失败，ofile2返回0值 coutcannot open codefile.txtn; return; for(int pos=0;posstrText.length();pos+) string strTmp=hmTree.Encode(strTextpos); coutstrTmp.c_str(); ofile2strTmp.c_str(); coutendl; system(PAUSE);void f3(char ch,int w,int n) HuffmanTree hmTree(ch,
10、w,n); string strText,strCode; cout读入codefile.txt,译码中.n; ifstream ifile(codefile.txt); /定义输入文件流对象，以输入方式打开磁盘文件codefile.txt if(!ifile) coutstrCode; /从磁盘文件读入编码串 cout编码串strCode.c_str() 译码为：; LinkList lkText=hmTree.Decode(strCode); lkText.Traverse(); lkText.Traversetofile(); coutendl; system(PAUSE);void f
11、4(char ch,int w,int n) HuffmanTree hmTree(ch,w,n); string strText,strCode,reSult; ifstream ifile1(codefile.txt); if(!ifile1) coutstrCode; ifstream ifile2(textfile.txt); /定义输入文件流对象，以输入方式打开磁盘文件textfile.txt if(!ifile2) coutstrText; ifstream ifile3(result.txt); /定义输入文件流对象，以输入方式打开磁盘文件result.txt if(!ifile
12、3) coutreSult; couttextfile.txt文件内容：strTextncodefile.txt文件内容： strCodennresult.txt文件内容：reSultendl; system(PAUSE);4.6、定义哈夫曼树类：在创建哈夫曼树之前先要对哈夫曼树进行一个类的定义，并确定哈夫曼树的数据成员与成员函数，比如权值，双亲结点，左右孩子节点还有字符个数等。还有编码和译码的成员函数。class HuffmanTree protected: HuffmanTreeNode *nodes; / 存储结点信息,nodes0未用 char *LeafChars; / 叶结点字符信
13、息,LeafChars0未用 string *LeafCharCodes; / 叶结点字符编码信息,LeafCharCodes0未用 int curPos; / 译码时从根结点到叶结点路径的当前结点 int num; / 叶结点个数 / 辅助函数: void Select(int cur,int &r1,int &r2); / nodes1 cur中选择双亲为0,权值最小的叶结点r1,r2 void CreatHuffmanTree(char ch,int w,int n); public: HuffmanTree(char ch, int w, int n); / 由字符,权值和字符个数构造
14、哈夫曼树 virtual HuffmanTree(); / 析构函数 string Encode(char ch); / 编码 LinkList Decode(string strCode); / 译码; void HuffmanTree:Select(int cur, int &r1, int &r2) r1=r2=0; / 0表示空结点 for (int pos=1;pos=cur;pos+) if (nodespos.parent!=0) continue; / 只处理双亲为0的结点 if (r1=0) r1=pos; else if(r2=0) r2=pos; else if(node
15、spos.weight nodesr1.weight) r1=pos; else if(nodespos.weight nodesr2.weight) r2=pos; 4.7、哈夫曼树的建立：在哈夫曼编码译码系统中，首先需要建立一个哈夫曼树，然后方便对相应字符串的编码与译码。void HuffmanTree:CreatHuffmanTree(char ch, int w, int n) /创建哈弗曼树 num=n; / 叶结点个数 int m=2*n-1; / 总结点个数 nodes = new HuffmanTreeNodem+1; / nodes0未用 LeafChars=new char
16、n+1; / LeafChars0未用 LeafCharCodes=new stringn+1; / LeafCharCodes0未用 int pos; / 临时变量 for (pos=1;pos=n;pos+) / 存储叶结点信息 nodespos.weight=wpos-1; / 权值 LeafCharspos=chpos-1; / 字符 for (pos=n+1;pos=m;pos+) / 建立哈夫曼树 int r1, r2; Select(pos-1,r1,r2); nodesr1.parent=nodesr2.parent=pos; / r1,r2双亲为pos nodespos.le
17、ftChild=r1; / r1为pos的左孩子 nodespos.rightChild=r2; / r2为pos的右孩子 nodespos.weight=nodesr1.weight+nodesr2.weight;/pos的权为r1,r2的权值之和 for (pos = 1; pos = n; pos+) / 求n个叶结点字符的编码 LinkList charCode; / 暂存叶结点字符编码信息 for (unsigned int child=pos,parent=nodeschild.parent;parent!=0;child=parent,parent=nodeschild.pare
18、nt) if (nodesparent.leftChild=child) charCode.Insert(1,0); else charCode.Insert(1,1); for(int i=1;i=charCode.Length();i+) LeafCharCodespos.append(1,charCode.GetElem(i);/没有直接可以从链表为字符串赋值的函数，只能一个字符一个字符的追加过去 curPos=m; 4.8、哈弗曼编码：创建好哈夫曼树之后，就可以对相应的字符串进行编码了，根数创建好的哈夫曼树，我们输入我们所需要编码的字符，然后系统就会帮我们自动编码。string Huf
19、fmanTree:Encode(char ch) /编码 for (int pos=1;pos=num; pos+) if (LeafCharspos=ch) return LeafCharCodespos;/ 找到字符,得到编码 return 0;4.9、哈夫曼译码：对编码后的0,1串进行译码得到相应的正确的字符编码。LinkList HuffmanTree:Decode(string strCode)/ 操作结果：对编码串strCode进行译码,返回编码前的字符序列 LinkList charList; / 编码前的字符序列 for (int pos = 0; pos strCode.le
20、ngth(); pos+)/ 处理每位编码 if (strCodepos = 0) curPos=nodescurPos.leftChild; / 0表示左分支 else curPos=nodescurPos.rightChild; / 1表示右分支 if (nodescurPos.leftChild=0&nodescurPos.rightChild=0)/ 译码时从根结点到叶结点路径的当前结点为叶结点 charList.Insert(charList.Length()+1,LeafCharscurPos); curPos =2*num-1; return charList; 五、测试与调试5
21、.1、概述 一般情况下，为解决一个问题所编写的程序代码较长，可能包括几百条甚至成千上万条语句。在检查并排除所有语法错误后，还会有不易发现的逻辑错误，因此要对程序进行认真仔细的测试与调试。测试是通过运行程序发现错误的过程，常见的错误有数据溢出、数组越界、进入死循环、语句顺序颠倒、多加“；”或少加“”等等。调试则是确定测试中找到的错误性质并改正错误的过程。测试与调试通常交替进行，即测试调试再测试再调试。能检查出尚未发现的、各种不同类型错误的测试才是成功的测试。测试程序需要测试用例，测试用例可用如下公式表示：测试用例测试数据预期结果。好的测试用例应该是用尽可能少的测试数据发现尽可能多的错误，即发现错
22、误的概率要大。要选择合适的测试数据，使系统在运行时尽量能执行到每条语句，以测试各指令是否正确。还应分别测试输入合法数据与非法数据时，程序的运行情况，。对于合法数据，还要考虑数据的一般性与特殊性，如求最大值的问题，应测试最大值在最前面、最后面、中间某一位置的情况。测试程序时，用监视窗口可以随时查看变量或表达式的值，有时还可以将部分程序代码用注释符暂时括起来，缩短程序，以便压缩出错代码的范围 5.2、程序测试在主菜单中选择1当用户输入1并按回车键后，即可进入数据输入界面。若是第一次运行该程序，应能实现从键盘输入哈夫曼树信息到链表中，当输入完信息后，结束建树过程，返回主菜单界面。若非第一次运行该程序
23、，应能实现从文件中读入编码信息到链表中，。其输入记录如图所示：在主菜单中选择2当用户输入2并按回车键后，即可进入编码界面。其编码过程如图所示： 在主菜单中选择3当用户输入3并按回车键后，即可进入译码界面。其译码过程如图所示： 在主菜单中选择0当用户输入0并按回车键后，即可执行退出哈夫曼编码译码程序的操作，返回操作系统。其操作结果提示信息如图所示：在文件中的存储的字符串和编码如下：六、系统维护经测试与调试确认软件无错时，开发就告一段落，这时可以交付软件供用户使用，但是在软件的使用过程中还会面临更加漫长的工作，即软件维护。一般维护的工作有：更改使用中发现的错误；为适应实际环境而对程序进行修改；为满
24、足新的需求而对程序作必要的改进等等。七、归纳总结 通过两个星期的程序设计，让我更加深入的了解了C语言、C+语言和数据结构知识，在设计过程的一开始，每个人都是一筹莫展，虽然不是第一次做实训，但是每次的实训都有新的难点需要突破，将C、C+和数据结构综合在一起，一开始真的不知该如何下手，然后在设计的过程中，碰到了许多问题，比如“”对应的不正确，语句的多余，在不同的编译环境里，也会出现问题，有时候脑子一浑，找个之前写好的函数都很难找到，有时候链接出错，还不知道是哪个里面出了问题，定义的函数太多，问题找起来就显得很吃力，有好些时候都快做不下去了。还好有老师和同学的帮助，我才可以解决这些拦路虎，完成这个程
25、序，这个程序看起来不是很复杂，我也不敢弄得很复杂，怕最后越写越乱。这个程序的设计也完全可以认为不完美，程序界面也不够美观大方，所以今后在程序设计方面还需要注意很多，可能还要花费更多的时间。虽然有不足，但是有不足才会有进步，通过这次实践，让我对程序设计的兴趣又加深了一些，这为我今后的学习奠定了很好的基础，我也会在今后好好完善自己，加强自己的动手能力，让自己能写出更完善更漂亮的程序。八、附源程序代码#include /程序中要用到文件流类ofstream，ofstream是在这个中定义的#include #include#include /系统自带的字符串库函数 ，strcpy包含在这个头文件中u
26、sing namespace std; struct Node char data; / 节点数据域为字符型 Node *next; Node() next = NULL; Node(char item,Node*link=NULL) data=item; next=link; ; ; class LinkList /仅保留几个用得到的成员函数protected: Node *head; Node *curPtr; int count,curPosition; Node *GetElemPtr(int position); / 返回指向第position个结点的指针public: LinkList(); int Length() const; bool Empty() const; void Traverse(); /遍历 void Traversetofile(); void Insert(int position, const char &e); char GetElem(int position); ;Node * LinkList:GetElemPtr(int position) if (curPositionposition)
