[计算机软件及应用]赫夫曼编译码器说明书

《[计算机软件及应用]赫夫曼编译码器说明书》由会员分享，可在线阅读，更多相关《[计算机软件及应用]赫夫曼编译码器说明书（34页珍藏版）》请在装配图网上搜索。

1、目 录摘 要1前 言2正 文31.采用类c语言定义相关的数据类型32.各模块的伪码算法33.函数的调用关系图34.调试分析35.测试结果36.源程序（带注释）3总 结4参考文献5致 谢6附件 部分源程序代码7摘 要本课程设计主要研究如何解决对于给定的叶子数目及其权值构造最优二叉树的方法。通过对问题的分析，采用哈夫曼算法的设计思想。根据给定的权值构成二叉树森林，在森林中任意选取两棵根结点权值最小的树，将这两棵树合并为新的树，为保证新树仍为二叉树，需要增加一个新的结点作为根将这两个孩子的权值之和作为新树根的权值。对新的森林重复上述步骤直到森林中只剩一棵树为止。此树即为哈夫曼树。前 言字符以某种编码

2、形式存储在计算机中，目前世界上应用最广泛的两个字符是ASCII码（美国信息交换标准码）和EBCDIC码（扩充的二进制的十进制信息码）。当采纳这两个字符集时字符在计算机内是以固定长度的比特串表示的。但事实上，在具体应用中字符集中字符的使用频率常常差别很大，为了提高存储和传输的效率，可采用不等长的编码方式。若要设计不等长编码，则要求对字符集中任一字符的编码都不是另一个字符编码的前缀，称这种编码符合前缀特性，也称前缀编码，前缀编码可以一个字符一个字符地进行译码，不需要在字符之间添加分隔符。利用哈夫曼编码可以解决上述问题。正 文1. 采用类c语言定义相关的数据类型用C语言实现 :typedef str

3、uct HaffmanTreeNode char ch, code15; /ch 代表当前字符，code 代表这个字符的编码 int weight; /当前统计的字符的个数 int parent, lchild, rchild; HTNode, *HaTree; typedef struct HTNode arrMAX_NODE; int total; HTree; Max_Node 代表数的最大结点数 Max_Weight 代表权值的最大值typedef struct /结点类型int weight; /根节点的权值int flag; /标志位,为0即没有双亲,反之则是int parent;

4、 /双亲结点 char ch; /要编码的字符,即哈夫曼树叶子int lchild; /根节点的左孩子int rchild; /根节点的右孩子HafNode;typedef struct /哈夫曼编码int bitMAX_NODE; /二进制编码位,用于存放哈夫曼树编码int start; /编码的值在数组存放的起始位置int weight; /要编码的字符出现的频率,即权值char ch; /要编码的字符Code;typedef struct /编码操作类型char bitMAX_NODE; /将字符的编码结果存入bit数组中char ch; /要编码的字符int weight; /字符出现

5、的频率Coding;typedef struct /输入字符信息 HafNode arrMAX_NODE; /数组结点信息 int total; /统计输入字符的种类个数 HTree;2. 各模块的伪码算法算法描述 : int statistic_char(char *text, HTree *t) /* 统计字符出现的频率 */ int text_len = strlen(text); t-total = 0; for (i=0; itext_len; i+) for (j=0;jtotal ; j+) if (t-arrj.ch = texti) .统计已经出现的字符的个数 if (j=t

6、-total) .记录新出现的字符 return t-total; /打印出字符和它们的出现的次数 int create_htree(HTree *t) /* 建立一棵赫夫曼树,并对数据初始化 */ for (i=0; itotal total_node) /初始森林根节点数小于合并后新树的所有结点数 min1 = min2 = Max_Weight; for (i=0; itotal; i+) .找到当前权值最小的两个结点,并把它们建立成一棵新树,其中树根的权值为这两个的权值的和 t-total +; return 0; void coding(HTree *t, int head_i, c

7、har *code) /* 对哈夫曼树进行编码 */ if ( head_i = -1) /判断是否为空，为空返回 return;.从树的根节点出发，查找左子树输出0，查找右子树输出1，直到找到该树的叶子结点，按每个叶子结点在数组中的下标依次输出 void print_htree_ldr(HTree *t, int head_i, int deep, int* path) /* 中序打印树 */ .判断是否为空树，是的话返回；不是的话，按照先输出左孩子，然后输出双亲，再输出右孩子的方法依次打印各个字符和它的权值； void code_string(char *text, HTree *t) /

8、* 对字符进行编码 */ 变量初始化： for (条件判断) 依次输出每个字符的编码 3. 函数的调用关系图4. 调试分析a、 调试中遇到的问题及对问题的解决方法调试过程中遇到的问题及解决： 我在该程序中遇到的最大问题是如何以文件形式存储赫夫曼树，以及如何从文件读取赫夫曼树，读与存都要涉及到字符串转换成整数或整数转换成字符串的问题，最后终于成功了，可是很耗时，不知道是不是我的方法太不好了。b、算法的时间复杂度和空间复杂度算法的时空分析 在此程序中，存储字符串都用了指针，先动态申请空间，然后再存，这样就有效的利用了空间，不过为了实现任意长字符串的输入，最后转存到字符指针里，这样就浪费了一些空间。

9、 而对于哈夫曼树算法本身，由于这里只是一个静态的，所以当进行网络传输时，可能会显得效率比较低。 5. 测试结果6. 源程序（带注释）#include #include #include #define MAX_NODE 100 /代表哈夫曼树最大的结点数#define MAX_VALUE 10000 /代表权值的最大值typedef struct /结点类型int weight; /根节点的权值int flag; /标志位,为0即没有双亲,反之则是int parent; /双亲结点 char ch; /要编码的字符,即哈夫曼树叶子int lchild; /根节点的左孩子int rchild;

10、/根节点的右孩子HafNode;typedef struct /哈夫曼编码int bitMAX_NODE; /二进制编码位,用于存放哈夫曼树编码int start; /编码的值在数组存放的起始位置int weight; /要编码的字符出现的频率,即权值char ch; /要编码的字符Code;typedef struct /编码操作类型char bitMAX_NODE; /将字符的编码结果存入bit数组中char ch; /要编码的字符int weight; /字符出现的频率Coding;typedef struct /输入字符信息 HafNode arrMAX_NODE; /数组结点信息 i

11、nt total; /统计输入字符的种类个数 HTree; void statistic_char(char text, HTree *t) /* 统计字符出现的频率 */ FILE *fp,*fp1; char ch,ch120;printf(请输入一批字符数据: nA:键盘输入 B:文件输入n);scanf(%c,&ch);if(ch=A)scanf( %s,text);if(ch=B)printf(请输入文件名: n);scanf( %s,ch1); if(fp=fopen(ch1,r)=NULL) puts(cant open file!); exit(0); fscanf(fp,%s

12、,text); fclose(fp); fp1=fopen(zifu_quanzhi.txt,w+);int text_len = strlen(text); t=(HTree *)malloc(sizeof(HTree); t-total = 0; int i,j; for (i=0; itext_len; i+) for (j=0;jtotal; j+) if (t-arrj.ch = texti) /要统计字符在之前已出现 t-arrj.weight+; break; if (j=t-total) /记录新出现的字符 t-total+; t-arrj.ch=texti; t-arrj.w

13、eight=1; printf(共有%d个数据项!n,t-total); fprintf(fp1,%dn,t-total);printf(字符t 出现次数n); for(j=0;jtotal;j+) /打印出字符和它们的出现的次数printf(%ct %dn,t-arrj.ch,t-arrj.weight);fprintf(fp1,%c%d ,t-arrj.ch,t-arrj.weight);free(t); fclose(fp1); void Haffman(int weight,char ch,int n,HafNode haffTree) /* 生成哈夫曼树的函数 */int i,j,m

14、1,m2,x1,x2;for (i=0;i2*n-1;i+) /对所有结点初始化if(in) /对n个叶子结点赋值haffTreei.weight=weighti;haffTreei.ch=chi;else /对n-1个新结点权值清0haffTreei.weight=0;haffTreei.parent=-1;haffTreei.flag=0;haffTreei.lchild=-1;haffTreei.rchild=-1;for (i=0;in-1;i+) /找到当前权值最小的两个结点,并把它们建立成一棵新树,其中树根的权值为这两个的权值的和m1=m2=MAX_VALUE;x1=x2=0;fo

15、r (j=0;jn+i;j+) /每次比较中m1等于符合比较条件的所有结点中最小的权值,相应的m2为次小 if (haffTreej.weightm1&haffTreej.flag=0) /注意:已有根节点的叶子在第2次以后的比较中实际不需比较m2=m1; /m2取相比较权值的较大值x2=x1; /x2取较大结点的下标m1=haffTreej.weight; /m1取相比较结点的较小权值x1=j; /x1取该结点所在下标值else if(haffTreej.weightm2 & haffTreej.flag=0)m2=haffTreej.weight;x2=j;haffTreex1.paren

16、t= n + i; /x1,x2指向新节点,其值等于在haffTree数组中的下标haffTreex2.parent = n + i;haffTreex1.flag = 1; /标志位置1haffTreex2.flag = 1;haffTreen+i.weight = haffTreex1.weight + haffTreex2.weight;haffTreen+i.lchild = x1;haffTreen+i.rchild = x2;FILE *fp; fp=fopen(haffman_tree.txt,w+);printf(本次输入初始森林根节点数:%dn,n); /输出叶子结点的个数f

17、printf(fp,%dn,n); /并写入文件for (i=0;in;i+)/写入文件的所有叶子结点的信息fprintf(fp,%c %d %d %dn,haffTreei.ch,haffTreei.parent,haffTreei.lchild,haffTreei.rchild); for (i=n;i2*n-1;i+) /写入文件的新结点的信息fprintf(fp,%d %d %dn,haffTreei.parent,haffTreei.lchild,haffTreei.rchild); fclose(fp);void HaffmanCode (HafNode haffTree,int

18、n,Code haffCode) /* 生成哈夫曼编码的函数 */Code *cd=( Code *) malloc (sizeof (Code);int i,j,child,parent;for (i=0; istart=n-1; cd-weight=haffTreei.weight;cd-ch=haffTreei.ch;child=i; parent=haffTreechild.parent;while (parent !=-1) /从叶子结点开始一直找到一棵树的根结点if (haffTreeparent.lchild=child)cd-bitcd-start=0;elsecd-bitcd

19、-start=1;cd-start-;child =parent;parent=haffTreechild.parent;for (j=cd-start+1; jbitj; haffCodei.start =cd-start+1; haffCodei.weight=cd-weight; haffCodei.ch=cd-ch;free(cd);void Init(int weight,char ch) /* 初始化操作,生成哈夫曼树及哈夫曼编码 */FILE *fp; int i,j,n; char ch1=0;printf(n现在进行初始化操作,相关数据从文件zifu_quanzhi.txt导

20、入.n,ch1);if(fp=fopen(zifu_quanzhi.txt,r)=NULL) puts(cant open file!); exit(0) ;fscanf(fp,%dn,&n);HafNode *myHaffTree=(HafNode *)malloc(sizeof (HafNode)*(2*n+1);Code *myHaffCode =(Code *)malloc (sizeof (Code)*n);for (i=0;iarrj.ch,t-arrj.weightfclose(fp);Haffman(weight,ch,n,myHaffTree); /CALL Haffman;

21、HaffmanCode(myHaffTree,n,myHaffCode); /CALL HaffmanCode;fp=fopen(leaves.txt,w+);printf(初始化后哈夫曼编码信息: n字符t权值t二进制编码 n);for (i=0;in;i+) printf(%ct %dt,myHaffCodei.ch,myHaffCodei.weight);fprintf(fp,%c %d ,myHaffCodei.ch,myHaffCodei.weight); for ( j=myHaffCodei.start; jn; j+) /从屏幕输出哈夫曼编码并写入到文件中printf(%d,m

22、yHaffCodei.bitj);fprintf(fp,%d,myHaffCodei.bitj); fprintf(fp,n);printf(n); fclose(fp); free(myHaffTree); free(myHaffCode);printf(初始化成功!n); printf(要清屏吗?(Y/N)n);scanf( %c,&ch1);if(ch1=Y)system(cls);void Caozuo_C() /* 哈夫曼编码过程的函数，用于将文件编码 */FILE *fp,*fp1,*fp2;char zf500;if(fp=fopen(leaves.txt,r)=NULL) pu

23、ts(cant open file!); exit(0) ; Coding ch100;char c;int i=0;while (feof(fp)=0) fscanf(fp,%c %d %sn,&chi.ch,&chi.weight,chi.bit); /对应150和161行myHaffCode输入的信息 i+; fclose(fp);printf(现在进行编码操作.n请选择:nA.键盘输入 B.文件输入n);scanf( %c,&c);if (c=A) printf(请输入字符串:n);scanf( %s,zf);char ch120,ch220; int j;if (c=B)scanf(

24、 %s,ch1);if(fp1=fopen(ch1,r)=NULL) puts(cant open file!); exit(0) ;printf(请输入保存结果的文件名:n);scanf( %s,ch2);fp2=fopen(ch2,w+);if (c=A) printf(二进制编码为: );int len,k;len=strlen(zf);for (k=0;klen;k+)for (j=0;ji;j+)if (chj.ch=zfk)fprintf(fp2,%s,chj.bit);printf(%s,chj.bit);printf(n);if (c=B)printf(二进制编码为: );wh

25、ile(feof(fp1)=0) fscanf(fp1,%c,&c);for (j=0;ji;j+) /对文件中的每一个字符进行编码if (chj.ch=c)fprintf(fp2,%s,chj.bit);printf(%s,chj.bit);fprintf(fp2,n); printf(n);fclose(fp1);fclose(fp2);printf(编码过程完成!同时已将结果存入%s中.nn,ch2);void Caozuo_D() /* 译码操作 */FILE *fp,*fp1,*fp2; if(fp=fopen(haffman_tree.txt,r)=NULL) puts(cant

26、open file!); exit(0) ; int i,n;fscanf(fp,%dn,&n);HafNode *myHaffTree=(HafNode *)malloc(sizeof (HafNode)*(2*n+1);for (i=0;in;i+) fscanf(fp,%c %d %d %dn,&myHaffTreei.ch,&myHaffTreei.parent,&myHaffTreei.lchild,&myHaffTreei.rchild); for (i=n;i2*n-1;i+) fscanf(fp,%d %d %dn,&myHaffTreei.parent,&myHaffTree

27、i.lchild,&myHaffTreei.rchild); fclose(fp);printf(请输入译码文件的文件名:n); /对应输入的文件名为ch2.txt(函数Caozuo_C中的)char ch,ch120,ch220;scanf( %s,ch1);printf(请输入结果文件的文件名:n);scanf( %s,ch2);if(fp1=fopen(ch1,r)=NULL) puts(cant open file!); exit(0) ; fp2=fopen(ch2,w+);i=2*n-2; /该值对应最后一个新的结点(即该树的根结点)在数组中的下标printf(译码结果是: );w

28、hile (!feof(fp1) fscanf(fp1,%c,&ch);if (ch=0) /若编码为0,则找此结点的左孩子;i=myHaffTreei.lchild;if (ch=1) /若编码为1,则找此结点的右孩子;i=myHaffTreei.rchild; if (in) /表示找到了树的叶子结点,即对应译码后的字符printf(%c,myHaffTreei.ch); fprintf(fp2,%c,myHaffTreei.ch);i=2*n-2; /继续读下一个编码,再从根结点顺序查找叶子结点printf(n);fprintf(fp2,n);fclose(fp1);fclose(fp2

29、);printf(译码过程完成!已将结果存入%s中.n,ch2); free(myHaffTree);void Caozuo_P() /* 打印代码文件的操作 */FILE *fp1,*fp2;printf(请输入文件名:n);char ch120,ch220;scanf( %s,ch1);printf(请输入结果保存的文件名:n);scanf( %s,ch2);if(fp1=fopen(ch1,r)=NULL) puts(cant open file!); exit(0) ; fp2=fopen(ch2,w+);int count=0;char ch;printf(打印结果:n);while

30、 (!feof(fp1) ch=fgetc(fp1);printf(%c,ch);fprintf(fp2,%c,ch);count+;if (count=50) /每打印50个字符进行换行printf(n);fprintf(fp2,n); count=0;printf(n);fprintf(fp2,n); fclose(fp1); fclose(fp2); printf(打印代码过程完成!已将结果存入%s中.nn,ch2);void PrintTree_ldr(HafNode *huf,Coding *cod,int n,int p,FILE *fp) /* 中序打印哈夫曼树(具体过程) hu

31、f表示获取结点信息, cod表示获取叶子结点权值,n表示结点数目,p表示空出一定的空格用于打印左右分支, fp表示文件指针,用来将打印出的哈夫曼树存入文件中 */int i;if (n=-1) /判断是否为空树,是的话返回return; PrintTree_ldr(huf,cod,hufn.lchild,p-1,fp); /打印左子树 for (i=0;i=0&hufn.rchild=-1) /如果此结点为叶子结点,则将此结点输出；printf(-%d,codn.weight); /打印字符权值printf(%cn,hufn.ch); /打印各个字符 fprintf(fp,-%d,codn.w

32、eight);fprintf(fp,%cn,hufn.ch);else /如果此结点为非叶子结点(即双亲),则输出;if(p=6) printf(根)n);fprintf(fp,(根)n); else printf(n); fprintf(fp,n); PrintTree_ldr(huf,cod,hufn.rchild,p-1,fp); /打印右子树void Caozuo_T() /* 打印哈夫曼树的操作 */FILE *fp,*fp1,*fp2; if(fp=fopen(haffman_tree.txt,r)=NULL) puts(cant open file!); exit(0) ; in

33、t i,n;fscanf(fp,%dn,&n);HafNode *myHaffTree=(HafNode *)malloc(sizeof (HafNode)*(2*n+1);for (i=0;in;i+)fscanf(fp,%c %d %d %dn,&myHaffTreei.ch,&myHaffTreei.parent,&myHaffTreei.lchild,&myHaffTreei.rchild);for (i=n;i2*n-1;i+)fscanf(fp,%d %d %dn,&myHaffTreei.parent,&myHaffTreei.lchild,&myHaffTreei.rchild

34、);fclose(fp); if(fp1=fopen(zifu_quanzhi.txt,r)=NULL) puts(cant open file!); exit(0) ; fscanf(fp1,%*cn);Coding *myHaffCode =(Coding *)malloc (sizeof (Coding)*n);for(i=0;in;i+)fscanf(fp1,%*c%d ,&myHaffCodei.weight);fclose(fp1);printf(请输入保存结果的文件名:n);char ch120;scanf( %s,ch1);fp2=fopen(ch1,w+); PrintTre

35、e_ldr(myHaffTree,myHaffCode,2*n-2,6,fp2); /CALL PrintTree fclose(fp2); printf(打印哈夫曼树过程完成!同时已将结果存入%s中.nn,ch1);free(myHaffTree); free(myHaffCode);void print()printf(*n);printf(* 欢迎使用哈夫曼编译码器 *n);printf(* *n);printf(* 温馨提醒:1.在使用本软件前先看下随附的说明书,请按照说明书的规范要求 *n); printf(* 操作,否则可能会产生难以意料的结果! *n);printf(* 2.对于

36、与程序相关的文件只能在本路径下使用,请妥善保管. *n);printf(*n);int main() int weight100; /存储字符权值数组char ch100,cha; /数组ch用于存放字符名print(); /打印说明书char s500; HTree *t=NULL; /数组s用于存放要编码的一批数据,HTree *t用于获取字符和权值信息 statistic_char(s,t); /统计字符出现的频率Init(weight,ch); /对字符数据进行初始化操作,生成哈夫曼树及哈夫曼编码while (1) printf(*n);printf(* _ 我们为您提供的相关服务 _

37、 *n); printf(* C.编码D.译码T.印哈夫曼树P.印代码文件E.退出 *n); printf(*n);printf(请选择: ); scanf( %c,&cha);if (cha=E) break; switch (cha)case C:Caozuo_C();break;/执行编码操作case D:Caozuo_D();break;/执行译码操作case T:Caozuo_T();break;/打印哈夫曼树case P:Caozuo_P();break;/打印代码文件printf(要清屏吗?(Y/N)n); scanf( %c,&cha); if(cha=Y) system(cl

38、s);return 0;总 结这次的课程设计让我感受颇多，刚开始选题的时候，我就觉得我们的这一个课题应该是一个还不错的题目，因为上课的时候我听懂了哈夫曼数以及编码的问题，也就是说我应该可以做好，而且像这样的问题在网络上可以找到很多相关的内容。但是在我们真正开始做的时候我却发现问题不是我想像的那么简单，我们遇到了很多的麻烦。首先，在我们开始做的时候发现根本不知道该从什么地方下手，接着我们便开始上网查找，但是网络上的东西很多都是没有用的，于是自己开始去图书馆找资料，看了很有关哈夫曼方面的知识以后，开始对哈夫曼有了一定的了解，于是在掌握了这些基础知识之上，我就对我们的课题进行分析，然后便一步步按照要

39、求编写程序。其次，我们发现我遇到了不少问题，但是当我们遇到不懂的问题，我就和组员一起讨论，逐步将程序的一个个功能实现。虽然设计的过程是比较辛苦的，但是当我们看到设计成功的时候我们非常的开心。毕竟这一设计是我们亲手完成的。我们再辛苦，再劳累，都是值得的。毕竟我们从这次的课程设计中学到了很多知识。例如：哈夫曼的编码的算法，我们是经过了认真的复习，才基本掌握了。还有，我们还复习了C+的相关知识，因为我们感觉到在编程序的时候，我们明显感觉到自己的C+，以及数据结构方面的知识还是有所欠缺的。例如：我们的课程设计用到了文件有关方面的知识，这些知识都是我们以前比较薄弱的地方，通过此次课程设计我们更加理解了这

40、方面的内容。这次的课程设计不仅考查了我们理论知识，更主要的是考查了我们动手实践的能力，考查了我们用C+，数据结构编程的能力。而且还考查了我们组员分配和协作的能力。在这一周中，我们合理的分配了任务，并经过我们共同的努力才把这一课题基本完成了。从这次的课程设计中，我看到了自己的不足，首先就是比较轻浮，不能够踏踏实实的，其次，就是我个人的动手操作能力，即上机编程能力还是十分欠缺的，这还是我们平时锻炼的少所造成的。所以在以后的学习中我们要加强这方面的锻炼，为我们走上社会打下坚实的基础。所以此次的课程设计对我来说意义重大。参考文献1 严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社.2 严蔚敏，吴伟

41、民.数据结构题集（C语言版）.清华大学出版社.3 DATA STRUCTURE WITH C+. William Ford,William Topp .清华大学出版社（影印版）. 4 谭浩强.c语言程序设计. 清华大学出版社. 5数据结构与算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 张铭,刘晓丹译电子工业出版社 2001 年1月致 谢此次的课程设计，我们又学到了很多知识。因此我们首先要感谢老师，是他们为我们提供了实践的机会，我们才有这样一个学习知识的机会。其次，这次课程设计的过程中，我查阅了大量的书籍资料，并且我自己的技术和能力有了很大的提高。设计工作还是比较顺利，但也遇到了不少问题，在同学和老师那儿得到一些有益的帮助，更重要的是指导老师也不辞辛苦，总能及时的对我进行指导，正是由于他们的无私的帮助和指导，我才能比较顺利的完成这次毕业设计任务。在此，我表示由衷地感谢！附件 部分源程序代码