huffuman编码.doc

实 验 报 告实验课程名称 数据结构与算法 实验项目名称 Huffuman编码与译码 年 级 2011 、专 业 数学与应用数学 信息与计算科学 学生姓名 何广陆1107010230 邹子建1107010232 黄瑶 1107010231 理 学 院实验时间： 2013 年 10 月 25 日学生实验室守则一、按教学安排准时到实验室上实验课，不得迟到、早退和旷课。二、进入实验室必须遵守实验室的各项规章制度，保持室内安静、整洁，不准在室内打闹、喧哗、吸烟、吃食物、随地吐痰、乱扔杂物，不准做与实验内容无关的事，非实验用品一律不准带进实验室。三、实验前必须做好预习（或按要求写好预习报告），未做预习者不准参加实验。四、实验必须服从教师的安排和指导，认真按规程操作，未经教师允许不得擅自动用仪器设备，特别是与本实验无关的仪器设备和设施，如擅自动用或违反操作规程造成损坏，应按规定赔偿，严重者给予纪律处分。五、实验中要节约水、电、气及其它消耗材料。六、细心观察、如实记录实验现象和结果，不得抄袭或随意更改原始记录和数据，不得擅离操作岗位和干扰他人实验。七、使用易燃、易爆、腐蚀性、有毒有害物品或接触带电设备进行实验，应特别注意规范操作，注意防护；若发生意外，要保持冷静，并及时向指导教师和管理人员报告，不得自行处理。仪器设备发生故障和损坏，应立即停止实验，并主动向指导教师报告，不得自行拆卸查看和拼装。八、实验完毕，应清理好实验仪器设备并放回原位，清扫好实验现场，经指导教师检查认可并将实验记录交指导教师检查签字后方可离去。九、无故不参加实验者，应写出检查，提出申请并缴纳相应的实验费及材料消耗费，经批准后，方可补做。十、自选实验，应事先预约，拟订出实验方案，经实验室主任同意后，在指导教师或实验技术人员的指导下进行。十一、实验室内一切物品未经允许严禁带出室外，确需带出，必须经过批准并办理手续。学生所在学院：理学院 专业： 数学与应用数学 信息与计算科学 班级：111姓 名学 号实验组12实验时间2013.10.25指导教师彭长根成 绩实验项目名称Huffuman编码与译码实验目的： 1) 熟悉掌握二叉树的特点和性质、Huffuman树，以及Huffuman树的建立方法； 2) 编程实现Huffuman树的编码方法，然后设计Huffuman树的译码方法。实验要求：1) 建立Huffuman树，实现对英文字符的编码； 2) 根据Huffuman树，对编码的英文字符解码。实验内容：根据Huffuman树的建立方法，读入英文字符文本，对英文字符文本进行Huffuman编码，输出编码文本。然后对编码的英文字符文本进行译码。实验原理：根据Huffuman树的建立方法，读入英文字符文本，并且保存英文字符文本，然后根据英文字符都是由26个英文字母组成，据此规律对英文字符文本进行Huffuman编码，输出编码文本。然后对编码的英文字符文本进行译码，读入编码的英文字符文本，从根结点出发，按字符0或1确定找左孩子或右孩子，直至叶子结点，便求得该子串相应的字符。实验硬件及软件平台：PC机 #include #include /要用system函数要调用的头文件#include /用getch()要调用的头文件#include #define N 50 /义用N表示50叶节点数#define M 2*N-1 /用M表示节点总数 当叶节点数位n时总节点数为2n-1#define MAXSIZE 100typedef struct char data; /结点值 int weight; /权值 int parent; /双亲结点 int lchild; /左孩子结点 int rchild; /右孩子结点HTNode; typedef struct char cdN; /存放哈夫曼码 int start; /从start开始读cd中的哈夫曼码HCode;void CreateHT(HTNode ht,int n) /调用输入的数组ht,和节点数n int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有结点的相关域置初值-1 for (i=n;i2*n-1;i+) /构造哈夫曼树 min1=min2=32767; /int的范围是-32768-32767 lnode=rnode=-1; /lnode和rnode记录最小权值的两个结点位置 for (k=0;k=i-1;k+) if (htk.parent=-1) /只在尚未构造二叉树的结点中查找 if (htk.weightmin1) /若权值小于最小的左节点的权值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k;else if (htk.weightmin2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /两个最小节点的父节点是i hti.weight=htlnode.weight+htrnode.weight; /两个最小节点的父节点权值为两个最小节点权值之和 hti.lchild=lnode;hti.rchild=rnode; /父节点的左节点和右节点void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;in;i+) /根据哈夫曼树求哈夫曼编码 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到树根结点结束循环 if (htf.lchild=c) /处理左孩子结点 hc.cdhc.start-=0; else /处理右孩子结点 hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; /start指向哈夫曼编码hc.cd中最开始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /输出哈夫曼编码的列表 int i,k; printf( 输出哈夫曼编码:n);for (i=0;in;i+) /输出data中的所有数据，即A-Z printf( %c:t,hti.data); for (k=hcdi.start;k=n;k+) /输出所有data中数据的编码 printf(%c,hcdi.cdk); printf(n); void editHCode(HTNode ht,HCode hcd,int n) /编码函数char stringMAXSIZE; int i,j,k;scanf(%s,string); /把要进行编码的字符串存入string数组中printf(n输出编码结果:n);for (i=0;stringi!=#;i+) /#为终止标志for (j=0;jn;j+)if(stringi=htj.data) /循环查找与输入字符相同的编号，相同的就输出这个字符的编码for (k=hcdj.start;k=n;k+) printf(%c,hcdj.cdk);break; /输出完成后跳出当前for循环void deHCode(HTNode ht,HCode hcd,int n) /译码函数char codeMAXSIZE;int i,j,l,k,m,x;scanf(%s,code); /把要进行译码的字符串存入code数组中while(code0!=#)for (i=0;in;i+)m=0; /m为想同编码个数的计数器 for (k=hcdi.start,j=0;k=n;k+,j+) /j为记录所存储这个字符的编码个数if(codej=hcdi.cdk) /当有相同编码时m值加1m+;if(m=j) /当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据printf(%c,hti.data);for(x=0;codex-1!=#;x+) /把已经使用过的code数组里的字符串删除codex=codex+j;void main() int n=26,i; char orz,back,flag=1; char str=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立结构体 HCode hcdN; /建立结构体 for (i=0;in;i+) /把初始化的数据存入ht结构体中 hti.data=stri; hti.weight=fnumi; while (flag) /菜单函数，当flag为0时跳出循环 printf(n); printf( *); printf(n * A-显示编码 *); printf(n * B-进行编码 *); printf(n * C-进行译码 *); printf(n * D-退出 *n); printf( *); printf(n); printf( 请输入选择的编号:); scanf(%c,&orz); switch(orz) case a: case A: system(cls); /清屏函数 CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf(n按任意键返回.); getch(); system(cls); break; case b: case B: system(cls); printf(请输入要进行编码的字符串(以#结束):n); editHCode(ht,hcd,n); printf(n按任意键返回.); getch(); system(cls);