C语言-哈夫曼编码实验报告

福 建 工 程 学 院

课程设计

课 程： 数据结构

题 目： 哈夫曼编码和译码

专 业： 信息管理信息系统

班 级：

座 号： 15号

姓 名： 林左权

2011年 6月 27日

实验题目：哈夫曼编码和译码

一、要解决的问题

利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。

二、算法基本思想描述：

根据给定的字符和其中每个字符的频度,构造哈夫馒树,并输出字符集中每个字符的哈夫曼编码.将给定的字符串根据其哈夫曼编码进行编码,并进行相应的译码.

三、设计

1. 数据结构的设计

（1）哈夫曼树的表示

设计哈夫曼树的结构体（htnode），其中包含权重、左右孩子、父母和要编码的字符。用这个结构体（htnode）定义个哈夫曼数组（hfmt[]）。

迷宫定义如下：

typedef struct

{

int weight;

int lchild;

int rchild;

int parent;

char key;

}htnode;

typedef htnode hfmt[MAXLEN];

（2）对原始字符进行编码

初始化哈夫曼树（inithfmt）。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。

并显示出每个字符的编码。

1.void inithfmt(hfmt t)//对结构体进行初始化

2.void inputweight(hfmt t)//输入函数

3.void selectmin(hfmt t,int i,int *p1,int *p2)//选中两个权值最小的函数

4.void creathfmt(hfmt t)//创建哈夫曼树的函数

5.void phfmnode(hfmt t)//对字符进行初始编码

（3）对用户输入的字符进行编码

void encoding(hfmt t)//对用户输入的电文进行编码

{

char r[1000];//用来存储输入的字符串

int i,j;

printf("\n\n请输入需要编码的字符:");

gets(r);

printf("编码结果为:");

for(j=0;r[j]!='\0';j++)

for(i=0;i

if(r[j]==t[i].key)

hfmtpath(t,i,j);

printf("\n");

}

（4）对用户输入的字符进行编码

void decoding(hfmt t)//对用户输入的密文进行译码

{

char r[100];

int i,j,len;

j=2*n-2;//j初始从树的根节点开始

printf("\n\n请输入需要译码的字符串:");

gets(r);

len=strlen(r);

printf("译码的结果是:");

for(i=0;i

{

if(r[i]=='0')

{

j=t[j].lchild;

if(t[j].lchild==-1)

{

printf("%c",t[j].key);

j=2*n-2;

}

}

else if(r[i]=='1')

{

j=t[j].rchild;

if(t[j].rchild==-1)

{

printf("%c",t[j].key);

j=2*n-2;

}

}

}

printf("\n\n");

}

四、源程序清单：

#include

#include

#include

#define MAXLEN 100

typedef struct

{

int weight;

int lchild;

int rchild;

int parent;

char key;

}htnode;

typedef htnode hfmt[MAXLEN];

int n;

void inithfmt(hfmt t)//对结构体进行初始化

{

int i;

printf("\n");

printf("------------------------------------------------------------------\n"); printf("******************************输入区******************************\n");

printf("\n请输入n=");

scanf("%d",&n);

getchar();

for(i=0;i

{

t[i].weight=0;

t[i].lchild=-1;

t[i].rchild=-1;

t[i].parent=-1;

}

printf("\n");

}

void inputweight(hfmt t)//输入函数

{

int w;//w表示权值

int i;

char k;//k表示获取的字符

for(i=0;i

{

printf("请输入第%d个字符:",i+1);

scanf("%c",&k);

getchar();

t[i].key=k;

printf("请输入第%d个字符的权值:",i+1);

scanf("%d",&w);

getchar();

t[i].weight=w;

printf("\n");

}

}

void selectmin(hfmt t,int i,int *p1,int *p2)//选中两个权值最小的函数

{

long min1=999999;

long min2=999999;

int j;

for(j=0;j

if(t[j].parent==-1)

if(min1>t[j].weight)

{

min1=t[j].weight;

*p1=j;

}

for(j=0;j

if(t[j].parent==-1)

if(min2>t[j].weight && j!=(*p1))//注意 j!=(*p1))

{

min2=t[j].weight;

*p2=j;

}

}

void creathfmt(hfmt t)//创建哈夫曼树的函数

{

int i,p1,p2;

inithfmt(t);

inputweight(t);

for(i=n;i

{

selectmin(t,i-1,&p1,&p2);

t[p1].parent=i;

t[p2].parent=i;

t[i].lchild=p1;

t[i].rchild=p2;

t[i].weight=t[p1].weight+t[p2].weight;

}

}

void printhfmt(hfmt t)//打印哈夫曼树

{

int i;

printf("------------------------------------------------------------------\n"); printf("**********************哈夫曼编数结构:*****************************\n");

printf("\t\t权重\t父母\t左孩子\t右孩子\t字符\t");

for(i=0;i

{

printf("\n");

printf("\t\t%d\t%d\t%d\t%d\t%c",t[i].weight,t[i].parent,t[i].lchild,t[i].rchild,t[i].key);

}

printf("\n------------------------------------------------------------------\n");

printf("\n\n");

}

void hfmtpath(hfmt t,int i,int j)//编码的重要哈夫曼树路径递归算法

{

int a,b;

a=i;

b=j=t[i].parent;

if(t[j].parent!=-1)

{

i=j;

hfmtpath(t,i,j);

}

if(t[b].lchild==a)

printf("0");

else

printf("1");

}

void phfmnode(hfmt t)//对字符进行初始编码

{

int i,j,a;

printf("\n------------------------------------------------------------------\n");

printf("**************************哈夫曼编码

******************************");

for(i=0;i

{

j=0;

printf("\n");

printf("\t\t%c\t",t[i].key,t[i].weight);

hfmtpath(t,i,j);

}

printf("\n------------------------------------------------------------------\n");

}

void encoding(hfmt t)//对用户输入的电文进行编码

{

char r[1000];//用来存储输入的字符串

int i,j;

printf("\n\n请输入需要编码的字符:");

gets(r);

printf("编码结果为:");

for(j=0;r[j]!='\0';j++)

for(i=0;i

if(r[j]==t[i].key)

hfmtpath(t,i,j);

printf("\n");

}

void decoding(hfmt t)//对用户输入的密文进行译码

{

char r[100];

int i,j,len;

j=2*n-2;//j初始从树的根节点开始

printf("\n\n请输入需要译码的字符串:");

gets(r);

len=strlen(r);

printf("译码的结果是:");

for(i=0;i

{

if(r[i]=='0')

{

j=t[j].lchild;

if(t[j].lchild==-1)

{

printf("%c",t[j].key);

j=2*n-2;

}

}

else if(r[i]=='1')

{

j=t[j].rchild;

if(t[j].rchild==-1)

{

printf("%c",t[j].key);

j=2*n-2;

}

}

}

printf("\n\n");

}

int main()

{

int i,j;

hfmt ht;

char flag;

printf(" |----------------------|\n");

printf(" |信管1002--林左权--15号|\n");

printf(" |**********************|\n");

printf(" | 哈夫曼编码课程设计 |\n");

printf(" |**********************|\n");

printf(" |设计完成时间:2011/6/27|\n");

printf(" |----------------------|\n");

creathfmt(ht);

printhfmt(ht);

phfmnode(ht);

printf("\n------------------------------------------------------------------\n");

printf("***************************编码&&译码&&退出***********************");

printf("\n【1】编码\t【2】\t译码\t【0】退出");

printf("\n您的选择：");

flag=getchar();

getchar();

while(flag!='0')

{

if(flag=='1')

encoding(ht);

else if(flag=='2')

decoding(ht);

else

printf("您的输入有误，请重新输入。\n");

printf("\n***************************编码&&译码&&退出***********************");

printf("\n【1】编码\t【2】\t译码\t【0】退出");

printf("\n您的选择：");

flag=getchar();

getchar();

}

printf("\n\n-----------------------------------------------------------------\n");

printf("***************欢迎使用林左权的哈夫曼编码系统********************\n");

printf("-----------------------------------------------------------------\n"); system("pause");

}

五、测试数据及测试结果：

例如：

六、心得体会： （略）

11