哈夫曼树课程设计

《哈夫曼树课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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、哈夫曼树的建立、初始化和遍历voidCHFMDlg::CrtHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){intm,i,s1,s2;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(i=1;i<=n;++i)//1-

3、-n号存放叶子结点，初始化{HT[i].weight=*w;HT[i].LChild=0;HT[i].parent=0;HT[i].RChild=0;}for(i=n+1;i<=m;i++){HT[i].weight=0;HT[i].LChild=0;HT[i].parent=0;HT[i].RChild=0;}//非叶子结点初始化for(i=n+1;i<=m;i++)//创建非叶子结点，建哈夫曼树{Select(HT,i-1,&s1,&s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].

4、LChild=s1;HT[i].RChild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}char*cd;intj,start,p;unsignedintc;HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个编码的头指针cd=(char*)malloc(n*sizeof(char));//分配求当前编码的工作空间cd[n-1]='';//从右向左逐位存放编码，首先存放编码结束符for(j=1;j<=n;j++)//求n个叶

5、子结点对应的哈夫曼编码{start=n-1;//初始化编码起始指针for(c=j,p=HT[j].parent;p!=0;c=p,p=HT[p].parent)//从叶子到根结点遍历求编码if(HT[p].LChild==c)cd[--start]='0';//左分支标0elsecd[--start]='1';//右分支标1HC[j]=(char*)malloc((n-start)*sizeof(char));//为第i个编码分配空间strcpy(HC[j],&cd[start]);}free(cd);}2、voidCH

6、FMDlg::Select(HuffmanTreeHT,intn,int*s1,int*s2)//在HT[1]~HT[i-1]的范围内选择两个parent为0//且weight最小的结点，其序号分别赋值给s1、s2{inti,min;for(i=1;i<=n;i++){if(HT[i].parent==0){min=i;break;}}for(i=1;i<=n;i++){if(HT[i].parent==0){if(HT[i].weight

7、<=n;i++){if(HT[i].parent==0&&i!=(*s1)){min=i;break;}}for(i=1;i<=n;i++){if(ht[i].parent==0&&i!=(*s1)){if(HT[i].weight

8、Style;dwOldStyle=GetWindowLong(hWnd,GWL_STYLE);if((dwOldStyle&LVS_TYPEMASK)!=dwNewStyle){dwOldStyle&=~LVS_TYPEMASK;dwNewStyle

9、=dwOldStyle;SetWindowLong(hWnd,GW