哈弗曼编码.docx
- 文档编号:14904598
- 上传时间:2023-06-28
- 格式:DOCX
- 页数:9
- 大小:73.87KB
哈弗曼编码.docx
《哈弗曼编码.docx》由会员分享,可在线阅读,更多相关《哈弗曼编码.docx(9页珍藏版)》请在冰点文库上搜索。
哈弗曼编码
甘肃政法学院
本科生实验报告
(一)
姓名:
马大哈
学院:
计算机科学学院
专业:
计算机科学与技术
班级:
2011级计算机科学与技术本科班
实验课程名称:
数据结构
实验日期:
2012年10月26日
指导教师及职称:
陆军老师
实验成绩:
开课时间:
2012-2013学年第一学期
甘肃政法学院实验管理中心印制
实验题目
哈弗曼编码
小组合作
无
姓名
马大哈
班级
2011级计本
学号
201181110100
一、实验目的
学会构造哈弗曼树和哈弗曼编码
并对abcdefg
510152030155
进行编码
二.实验环境
MicrosoftVisualC++6.0
三、实验内容与步骤
并对abcdefg
510152030155
进行编码的源码如下
#include"c1.h"
#include"c6-7.h"
intmin1(HuffmanTreet,inti)
{/*函数voidselect()调用*/
intj,flag;
unsignedintk=UINT_MAX;/*取k为不小于可能的值*/
for(j=1;j<=i;j++)
if(t[j].weight k=t[j].weight,flag=j; t[flag].parent=1; returnflag; } voidselect(HuffmanTreet,inti,int*s1,int*s2) {/*s1为最小的两个值中序号小的那个*/ intj; *s1=min1(t,i); *s2=min1(t,i); if(*s1>*s2) { j=*s1; *s1=*s2; *s2=j; } }/*以上同algo6-1.c*/ voidHuffmanCoding(HuffmanTree*HT,HuffmanCode*HC,int*w,intn) {/*w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC*/ intm,i,s1,s2;/*此句与algo6-1.c不同*/ unsignedc,cdlen;/*此句与algo6-1.c不同*/ HuffmanTreep; char*cd; if(n<=1) return; m=2*n-1; *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));/*0号单元未用*/ for(p=*HT+1,i=1;i<=n;++i,++p,++w) { (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; } for(;i<=m;++i,++p) (*p).parent=0; for(i=n+1;i<=m;++i)/*建赫夫曼树*/ {/*在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2*/ select(*HT,i-1,&s1,&s2); (*HT)[s1].parent=(*HT)[s2].parent=i; (*HT)[i].lchild=s1; (*HT)[i].rchild=s2; (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight; } *HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); /*分配n个字符编码的头指针向量([0]不用)*/ cd=(char*)malloc(n*sizeof(char));/*分配求编码的工作空间*/ c=m; cdlen=0; for(i=1;i<=m;++i) (*HT)[i].weight=0;/*遍历赫夫曼树时用作结点状态标志*/ while(c) { if((*HT)[c].weight==0) {/*向左*/ (*HT)[c].weight=1; if((*HT)[c].lchild! =0) { c=(*HT)[c].lchild; cd[cdlen++]='0'; } elseif((*HT)[c].rchild==0) {/*登记叶子结点的字符的编码*/ (*HC)[c]=(char*)malloc((cdlen+1)*sizeof(char)); cd[cdlen]='\0'; strcpy((*HC)[c],cd);/*复制编码(串)*/ } } elseif((*HT)[c].weight==1) {/*向右*/ (*HT)[c].weight=2; if((*HT)[c].rchild! =0) { c=(*HT)[c].rchild; cd[cdlen++]='1'; } } else {/*HT[c].weight==2,退回*/ (*HT)[c].weight=0; c=(*HT)[c].parent; --cdlen;/*退到父结点,编码长度减1*/ } } free(cd); } voidmain() {/*主程序同algo6-1.c*/ HuffmanTreeHT; HuffmanCodeHC; int*w,n,i; printf("请输入权值的个数(>1): "); scanf("%d",&n); w=(int*)malloc(n*sizeof(int)); printf("请依次输入%d个权值(整型): \n",n); for(i=0;i<=n-1;i++) scanf("%d",w+i); HuffmanCoding(&HT,&HC,w,n); for(i=1;i<=n;i++) { printf("第%d个结点的编码为: ",i); puts(HC[i]); } } 四、实验过程与分析 此程序的运行结果如图4-1所示: 图4-1 程序中的编码是将所有的左子树都编码为“0”,所有的右子树都编码为“1”。 在函数HuffmanCoding中调用了函数select,select的作用是找出所有数中的两个最小的数,而在select中又调用了函数min1,min1的作用是找出所有数中最小的一个。 函数HuffmanCoding在执行到while循环之前时,指针*HT所指空间的数据如图4-2所示。 图4-2 当执行完while循环时,指针*HC所指的空间如图4-3所示。 图4-3 指针*HT和指针*HC所指的空间虽然不同,但它们1到7号的地址都对应结点a,b,c,d,e,f,g。 因此在输出时只用for循环按顺序输出即为结点编码的顺序。 五、实验总结 当输入的权值顺序不同时,所输出的编码是不同的,但这两种都正确。 这是因为计算机中进行编码时,是严格的按照顺序进行的。 在本程序中的min1函数中有如下代码: for(j=1;j<=i;j++) if(t[j].weight k=t[j].weight,flag=j; “严格的按顺序”是指当所有数据中出现两个或两个以上相同的数据时,计算机先取排在最前面的数据,按次序取走相同的数据。 而不像我们人脑,碰见哪个是哪个(当然这种编出的码是正确的),编码为a: 0000,b: 001,c: 100,d: 01,e: 11,f: 101,g: 0001,如图5-1。 图5-1 所以当输入的结点顺序是a(5),b(10),c(15),d(20),e(30),f(15),g(5),权值的输入顺序就必须是5,10,15,20,30,15,5。 如此,在程序中所建的哈弗曼树如图5-2所示,编码为: a: 0110,b: 010,c: 110,d: 00,e: 10,f: 111,g: 0111。 图5-2 如果顺序输入不是如上所示的顺序,那么输出的编码就不是按照a,b,c,d,e,f,g。 在输入权值时,各个权值之间要么用空格分开,要么每输入一个权值按一次回车,但绝不能用逗号等之类的符号分隔,否则程序会错把这些符号的ASCII码当做权值进行编码,而忽略掉后面结点的权。 在本程序中若用逗号将输入的值分隔,则程序会将30,15,5,这三个权值忽略,运行结果如图5-3所示,其结果是错误的。 图5-3
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈弗曼 编码