5哈夫曼编码和译码的算法设计与实现.doc

实验名称哈夫曼编码和译码的算法设计与实现实验方案实验成绩实验日期实 验 室信息系统设计与仿真室I实验操作实验台号班级姓名通信一班 杨林实验结果 学号 14112300954 序号 27 实验目的 1、掌握哈夫曼编码的二叉树结构表示方法； 2、编程实现哈夫曼编码译码器； 3、掌握贪心算法的设计策略。 实验任务 ① 从文件中读取数据，构建哈夫曼树； ② 利用哈夫曼树，对输入明文进行哈夫曼编码； ③ 利用哈夫曼树，对输入编码译码为明文。 实验设计方案 结构体设计 Huffman树：包括字符，权，父亲下标，左孩子下标，右孩子下标 #define N 29 //26个小写字母，逗号，句号和空格字符. struct treenode{ //静态链表 char c; //char int w; //weight int f; //father int l; //left child index int r; //right child index }; struct treenode htree[2*N-1]; 自定义函数设计 函数原型声明 void input(); //读取文件字符、权值数据 void huffman(); //建立huffman树 void getcode(int i, char *str); //得到单个字符的huffman编码 void encode(char ch); //将明文进行huffman编码 void decode(char *str); //将huffman编码译为明文 ② 读取文件字符、权值数据 void input() { int i; char c; int f; freopen(in.txt,r,stdin); for(i=0;iN;i++) { c=getchar(); //接收字符 scanf(%d,f); //接收权值 getchar(); //接收回车 ht[i].c=c; ht[i].w=f; ht[i].l=ht[i].f=ht[i].r=-1; //初始化父亲、左右孩子下标 } freopen( CON, r, stdin); } ③建立huffman树 //使用贪心法建立huffman树,每次选择权值最小的根结点 void huffman() { void huffman() { int j,k,n; input(); j=0; k=N; for(n=N;n2*N-1;n++){ //建立huffman树，共合并N-1次 int r=0,s=0; ht[n].l=ht[n].f=ht[n].r=-1; while(r2){ //选择两个最小的权值结点 if((ht[k].w==0 || ht[k].wht[j].w) jN){ s+=ht[j].w; if(r==0) ht[n].l = j; //修改父亲、孩子下标 else ht[n].r=j; ht[j].f=n; j++; } else{ s+=ht[k].w; if(r==0) ht[n].l = k; //修改父亲、孩子下标 else ht[n].r=k; ht[k].f=n; k++; } r++; } ht[n].w=s; //修改权值 } } ④ 根据字符下标找到字符的huffman编码 //根据字符所在的下标，从叶子结点往上搜索到根节点，然后逆置得到该字符的huffman编码 void getcode(int i, char *str){ int n,j,l=0; for(n=i;ht[n].f!=-1;n=ht[n].f){ //沿着父亲往上搜索 int m=ht[n].f; if(n==ht[m].l) str[l++]=0; //左孩子记为0 else str[l++]=1; //右孩子记为1 } for(j=0;j=(l-1)/2;j++){ //将编码逆置