哈夫曼编码译码器

哈夫曼编码译码器 沈阳航空航天大学 课 程 设 计 报 告 课程设计名称:数据结构课程设计 课程设计题目:哈夫曼编码/译码器 院(系):计算机学院 专 业:计算机科学与技术 班 级: 学 号: 姓 名: 指导教师: 沈阳航空航天大学课程设计 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 目录 沈阳航空航天大学....................................................................................................... I 第1章 概要设计 ........................................................................................................ 1 1.1题目的内容与要求 ............................................................................................. 1 1.2总体结构 ............................................................................................................. 1 第2章 算法 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ........................................................................................................ 2 2.1核心算法思想 ..................................................................................................... 2 2.2算法结构定义 ..................................................................................................... 2 第3章 详细设计 ........................................................................................................ 3 3.1功能流程 ............................................................................................................. 3 第4章 系统实现 ........................................................................................................ 5 4.1错误分析 ............................................................................................................. 5 4.2运行结果 ............................................................................................................. 5 参考文献 ...................................................................................................................... 8 附 录 .......................................................................................................................... 9 I 沈阳航空航天大学课程设计报告 第1章 概要设计 1.1题目的内容与要求 内容:设计一个利用哈夫曼算法的编码和译码系统，可以接收从键盘输入的字符集大小、字符和权值信息，创建哈夫曼树生成哈夫曼编码并能对其进行解码。 要求: 1(存储结构自定; 2(将生成的哈夫曼编码与等长编码进行比较，判断优劣; 3(给出动态演示过程(选作)。 1.2总体结构 本程序主要分为3个模块(功能模块图见图1.1):主模块，编码模块，译码模块。主模块:程序的主体部分，分别调用各个模块，实现各项功能。编码模块:对每个出现的字符进行编码。译码模块:将已有编码译成字符，使之可以直接被读出。 哈夫曼编码/译码器 编译主码码模模模块块块 图1.1功能模块图 1 沈阳航空航天大学课程设计报告 第2章 算法分析 2.1核心算法思想 哈夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算法的第二步是:将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树;每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行n,1次合并，所以共产生n,1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中一共有2n,1个结点，其中n个结点是初始森林的n个孤立结点。并且哈夫曼树中没有度数为1的分支结点。我们可以利用一个大小为2n--1的一维数组来存储哈夫曼树中的结点。 哈夫曼编码是可变字长编码。编码时借助哈夫曼树，也即带权路径长度最小的二叉树，来建立编码。 译码的基本思想是:读文件中编码，并与原先生成的赫夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中。 2.2算法结构定义 结构体存储表示 typedef struct{ int weight; int parent,lchild,rchild; }Htnode,*Hfmtree; //动态分配数组存储哈夫曼树 typedef char **Hfmcode; //动态分配数组存储哈弗曼编码表 2 沈阳航空航天大学课程设计报告 第3章 详细设计 3.1功能流程 此流程图为构造哈夫曼树的过程，输入字符的次数为权值对每个结点赋值， 构造哈夫曼树，如图3.1 开始 以读入字符次数对各结点 赋初值并令i=2n-1 Yi为0 N 找出根结点权值最小和次小树s1, s2 两树合并成新树n+i i减1 结束 图3.1 流程图 3 沈阳航空航天大学课程设计报告 此流程图(图3.2)为对字符进行哈夫曼编码的过程，将字符转化为哈夫曼编码。 开始 第一个字符，i=1 Ni<=n Y N 结点是否是根结点 Y 双亲结点的左结点是否等于该结点 N将得到的编码存储Y 记编码0 记编码1 图3.2字符编码模块流程图 i=i+1 4 结束 沈阳航空航天大学课程设计报告 第4章 系统实现 4.1错误分析 在此程序调试过程中主要遇到以下几类问题: 1、本程序运用了对文件进行操作，一定要注意在操作文件是文件的位置，我在做次程序是就是因为操作的文件位置错了导致程序无法正常运行。 2、在函数内部有时需要多定义参数，注意参数的作用域，而且注意传引用调用和传值调用的区别，不能不正确的修改实参的值，否则会导致程序运行的错误。 3、本程序用到的外部函数较多，在调用时一定要注意传入的参数是否符合函数的定义，而且位置也不能错，这是引用函数要注意的一点。 4、刚开始时清屏函数运用出错，导致操作界面消失，使用户无法操作，因此，在使用一些函数是一定要注意。 4.2运行结果 运行程序首先出现界面图，如图4.2所示。 图4.1界面图 选择操作1后，输入相应的字符大小，字符和权值，生成哈夫曼树。系统会显示每个字符的哈夫曼编码，如图4.2所示。 5 沈阳航空航天大学课程设计报告 图4.2程序运行截图 选择操作2后，输入字符串，系统会显示对字符串进行哈弗曼编码得到的哈弗曼编码，显示以下界面(图4.3)供用户选择。 图4.3程序运行截图 选择操作3后，系统会显示用哈夫曼编码翻译成的字符，显示以下界面(图4.4)供用户选择 图4.4程序运行截图 选择操作4后，退出系统，显示以下界面(图4.5) 6 沈阳航空航天大学课程设计报告 图4.5程序运行截图 7 沈阳航空航天大学课程设计报告 参考文献 [1] 严蔚敏.数据结构(C语言版).清华大学出版社，2007 [2] 谭浩强.C语言程序设计教程.高等教育出版社，2006 [3] 苏仕华.数据结构课程设计.机械工业出版社，2007 8 沈阳航空航天大学课程设计报告 附 录 源程序如下: #include #include #include #include #include typedef struct{ //赫夫曼树的结构体 char ch; int weight; //权值 int parent,lchild,rchild; }Htnode,*Hfmtree; //动态分配数组存储赫夫曼树 typedef char **Hfmcode; //动态分配数组存储赫夫曼编码表 void Select(Hfmtree &HT,int a,int *s1,int *s2) //Select函数，选出HT树到a为止，权值最小且parent为0的2个节点 { int i,j,x,y; for(j=1;j<=a;++j){ if(HT[j].parent==0){ x=j; break; } } for(i=j+1;i<=a;++i){ if(HT[i].weighty){ *s1=y; *s2=x; } else { *s1=x; *s2=y; } } void Hfmcoding(Hfmtree &HT,Hfmcode &HC,int n) //构建赫夫曼树HT，并求出n 10 沈阳航空航天大学课程设计报告 个字符的赫夫曼编码HC { int i,start,c,f,m,w; int p1,p2; char *cd,z; if(n<=1){ return; } m=2*n-1; HT=(Hfmtree)malloc((m+1)*sizeof(Htnode)); for(i=1;i<=n;++i) //初始化n个叶子结点 { printf("请输入第%d字符信息和权值:",i); scanf("%c%d",&z,&w); while(getchar()!='\n') { continue; } HT[i].ch=z; HT[i].weight=w; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(;i<=m;++i) //初始化其余的结点 { HT[i].ch='0'; 11 沈阳航空航天大学课程设计报告 HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(i=n+1;i<=m;++i) //建立赫夫曼树 { Select(HT,i-1,&p1,&p2); HT[p1].parent=i; HT[p2].parent=i; HT[i].lchild=p1; HT[i].rchild=p2; HT[i].weight=HT[p1].weight+HT[p2].weight; } HC=(Hfmcode)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'; 12 沈阳航空航天大学课程设计报告 } else { cd[--start]='1'; } } HC[i]=(char*)malloc((n-start)*sizeof(char)); //为地i个字符 编码分配空间 strcpy(HC[i],&cd[start]); } free(cd); } void main() { char code[100],h[100],hl[100]; int n,i,j,k,l; ifstream input_file; //文件输入输出流 ofstream output_file; char choice,str[100]; Hfmtree HT; Hfmcode HC; while(choice!='4') //当choice的值4时循环 { printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); 13 沈阳航空航天大学课程设计报告 printf(" *************************赫夫曼编码/译码器*************************\n"); printf(" ************************* 1 创建哈夫曼树 *************************\n"); printf(" ************************* 2 编码 *************************\n"); printf(" ************************* 3 译码 *************************\n"); printf(" ************************* 4 退出 *************************\n"); printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); printf("请输入您要操作的步骤"); cin>>choice; if(choice=='1') //初始化赫夫曼树 { cout<<"请输入字符个数:"; cin>>n; Hfmcoding(HT,HC,n); for(i=1;i<=n;++i) { cout<>code; cout<<"编码码值为:"<>h; input_file.close(); output_file.open("Textfile.txt"); if(!output_file) 16 沈阳航空航天大学课程设计报告 { cout<<"can't oen file!"<>h; cout< 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf : 通过近两周的课程设计使我对哈夫曼树以及哈夫曼编码译码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。 在做课设的过程中我也遇到了很多问题:开始的时候，代码中有许多的错误，特别是有一个“无法找到文件”的错误让我束手无策，最后还是屏蔽了定义的四个头文件然后慢慢地改正错误才让我又看到了希望。然后在实现文章的读入时，由于对文件不是太熟悉，只好翻开C语言和C++语言书本仿照其模式编写，但后来进入了死循环，最后的解决方式是在main函数里有一个控制语句使用不正确。 我们遇到问题很正常，说明我们掌握的知识还是太少不灵活，并且这些错误也让我明白了一个道理---细节决定成败。同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师和同学也很重要，毕竟对待同一问题我们会有不同的理解和分析，相互之间的交流也是一种学习方法的沟通。 通过这次课程设计，我看清楚了自己的编程功底和动手能力还不如人意，这主要是平时实践太少的缘故。我想，在即将到来的寒假中，我会努力尝试编写一些程序，争取提高自己的编程水平。我相信通过我的不断努力，我一定能收获更多果实。 指导教师评语: 指导教师(签字): 年 月 日 课程设计成绩 19 沈阳航空航天大学课程设计报告 20