哈夫曼树上机实验报告

霍夫曼树

实验目的：

掌握结构体、指针及二叉树的生成、遍历等操作掌握霍夫曼编码/译码的原理。

基本要求：

熟练掌握树的操作。

程序实现：

程序第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并把树的信息保存起来，以便解压时创建同样的哈夫曼树进行解压；第二遍，根据第一遍扫描得到的哈夫曼树进行编码，并把编码后的码字存储。

要点分析:

题目中涉及的主要知识点：

1、本程序参考霍夫曼算法（由给定的权值构造赫夫曼树）：

（1）由给定的n个权值{w0, w1, w2, „, wn-1}，构造具有n棵二叉树的集合F ={T0, T1, T2, „, Tn-1}，其中每一棵二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。

（2）重复以下步骤, 直到F中仅剩下一棵树为止:① 在F中选取两

棵根结点的权值最小的二叉树, 做为左、右子树构造一棵 新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。② 在F中删去这两棵二叉树。③ 把新的二叉树加入F。

2、用构造赫夫曼树以完成赫夫曼编码:把d1,d2,„, dn 作为叶子结

点，把w1,w2,„,wn作为叶子结点 的权，构造赫夫曼树。在赫夫曼树中结点的左分支赋0，右 分支赋1，从根结点到叶子结点的路径上的数字拼接起来就 是这个叶子结点字符的编码。

3、译码的过程是分解电文中的字符串，从根出发，按字符‘0’或‘1’确定找左孩子或右孩子，直至叶子节点，便求得该子串相应的字符。 心得体会：

通过本次实验，我熟练掌握了结构体、指针及二叉树的生成、遍历等操作，掌握了霍夫曼编码和译码的原理，熟练掌握树的操作，尤其是对霍夫曼树有了更深刻的理解。同时，在编写代码的过程中方，对字符串的相关知识进行了回顾。

代码

#include

#include

#include

typedef struct

{

int weight;

int parent,lchild,rchild;

int sign;

}HTNode,*HuffmanTree;

typedef char * *HuffmanCode;

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n,char *s); void select(HuffmanTree &HT,int i,int &s1,int &s2);

void creatHuffmanTree(int *w,char *s,char *r);

void pr(HuffmanCode &HC,char r[],char s,char a[]);

void HuffmanYM(HuffmanCode &HC,char r[],char a[],int n,HuffmanTree &HT); void HuffmanPass(HuffmanCode &HC,char r[],int n,HuffmanTree &HT);

int main()

{

char s[100];

char r[100];

char a[100]="a";

int w[100];

int n,p;

HuffmanTree HT;

HuffmanCode HC;

printf("请输入进行编码的字符串\n");

scanf("%s",s);

p=strlen(s);

if(p!=1)creatHuffmanTree(w,s,r);

printf("进行编码......\n");

if(p!=1)

HuffmanCoding(HT,HC,w,strlen(r)-1,r);

else printf("%c的霍夫曼编码是: %c\n",s[0],'0');

printf("霍夫曼码序列为：\n");

if(p!=1)

for(int i=0;i

pr(HC,r,s[i],a);

printf("\n");

n=strlen(r)-1;

if(p==1)printf("0\n");

printf("霍夫曼编码进行译码:\n");

if(p==1)

printf("%c",s[0]);

else HuffmanYM(HC,r,a,n,HT);

printf("\n");

printf("先序遍历输出叶子节点\n");

if(p==1)

{

printf("%c\n",s[0]);

}

else HuffmanPass(HC,r,n,HT);

return 0;

}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int w[],int n,char s[]) {

int s1,s2,f,c;

int m,i,l;

int start;

char cd[101];

if(n

l=strlen(s);

m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));

HT[0].weight=10000;

for (i=1;i

{

HT[i].weight=w[i-1];

HT[i].parent=0;

HT[i].lchild=0;

HT[i].rchild=0;

HT[i].sign=0;

}

for(;i

{

HT[i].weight=0;

HT[i].parent=0;

HT[i].lchild=0;

HT[i].rchild=0;

HT[i].sign=0;

}

for(i=n+1;i

{

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;

}

HC=(HuffmanCode)malloc((n+1)*sizeof(char *));

cd[n-1]='\0';

for(i=1;i

{

start=n;

c=i;

for(f=HT[i].parent;f!=0;f=HT[f].parent)

{

if(HT[f].lchild==c)

{

start--;

cd[start]='0';

}

else

{

start--;

cd[start]='1';

}

c=f;

}

HC[i]=(char *)malloc((n-start)*sizeof(char));

for(int a=0;a

{

HC[i][a]=cd[start+a];

}

HC[i][a]='\0';

printf("%c的霍夫曼编码是: %s\n",s[i],HC[i]);

}

}

void select(HuffmanTree &HT,int i,int &s1,int &s2)

{

s1=0;

s2=0;

for(int j=1;j

{

if(HT[j].parent==0)

if(HT[j].weight

s1=j;

else continue;

}

else continue;

}

for(j=1;j

{

if(j==s1)continue;

else

if(HT[j].parent==0)

{

if(HT[j].weight

s2=j;

else continue;

}

else continue;

}

}

void creatHuffmanTree(int w[],char s[],char r[])

{

int g=1;

int q=0;

r[0]='0';

r[1]=s[0];

w[0]=1;

for(int e=1;e

{

for(int k=1;k

{

if(r[k]==s[e])

{

w[k-1]++;

q=1;

}

else continue;

}

if(q==0)

{

r[++g]=s[e];

w[g-1]=1;

q=0;

}

r[++g]='\0';

}

void pr(HuffmanCode &HC,char r[],char s,char a[])

{

for(int i=1;i

{

if(r[i]==s)

{

printf("%s",HC[i]);

strcat(a,HC[i]);

}

else continue;

}

}

void HuffmanYM(HuffmanCode &HC,char r[],char a[],int n,HuffmanTree &HT) {

int e=strlen(a);

int k=0;

int f=2*n-1;

char b[10]="1";

for(int j=1;j

{

if(HT[f].lchild!=0||HT[f].rchild!=0)

{

b[k]=a[j];

k++;

if(a[j]=='1')

f=HT[f].rchild;

else if(a[j]=='0')

f=HT[f].lchild;

}

else

{

for(int s=1;s

{

if(strcmp(HC[s],b)==0)

{

printf("%c",r[s]);

break;

}

else continue;

}

for(int u=0;u

b[u]='\0';

k=0;

f=2*n-1;

j=j-1;

}

}

}

void HuffmanPass(HuffmanCode &HC,char r[],int n,HuffmanTree &HT) {

int f,k=0;

char b[10]="a";

f=2*n-1;

HT[f].sign=0;

if(HT[f].lchild==0&&HT[f].rchild==0)

return;

do

{

if(HT[f].lchild==0&&HT[f].rchild==0)

{

for(int s=1;s

{

if(strcmp(HC[s],b)==0)

{

printf("%c",r[s]);

break;

}

else continue;

}

b[k--]='\0';

HT[f].sign=2;

f=HT[f].parent;

}

if(HT[f].sign==0)

{

b[k]='0';

HT[f].sign++;

f=HT[f].lchild;

k++;

}

else

if(HT[f].sign==1)

{

b[k]='1';

HT[f].sign++;

f=HT[f].rchild; k++;

}

else

if(HT[f].sign==2) {

f=HT[f].parent; b[k--]='\0'; }

}while(f!=0);

printf("%\n");

}