数据结构课程设计
---哈夫曼树编码
哈夫曼树编码
一、实现功能
给出一串字符，根据每个字符出现的频数进行编码，将文字转化为二进制的字符组成的字符串，即加密。加密过程根据频数生成哈夫曼树，然后进行遍历，得到二进制编码。
二、 哈夫曼算法叙述
（1）.根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权值为Wi的根结点，其左右子树均为空。
（2）.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和
（3）.在F中删除这两棵树，同时将新得到的二叉树加入F中。
（4）.重复（2）和（3），直到F中只含一棵二叉树为止，即哈夫曼树。
三、根据书上算法介绍进行代码编写（VC++编写）
1、哈夫曼树的建立、初始化和遍历
void CHFMDlg::CrtHuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w,int n)
{
int m,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;
int j,start,p;
unsigned int c;
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、
void CHFMDlg::Select(HuffmanTree HT, int n, int *s1, int *s2)
//在HT[1]~HT[i-1]的范围内选择两个parent为0
//且weight最小的结点，其序号分别赋值给s1、s2
{
int i,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<HT[min].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<HT[min].weight)
min=i;
}
}
*s2=min;
}
四、 在MFC中进行代码编译
添加列表框显示每个字符的编码
界面如下：CHFMDlg对话框
void CHFMDlg::SetCtrlStyle(HWND hWnd, DWORD dwNewStyle)
//设置列表控件风格
{
DWORD dwOldStyle;
dwOldStyle=GetWindowLong(hWnd,GWL_STYLE);
if ((dwOldStyle&LVS_TYPEMASK)!=dwNewStyle)
{
dwOldStyle&=~LVS_TYPEMASK;
dwNewStyle|=dwOldStyle;
SetWindowLong(hWnd,GWL_STYLE,dwNewStyle);
}
}
BOOL CHFMDlg::OnInitDialog()//初始化列表控件
{
CDialog::OnInitDialog();
……………
SetCtrlStyle(m_ListCtrl.m_hWnd,LVS_REPORT);
CString strHeader[2]={"字符","编码"};
int nWidth[2]={80,100};
for (int nCol=0;nCol<2;nCol++)
{
m_ListCtrl.InsertColumn(nCol,strHeader[nCol],LVCFMT_LEFT,nWidth[nCol]);
}
return TRUE;
}
void CHFMDlg::OnOK()//编译按钮
{
// TODO: Add extra validation here
UpdateData();
CString strContent,str,strValue;
strContent=m_strContent;//获取编辑框中的字符串并赋//strContent
int size=strContent.GetLength();//获得字符串长度
str=strContent.GetAt(0);
for (int i=0;i<size;i++)//将不同的字符存入str中
{
int m=0;
for (int j=0;j<str.GetLength();j++)
if (strContent.GetAt(i)==str.GetAt(j))
m++;
if (m==0) str=str+strContent.GetAt(i);
}
int n=str.GetLength();
int *strnum=new int(n);
for (int k=0;k<n;k++)//计算str中字符出现的次数，即权值，存//入strnum数组中
{
int num=0;
for (int j=0;j<size;j++)
if (strContent.GetAt(j)==str.GetAt(k))
num++;
strnum[k]=num;
}
HuffmanTree HT;
HuffmanCode HC;
CrtHuffmanCoding(HT,HC,strnum,n);
CString strShow="";
for (int m=0;m<size;m++)
{
for (int t=0;t<n;t++)
if(strContent.GetAt(m)==str.GetAt(t))
strShow=strShow+"*"+HC[t+1];
}
SetDlgItemText(IDC_EDIT2,strShow);
for (int x=0;x<n;x++)
{
CString s=str.GetAt(x);
Int nIndex=m_ListCtrl.InsertItem(m_ListCtrl.GetItemCount(),s);
m_ListCtrl.SetItemText(nIndex,1,HC[nIndex+1]);
}
}
void CHFMDlg::SetCtrlStyle(HWND hWnd, DWORD dwNewStyle)
{
DWORD dwOldStyle;
dwOldStyle=GetWindowLong(hWnd,GWL_STYLE);
if ((dwOldStyle&LVS_TYPEMASK)!=dwNewStyle)
{
dwOldStyle&=~LVS_TYPEMASK;
dwNewStyle|=dwOldStyle;
SetWindowLong(hWnd,GWL_STYLE,dwNewStyle);
}
}
四、编译结果如下：
第二篇：课程设计构造哈夫曼树
中国矿业大学徐海学院计算机系
《软件认知实践》报告
姓 名：学 号：
专 业：
设计题目：
指导教师：
20##年12月
目 录
第1章 题目概述. 1
第1.1节 题目要求... 1
第1.2节 主要难点... 1
第2章 系统流程图. 1
第3章 数据结构和算法. 1
第4章 核心代码分析. 1
第5章 实验小结. 1
参考文献. 1
第1章 题目概述
设计程序以实现构造哈夫曼树的哈夫曼算法
第1.1节 题目要求
（1）可以使用实验工具的有关功能。
（2）要能演示构造过程。
（3）求解出所构造的哈夫曼树的带权路径长度。
第1.2节 主要难点
(1)构造哈夫曼树：根据给定的权值构成二叉树集合，其中每棵二叉树中只有一个带权的根节点，其左右子树均为空；在二叉树集合中选取两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且新的二叉树的根节点的权值为其左、右子树上根节点的权值之和；在二叉树集合中删除这两棵树，并将得到的二叉树加入集合中；重复上述步骤，直至二叉树集合中只含一棵树为止。
(2)求带权路径长度：先求每个叶子结点到树根之间的路径长度与该叶子结
点所带权值之积，在将所得之积求和。
第2章 系统流程图
第3章 数据结构和算法
使用树TREE的结构，编造最优二叉树（即哈夫曼树），涉及到主要函数有Inithuffmantree,Destoryhuffmantree,huffmancodeing,Visithuffmantree等，用于在一定时间复杂度内寻找到最佳（最短）路径，节约比较次数。
1.Init huffmantree(&T)
操作结果：构造一个已知结点和权值的huffmantree.
2.Destory huffmantree(&T)
条件：huffmantree已经存在
结果：销毁huffmantree.
3.huffman coding(&T)
条件：huffmantree已经存在
结果：输出huffman code.
4.Visit huffmantree(&T)
条件：huffmantree已经存在
结果：显示 huffman tree.
代码运行结果
第4章 核心代码分析
（1） 定义
int s1=0,s2=0;//定义两个全局变量
typedef struct// 定义/结构体
{
int c;//字符域
int w;//权值域
int p,l,r;/双亲域/左孩子域右孩子域，
}HT,*HuffmanTree;//动态分配数组存储赫夫曼树
typedef char * *HuffmanCode;//动态分配数组存储赫夫曼编码
HT *HTree;
（2） 找出两个最小权值s1，s2
void Select(HT *HTree,int b)
{
int i,j,t;
for(i=1;i<=b;i++)
if(!HTree[i].p)
{
s1 = i;
break;
}
for(j=i+1;j<=b;j++)
if(!HTree[j].p)
{
s2 = j;
break;
}
for(i=1;i<=b;i++)
if((HTree[s1].w>HTree[i].w)&&(!HTree[i].p)&&(s2!=i))
s1=i;
for(j=1;j <= b;j++)
if((HTree[s2].w>HTree[j].w)&&(!HTree[j].p)&&(s1!=j))
s2=j;
if(s1>s2)//令s1小于s2
{
t=s1;
s1=s2;
s2=t;
}
}
HuffmanCode HCode
（3） 输出状态图
void pr(HT *HTree,int m)
{
int i;
HT *h;
printf("\n输出状态图\n字符\t权值\t双亲\t左孩子\t右孩子");
h=HTree+1;
for(i=1;i<=m;i++,h++)
{
printf("\n%c\t%d\t%d\t%d\t%d",h->c,h->w,h->p,h->l,h->r);
}
（4） 逐个字符求赫夫曼编码
void Strcpy(char *p1,char *p2,int i,int j)
{
int k;
for(k=0;i<=j;k++,i++)
*(p1+k)=*(p2+i);
}
（5） 逐个字符求赫夫曼编码
void bm(HT *HTree,int n,char *code)
{
int i,start,t,P;
for(i=1;i<=n;i++)
{
start=n-1;//编码结束符位置
for(t=i,P=HTree[i].p;P!=0;t=P,P=HTree[P].p)//从叶子到根逆向求编码
{
if (HTree[P].l==t)
code[--start]='0';//左孩子编码为0
else
code[--start]='1';//有孩子编码为1
}
HCode[i]=(char *)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间
Strcpy(HCode[i],code,start,n-1);//把code占到hcode上
}
}
（6） 输出赫夫曼编码函数
void Print(HuffmanTree HTree,HuffmanCode HCode,int n)
{
int i;
for(i=1;i<=n;i++)
{
printf("%c--",HTree[i].c);
printf("%d--",HTree[i].w);
printf("%s",HCode[i]);
printf("\n");
}
}
（7） 带权路径长度
dq(HT *HTree,int n)
{
int i,l,P,WPL;
int wpl[100];
for(i=1;i<=n;i++)
{
for(l=0,P=HTree[i].p;P!=0;P=HTree[P].p)
l+=1;//l是路径个数
wpl[i]=HTree[i].w*l;
}
for(i=1,WPL=0;i<=n;i++)
WPL+=wpl[i];
return WPL;
}
（8） 主函数
void main()
{
int n,m,i,C,W,WPL;
HT *h;
printf("赫夫曼树应用！");
printf("\n输入叶子节点个数:");
scanf("%d",&n);
m=2*n-1;
HTree=(HT *)malloc((m+1)*sizeof(HT));//0号单元未用,初始化赫夫曼树
h=HTree+1;
printf("\n输入%d个字符的Asc码(97-133)和权值:",n);
//叶子结点初始化
for(i=1;i<=n;i++,h++)
{
scanf("%d",&C);
scanf("%d",&W);
h->c=C;
h->w=W;
h->p=0;
h->l=0;
h->r=0;
}
//中间结点初始化
for(i=n+1;i<=m;i++,h++)
{
h->c=' ';
h->w=0;
h->p=0;
h->l=0;
h->r=0;
}
printf("\n初始\n");
pr(HTree,m);//输出初始状态图
//建赫夫曼树
for(i=n+1;i<=m;i++)
{
Select(HTree,i-1);
HTree[s1].p=i;
HTree[s2].p=i;
HTree[i].l=s1;
HTree[i].r=s2;
HTree[i].w=HTree[s1].w+HTree[s2].w;
}
//输出终结状态图
printf("\n终结\n");
pr(HTree,m);
//从叶子到根逆向求赫夫曼树编码
char *code;
HCode=(HuffmanCode)malloc((n+1)*sizeof(char));//0号单元未用,分配n个字符编码的头指针向量
code=(char *)malloc(n*sizeof(char));//分配求编码的公用工作空间
code[n-1]='\0';//编码结束符
bm(HTree,n,code);
printf("\n赫夫曼编码为:\n");
Print(HTree,HCode,n);
//带权路径长度
WPL=dq(HTree,n);
printf("\n带权路径长度:%d\n",WPL);
}
第5章 实验小结
通过这一段时间的课程设计，我通过查找资料，仔细思考，运行修改，编出赫夫曼树应用这个程序。
在编程序的过程中，也遇到了很多困难：检查没有错误却无法得出想要的结果，语句也和书上的一样却无法连接结点，又或是想达到的效果编不出来等等。这说明我们掌握的知识不够完整，不够扎实，需要加深巩固。我们一点点地摸索、求证、询问、查找，虽然还有不完美的地方，终于将程序完成，也对树的知识有了更深的理解。
这一周的课程设计让我收获颇丰，也感谢老师平时上课的教导。
参考文献
严蔚敏 吴伟民编.《数据结构（c语言版）》. 清华大学出版社
谭浩强编.《C程序设计》.清华大学出版社