哈工大数据结构大作业哈夫曼树生成编码遍历.docx
- 文档编号:1218634
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:14
- 大小:99.44KB
哈工大数据结构大作业哈夫曼树生成编码遍历.docx
《哈工大数据结构大作业哈夫曼树生成编码遍历.docx》由会员分享,可在线阅读,更多相关《哈工大数据结构大作业哈夫曼树生成编码遍历.docx(14页珍藏版)》请在冰点文库上搜索。
一、问题描述
1.用户输入字母及其对应的权值,生成哈夫曼树;
2.通过最优编码的算法实现,生成字母对应的最优0、1编码;
3.先序、中序、后序遍历哈夫曼树,并打印其权值。
二、方法思路
1.哈夫曼树算法的实现
§存储结构定义
#definen100/*叶子树*/
#definem2*(n)–1/*结点总数*/
typedefstruct{/*结点型*/
doubleweight;/*权值*/
intlchild;/*左孩子链*/
intrchild;/*右孩子链*/
intparent;/*双亲链*/优点?
}HTNODE;
typedefHTNODEHuffmanT[m];
/*huffman树的静态三叉链表表示*/
算法要点
1)初始化:
将T[0],…T[m-1]共2n-1个结点的三个链域均置空(-1),权值为0;
2)输入权值:
读入n个叶子的权值存于T的前n个单元
T[0],…T[n],它们是n个独立的根结点上的权值;
3)合并:
对森林中的二元树进行n-1次合并,所产生的新结点
依次存放在T[i](n<=i<=m-1)。
每次合并分两步:
(1)在当前森林中的二元树T[0],…T[i-1]所有结点中选取权值
最小和次最小的两个根结点T[p1]和T[p2]作为合并对象,这
里0<=p1,p2<=i–1;
(2)将根为T[p1]和T[p2]的两株二元树作为左、右子树合并为一
株新二元树,新二元树的根结点为T[i]。
即
T[p1].parent=T[p2].parent=i,T[i].lchild=p1,T[i].rchild=p2,T[i].weight=T[p1].weight+T[p2].weight。
2.用huffman算法求字符集最优编码的算法:
1)使字符集中的每个字符对应一株只有叶结点的二叉树,叶的权值为对应字符的使用频率;
2)利用huffman算法来构造一株huffman树;
3)对huffman树上的每个结点,左支附以0,右支附以1(或者相反),则从根到叶的路上的0、1序列就是相应字符的编码
Huffman编码实现:
存储结构
typedefstruct{
charch;//存储字符
charbits[n+1];//字符编码位串
}CodeNode;
typedefCodeNodeHuffmanCode[n];
HuffmanCodeH;
3.二叉树遍历的递归定义
先根顺序遍历二叉树:
若二叉树非空则:
{
访问根结点;
先根顺序遍历左子树;
先根顺序遍历右子树;
}
中根顺序遍历二叉树:
若二叉树非空则:
{
中根顺序遍历左子树;
访问根结点;
中根顺序遍历右子树;
}
后根顺序遍历二叉树:
若二叉树非空则:
{后根顺序遍历左子树;
后根顺序遍历右子树;
访问根结点;
};
三、主要数据结构及源程序代码及其注释
1.扩充二叉树:
内结点、外结点
(增长树)
2.哈夫曼树
3.Huffman编码实现
源程序代码及注释
#include"stdafx.h"
#include
#include
#include
#definen10
#definem2*(n)-1
typedefstruct//建立哈夫曼结点结构体
{
chardata;
floatweight;
intlchild;
intrchild;
intparent;
}htnode;
typedefstruct//建立哈夫曼编码结构体
{
charch;
charbits[n+1];
}htcode;
voidSelectMin(htnodeT[m],intnn,int&p1,int&p2)//选择哈夫曼树所有结点中权值最小的两个根结点
{
inti,j;
for(i=0;i<=nn;i++)
{
if(T[i].parent==-1)
{
p1=i;
break;
}
}
for(j=i+1;j<=nn;j++)
{
if(T[j].parent==-1)
{
p2=j;
break;
}
}
for(i=0;i<=nn;i++)
{
if((T[p1].weight>T[i].weight)&&(T[i].parent==-1)
&&(p2!
=i))
p1=i;
}
for(j=0;j<=nn;j++)
{
if((T[p2].weight>T[j].weight)&&(T[j].parent==-1)
&&(p1!
=j))
p2=j;
}
}
voidCreatHT(htnodeT[m])//建立哈夫曼树
{
inti,p1,p2;
for(i=0;i { T[i].parent=T[i].lchild=T[i].rchild=-1;//赋初值 } for(i=n;i { SelectMin(T,i-1,p1,p2); T[p1].parent=T[p2].parent=i; if(T[p1].weight T[i].lchild=p1; T[i].rchild=p2; } else{ T[i].lchild=p2; T[i].rchild=p1; } T[i].weight=T[p1].weight+T[p2].weight; } } voidHuffmanEncoding(htnodeT[m],htcodeC[n])//哈夫曼编码 { intc,p,i; charcd[n+1]; intstart; cd[n]='\0';//结束表示 for(i=0;i { C[i].ch=T[i].data; start=n; c=i; while((p=T[c].parent)>=0) { start=start-1; if(T[p].lchild==c) { cd[start]='0'; } else { cd[start]='1'; } c=p; } strcpy(C[i].bits,&cd[start]); } } voidpreorder(htnodeT[],inti)//先序遍历哈夫曼树: 递归的办法 { printf("%f",T[i].weight); if(T[i].lchild! =-1) { preorder(T,T[i].lchild); preorder(T,T[i].rchild); } } voidinorder(htnodeT[],inti)//中序遍历哈夫曼树 { if(T[i].lchild! =-1) { inorder(T,T[i].lchild); printf("%f",T[i].weight); inorder(T,T[i].rchild); } else{ printf("%f",T[i].weight);//防止左儿子为空,程序退出 } } voidpostorder(htnodeT[],inti)//后序遍历哈夫曼树 { if(T[i].lchild! =-1) { postorder(T,T[i].lchild); postorder(T,T[i].rchild); printf("%f",T[i].weight); } else{ printf("%f",T[i].weight);//防止左儿子为空,程序退出 } } voidmain() { inti; intj; j=m-1; htnodeT[m]; htcodeC[n]; htnode*b; printf("Input10elementsandweights: "); for(i=0;i { printf("InputNO.%delement: \n",i); scanf("%c",&T[i].data); printf("InputtheweightofNO.%delement: \n",i); scanf("%f",&T[i].weight); } CreatHT(T);//建立哈夫曼树 HuffmanEncoding(T,C);//建立哈夫曼编码 printf("OutputHuffmancoding: \n"); for(i=0;i { printf("%c: ",C[i].ch); printf("%s\n",C[i].bits); } printf("OutputHaffmanTressinpreorderway: \n"); preorder(T,j);//先序遍历哈夫曼树 printf("\n"); printf("OutputHaffmanTressininorderway: \n");//中序遍历哈夫曼树 inorder(T,j); printf("OutputHaffmanTressinpostorderway: \n");//后序遍历哈夫曼树 postorder(T,j); while (1);//运行结果停止在当前画面 } 四、运行结果 #include"stdafx.h" #include #include #include #definen10 #definem2*(n)-1 typedefstruct//建立哈夫曼结点结构体 { chardata; floatweight; intlchild; intrchild; intparent; }htnode; typedefstruct//建立哈夫曼编码结构体 { charch; charbits[n+1]; }htcode; voidSelectMin(htnodeT[m],intnn,int&p1,int&p2)//选择哈夫曼树所有结点中权值最小的两个根结点 { inti,j; for(i=0;i<=nn;i++) { if(T[i].parent==-1) { p1=i; break; } } for(j=i+1;j<=nn;j++) { if(T[j].parent==-1) { p2=j; break; } } for(i=0;i<=nn;i++) { if((T[p1].weight>T[i].weight)&&(T[i].parent==-1) &&(p2! =i)) p1=i; } for(j=0;j<=nn;j++) { if((T[p2].weight>T[j].weight)&&(T[j].parent==-1) &&(p1! =j)) p2=j; } } voidCreatHT(htnodeT[m])//建立哈夫曼树 { inti,p1,p2; for(i=0;i { T[i].parent=T[i].lchild=T[i].rchild=-1;//赋初值 } for(i=n;i { SelectMin(T,i-1,p1,p2); T[p1].parent=T[p2].parent=i; if(T[p1].weight T[i].lchild=p1; T[i].rchild=p2; } else{ T[i].lchild=p2; T[i].rchild=p1; } T[i].weight=T[p1].weight+T[p2].weight; } } voidHuffmanEncoding(htnodeT[m],htcodeC[n])//哈夫曼编码 { intc,p,i; charcd[n+1]; intstart; cd[n]='\0';//结束表示 for(i=0;i { C[i].ch=T[i].data; start=n; c=i; while((p=T[c].parent)>=0) { start=start-1; if(T[p].lchild==c) { cd[start]='0'; } else { cd[start]='1'; } c=p; } strcpy(C[i].bits,&cd[start]); } } voidpreorder(htnodeT[],inti)//先序遍历哈夫曼树: 递归的办法 { printf("%f",T[i].weight); if(T[i].lchild! =-1) { preorder(T,T[i].lchild); preorder(T,T[i].rchild); } } voidinorder(htnodeT[],inti)//中序遍历哈夫曼树 { if(T[i].lchild! =-1) { inorder(T,T[i].lchild); printf("%f",T[i].weight); inorder(T,T[i].rchild); } else{ printf("%f",T[i].weight);//防止左儿子为空,程序退出 } } voidpostorder(htnodeT[],inti)//后序遍历哈夫曼树 { if(T[i].lchild! =-1) { postorder(T,T[i].lchild); postorder(T,T[i].rchild); printf("%f",T[i].weight); } else{ printf("%f",T[i].weight);//防止左儿子为空,程序退出 } } voidmain() { inti; intj; j=m-1; htnodeT[m]; htcodeC[n]; htnode*b; printf("Input10elementsandweights: "); for(i=0;i { printf("InputNO.%delement: \n",i); scanf("%c",&T[i].data); printf("InputtheweightofNO.%delement: \n",i); scanf("%f",&T[i].weight); } CreatHT(T);//建立哈夫曼树 HuffmanEncoding(T,C);//建立哈夫曼编码 printf("OutputHuffmancoding: \n"); for(i=0;i { printf("%c: ",C[i].ch); printf("%s\n",C[i].bits); } printf("OutputHaffmanTressinpreorderway: \n"); preorder(T,j);//先序遍历哈夫曼树 printf("\n"); printf("OutputHaffmanTressininorderway: \n");//中序遍历哈夫曼树 inorder(T,j); printf("OutputHaffmanTressinpostorderway: \n");//后序遍历哈夫曼树 postorder(T,j); while (1);//运行结果停止在当前画面 }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈工大 数据结构 作业 哈夫曼树 生成 编码 遍历