WHCSRL 技术网

C++链表:哈夫曼树(附源码)

 在开始之前先给大家介绍一下什么是哈夫曼树

          哈夫曼树就是给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。

1、路径和路径长度

在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。

 

2、结点的权及带权路径长度

若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。

 

3、树的带权路径长度

树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL。

我们现在进入正题,那如何用代码来实现哈夫曼树呢 

首先就是进行哈夫曼编码

  1. void Encoding( HuffmanTree & HT,HuffmanCode & HC,char EnteringData[] ) //编码
  2. {
  3. if( HC[0].ch == NULL )
  4. {
  5. char code[MAXCODELEN];
  6. CreateHuffmanTree( HT,HC );
  7. HuffmanTree RootNode = HT->next;
  8. while( RootNode->next != NULL ) //找根结点
  9. {
  10. RootNode = RootNode->next;
  11. }
  12. PreOrderEncode( RootNode,HC,code,0 ); //先序遍历编码
  13. }
  14. else
  15. {
  16. MessageBox(NULL,"没有文档录入,请录入文档后编码!","提示",MB_ICONERROR | MB_OK);
  17. return;
  18. }
  19. int ref = MessageBox(NULL,"编码成功,是否要保存哈夫曼编码?","提示",MB_ICONQUESTION | MB_YESNO);
  20. if( IDYES == ref )
  21. {
  22. FILE *fp = fopen("HuffmanCode.txt","wb");
  23. if( ! fp )
  24. {
  25. MessageBox(NULL,"文件打开失败!","提示",MB_ICONERROR | MB_OK);
  26. system("cls");
  27. return;
  28. }
  29. for( int i = 0; EnteringData[i] != ''; ++i )
  30. {
  31. int Ascii = EnteringData[i];
  32. if( Ascii < 0 ) //当出现在不是0~128的Ascii时,不能实现编码,退出循环
  33. break;
  34. fputs( HC[Ascii].code,fp );
  35. }
  36. fclose( fp );
  37. }
  38. else
  39. {
  40. system("cls");
  41. return;
  42. }
  43. }

然后进行先序遍历编码,用递归实现

  1. void PreOrderEncode( HuffmanTree RootNode,HuffmanCode & HC,char code[],int n ) //先序遍历编码,用递归实现
  2. {
  3. if( RootNode->lchild == NULL && RootNode->rchild == NULL )
  4. {
  5. int Ascii = RootNode->ch;
  6. HC[Ascii].code = ( char * )malloc( (n+1) * sizeof( char ) );
  7. if( ! HC[Ascii].code )
  8. exit( OVERFLOW );
  9. for( int i = 0; i < n; ++i )
  10. {
  11. HC[Ascii].code[i] = code[i];
  12. }
  13. HC[Ascii].code[i] = '';
  14. return;
  15. }
  16. if( RootNode->lchild )
  17. {
  18. code[n] = '0';
  19. PreOrderEncode( RootNode->lchild,HC,code,n+1 );
  20. }
  21. if( RootNode->rchild )
  22. {
  23. code[n] = '1';
  24. PreOrderEncode( RootNode->rchild,HC,code,n+1 );
  25. }
  26. }

进行链表排序,哈夫曼加码解码

  1. void HuffmanNodeSort( HuffmanTree & HT,int & Len ) //排序函数
  2. {
  3. int len = 0;
  4. HuffmanTree Head = HT->next,Prior,Next;
  5. while( Head != NULL )
  6. {
  7. ++len;
  8. Head = Head->next;
  9. }
  10. Len = len;
  11. bool exchange = TRUE;
  12. while( exchange ) //对链表进行排序, 采用优化后的冒泡排序算法
  13. {
  14. exchange = FALSE;
  15. Prior = HT;
  16. Head = HT->next;
  17. Next = Head->next;
  18. for( int i = 0; i < len-1; ++i )
  19. {
  20. if( Head->weigth > Next->weigth )
  21. {
  22. Prior->next = Next;
  23. Head->next = Next->next;
  24. Next->next = Head;
  25. Prior = Next;
  26. Next = Head->next;
  27. exchange = TRUE;
  28. }
  29. else
  30. {
  31. Prior = Prior->next;
  32. Head = Head->next;
  33. Next = Head->next;
  34. }
  35. }
  36. len--;
  37. }
  38. }
  39. void InsertNode( HuffmanTree & SecondFind,HuffmanTree & FirstFind,HuffmanTree &New )
  40. {
  41. HuffmanTree Prior,Next;
  42. Prior = SecondFind;
  43. Next = SecondFind->next;
  44. if( SecondFind->next == NULL ) //SecondFind 指向链表结尾的情况,并将新结点插入链表
  45. {
  46. SecondFind->next = New;
  47. return;
  48. }
  49. while( New->weigth > Next->weigth && Next->next != NULL ) //SecondFind 没有指向链尾,进行有序插入
  50. {
  51. Prior = Prior->next;
  52. Next = Next->next;
  53. }
  54. if( Next->next == NULL ) //实现链表的插入
  55. {
  56. Next->next = New;
  57. }
  58. else
  59. {
  60. New->next = Next;
  61. Prior->next = New;
  62. }
  63. FirstFind = SecondFind->next; //First Second 分别指向下两个结点
  64. SecondFind = FirstFind->next;
  65. }
  66. void Decoding( HuffmanTree & HT,HuffmanCode & HC )
  67. {
  68. int i = 0;
  69. char EnteringData[MAX_FILE_SIZE];
  70. HT = ( HuffmanTree )malloc( sizeof( HTNode ) );
  71. HT->next = NULL;
  72. HT->weigth = 0;
  73. HT->lchild = NULL;
  74. HT->rchild = NULL;
  75. HT->parent = NULL;
  76. HT->ch = NULL;
  77. FILE *fp = fopen("HuffmanTree.txt","rb");
  78. if( ! fp )
  79. {
  80. MessageBox(NULL,"文件打开失败!","提示",MB_OK);
  81. system("cls");
  82. return;
  83. }
  84. else
  85. {
  86. for( int i = 0; i < MAX_CHAR_SIZE; ++i )
  87. {
  88. fread( &HC[i],sizeof( struct Huffman ),1,fp );
  89. }
  90. fclose( fp );
  91. CreateHuffmanTree( HT,HC );
  92. }
  93. fp = fopen("HuffmanCode.txt","rb");
  94. if( ! fp )
  95. {
  96. MessageBox(NULL,"文件打开失败!","错误",MB_ICONERROR | MB_OK);
  97. system("cls");
  98. return;
  99. }
  100. HuffmanTree RootNode = HT->next,Decode;
  101. while( RootNode->next != NULL ) //找根结点
  102. {
  103. RootNode = RootNode->next;
  104. }
  105. Decode = RootNode;
  106. gotoxy(0,23);
  107. while( ! feof( fp ) ) //解码,采用非递归算法
  108. {
  109. char ch = fgetc( fp );
  110. if( ch == '0' && Decode->lchild )
  111. {
  112. Decode = Decode->lchild;
  113. }
  114. if( ch == '1' && Decode->rchild )
  115. {
  116. Decode = Decode->rchild;
  117. }
  118. if( Decode->lchild == NULL && Decode->rchild == NULL )
  119. {
  120. EnteringData[i] = Decode->ch;
  121. ++i;
  122. printf("%%%%c",Decode->ch);
  123. Decode = RootNode;
  124. }
  125. }
  126. EnteringData[i] = '';
  127. fclose( fp );
  128. printf(" 请按任意键继续... ");
  129. getch();
  130. int ref = MessageBox(NULL,"译码成功,是否要保存译码内容?","提示",MB_ICONQUESTION | MB_YESNO);
  131. if( IDYES == ref )
  132. {
  133. fp = fopen("contents.txt","wb");
  134. if( ! fp )
  135. {
  136. MessageBox(NULL,"文件打开失败!","提示",MB_ICONERROR | MB_OK);
  137. system("cls");
  138. return;
  139. }
  140. i = 0;
  141. while( EnteringData[i] != '' )
  142. {
  143. fputc( EnteringData[i],fp );
  144. ++i;
  145. }
  146. fclose( fp );
  147. system("cls");
  148. }
  149. else
  150. {
  151. system("cls");
  152. return;
  153. }
  154. }

这就是哈夫曼树实现的基本过程,其实可以看到代码并不是很难,更重要的是对于逻辑的理解和算法是熟悉

UP在主页上传了一些学习C/C++编程的视频教程,有兴趣或者正在学习的小伙伴一定要去看一看哦!会对你有帮助的~ 

  加群1083227756!!!

分享(源码、项目实战视频、项目笔记,基础入门教程)

想要哈夫曼树源码的同学也可以加群加群1083227756!!!来领取

推荐阅读