数据结构，哈夫曼C程序实验报告（C程序C-Free测试下通过）.doc

课程名称 数据结构 实验项目名称 哈夫曼码编、译码器 实验目的和要求 熟练哈夫曼树的定义，掌握构造哈夫曼树的方法、哈夫曼编码和译码的方法 基本要求： 一个完整的系统应具有以下功能： 初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存在于文件hfmTree中。 编码。利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件的正文进行编码，然后将结果存入文件CodeFile中。 译码。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入在文件TextFile中。 实验原理和主要内容 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编码、译码系统。试为这样的信息收发站写一个哈夫曼码的编码、译码系统。 主要仪器设备 计算机，VC++高级程序语言 调试分析 哈夫曼是树的深层次应用，必须掌握构造哈夫曼树以及哈夫曼编码译码，根据课本145-147内容大致可以完成该程序写好程序后根据书上6-2运行检查即可 测试结果 附录程序 #include stdio.h #include string.h #include stdlib.h #include malloc.h #include conio.h typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; } HTNode,*HuffmanTree; typedef char **HuffmanCode; typedef struct { unsigned int s1; unsigned int s2; } MinCode; void Error(char *message); HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n); MinCode Select(HuffmanTree HT,unsigned int n); void Error(char *message) { fprintf(stderr,Error:%s\n,message); exit(1); } HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n) { unsigned int i,s1=0,s2=0; HuffmanTree p; char *cd; unsigned int f,c,start,m; MinCode min; if(n=1) Error(Code too small!); m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT,i=0;i=n;i++,p++,w++) { p-weight=*w; p-parent=0; p-lchild=0; p-rchild=0; } for(;i=m;i++,p++) { p-weight=0; p-parent=0; p-lchild=0; p-rchild=0; } for(i=n+1;i=m;i++) { min=Select(HT,i-1); s1=min.s1; s2=min.s2; HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1;