Huffman树实验报告.doc

数据结构实验2——Huffmam编码/译码 PAGE9 / NUMPAGES9 数据结构实验2 实验名称： 学号： 姓名： 班级： 指导老师： 问题描述 利用huffman编码进行通信可以大大挺高通信道利用率，缩短信息传输时间，试为这样的信息收发站写一个Huffman编码/译码的系统。 实验目的： 在掌握相关基础知识的基础上，学会自己设计实验算法，熟练掌握Huffman树的建立方法，Huffman编码的方法，进而设计出Huffman译码算法，并编程实现。 编码： 实验分析： 首先要建立huffman树，然后才能进行编码译码，要建立huffman树必须知道各个字符的权值，这个权值我们可以从终端输入。编码阶段就是从也是从叶子点出发走一条从叶子到根的路径；而译码是从根出发走一条从根到叶子的路径。 2.算法设计以及程序代码如下： #includestdio.h #includestring.h #includemalloc.h #define Maxsize 1000 //修改此处调整输入正文大小 typedef struct { int weight; //权值 int lchild,rchild,parent; //左右孩子及双亲指针 }HTNode; //树中结点类型 typedef HTNode *HuffmanTree; //动态分配数组存储赫夫曼树 typedef char **HuffmanCode; //动态分配数组指针存储赫夫曼编码表 //统计字符串中字符个数n以及从获取权值 void Calculate(char Text[],int *n,char c[],int w[],int weight[]) { int i,len,sum=0; char t; len=strlen(Text); for(i=0;ilen;i++) { if(Text[i]!=\n) { t=Text[i]; sum++; c[sum]=t; if(Text[i]== ) //从权值库中找到所要编码的字符的权值 w[sum]=weight[0]; else w[sum]=weight[(int(Text[i])-96)]; } } c[sum+1]=\0; *n=sum; } void Select(HuffmanTree HT,int n,int *s1,int *s2) { int k,a; for(k=1;k=n;++k) if(!HT[k].parent) { a=HT[k].weight; *s1=k; break; } for(k=1;k=n;++k) //找s1 if(!HT[k].parent) //父母一定为0时才执行 if(HT[k].weighta) { a=HT[k].weight; *s1=k; } for(k=1;k=n;++k) if(!HT[k].parentk!=*s1) { a=HT[k].weight; *s2=k; break; } for(k=1;k=n;++k) //找s2 if(!HT[k].parentk!=*s1) if(HT[k].weighta) { a=HT[k].weight; *s2=k; } } //建立赫夫曼树 void HuffmanTree_Create(HuffmanTree HT,int w[],int n) //w存放n个字符的权值(均0),构造n个字符的赫夫曼树HT { int i,m; int s1,s2; if(n=1) return; m=2*n-1; for(i=1;i=n;++i) //为叶子结点赋初值 { HT[i].weight=w[i]; HT[i].parent=