数据结构试验(哈夫曼编码信息系统).docVIP

《数据结构》课程实验 实 验 报 告 题目： 基于哈夫曼编码的通信系统的设计与实现 专业： 计算机科学与技术 班级： 姓名： 学号： 完成日期： 一、试验内容 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个基于哈夫曼编码的通信系统。 二、试验目的 （1）掌握二叉树的存储结构及其相关操作。 （2）掌握构造哈夫曼树的基本思想，及其编码/译码过程。 三、流程图 四、源程序代码 #includestdio.h #includestdlib.h #includestring.h int hfmbm(int n,int m,char p[]) { typedef struct{ float we; int pa,lc,rc; }htnode,*huff; huff HT; typedef char **huffman; huffman HC; FILE *fp,*fp1; int i,j,t,d,min[2],*h; float *g; char a,*q[100],*temp; h=(int *)malloc(m); for(i=0;i100;i++){ q[i]=(char *)malloc(m+1); //对信息进行字符编码 for(j=0;jm;j++){ if(i==0){h[j]=1;q[i][j]=p[h[j]];continue;} else if(j==0){h[j]+=1;q[i][j]=p[h[j]];} else q[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;i100;i++){fputs(q[i],fp);} fclose(fp); g=(float *)malloc(n); for(i=0;in;i++) g[i]=0; for(i=0;i100;i++) for(j=0;jm;j++) for(t=1;tn+1;t++) if(q[i][j]==p[t]) g[t-1]++; for(i=0;in;i++) g[i]=g[i]/800;//计算每个字符出现的概率 HT=(huff)malloc((2*n-1)*sizeof(htnode)); //计算哈弗曼编码 for(i=0;in;i++){HT[i].we=g[i];HT[i].pa=0;HT[i].lc=-1;HT[i].rc=-1;} for(;i2*n-1;i++){ for(t=0;t2;t++){ for(j=0;ji;j++){ if(HT[j].pa==0){min[t]=j;continue;} if(HT[j].pa==0HT[j].weHT[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;} else if(HT[t].rc==-1){ if(t=0tn){d++;HC[t]=(char *)malloc(i+1);