WHCSRL 技术网

huffmantree(哈夫曼树)C语言,用结构数组实现

废话不多说直接看代码,有什么对于哈夫曼树的疑问直接去百度就行了,这里就不啰嗦了:

  1. #include<stdio.h>
  2. #define N 5
  3. #define M 2*N-1
  4. typedef struct huffmantree
  5. {
  6. int weight;
  7. int parent;
  8. int lchild;
  9. int rchild;
  10. int ownplase; //每个带权值的节点的位置//
  11. }huffmantree; //一般清空下,第0号元素不用//
  12. void Inittree(huffmantree T[]) //初始化全部值赋值为0//
  13. {
  14. for(int i=0;i<M+1;i++)
  15. {
  16. T[i].weight=0;
  17. T[i].parent=0;
  18. T[i].lchild=0;
  19. T[i].rchild=0;
  20. }
  21. for(int j=1;j<M+1;j++) //节点从1开始//
  22. {
  23. T[j].ownplase=j;
  24. }
  25. }
  26. void createdhuffmantree(huffmantree T[]) //输入前N项的权值//
  27. {
  28. for(int i=1;i<N+1;i++)
  29. {
  30. scanf("%%d",&T[i].weight);
  31. }
  32. }
  33. void select(huffmantree T[],int n,int m) //n是开始,m是结束//
  34. {
  35. int i,j,e;
  36. for(i=n;i<m;i++) //冒泡排序将权值从小到达排序,为后面的huffman选取最小组合减小筛选时间//
  37. {
  38. for(j=n;j<m;j++)
  39. {
  40. if(T[i].weight<T[j].weight) //交换就要交换所有值//
  41. {
  42. e=T[i].weight;
  43. T[i].weight=T[j].weight;
  44. T[j].weight=e;
  45. e=T[i].ownplase;
  46. T[i].ownplase=T[j].ownplase;
  47. T[j].ownplase=e;
  48. e=T[i].lchild;
  49. T[i].lchild=T[j].lchild;
  50. T[j].lchild=e;
  51. e=T[i].rchild;
  52. T[i].rchild=T[j].rchild;
  53. T[j].rchild=e;
  54. e=T[i].parent;
  55. T[i].parent=T[j].parent;
  56. T[j].parent=e;
  57. }
  58. }
  59. }
  60. }
  61. void judgehuffmantree(huffmantree T[])
  62. {
  63. int e,flag,n,m;
  64. n=1;
  65. m=N+1;
  66. flag=1;
  67. while(flag)
  68. {
  69. select(T,n,m);
  70. T[n].parent=T[m].ownplase;
  71. T[n+1].parent=T[m].ownplase;
  72. T[m].weight=T[n].weight+T[n+1].weight; //开始修改后N个节点的权值//
  73. T[m].lchild=T[n].ownplase; //赋值给左孩子,次序无所谓 //
  74. T[m].rchild=T[n+1].ownplase; //赋值给右孩子//
  75. m++;
  76. n+=2;
  77. if(n!=m)
  78. {
  79. flag=1;
  80. }else{
  81. flag=0;
  82. }
  83. }
  84. T[M].parent=NULL;
  85. }
  86. void printhuffmantree(huffmantree T[])
  87. {
  88. printf("wgight parent lchild rchild ");
  89. for(int i=1;i<M+1;i++)
  90. {
  91. for(int j=1;j<M+1;j++)
  92. {
  93. if(T[j].ownplase==i)
  94. {
  95. printf("%%-6d %%-6d %%-6d %%-6d ",T[j].weight,T[j].parent,T[j].lchild,T[j].rchild);
  96. }
  97. }
  98. }
  99. }
  100. int main()
  101. {
  102. huffmantree T[M+1];
  103. Inittree(T);
  104. printf("请输入哈夫曼树的前N项权值: ");
  105. createdhuffmantree(T);
  106. judgehuffmantree(T);
  107. int MPL=0; //计算该huffmantree的MPL//
  108. for(int i=1;i<M;i++)
  109. {
  110. MPL=MPL+T[i].weight;
  111. }
  112. printf("此huffmantree的MPL=%%d ",MPL);
  113. printhuffmantree(T);
  114. return 0;
  115. }

给大家加一个例子:

question:Please input 5 trees with weights(5.7.3.2.8) from the keyboard and print huffman table。

 

 

 

 

 

 

推荐阅读