树和二叉树的应用

【实验题目】

树和二叉树的应用

【实验内容】

哈夫曼编码设计

【实验目的】

掌握树和二叉树的概念及工作原理，运用其原理及概念完成上述实验题中的内容。

【实验要求】

通过程序设计，实现哈弗曼编码的设计。更好的掌握与理解课堂上老师所讲的概念与原理，通过树和二叉树的方法实现。

【设计原理】

可以利用二叉树来设计二进制的前缀编码。可以从根节点到叶子节点的路径上分支字符组成的字符串作为该叶子节点字符的编码。如此得到的必为二进制前缀码。设计电文总长最短的二进制前缀码既为以N种字符出现的频率作权，设计一棵哈夫曼树的问题，由此得到的二进制前缀编码成为哈弗曼编码。

【程序清单及注释说明】

#include

#include

#include

#include

#include

#define MAXVALUE 10000 /*权值最大值*/

#define MAXLEAF 30 /*叶子最多个数*/

#define MAXNODE MAXLEAF*2-1 /* 结点数的个数*/

#define MAXBIT 50 /*编码的最大位数*/

typedef struct node /*结点类型定义*/

{

char letter;

int weight;

int parent;

int lchild;

int rchild;

}HNodeType;

typedef struct /*编码类型定义*/

{

char letter;

int bit[MAXBIT];

int start;

}HCodeType;

typedef struct /*输入符号的类型*/

{

char s;

int num;

}lable;

void HuffmanTree(HNodeType HuffNode[],int n,lable a[]) /*定义哈弗曼树*/

{

int i,j,m1,m2,x1,x2,temp1;

char temp2;

for (i=0;i<2*n-1;i++) /*结点初始化*/

{

HuffNode[i].letter=0;

HuffNode[i].weight=0;

HuffNode[i].parent=-1;

HuffNode[i].lchild=-1;

HuffNode[i].rchild=-1;

}

for (i=0;ifor (j=i+1;jif (a[j].num>a[i].num)

{

temp1=a[i].num;

a[i].num=a[j].num;

a[j].num=temp1;

temp2=a[i].s;

a[i].s=a[j].s;

a[j].s=temp2;

}

for (i=0;i{

HuffNode[i].weight=a[i].num;

HuffNode[i].letter=a[i].s;

}

for (i=0;i{

m1=m2=MAXVALUE;

x1=x2=0;

for (j=0;j{

if (HuffNode[j].parent==-1&&HuffNode[j].weight{

m2=m1;

x2=x1;

m1=HuffNode[j].weight;

x1=j;

}

else if (HuffNode[j].parent==-1&&HuffNode[j].weight{

m2=HuffNode[j].weight;

x2=j;

}

}

HuffNode[x1].parent=n+i;

HuffNode[x2].parent=n+i; /*权值最小与次小的结点进行组合*/

HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;

HuffNode[n+i].lchild=x1;

HuffNode[n+i].rchild=x2;

}

}

void HuffmanCode(int n,lable a[])

{

HNodeType HuffNode[MAXNODE];

HCodeType HuffCode[MAXLEAF],cd;

int i,j,c,p;

HuffmanTree(HuffNode,n,a);

for (i=0;i{

cd.start=n-1;

c=i;

p=HuffNode[c].parent;

while (p!=-1)

{

if (HuffNode[p].lchild==c)

cd.bit[cd.start]=0;

else cd.bit[cd.start]=1;

cd.start--;

c=p;

p=HuffNode[c].parent;

}

for (j=cd.start+1;jHuffCode[i].bit[j]=cd.bit[j];

HuffCode[i].start=cd.start;

}

for (i=0;i{

HuffCode[i].letter=HuffNode[i].letter;

printf(\"%c 哈弗曼编码：\

for (j=HuffCode[i].start+1;jprintf(\"%d\j]);

printf(\"\\n\");

}

}

int main()

{

lable data[30];

char s[100],*p;

int i,count=0;

printf(\"哈夫曼编码设计\");

printf(\"\\n\");

printf(\"输入字符:\");

scanf(\"%s\

for (i=0;i<30;i++)

{

data[i].s=0;

data[i].num=0;

}

p=s;

while (*p) /*计算字符个数与出现次数(即权值)*/

{

for (i=0;i<=count+1;i++)

{

if (data[i].s==0)

{

data[i].s=*p;

data[i].num++;

count++;

break;

}

else if (data[i].s==*p)

{

data[i].num++;

break;

}

}

p++;

}

for (i=0;i{

printf(\"%c \

printf(\"权重(出现次数):%d\\n\

}

printf(\"\\n\");

HuffmanCode(count,data);

count=0;

return 0;

}

【运行与测试及结果】

【问题及解决方法】

进行实验的过程中，刚刚开始的时候定义哈夫曼树出现了错误，程序无法顺利执行，后来经过上网查询，询问老师，查找书籍，将问题顺利的解决了。