哈夫曼编码编译器实践报告.doc

计算机软件基础课 程 设 计报告设计题目： 哈夫曼编译码器 专 业 信息工程(系统工程方向)班 级 09系统1班 学 生 董健 学 号 20091325048 指导教师 陈金辉 10一、设计题目设计题目一 哈夫曼编译码器设计要求：1.初始化，键盘输入字符集大小n，n个字符和n个权植，建立哈夫曼树。2.编码，利用建好的huffman树生成huffman编码；3.输出编码；4.译码功能；5.字符和频度如下：字符 空格 A B C D E F G H I J K L M N O P Q频度 186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 1字符 R S T U V W X Y Z频度 48 51 80 23 8 18 1 161.1 问题分析构造哈夫曼树时，首先将由n各字符形成的n个叶子节点存放到数组HTNode的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树，每次构成的新子树的根节点顺序放到HTNode数组中的前n个分量的后面。译码功能，假定电文中只使用A、B、C、D、E、F6种字符，若进行等长编码，它们分别需要3位二进制字符，可一次编码为000、001、010、011、100、101。1.2 数据结构与算法设计哈夫曼编译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码 。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为哈夫曼编码。最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。哈夫曼树课用于构造使电文的编码总长最短的编码方案。开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用SELECT函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0I2*N?I+编码为1结束否否否右子是否为空是是否否是是是哈夫曼树编译码器流程图1.3 核心代码哈夫曼编译码器程序的主要代码如下所示:#include #include /要用system函数要调用的头文件#include /用getch()要调用的头文件#include #define N 50 /义用N表示50叶节点数#define M 2*N-1 /用M表示节点总数 当叶节点数位n时总节点数为2n-1#define MAXSIZE 100typedef struct char data; /结点值 int weight; /权值 int parent; /双亲结点 int lchild; /左孩子结点 int rchild; /右孩子结点HTNode; typedef struct char cdN; /存放哈夫曼码 int start; /从start开始读cd中的哈夫曼码HCode;void CreateHT(HTNode ht,int n) /调用输入的数组ht,和节点数n int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有结点的相关域置初值-1 for (i=n;i2*n-1;i+) /构造哈夫曼树 min1=min2=32767; /int的范围是-3276832767 lnode=rnode=-1; /lnode和rnode记录最小权值的两个结点位置 for (k=0;k=i-1;k+) if (htk.parent=-1) /只在尚未构造二叉树的结点中查找if (htk.weightmin1) /若权值小于最小的左节点的权值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /两个最小节点的父节点是i hti.weight=htlnode.weight+htrnode.weight; /两个最小节点的父节点权值为两个最小节点权值之和 hti.lchild=lnode;hti.rchild=rnode; /父节点的左节点和右节点void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;in;i+) /根据哈夫曼树求哈夫曼编码 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到树根结点结束循环 if (htf.lchild=c) /处理左孩子结点 hc.cdhc.start-=0; else /处理右孩子结点 hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; /start指向哈夫曼编码hc.cd中最开始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /输出哈夫曼编码的列表 int i,k; printf( 输出哈夫曼编码:n);for (i=0;in;i+) /输出data中的所有数据，即A-Z printf( %c:t,hti.data); for (k=hcdi.start;k=n;k+) /输出所有data中数据的编码 printf(%c,hcdi.cdk); printf(n); void editHCode(HTNode ht,HCode hcd,int n) /编码函数char stringMAXSIZE; int i,j,k;scanf(%s,string); /把要进行编码的字符串存入string数组中printf(n输出编码结果:n);for (i=0;stringi!=#;i+) /#为终止标志for (j=0;jn;j+)if(stringi=htj.data) /循环查找与输入字符相同的编号，相同的就输出这个字符的编码for (k=hcdj.start;k=n;k+) printf(%c,hcdj.cdk);break; /输出完成后跳出当前for循环void deHCode(HTNode ht,HCode hcd,int n) /译码函数char codeMAXSIZE;int i,j,l,k,m,x;scanf(%s,code); /把要进行译码的字符串存入code数组中while(code0!=#)for (i=0;in;i+)m=0; /m为想同编码个数的计数器 for (k=hcdi.start,j=0;k=n;k+,j+) /j为记录所存储这个字符的编码个数if(codej=hcdi.cdk) /当有相同编码时m值加1m+;if(m=j) /当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据printf(%c,hti.data);for(x=0;codex-1!=#;x+) /把已经使用过的code数组里的字符串删除codex=codex+j;void main() int n=26,i; char orz,back,flag=1; char str=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立结构体 HCode hcdN; /建立结构体 for (i=0;in;i+) /把初始化的数据存入ht结构体中 hti.data=stri; hti.weight=fnumi; while (flag) /菜单函数，当flag为0时跳出循环 printf(n); printf( ); printf(n A-显示编码 ); printf(n B-进行编码 ); printf(n C-进行译码 ); printf(n D-退出 n); printf( ); printf(n); printf( 请输入选择的编号:); scanf(%c,&orz); switch(orz) case a: case A: system(cls); /清屏函数 CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf(n按任意键返回.); getch(); system(cls); break; case b: case B: system(cls); printf(请输入要进行编码的字符串(以#结束):n); editHCode(ht,hcd,n); printf(n按任意键返回.); getch(); system(cls); break; case c: case C: system(cls); DispHCode(ht,hcd,n); printf(请输入编码(以#结束):n); deHCode(ht,hcd,n); printf(n按任意键返回.); getch(); system(cls); break; case d: case D: flag=0; break; default: system(cls); 1.4 运行结果下面是程序的运行结果：第一步运行程序为进入主菜单，如下图1-2所示。图1-2 进入主菜单第二步输入编号A显示编码，输出结果如下图1-3所示。图1-3 输出哈夫曼编码第三步返回主菜单后输入B进行编码，输入“OHMYGOD#”回车后显示编码，如图1-4所示。图1-4 编码第四步返回主菜单后输入C进行译码，输入“110100