实验三哈夫曼编码

PAGE第8页共9页华北水利水电学院数据结构实验报告2012～2013学年第一学期2010级计算机科学与技术专业班级：2010134学号：201013432姓名：蔡启林实验三树的应用实验题目：树的应用——哈夫曼编码实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求出各字符的哈夫曼编码。要求：输出存放哈夫曼树的数组HT的初态和终态；输出每个字符的哈夫曼编码；输入由上述若干字符组成的字符串，对电文进行编码并输出；（选作）输入电文的哈夫曼编码，进行译码并输出。程序源代码：#include<stdio.h>#include<string.h>#include<stdlib.h>#include<conio.h>#defineMAXLEAF100structHTNode{ charletter; intparent; intlchild; intrchild; intweight;};structChNode{ charletter; intweight;};structHCode{ charcode[MAXLEAF]; intm_start;};//创建哈夫曼树voidCreateHT(HTNodeht[],intn,ChNodes[]){ inti,k,s1,s2; intm1,m2; for(i=0;i<2*n-1;i++) { ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; ht[i].weight=0; } for(i=0;i<n;i++) { ht[i].letter=s[i].letter; ht[i].weight=s[i].weight; } printf("哈夫曼树初态为:\n"); printf("dataweightparentlchildrchild\n"); for(i=0;i<2*n-1;i++) { printf("%-6c%-6d%-6d%-6d%-6d\n",ht[i].letter,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild); } for(i=n;i<2*n-1;i++) { m1=m2=32767; s1=s2=0; for(k=0;k<=i-1;k++) { if(ht[k].parent==0) { if(ht[k].weight<m1) { m2=m1; s2=s1; m1=ht[k].weight; s1=k; } elseif(ht[k].weight<m2) { m2=ht[k].weight; s2=k; } } } ht[s1].parent=i; ht[s2].parent=i; ht[i].weight=ht[s1].weight+ht[s2].weight; ht[i].lchild=s1; ht[i].rchild=s2; } printf("\n哈夫曼树终态为:\n"); printf("dataweightparentlchildrchild\n"); for(i=0;i<2*n-1;i++) { printf("%-6c%-6d%-6d%-6d%-6d\n",ht[i].letter,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild); } printf("\n");}//哈夫曼编码voidCreateCode(HTNodeht[],HCodehcd[],intn){ inti,f,letter; HCodehc; for(i=0;i<n;i++) { hc.m_start=n-1; letter=i; f=ht[i].parent; while(f!=-1) { if(ht[f].lchild==letter) hc.code[hc.m_start--]='0'; else hc.code[hc.m_start--]='1'; letter=f; f=ht[f].parent; } hc.m_start++; hcd[i]=hc; } printf("哈夫曼编码:\n"); printf("结点信息权值哈夫曼编码\n"); for(i=0;i<n;i++) { printf("%c%s%d%s",ht[i].letter,"",ht[i].weight,""); for(intj=hcd[i].m_start;j<n;j++) printf("%c",hcd[i].code[j]); printf("\n"); }}//译码voidCoding(HTNodeht[],HCodehcd[],intn,charstr[]){ for(inti=0;str[i]!='\0';i++) { for(intj=0;j<n;j++) { if(str[i]==ht[j].letter) { for(intk=hcd[j].m_start;k<n;k++) { printf("%c",hcd[j].code[k]); } break; } } } printf("\n");}voidmain(){ charstr[MAXLEAF]; printf("**********************欢迎使用赫夫曼编译系统**********************\n"); printf("从键盘输入若干字符:\n"); scanf("%s",str); ChNodes[20]; memset(s,0,sizeof(ChNode)*20); intj=0; for(inti=0;str[i]!='\0';i++) { intflag=0; for(intk=0;k<j;k++) { if(str[i]==s[k].letter) { s[k].weight++; flag=1; break; } } if(!flag) { s[j].letter=str[i]; s[j].weight=1; j++; } } HTNodeht[MAXLEAF]; memset(ht,0,sizeof(HTNode)*MAXLEAF); HCodehcd[MAXLEAF]; intnum=-1; while(1) { printf("************************主菜单********************************\n"); printf("**1.创建哈夫曼树并查看初态和终态**\n"); printf("**2.创建并查看哈夫曼编码**\n"); printf("**3.译码**\n"); printf("**4.退出**\n"); printf("****************************************************************\n"); scanf("%d",&num); if(num==0) break; switch(num) { case1: { CreateHT(ht,j,s); } break; case2: { CreateCode(ht,hcd,j); } break; case3: { charstr[MAXLEAF]; printf("请输入译文:\n"); scanf("%s",str); printf("译码后为:"); Coding(ht,hcd,j,str); } break; default: break; } printf("按任意键继续..."); getch(); system("cls"); }}测试结果：五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）注：内容一律使用宋体五号字，单倍行间距通过这次的课程设计,我对赫夫曼树以及赫夫曼编码有了更深的认识和理解，我在设计期间遇到的难点就是开始的时候，代码中有许多的错误，特别是输出赫夫曼树的存储结构的初态和终态。后来在好好的看教材的基础上解决了这个问题，但是这个存储结构还有一些问题，在这次编译哈夫曼树的存储结构的初态和终态，使得我更加的明白了哈夫曼到底是怎么存储信息的。这次的编译过程遇到很小的知识错误，就是设置清屏时没有设置头文件，就是这个小小的错误，让我在调试程序的时候没有捕获的数据，后来修改后才解决这个问题。许多的错误让我明白了一个道理细心是非常重要的。同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师也很重要，因为毕