华北水利水电学院 数据结构实验报告
2012～2013学年 第一学期 2010级 计算机科学与技术 专业
班级： 2010134 学号： 201013432 姓名：蔡启林
实验三 树的应用
一、 实验题目：
树的应用——哈夫曼编码
二、 实验内容：
利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。
从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求出各字符的哈夫曼编码。要求：
1． 输出存放哈夫曼树的数组HT的初态和终态；
2． 输出每个字符的哈夫曼编码；
3． 输入由上述若干字符组成的字符串，对电文进行编码并输出；
4． （选作）输入电文的哈夫曼编码，进行译码并输出。
三、程序源代码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define MAXLEAF 100
struct HTNode
{
char letter;
int parent;
int lchild;
int rchild;
int weight;
};
struct ChNode
{
char letter;
int weight;
};
struct HCode
{
char code[MAXLEAF];
int m_start;
};
//创建哈夫曼树
void CreateHT(HTNode ht[],int n,ChNode s[])
{
int i,k,s1,s2;
int m1,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("data weight parent lchild rchild\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;
}
else if (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("data weight parent lchild rchild\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");
}
//哈夫曼编码
void CreateCode(HTNode ht[],HCode hcd[],int n)
{
int i,f,letter;
HCode hc;
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 (int j=hcd[i].m_start;j<n;j++)
printf("%c",hcd[i].code[j]);
printf("\n");
}
}
//译码
void Coding(HTNode ht[],HCode hcd[],int n,char str[])
{
for (int i=0;str[i]!='\0';i++)
{
for (int j=0;j<n;j++)
{
if (str[i]==ht[j].letter)
{
for (int k=hcd[j].m_start;k<n;k++)
{
printf("%c",hcd[j].code[k]);
}
break;
}
}
}
printf("\n");
}
void main()
{
char str[MAXLEAF];
printf("**********************欢迎使用赫夫曼编译系统**********************\n");
printf("从键盘输入若干字符:\n");
scanf("%s",str);
ChNode s[20];
memset(s,0,sizeof(ChNode)*20);
int j=0;
for (int i=0;str[i]!='\0';i++)
{
int flag=0;
for(int k=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++;
}
}
HTNode ht[MAXLEAF];
memset(ht,0,sizeof(HTNode)*MAXLEAF);
HCode hcd[MAXLEAF];
int num=-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)
{
case 1:
{
CreateHT(ht,j,s);
}
break;
case 2:
{
CreateCode(ht,hcd,j);
}
break;
case 3:
{
char str[MAXLEAF];
printf("请输入译文:\n");
scanf("%s",str);
printf("译码后为:");
Coding(ht,hcd,j,str);
}
break;
default:
break;
}
printf("按任意键继续...");
getch();
system("cls");
}
}
四、测试结果：
五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）
注：内容一律使用宋体五号字，单倍行间距
通过这次的课程设计,我对赫夫曼树以及赫夫曼编码有了更深的认识和理解，我在设计期间遇到的难点就是开始的时候，代码中有许多的错误，特别是输出赫夫曼树的存储结构的初态和终态。后来在好好的看教材的基础上解决了这个问题，但是这个存储结构还有一些问题，在这次编译哈夫曼树的存储结构的初态和终态，使得我更加的明白了哈夫曼到底是怎么存储信息的。这次的编译过程遇到很小的知识错误，就是设置清屏时没有设置头文件，就是这个小小的错误，让我在调试程序的时候没有捕获的数据，后来修改后才解决这个问题。
许多的错误让我明白了一个道理---细心是非常重要的。同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师也很重要，因为毕竟我们是新手，对于某些问题很难弄清楚。而且，某些错误对于我们来说有时候想半天都弄不来，但老师几下下就搞好了，这样就更加有效地节约了时间。
这次的赫夫曼编码的好多代码老师已经在课堂上讲了，我曾经把教材上的代码编译运行过，感觉的确很简单，但是毕竟不是我自己做出来的，所以我自己就编译了一个与教材不同的程序，遇到的问题很多，编的也不太完美，也有一些小问题，但是确实我自己做出来的，成就感很大，让我对赫夫曼有了更深的了解，也让我对今后的学习更有信心了
第二篇：实验七哈夫曼编码
算法设计与分析实验报告
姓名：杨勇涛
班级：计科102班
一、实验名称： 哈夫曼编码
时间：20xx年4月4日，星期三，第四节
地点：12#311
二、实验目的及要求
设计任务： ?从键盘输入一串电文字符能输出对应的哈夫曼编码。同时，能翻译由哈夫曼编码生成的代码串，输出相应的电文字符串。?
设计要求：?(1)从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树及哈夫曼编码。?(2)利用已经建好的哈夫曼树，对输入的字符串进行编码，输出编码序列。?(3)利用已建好的哈夫曼树对输入的二进制编码进行译码，并输出结果。??设计任务： ?从键盘输入一串电文字符能输出对应的哈夫曼编码。同时，能翻译由哈夫曼编码生成的代码串，输出相应的电文字符串。?设计要求：?(1)从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树及哈夫曼编码。?(2)利用已经建好的哈夫曼树，对输入的字符串进行编码，输出编码序列。?(3)利用已建好的哈夫曼树对输入的二进制编码进行译码，并输出结果。??
三、实验环境
Vc++
四、实验内容
从键盘输入一串电文字符能输出对应的哈夫曼编码。同时，能翻译由哈夫曼编码生成的代码串，输出相应的电文字符串。?
五、算法描述及实验步骤
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。?
三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。?
四、重复二和三两步，直到集合F中只有一棵二叉树为止。?
六、调试过程及实验结果
七、总结
通过这次编程使我对哈弗曼编码有了更深刻的理解，并且学会了将之前学过的东西运用到程序中来。
八、源程序
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码
typedef struct
{
unsigned int weight; //用来存放各个结点的权值
unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树
//选择两个parent为0，且weight最小的结点s1和s2
void Select(HuffmanTree *ht,int n,int *s1,int *s2)
{
int i,min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0)
{
min=i;
break;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0)
{
if((*ht)[i].weight<(*ht)[min].weight)
min=i;
}
}
*s1=min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0 && i!=(*s1))
{
min=i;
break;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0 && i!=(*s1))
{
if((*ht)[i].weight<(*ht)[min].weight) min=i; }
}
*s2=min;
}
//构造哈夫曼树ht。w存放已知的n个权值
void CrtHuffmanTree(HuffmanTree *ht,int *w,int n) {
int m,i,s1,s2;
m=2*n-1;
*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(i=1; i<=n; i++) //1--n号存放叶子结点，初始化 {
(*ht)[i].weight=w[i];
(*ht)[i].LChild=0;
(*ht)[i].parent=0;
(*ht)[i].RChild=0;
}
for(i=n+1; i<=m; i++)
{
(*ht)[i].weight=0;
(*ht)[i].LChild=0;
(*ht)[i].parent=0;
(*ht)[i].RChild=0;
} //非叶子结点初始化
printf("\nHuffmanTree: \n");
for(i=n+1; i<=m; i++) //创建非叶子结点，建哈夫曼树
{ //在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0
//且weight最小的结点，其序号分别赋值给s1、s2
Select(ht,i-1,&s1,&s2);
(*ht)[s1].parent=i;
(*ht)[s2].parent=i;
(*ht)[i].LChild=s1;
(*ht)[i].RChild=s2;
(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;
printf("%d (%d, %d)\n",(*ht)[i].weight,(*ht)[s1].weight,(*ht)[s2].weight); }
printf("\n");
} //哈夫曼树建立完毕
//从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码
void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)
{
char *cd;
int i,start,p;
unsigned int c;
hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); //分配n个编码的头指针
cd=(char *)malloc(n*sizeof(char)); //分配求当前编码的工作空间
cd[n-1]='\0'; //从右向左逐位存放编码，首先存放编码结束符
for(i=1; i<=n; i++) //求n个叶子结点对应的哈夫曼编码
{
start=n-1; //初始化编码起始指针
for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) //从叶子到根结点求编码
if( (*ht)[p].LChild==c) cd[--start]='0'; //左分支标0
else cd[--start]='1'; //右分支标1
hc[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间 strcpy(hc[i],&cd[start]);
}
free(cd);
for(i=1; i<=n; i++)
printf("HuffmanCode of %3d is %s\n",(*ht)[i].weight,hc[i]); printf("\n");
}
void main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,i,n,wei,m;
printf("\nn = " );
scanf("%d",&n);
w=(int *)malloc((n+1)*sizeof(int));
printf("\ninput the %d element's weight:\n",n);
for(i=1; i<=n; i++)
{
printf("%d: ",i);
fflush(stdin);
scanf("%d",&wei);
w[i]=wei;
}
CrtHuffmanTree(&HT,w,n);
CrtHuffmanCode(&HT,&HC,n);
}