哈夫曼树课程设计.docx
- 文档编号:2539303
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:9
- 大小:29.18KB
哈夫曼树课程设计.docx
《哈夫曼树课程设计.docx》由会员分享,可在线阅读,更多相关《哈夫曼树课程设计.docx(9页珍藏版)》请在冰点文库上搜索。
哈夫曼树课程设计
数据结构课程设计
---哈夫曼树编码
哈夫曼树编码
一、实现功能
给出一串字符,根据每个字符出现的频数进行编码,将文字转化为二进制的字符组成的字符串,即加密。
加密过程根据频数生成哈夫曼树,然后进行遍历,得到二进制编码。
二、哈夫曼算法叙述
(1).根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权值为Wi的根结点,其左右子树均为空。
(2).在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和
(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--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].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]='\0';
//从右向左逐位存放编码,首先存放编码结束符
for(j=1;j<=n;j++)//求n个叶子结点对应的哈夫曼编码
{
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';//左分支标0
else
cd[--start]='1';//右分支标1
HC[j]=(char*)malloc((n-start)*sizeof(char));
//为第i个编码分配空间
strcpy(HC[j],&cd[start]);
}
free(cd);
}
2、
voidCHFMDlg:
:
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 min=i; } } *s1=min; for(i=1;i<=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 min=i; } } *s2=min; } 四、在MFC中进行代码编译 添加列表框显示每个字符的编码 界面如下: CHFMDlg对话框 voidCHFMDlg: : SetCtrlStyle(HWNDhWnd,DWORDdwNewStyle) //设置列表控件风格 { DWORDdwOldStyle; dwOldStyle=GetWindowLong(hWnd,GWL_STYLE); if((dwOldStyle&LVS_TYPEMASK)! =dwNewStyle) { dwOldStyle&=~LVS_TYPEMASK; dwNewStyle|=dwOldStyle; SetWindowLong(hWnd,GWL_STYLE,dwNewStyle); } } BOOLCHFMDlg: : OnInitDialog()//初始化列表控件 { CDialog: : OnInitDialog(); …………… SetCtrlStyle(m_ListCtrl.m_hWnd,LVS_REPORT); CStringstrHeader[2]={"字符","编码"}; intnWidth[2]={80,100}; for(intnCol=0;nCol<2;nCol++) { m_ListCtrl.InsertColumn(nCol,strHeader[nCol],LVCFMT_LEFT,nWidth[nCol]); } returnTRUE; } voidCHFMDlg: : OnOK()//编译按钮 { //TODO: Addextravalidationhere UpdateData(); CStringstrContent,str,strValue; strContent=m_strContent;//获取编辑框中的字符串并赋//strContent intsize=strContent.GetLength();//获得字符串长度 str=strContent.GetAt(0); for(inti=0;i { intm=0; for(intj=0;j if(strContent.GetAt(i)==str.GetAt(j)) m++; if(m==0)str=str+strContent.GetAt(i); } intn=str.GetLength(); int*strnum=newint(n); for(intk=0;k { intnum=0; for(intj=0;j if(strContent.GetAt(j)==str.GetAt(k)) num++; strnum[k]=num; } HuffmanTreeHT; HuffmanCodeHC; CrtHuffmanCoding(HT,HC,strnum,n); CStringstrShow=""; for(intm=0;m { for(intt=0;t if(strContent.GetAt(m)==str.GetAt(t)) strShow=strShow+"*"+HC[t+1]; } SetDlgItemText(IDC_EDIT2,strShow); for(intx=0;x { CStrings=str.GetAt(x); IntnIndex=m_ListCtrl.InsertItem(m_ListCtrl.GetItemCount(),s); m_ListCtrl.SetItemText(nIndex,1,HC[nIndex+1]); } } voidCHFMDlg: : SetCtrlStyle(HWNDhWnd,DWORDdwNewStyle) { DWORDdwOldStyle; dwOldStyle=GetWindowLong(hWnd,GWL_STYLE); if((dwOldStyle&LVS_TYPEMASK)! =dwNewStyle) { dwOldStyle&=~LVS_TYPEMASK; dwNewStyle|=dwOldStyle; SetWindowLong(hWnd,GWL_STYLE,dwNewStyle); } } 四、编译结果如下: 资料仅供参考! ! !
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈夫曼树 课程设计
![提示](https://static.bingdoc.com/images/bang_tan.gif)