1、 数据结构数据结构课程设计课程设计 -哈夫曼树编码哈夫曼树编码 哈夫曼树编码哈夫曼树编码 一、一、实现功能 给出一串字符，根据每个字符出现的频数进行编码，将文字转化 为二进制的字符组成的字符串，即加密。加密过程根据频数生成哈夫 曼树，然后进行遍历，得到二进制编码。 二、二、 哈夫曼算法叙述 （1）.根据给定的 n 个权值w1,w2,wn构成 n 棵二叉树的集 合 F=T1,T2,Tn，其中每棵二叉树 Ti 中只有一个带权值为 Wi 的 根结点，其左右子树均为空。 （2）.在 F 中选取两棵根结点的权值最小的树作为左右子树构造 一棵新的二叉树， 且置新的二叉树的根结点的权值为其左右子树上根 结点
2、的权值之和 （3）.在 F 中删除这两棵树，同时将新得到的二叉树加入 F 中。 （4）.重复（2）和（3） ，直到 F 中只含一棵二叉树为止，即哈 夫曼树。 三、三、根据书上算法介绍进行代码编写（VC+编写） 1、哈夫曼树的建立、初始化和遍历 void CHFMDlg:CrtHuffmanCoding(HuffmanTree m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(i=1; i=n; +i) /1-n 号存放叶子结点，初始化 HTi.weight=*w; HTi.LChild=0; HTi.parent=0; HTi.R
3、Child=0; for(i=n+1; i=m; i+) HTi.weight=0; HTi.LChild=0; HTi.parent=0; HTi.RChild=0; /非叶子结点初始化 for(i=n+1; i=m; i+) /创建非叶子结点，建哈夫曼树 Select(HT,i-1, HTs1.parent=i; HTs2.parent=i; HTi.LChild=s1; HTi.RChild=s2; HTi.weight=HTs1.weight+HTs2.weight; char *cd; int j,start,p; unsigned int c; HC=(HuffmanCode)ma
4、lloc(n+1)*sizeof(char *); /分配 n 个编码的头指针 cd=(char *)malloc(n*sizeof(char); /分配求当前编 码的工作空间 cdn-1=0; /从右向左逐位存放编码，首先存放编码结束符 for(j=1; j=n; j+) /求 n 个叶子结点对应的哈夫曼编码 start=n-1; /初始化编码起始指针 for(c=j,p=HTj.parent; p!=0;c=p,p=HTp.parent) /从叶子到根结点遍历求编码 if( HTp.LChild=c) cd-start=0; /左分支标 0 else cd-start=1; /右分支标 1
5、 HCj=(char *)malloc(n-start)*sizeof(char); /为第 i 个编码分配空间 strcpy(HCj, free(cd); 2、 void CHFMDlg:Select(HuffmanTree HT, int n, int *s1, int *s2) /在 HT1HTi-1的范围内选择两个 parent 为 0 /且 weight 最小的结点，其序号分别赋值给 s1、s2 int i,min; for(i=1; i=n; i+) if(HTi.parent=0) min=i; break; for(i=1; i=n; i+) if(HTi.parent=0) if(HTi.weightHTmin.weight) min=i; *s1=min; for(i=1; i=n; i+) if(HTi.parent=0 break; for(i=1; i=n; i+) if(hti.parent=0 *s2=min; 四、 在 MFC 中进行代码编译 添加列表框显示每个字符的编码 界面如下：CHFMDlgCHFMDlg 对话框对话框 void CHFMDlg:SetCtrlStyle(HWND hWnd, DWORD dwNewStyle) /设置列表控件风格 DWORD dwOldS
