基于哈夫曼编码的通信系统的设计与实现.doc

河北工业大学

《数据结构》课程实验

实验报告

题目：基于哈夫曼编码的通信系统的设计与实现
专业：
班级：
姓名：
学号：
完成日期：

一、试验内容
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个基于哈夫曼编码的通信系统。
二、试验目的
（1）掌握二叉树的存储结构及其相关操作。
（2）掌握构造哈夫曼树的基本思想，及其编码/译码过程。
结束
对接收到的信息进行译码
判断
三、流程图
输入编码字符
及编码长度
进行哈夫曼
编码
输入要传送的信息

四、源程序代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
inthfmbm(intn,intm,charp[])
{
typedefstruct{
floatwe;
intpa,lc,rc;
}htnode,*huff;
huffHT;
typedefchar**huffman;
huffmanHC;
FILE*fp,*fp1;
inti,j,t,d,min[2],*h;
float*g;
chara,*q[100],*temp;
h=(int*)malloc(m);
for(i=0;i<100;i++){
q[i]=(char*)malloc(m+1);
//对信息进行字符编码
for(j=0;j<m;j++){
if(i==0){h[j]=1;q[i][j]=p[h[j]];continue;}
elseif(j==0){h[j]+=1;q[i][j]=p[h[j]];}
elseq[i][j]=p[h[j]];
if(h[j]>n){h[j]=1;h[j+1]+=1;q[i][j]=p[h[j]];}
}
q[i][j]='\0';
}
fp=fopen("zifu.txt","w+");//字符编码写入文件
for(i=0;i<100;i++){fputs(q[i],fp);}
fclose(fp);
g=(float*)malloc(n);
for(i=0;i<n;i++)g[i]=0;
for(i=0;i<100;i++)
for(j=0;j<m;j++)
for(t=1;t<n+1;t++)
if(q[i][j]==p[t])g[t-1]++;
for(i=0;i<n;i++)g[i]=g[i]/800;//计算每个字符出现的概率
HT=(huff)malloc((2*n-1)*sizeof(htnode));
//计算哈弗曼编码
for(i=0;i<n;i++){HT[i].we=g[i];HT[i].pa=0;HT[i].lc=-1;HT[i].rc=-1;}
for(;i<2*n-1;i++){
for(t=0;t<2;t++){
for(j=0;j<i;j++){
if(HT[j].pa==0){min[t]=j;continue;}
if(HT[j].pa==0&&HT[j].we<HT[min[t]].we)min[t]=j;
}
HT[min[t]].pa=i;
}
HT[i].we=HT[min[0]].we+HT[min[1]].we;
HT[i].pa=0;HT[i].lc=min[0];HT[i].rc=min[1];
}
HC=(huffman)malloc(n);
temp=(char*)malloc(m+1);
t=2*n-2;
d=-1;
//进行哈夫曼编码
for(i=0,d=0;d!=n;i++){
if(HT[t].lc!=-1){t=HT[t].lc;temp[i]='0';}
elseif(HT[t].rc==-1){
if(t>=0&&t<n){d++;HC[t]=(char*)malloc(i+1);for(j=0;j<i;j++)HC[t][j]=temp[j];HC[t][j]='\0';}
t=HT[t].pa;
if(temp[i-1]=='0')HT[t].lc=-1;
elseHT[t].rc=-1;
i=i-2;
}
else{t=HT[t].rc;temp[i]='1';}
}
fp=fopen("zifu.txt","r");
fp1=fopen("hm