数据结构课程设计--哈夫曼树结构设计

《数据结构课程设计--哈夫曼树结构设计》由会员分享，可在线阅读，更多相关《数据结构课程设计--哈夫曼树结构设计（8页珍藏版）》请在毕设资料网上搜索。

1、一、一、 摘要摘要 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降 低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在 接收端将传来的数据进行译码（复原） 。为实现这一功能可以利用现有数据结构 及相关课程的知识编一个这样的程序。 二、二、 需求分析需求分析 1 建立哈夫曼树。根据哈夫曼编码技术，可以将已经给出的字母的使用频率 建立一个哈夫曼树，即以二叉树的形式将英文字母和空格存储。 2 编码。利用二叉树的遍历知识，左孩子用“0”表示，右孩子用“1”表示， 将输入的一组英文句子进行编码。 3 测试和输出。程序要求的测试的英文句子是： “knowledge

2、is power” ，输 出每一个字母然后给出相应的哈夫曼编码。本程序输入字母以“#”结束。 4 译码。本程序要求对已编码的数字能够给以反编码。 三、三、 详细设计详细设计 1 哈夫曼树结构体设计 对一个结点如果父亲结点和两个孩子结点知道那么这个结点就定位了， 考虑 到叶子结点要有相应的值及相应的权重，结构体设计如下。 typedef struct /定义哈夫曼树的结点结构 char c; /结点的值 double weight;/结点的权重 int parent; /双亲结点 int lchild; /左孩子结点 int rchild; /右孩子结点 HTNode; 2 构造哈夫曼树设计 v

3、oid CreateHT(HTNode ht,int n)/建立哈夫曼树 int i,k,lnode,rnode; double min1,min2; for(i=0;iai; if(ai=#) break; coutendl“你输入的句子各字符的哈夫曼编码为:“endl; for(int n=0;ni;n+) for(int j=0;j27;j+) if(an=HTj.c) break; coutHTj.c“: “; for(int k=hcj.start;kN;k+) couthcj.cdk; coutendl; char *s1=“0111110011010010111111000100

4、101011110111001111111000100111110000 100101111110011011“; int m=0; cout“输入的反编码是： 011111001101001011111100010010101111011100111111100010011111000010010 1111110011011“endl; cout“英文字符为：“endl; while (HTm.parent!=-1) m+; int f=m; int j=-1; while(j200) if(HTf.lchild!=-1) j+; if(s1j=0) f=HTf.lchild; else f=HTf.rchild; else coutHTf.c; f=m; coutendl;