数据结构课程设计-赫夫曼编码的实现.doc

河南工程学院数据结构与算法课程设计成果报告赫夫曼编码的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1342班 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 26 日题 目赫夫曼书编码的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录一 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 课程设计要求1二 分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法描述32.4 程序流程图7三 程序清单8四 测试124.1测试数据124.2测试结果分析12五 总结15参考文献16一 课程设计目标与任务1.1 课程设计目标利用本次课程设计，使我们了解并掌握数据结构与算法结构的设计方法，增加独立分析和设计的能力，在算法的设计与实现方面得到更强的训练，加深对数据结构基本内容的理解和灵活应用，提高合理运用所学知识解决实际问题的能力。同时，培养初步的独立分析和设计的能力，在程序设计方法及上机操作方面得到更多的训练，也能培养上机所需要的动手能力。数据结构课程主要是研究非数值计算的程序设计问题中所现在的计算机操作对象以及它们之间的关系和操作的学科。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理，理解面向对象程序设计思想，初步具备运用面向对象程序设计方法进行程序设计的能力。1.2 课程设计任务根据所学的内容完成以下课程设计的任务：（1）任意输入若干个大写英文字母存入文件中，统计每个字母的频率并根据其频率构造赫夫曼树并使程序输出对应字母的赫夫曼编码；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所写程序来实现相关问题的求解。1.3 课程设计要求本次设计程序的要求是把随机输入的字符串中不同字符作为叶子结点元素，把其在该字符串中出现的次数作为权值构造一个赫夫曼树，并得到结点的赫夫曼编码，要求先对问题进行分析，了解题目的要求，画出流程图，然后用函数具体实现，认真完成软件设计的全部过程。同时通过课程设计来提高思维能力，促进综合应用能力和专业素质的提高。 二 分析与设计2.1 题目需求分析首先在一个文件中随机输入一个字符串，然后读取该文件中的字符并统计该文件中各个字符的频率，以频率作为权值，根据算法建立赫夫曼树，在根据对应字符的频率对出现的每个字符进行赫夫曼编码并输出。2.2 存储结构设计 1.构造赫夫曼树的步骤：（1）根据给定的n个权值w1,w2,.,wn构成n棵二叉树的集合F=T1，T2，.,Tn,其中每棵二叉树Ti中只有一个带权为wi的根节点，其左右子树均为空。（2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。（3）在F中删除这两棵树，同时将新得到的二叉树加入F中。（4）重复（2）和（3），直到F只含一棵树为止。这棵树便是赫夫曼树。2.赫夫曼编码：数据通信用的二进制编码。（1）思想：根据字符总频率编码，使电文总长最短。（2）编码规则：对于一棵二叉树规定左分支表示字符0，右分支表示字符1，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码，如此得到的必为二进制前缀编码。2.3 算法描述1.在一个文件中任意输入一段字符串，读取文件中的字符：int fileopen(char string) /读入文件 FILE *fp; if(fp=fopen(E:file.txtfll.txt,r)=NULL) printf(不能打开文件!n); exit(1); while(fgets(string,100,fp)!=NULL) printf(%sn,string); fclose(fp); return 0; 2.在ht中选择parent为0且权值最小的两个根结点的算法：void select_min(HuffmanTree T,int k,int &x1,int &x2) /选择权值最小的两个根结点,其序号为x1和x2 int i,j; int min1=1000; for(i=1;i=k;i+) /找最小值if(Ti.weightmin1 &Ti.parent=0) j=i; min1=Ti.weight; x1=j;min1=1000; for (i=1;i=k;i+) /找次小值if(Ti.weightmin1 & Ti.parent=0 & i!=x1) j=i; min1=Ti.weight; x2=j; 1. 统计字符串中的各个字母的个数：int tongji(char *s,int cishu,char str) /统计字符串中各种字母的个数以及字符的种类int i,j,k; char *p; int t27; for(i=1;i=A&*p=Z) k=*p-64; tk+; for(i=1,j=0;i=26;+i) if(ti!=0 ) j+; strj=i+64; /送对应的字母到数组中cishuj=ti; /存入对应字母的权值 return j; /j是输入字母种数 3.根据字符的个数构造赫夫曼树：void Create_huffmanTree(HuffmanTree ht,HuffmanCode hc,int cishu,char str) /生成哈夫曼树HT int i,s1,s2; for(i=0;i2*num-1;i+) hti.left=0; hti.right=0; hti.parent=0; hti.weight=0; for(i=1;i=num;i+) /输入num个叶 结点的权值hti.weight=cishui; for(i=num+1;i=2*num-1;i+) /选择parent为0且权值最小的两个根结点，其序号为s1和s2,i为双亲select_min(ht,i-1,s1,s2); hts1.parent=i;hts2.parent=i; hti.left=s1; hti.right=s2; hti.weight=hts1.weight+hts2.weight; for(i=0;i=num;i+) hci.ch=stri; /字符的种类i=1;while(i=num) printf(字符%c次数:%8dn,hci.ch,cishui+); 4.输出赫夫曼编码：void Huffman_bianma(HuffmanTree T,HuffmanCode H) /根据哈夫曼树T求哈夫曼编码H int child,parent,i; /child和parent分别指示t中孩子和双亲char coden; /存放编码int start; /指示码在code中的起始位置codenum=0; /最后一位（第num个）放上串结束符for(i=1;i0) /直至tchild是树根为止 /若tchild是tparent的左孩子,则生成0;否则生成1 if(Tparent.left=child) code-start=0; else code-start=1; child=parent; strcpy(Hi.co,&codestart); Hi.len=num-start; 2.4 程序流程图本程序流程为开始后先建立一个文件，若打开文件，在文件中任意输入若干个英文字母，读取文件的内容，统计字符的总数及频率。根据字符的频率构造赫夫曼树并输出赫夫曼编码，若不打开文件则结束程序。 建立赫夫曼树赫夫曼编码 结束输入字符存入文档字符总数num统计字符个数及频率 开始打开文件？否 是图2-1 程序流程图三 程序清单#include #include #include #include /类型相关变量的定义#define n 100 #define m 2*n-1 typedef struct char ch; char co9; /存放编码int len; CodeNode; typedef CodeNode HuffmanCoden+1; typedef struct int weight; int left,right,parent; HTNode; typedef HTNode HuffmanTreem+1; int num; void select_min(HuffmanTree T,int k,int &x1,int &x2) /选择权值最小的两个根结点,其序号为x1和x2 int i,j; int min1=1000; for(i=1;i=k;i+) /找最小值if(Ti.weightmin1 &Ti.parent=0) j=i; min1=Ti.weight; x1=j;min1=1000; for (i=1;i=k;i+) /找次小值if(Ti.weightmin1 & Ti.parent=0 & i!=x1) j=i; min1=Ti.weight; x2=j; int tongji(char *s,int cishu,char str) /统计字符串中各种字母的个数以及字符的种类int i,j,k; char *p; int t27; for(i=1;i=A&*p=Z) k=*p-64; tk+; for(i=1,j=0;i=26;+i) if(ti!=0 ) j+; strj=i+64; /送对应的字母到数组中cishuj=ti; /存入对应字母的权值 return j; /j是输入字母种数 void Create_huffmanTree(HuffmanTree ht,HuffmanCode hc,int cishu,char str) /生成哈夫曼树HT int i,s1,s2; for(i=0;i2*num-1;i+) hti.left=0; hti.right=0; hti.parent=0; hti.weight=0; for(i=1;i=num;i+) /输入num个叶 结点的权值hti.weight=cishui; for(i=num+1;i=2*num-1;i+) /选择parent为0且权值最小的两个根结点，其序号为s1和s2,i为双亲select_min(ht,i-1,s1,s2); hts1.parent=i;hts2.parent=i; hti.left=s1; hti.right=s2; hti.weight=hts1.weight+hts2.weight; for(i=0;i=num;i+) hci.ch=stri; /字符的种类i=1;while(i=num) printf(字符%c次数:%8dn,hci.ch,cishui+); void Huffman_bianma(HuffmanTree T,HuffmanCode H) /根据哈夫曼树T求哈夫曼编码H int child,parent,i; /child和parent分别指示t中孩子和双亲char coden; /存放编码int start; /指示码在code中的起始位置codenum=0; /最后一位（第num个）放上串结束符for(i=1;i0) /直至tchild是树根为止 /若tchild是tparent的左孩子,则生成0;否则生成1 if(Tparent.left=child) code-start=0; else code-start=1; child=parent; strcpy(Hi.co,&codestart); Hi.len=num-start; void coding(HuffmanCode hc ,char *str) /对str所代表的字符串进行编码并写入文件int i,j; FILE *fp; fp=fopen(codefile.txt,w); while(*str) for(i=1;i=num;i+) if(hci. ch=*str) for(j=0;j=hci.len;j+) fputc(hci.coj,fp); break; str+; fclose(fp); void output() /输出编码 FILE *fp; char ch; if(fp=fopen(codefile.txt,r+)=NULL) printf(errorn); exit(0); printf(编码为:n); ch=fgetc(fp); while(!feof(fp) putchar(ch); ch=fgetc(fp); printf(n); int fileopen(char string) /读入文件 FILE *fp; if(fp=fopen(E:file.txtfll.txt,r)=NULL) printf(不能打开文件!n); exit(1); while(fgets(string,100,fp)!=NULL) printf(%sn,string); fclose(fp); return 0; /主函数void main() char string100; char *s,str27; int cishu27; HuffmanTree HT; HuffmanCode HC; int x; printf(*n); printf(* 哈夫曼编码*n); printf(*n); while(1) printf(请选择); printf(t 1.开始n); printf(t 2.输出各字符统计个数n); printf(t 3.编码n); printf(t 4.输出编码n); printf(t 5.退出n); scanf(%d,&x); switch(x) case 1: printf(读出文本为：n); fileopen(string); break; case 2: num=tongji(string,cishu,str); /统计字符的种类及各类字符出现的次数Create_huffmanTree(HT,HC,cishu,str); break; case 3: Huffman_bianma(HT,HC); /生成哈夫曼编码coding(HC,string); /建立电文哈夫曼编码文件break; case 4: output(); break; case 5: exit(0); free(HT); default: printf(输入错误!n); continue; 四 测试4.1测试数据在编写及运行程序时出现了很多问题，如文件打开失败等问题，经过反复调试本程序可以实现界面上相应的功能，在运行程序时输入不同的选项可得出相应的操作结果。4.2测试结果分析1开始界面：进入系统后，选择操作1可得界面，如图4-1所示：图4-1 开始界面图2.统计频率：选择操作2时会出现对输入的字符进行统计频率如图4-2所示：图4-2 统计频率图3.输出编码：构造赫夫曼树并对所输入的字符进行编码，如图4-3所示：图4-3 输出编码图4.退出程序：选择5退出正在执行的程序，如图4-4所示：图4-4 退出程序图 五 总结此次课程设计让我懂得了理论与实际相结合是很重要的，只有理论知识与实践相结合起来，从理论中得出结论，从而提高自己的实际动手能力和独立思考的能力，每完成一个项目不仅是知识体系的完整和知识验证，更是编程技术的提升。这次课程设计也发现了自己很多的不足，对以前所学过的知识理解的不够深刻，掌握的不够牢固，知道了把在课堂上学习的东西运用到实际问题中并不容易，对我们来说每一次课程设计都是一次提高。“实验是检验真理正确性的唯一标准”，尤其是学习编程如果不通过自己动手，是无法真正领悟其中的道理的。课程设计是非常锻炼人的，多次编程之后就会自己摸索更高效的编程方法，在一次次的锻炼中会不断的登上更高的台阶。参考文献1王路群.数据结构-C语言描述.中国水利水电出版社2严蔚敏等.数据结构题集.清华大学出版社3严蔚敏.数据结构（C语言版）.清华大学出版社4王国钧.数据结构实验教程（C语言版）.清华大学出版社5殷人昆.数据结构.清华大学出版社6傅清祥等.算法与数据结构.电子工业出版社#include #include #include #include /类型相关变量的定义#define n 100 #define m 2*n-1 typedef struct char ch; char co9; /存放编码int len; CodeNode; typedef CodeNode HuffmanCoden+1; typedef struct int weight; int left,right,parent; HTNode; typedef HTNode HuffmanTreem+1; int num; void select_min(HuffmanTree T,int k,int &x1,int &x2) /选择权值最小的两个根结点,其序号为x1和x2 int i,j; int min1=1000; for(i=1;i=k;i+) /找最小值if(Ti.weightmin1 &Ti.parent=0) j=i; min1=Ti.weight; x1=j;min1=1000; for (i=1;i=k;i+) /找次小值if(Ti.weightmin1 & Ti.parent=0 & i!=x1) j=i; min1=Ti.weight; x2=j; int tongji(char *s,int cishu,char str) /统计字符串中各种字母的个数以及字符的种类int i,j,k; char *p; int t27; for(i=1;i=A&*p=Z) k=*p-64; tk+; for(i=1,j=0;i=26;+i) if(ti!=0 ) j+; strj=i+64; /送对应的字母到数组中cishuj=ti; /存入对应字母的权值 return j; /j是输入字母种数 void Create_huffmanTree(HuffmanTree ht,HuffmanCode hc,int cishu,char str) /生成哈夫曼树HT int i,s1,s2; for(i=0;i2*num-1;i+) hti.left=0; hti.right=0; hti.parent=0; hti.weight=0; for(i=1;i=num;i+) /输入num个叶 结点的权值hti.weight=cishui; for(i=num+1;i=2*num-1;i+) /选择parent为0且权值最小的两个根结点，其序号为s1和s2,i为双亲select_min(ht,i-1,s1,s2); hts1.parent=i;hts2.parent=i; hti.left=s1; hti.right=s2; hti.weight=hts1.weight+hts2.weight; for(i=0;i=num;i+) hci.ch=stri; /字符的种类i=1;while(i=num) printf(字符%c次数:%8dn,hci.ch,cishui+); void Huffman_bianma(HuffmanTree T,HuffmanCode H) /根据哈夫曼树T求哈夫曼编码H int child,parent,i; /child和parent分别指示t中孩子和双亲char coden; /存放编码int start; /指示码在code中的起始位置codenum=0; /最后一位（第num个）放上串结束符for(i=1;i0) /直至tchild是树根为止 /若tchild是tparent的左孩子,则生成0;否则生成1 if(Tparent.left=child) code-start=0; else code-start=1; child=parent; strcpy(Hi.co,&codestart); Hi.len=num-start; void coding(HuffmanCode hc ,char *str) /对str所代表的字符串进行编码并写入文件int i,j; FILE *fp; fp=fopen(codefile.txt,w); while(*str) for(i=1;i=num;i+) if(hci. ch=*str) for(j=0;j=hci.len;j+) fputc(hci.coj,fp); break; str+; fclose(fp