哈夫曼编译码器

湖南商学院 《计算机软件 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 》课程设计(实习)报告 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 　目   哈夫曼编/译码器                      姓 名: 陈琦 学 号: 080910044 专 业: 电信 班 级: 0802 指导教师: 李朝良 职 称: 教授     计算机与电子工程学院 2011年11月 课程设计(实习)评审表 姓 名 陈琦 学 院 计算机与电子工程学院 学 号 080910044 专业班级 电信0802 题 目 哈夫曼编/译码器 评 审 意 见   评审成绩   指导教师签名   职称   评审时间 年 月 日                       课程设计(实习)作品验收表 题目 哈夫曼编/译码器 参与人员 姓 名 陈琦   班 级 电信0802   学 号 080910044   设计任务与要求： 设计一个哈夫曼编/译码器，实现编码、译码功能。 作品完成情况： 成功运行，实现了简单编码译码功能。 验收情况： 验收教师签名：___________ 年 月 日         注：1. 除“验收情况”栏外，其余各栏均由学生在作品验收前填写。 2. “验收情况”栏由验收小组按实际验收的情况如实填写。 目录 1 课程设计任务与要求     1 1.1  课程设计任务    1 1.2  问题分析    1 2 系统总体设计    1 2.1总体设计思想、设计 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 的选择    1 2.2 系统结构图    3 3 系统详细设计    3 3.1 确定所需模块    3 3.2 各子模块功能描述    4 4 系统实现与测试    5 4.1系统测试用例的设计    5 4.2系统测试结果    6 5 课程设计总结    10 参考文献    10 附录    11 哈夫曼编/译码器 1 课程设计任务与要求 1.1  课程设计任务 此次课程设计要求设计一个哈夫曼编/译码器，实现如下功能： 一、在本程序中，用户通过键盘进行人机交互，可以在键盘上输入字符集大小，字符可以出现重码，字符输入顺序不受限制。 二、演示程序以用户与计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（可虑去输入中的非法字符）和运算结果显示在其后。  三、本演示程序中，当用户选择的功能错误时，系统会输出相应的提示。  四、在本程序中，用户对给定的原字符串进行编码，对给定的编码串进行译码。 1.2  问题分析 哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。构造好哈夫曼树后，就可根据哈夫曼树进行编码。然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方法就是哈夫曼算法。字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。 分析此次设计，是关于实现利用哈夫曼算法编码和译码功能的问题，要求能重复地显示并处理以下项目，即构造哈夫曼树，编码及译码几项功能，直到选择退出为止。本次设计就是为这样的一个哈夫曼的编/译码器。 2 总体设计 2.1总体设计思想、设计方案的选择 哈夫曼编码所以能产生较短的码文，是因为哈夫曼树具有最小加权路径长度的二叉树。如果叶结点的权值恰好是某个需编码的文本中各字符出现的次数，则编码后文本的长度就是该哈夫曼树的加权路径长度。译码过程为自做向右逐一扫描码文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与哈夫曼树上标的0，1相匹配，以确定一条从根到叶子结点的路径，一旦到达叶子，则译出了一个字符。再回到树根，从二进位串的下一位开始继续译码。  2.1.1建立设计模块间关系 本设计的函数调用关系如下图： 2.1.2数据结构的选择 为了建立哈夫曼树以及实现哈夫曼编码以及译码，因此我们选择了结点结构体，利用这一结构体，我们定义了一个结构体数组和一个树根指针，数组用来纪录输入数据的多少，树根指针用来连接哈夫曼树。从程序中可以看到使用哈夫曼算法构造哈夫曼树过程，是从n棵知识一个根结点的树组成的森林开始的。在算法执行中，哈夫曼树是由若干棵树组成的森林，通过不断地合作树，最后得到一棵哈夫曼树。 a.  typedef struct {  int weight; int parent,lchild,rchild; }HTNode,* HuffmanTree;    //动态分配数组存储赫夫曼树   typedef char **HuffmanCode;  //动态分配数组存储赫夫曼编码表 b.  int min(HuffmanTree t,int i)    // ---------求赫夫曼编码------------- c.  void select(HuffmanTree t,int i,int &s1,int &s2) //----slect函数---- d.  void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) // w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC e.  void Initialization()        //----------初始化赫夫曼链表-------------- f.  void InputCode()          //---------获取报文并写入文件------------- g.  void Encoding()          //----------------编码函数------------------ h.  void Decoding()          //-----------------译码函数----------------- i.  void Code_printing()      //-------------打印编码的函数-------------- j.  void coprint(HuffmanTree start,HuffmanTree HT) //------------------------打印赫夫曼树的函数----------------------- k.  void main()              //--------------------主函数------------------- 2.2 系统结构图  图2.2 哈夫曼编/译码器结构框图 3 详细设计 3.1 确定所需模块 一个完整的系统应具有以下功能模块：  主函数模块main()。 I：初始化（Initialization）模块。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。输出哈夫曼树，及各字符对应的编码。 W：输入（Input）模块。从终端读入需要编码的字符串s，将字符串s存入文件Tobetran.txt中。 E：编码（Encoding）与译码（Decoding）模块。 编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。 T：印哈夫曼树（Tree Printing）模块。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 Q：退出程序模块。返回WINDOWS界面。 3.2 主要子模块功能描述 3.2.1主函数模块 Void mian（） {打印表头； While(选择项不为q){ 输入选择项； Switch(选择项) {Case i： 初始化；break; Case w： 输入要编码的字符； break； Case e： 编码字符； break； Case t； 打印赫夫曼树； break； Default：输入命令错误，重新继续输入； } 3.2.2初始化模块 程序从文件abc.txt中自动获取26个英文字母的权值。 3.2.3编码模块 a.对输入的一段欲编码的字符串进行统计各个字符出现的次数，并它们转化为权值{w1,w2,……，wN}构成n棵二叉树的集合F={T1,T2,……，Tn}把它们保存到结构体数组HT[n]中,其中{Ti是按它们的ASCⅡ码值先后排序。其中每棵二叉树Ti中只有一个带权为Wi的根结点的权值为其左、右子树上根结点的权值之和。 b.在HT[1..i]中选取两棵根结点的权值最小且没有被选过的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。 c.哈夫曼树已经建立后，从叶子到根逆向求每一个字符的哈夫曼编码。 3.2.4译码模块 译码的过程是分解电文中字符串，从根出发，按字符'0',或'1'确定找左孩子或右孩子，直至叶子结点，便求的该子串相应字符并输出接着下一个字符。 4 系统实现与测试 4.1系统测试用例的设计 此次测试举例为对输入的英文HAPPYNEWYEAR应用创建的哈夫曼编译码器进行编码再译码。 声明：程序预先将Huffman编码解码所需的26个字母和权值保存在根目录下的abc.txt文件下。 a.按照程序提示输入i对Huffman进行初始化。 b.初始化后程序对abc.txt文件中的数据进行读取并运行编码函数进行哈夫曼编码。然后将字母、权值和哈夫曼编码存在根目录下的htmTree.txt文件中。在屏幕显示出字符、权值、编码。 c.输入w进入待编码字符输入窗口，并键入字符串（注意单词间无空格）“HAPPYNEWYEAR”。 d.可以看出所获得的字符串已经存入根目录下的tobetran.txt文件中。 e.输入e进行编码、译码和打印编码功能。 f.输入t打印哈夫曼树。 g.输入q退出程序。 4.2系统测试结果 5 课程设计总结 通过这次课程设计使我充分的理解了哈夫曼编译码问题的基本原理，知道了树的不同存储结构的定义和算法描述，同时也学会了编写简单的哈夫曼编译码程序。虽然这个程序不是最好的，但是总体还是一个比较能体现数据结构 知识点 高中化学知识点免费下载体育概论知识点下载名人传知识点免费下载线性代数知识点汇总下载高中化学知识点免费下载 能力的程序，当然只是相对于我这个初学者来说。在刚开始编程的时候，我感到很茫然，无从下手，很多细节没有注意，特别是在编写格式和符号代码上，曾多次编译出错。但是困难是可以解决的，只要通过努力，虚心学习请教，再难的题目也可以自己动手完成。通过这次的数据结构课程设计，我也深刻了解到这门学问的博大精深，要积极进取，不断学习，不断积累知识。同时我也认识到自己的不足和缺点，做什么事都需要细心和耐心，并坚持下去，这样才能有一个比较满意的结果。 参考文献 [1] 黄同成，黄俊民，董建寅．数据结构[M]．北京：中国电力出版社，2008 [2] 董建寅，黄俊民，黄同成．数据结构实验指导与题解[M]．北京：中国电力出版社，2008 [3] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社，2002 [4] 刘振鹏，张晓莉，郝杰．数据结构[M]．北京：中国铁道出版社，2003 附录 #include #include #include #include #include #include #include const int UINT_MAX=10000; typedef struct { int weight; int parent,lchild,rchild; }HTNode,* HuffmanTree;    typedef char **HuffmanCode; HuffmanTree HT; HuffmanCode HC; int *w,i,j; const int n=26; char *z; int flag=0; int numb=0; int min(HuffmanTree t,int i) {    int j,flag; int k=UINT_MAX; for(j=1;j<=i;j++) if(t[j].weights2) { j=s1; s1=s2; s2=j; } } void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) { int m,i,s1,s2,start; int c,f; HuffmanTree p; char *cd; if(n<=1) return; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT+1,i=1;i<=n;++i,++p,++w) { p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; } for(;i<=m;++i,++p) p->parent=0; for(i=n+1;i<=m;++i) { select(HT,i-1,s1,s2); HT[s1].parent=HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;i++) { start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd); } void Initialization() { flag=1; int num2; cout<<"下面初始化哈夫曼链表"<>base; *(z+i)=*base;//? fin>>num2; *(w+i)=num2; } HuffmanCoding(HT,HC,w,n); cout<<"字符"<n) { cout<<"字符错误，无法编码!"< 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 写入根目录下的文件textfile.txt中"<rchild,HT);            cout<weight<weight); coprint(HT+start->lchild,HT); numb--; fclose(TreePrint); } } void Tree_printing(HuffmanTree HT,int w) { HuffmanTree p; p=HT+w;                cout<<"下面打印哈夫曼树"<>choice; switch(choice) { case 'i': Initialization(); break; case 'w':      InputCode(); break; case 'e': Encoding();        Decoding(); Code_printing(); break; case 't': Tree_printing(HT,2*n-1); break; case 'q':                break; default: cout<<"输入命令错误 "<