基于C语言实现的哈夫曼树问题

Yee

发布日期: 2021-06-05 10:19:23 浏览量: 93
评分:
star star star star star star star star star star
*转载请注明来自write-bug.com

哈夫曼树问题

利用哈夫曼编码进行通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本,但是,这要求在发送端通过一一个编码系统对待传数据进行预先编码;在接受端将传来的数据进行解码(复原)对于双工信道(即可以双向传输的信道),每端都要有一个完整的编/译码系统。试为这样的信息收发站写-一个哈夫曼的编译码系统。

一、需求分析

基本要求:

  • 从终端读入字符集大小为 n,及 n 个字符和 n 个权值,建立哈夫曼树,进行编码并且输出。(选做)并将它存于文件 hfmtree 中

  • 利用已建好的哈夫曼编码文件 hfimtree,对键盘输入的正文进行译码。输出字符正文,再输出该文的二进制码

本演示程序中,用户可以输入键盘中的任意字符,长度为任意长,字符输入顺序不限,且允许出现重码。

演示程序以用户与计算机的对话方式执行,即在计算机终端上显示“提示信息”之后,由用户在键盘上输入演示程序中规定的运算命令,相应的输入数据(可虑去输入中的非法字符)和运算结果显示在其后。

本演示程序中,当用户选择的功能错误时,系统会输出相应的提示。

在本系统中,用户可以对任意长的字符串可进行编码/译码。

[测试数据]用下表中给出的字符集和频度的实际统计数据建立哈夫曼树:

并实现以下报文的译码和输出:“THISPROGRAMISMYFAVORITE”。

字符 A B C D E F G H I J K L M N
频度 64 13 22 32 103 21 15 47 57 1 5 32 20 57
字符 O P Q R S T U V W X Y Z 空格
频度 63 15 1 48 51 80 23 8 18 1 16 1 168

二、概要设计

抽象数据类型定义为

  1. ADT HuffmanTree{
  2. 数据对象:D={ai| aiCharSet,i=1,2,……,n, n0}
  3. 数据关系:R={
  4. < ai-1, ai > ai-1, aiD, ai-1<ai,i=23,……,n
  5. }
  6. 基本操作P
  7. HuffmanTree();
  8. 构造函数
  9. ~HuffmanTree();
  10. 析构函数
  11. void Createtree(DATA *hfmTree, int N)
  12. 操作结果:构造哈夫曼树。
  13. void Hfmcode(DATA *hfmTree, codetype *codeFile, int N)
  14. 初始条件:哈夫曼树已存在或者哈夫曼树已存到文件中。
  15. 操作结果:对字符串进行编码
  16. void Decode(DATA *hfmTree,char *ToBeTran, int N)
  17. 初始条件:哈夫曼树已存在且已编码。
  18. 操作结果:对二进制串进行译码

本程序包含三个模块:

  • 建设哈夫曼树模块:现定义的抽象数据类型

  • 编/译码模块:实现字符串的编/译码

  • 主程序模块:

    1. int main() {
    2. 初始化;
    3. 接受命令;
    4. 处理命令;
    5. }

存储结构设计

  1. typedef struct
  2. {
  3. char CH;//字符
  4. int weight;//权值
  5. int parent, lchild, rchild;//双亲,左孩子,右孩子
  6. } DATA; //树的结构体
  7. typedef struct
  8. {
  9. char code[30];
  10. int cnt;
  11. } codetype;

三、详细设计

3.1 哈夫曼树的定义

假设有 n 个权值{w1, w2, …, wn},试构造一棵含有 n 个叶子结点的二叉树,每个叶子节点带权威 wi,则其中带权路径长度 WPL 最小的二叉树叫做最优二叉树或者哈夫曼树。

特点:哈夫曼树中没有度为 1 的结点,故由 n0 = n2+1 以及 m= n0+n1+n2,n1=0 可推出 m=2*n0-1,即一棵有 n 个叶子节点的哈夫曼树共有 2n-1 个节点。

哈夫曼树结构体定义:

  1. typedef struct
  2. {
  3. char CH;//字符
  4. int weight;//权值
  5. int parent, lchild, rchild;//双亲,左孩子,右孩子
  6. } DATA; //树的结构体
  7. typedef struct
  8. {
  9. char code[30];
  10. int cnt;
  11. } codetype;

3.2 主要子程序详细设计

主程序的流程

  1. int main()
  2. {
  3. 初始化;
  4. 接受命令;
  5. 处理命令;
  6. }

构建哈夫曼树

  1. void Createtree(DATA *hfmTree, int N)//构建哈夫曼树,传数组hfmTree和字符个数N做参数
  2. {
  3. int i, j, min, cmin;
  4. int m, c;
  5. hfmTree[0].CH = ' ';//空格用0号单元直接存(特殊处理)
  6. hfmTree[0].parent = hfmTree[0].lchild = hfmTree[0].rchild = -1;
  7. scanf("%d", &hfmTree[0].weight);//输入空格的权值
  8. /*输入A~Z的权值初始化哈夫曼树*/
  9. for (i = 1; i<N; i++)
  10. {
  11. hfmTree[i].CH = 'A' + i - 1;
  12. hfmTree[i].parent = hfmTree[i].lchild = hfmTree[i].rchild = -1;
  13. scanf("%d", &hfmTree[i].weight);
  14. }
  15. /*构建哈夫曼的过程注意 找到的最小值作为新根的左孩子,次小值作为右孩子*/
  16. for (i = N; i<2 * N - 1; i++)
  17. {
  18. min = 99999;//最小值
  19. cmin = 99999;//次小值
  20. m = 0;
  21. c = 0;//记录最小值和次小值的下标
  22. for (j = 0; j<i; j++)
  23. {
  24. if (hfmTree[j].parent == -1)
  25. if (hfmTree[j].weight<min)
  26. {
  27. c = m;
  28. cmin = min;
  29. min = hfmTree[j].weight;
  30. m = j;
  31. }
  32. else if (hfmTree[j].weight<cmin)
  33. {
  34. cmin = hfmTree[j].weight;
  35. c = j;
  36. }
  37. }
  38. hfmTree[i].weight = min + cmin;//hfmTree[m].weight+hfmTree[c].weight;
  39. hfmTree[i].CH = ' ';//方便整体输出加个字符空格
  40. hfmTree[i].lchild = m;
  41. hfmTree[i].rchild = c;
  42. hfmTree[m].parent = i;
  43. hfmTree[c].parent = i;
  44. hfmTree[i].parent = -1;//新结点的双亲没有为-1
  45. }
  46. }

哈夫曼编码

Huffman 树在通讯编码中的一个应用

利用哈夫曼树构造一组最优前缀编码。主要用途是实现数据压缩。在某些通讯场合,需将传送的文字转换成由二进制字符组成的字符串进行传输。

方法

利用哈夫曼树构造一种不等长的二进制编码,并且构造所得的哈夫曼编码是一种最优前缀编码,使所传电文的总长度最短。

不等长编码:即各个字符的编码长度不等(如:0,10,110,011),可以使传送电文的字符串的总长度尽可能地短。对出现频率高的字符采用尽可能短的编码,则传送电文的总长度便尽可能短。

前缀编码:任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。

  1. void Hfmcode(DATA *hfmTree, codetype *codeFile, int N)//哈夫曼编码
  2. {
  3. int i, p, c;
  4. codetype S;
  5. for (i = 0; i<N; i++)//对N的字符进行编码
  6. {
  7. c = i;//意思是将树中的第一个字符的下标给c暂存
  8. p = hfmTree[c].parent;//找得到c下标字符的双亲(是地址)给p暂存
  9. S.cnt = N;//把cnt的值初始化为N,后续再用数组(S->code[])存字符的编码时,倒着存
  10. S.code[N] = '\0';
  11. while (p != -1)//要将第i个字符从它自身找到它的双亲为止
  12. {
  13. if (hfmTree[p].lchild == c)//第i个字符是双亲p的左孩子,S.code[]中存‘0’;
  14. S.code[--S.cnt] = '0';
  15. else//否则存‘1’
  16. S.code[--S.cnt] = '1';
  17. c = p;
  18. p = hfmTree[c].parent;
  19. }
  20. codeFile[i] = S;//第i个字符的编码存入codeFile
  21. }
  22. }

哈夫曼译码

哈夫曼译码:译码分解、识别、还原数据的过程。从哈弗曼树的根出发,根据每位编码的 0 或 1 确定进入左子树还是右子树,直到叶子节点。

  1. void Decode(DATA *hfmTree,char *ToBeTran, int N)//解码过程
  2. {
  3. int i,ct=0;
  4. char ch;
  5. scanf("%c", &ch);
  6. i = 2 * N - 2;//根结点的小标(地址)为2*N-2
  7. while (ch!='#')//#结束后不再翻译
  8. {
  9. if (ch == '0')//‘0’判断左走
  10. i = hfmTree[i].lchild;
  11. else if (ch == '1')//‘1’判断右走
  12. i = hfmTree[i].rchild;
  13. if (hfmTree[i].lchild == -1 || hfmTree[i].rchild == -1)//从根结点一直找到叶子
  14. {
  15. ToBeTran[ct++] = hfmTree[i].CH;
  16. i = 2 * N - 2;//译完一段编码后置为头结点继续翻译
  17. }
  18. scanf("%c", &ch);
  19. }
  20. if ((hfmTree[i].lchild != -1 || hfmTree[i].rchild != -1) && i != 2 * N - 2)
  21. printf("编码有误!");
  22. ToBeTran[ct] = '\0';
  23. }

主程序伪码算法

  1. int main()
  2. {
  3. int N;
  4. int i, j;
  5. //char str[]="THIS PROGRAM IS MY FAVORITE";
  6. char str[200];
  7. char *ToBeTran,c;
  8. DATA *hfmTree;
  9. codetype *codeFile;//定义一个存编码信息的数组,大小动态分配
  10. printf("字符集大小:");
  11. scanf("%d", &N);//字符个数
  12. ToBeTran = (char *)malloc(sizeof(char) * 40);
  13. codeFile = (codetype *)malloc(sizeof(codetype)*N);//给codeFile数组分配空间
  14. hfmTree = (DATA *)malloc(sizeof(DATA)*(2 * N - 1));//哈夫曼树结点个数
  15. printf("输入空格和A~Z字母的频度:\n");
  16. Createtree(hfmTree, N);//建树
  17. Hfmcode(hfmTree, codeFile, N);//编码
  18. /*for (i = 0; i<N; i++)
  19. {
  20. printf("%c字符的编码:", hfmTree[i].CH);
  21. printf("%s", codeFile[i].code + codeFile[i].cnt);
  22. printf("\n");
  23. }*/
  24. scanf("%c", &c);//接收回车符的不然会被gets(str)这句录入
  25. printf("请输入需要编码的字符串:\n");
  26. gets(str);
  27. printf("\n");
  28. printf("该字符串编码为:\n");
  29. for (i = 0; i < strlen(str); i++)
  30. {
  31. if (str[i] == ' ')
  32. printf("%s", codeFile[0].code + codeFile[0].cnt);
  33. else
  34. printf("%s", codeFile[str[i] - 'A' + 1].code + codeFile[str[i] - 'A' + 1].cnt);//由于是倒着存的所以正着输出时要找到起始点
  35. }
  36. printf("\n\n");
  37. printf("输入需要译文的编码(以#号结束):\n");
  38. Decode(hfmTree, ToBeTran, N);
  39. printf("\n");
  40. printf("编码译文为:\n");
  41. printf("%s", ToBeTran);
  42. return 0;
  43. }

四、调试分析

执行程序时程序停止运行,推测可能的原因:遇到死循环、参数设置不合理或者结构体没有造好。首先对结构体进行了检查,各个成员声明正常无误,再对程序进行调试,程序正常跳出循环,应该是自定义函数的参数设置不合理,因此对调用的自定义函数进行相应的改动,将参数由具体类型改为指针类型后,程序正常运行。

程序不停的输出同一个结点的数据,表示指针没有按预期进行指向,对程序进行调试发现,程序没有添加循环结束条件,添加循环结束条件后,只能输出输的部分结点的数据,对标志位进行修改后,程序运行正常,也能正确输出遍历结果。

结构体数组即每个元素都是结构体,指向结构体的二级指针即二级指针元素是一级指针,一级指针元素是结构体类型数据。

scanf函数的一般形式为:scanf(“格式控制字符串”, 地址表列);格式控制字符串中不能显示非格式字符串,也就是不能显示提示字符串和换行符。” %d” 和“%d”作用一样,%d前面的空格不起作用,”%d “空格加在%d后面赋值时要多输入一个值,实际赋值操作时多输入的数并没有被赋值只是缓存到了输入流stdin中,要先用fflush(stdin);语句强制清除缓存再赋值,否则原先在stdin中的值就会被赋过去导致错误。

五、测试结果

上传的附件 cloud_download 实验六 树与二叉树(三) 刘娟 181101410126.docx ( 47.21kb, 3次下载 ) cloud_download hfmtree.cpp ( 5.35kb, 2次下载 )

Yee

发送私信

3
文章数
0
评论数
最近文章
eject