gpt4 book ai didi

C++实现哈夫曼树的方法

转载 作者:qq735679552 更新时间:2022-09-29 22:32:09 27 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C++实现哈夫曼树的方法由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.

序言 。

对于哈夫曼编码,个人的浅薄理解就是在压缩存储空间用很大用处。 用一个很简单例子,存储一篇英文文章时候,可能A出现的概率较大,Z出现的记录较小,如果正常存储,可能A与Z存储使用的空间一样。但是用哈夫曼编码方式,A经常出现,所用编码长度就短.

构造哈夫曼树,生成哈夫曼编码 。

1、定义节点类型 。

?
1
2
3
4
5
6
struct Node {
  char C;
  long key;
  Node *Left, *Right,*parent;
  Node() { Left = Right = NULL; }
};

2、定义树类型(节点数组) 。

三要素:不定长数组,元素大小,有效元素个数 。

?
1
2
3
4
5
6
7
struct RootA {
  Node *NodeA;
  const int Size;
  int n;
  RootA( int Size) :Size(Size) { n = 0; NodeA = new Node[Size]; }
  ~RootA() { delete []NodeA; }
};

3、创建哈夫曼树 。

1.将每一个节点都当成一棵树,初始化数组大小,并进行赋值 。

?
1
2
3
4
5
6
7
8
RootA RA(4);
  //1.在RA.NodeA中存入字母和权值
  for (RA.n = 0;RA.n < RA.Size ;RA.n++) {
  cout << "字母:";
  cin >> RA.NodeA[RA.n].C;
  cout << "权值:";
  cin >> RA.NodeA[RA.n].key;
  }

2.将树按权值大小排序 。

?
1
2
3
4
5
6
7
8
9
10
11
12
void Sort(RootA *ra) {
  for ( int i = 0;i < ra->n;i++) {
  bool ESC = false ;
  for ( int j = 0;j < ra->n - i - 1;j++) {
   if (ra->NodeA[j].key > ra->NodeA[j + 1].key) {
   Node T;T = ra->NodeA[j];ra->NodeA[j] = ra->NodeA[j + 1];ra->NodeA[j + 1] = T;
   ESC = true ;
   }
  }
  if (!ESC) return ;
  }
}

3.(1)遍历数组,将RA.NodeA[0]和RA.Node[1]合并,其余向前移动,重新排序 (2)将RA.NodeA[0],RA.NodeA[1]分别放在新合并的RA.NodeA[0]的左右子结点中 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
while (RA.n > 1) {
  //1.将RA.NodeA[0]和RA.NodeA[1]合并,将其余向前移动
  Node *NewNode0 = new Node;
  *NewNode0 = RA.NodeA[0];
  Node *NewNode1 = new Node;
  *NewNode1 = RA.NodeA[1];
  RA.NodeA[0].C = ' ' ;
  RA.NodeA[0].key = RA.NodeA[0].key + RA.NodeA[1].key;
  RA.NodeA[0].Left = NewNode0;
  NewNode0->parent = &RA.NodeA[0];
  RA.NodeA[0].Right = NewNode1;
  NewNode1->parent = &RA.NodeA[0];
  for ( int i = 1;i < RA.n-1;i++) {
   RA.NodeA[i] = RA.NodeA[i + 1];
  }
  RA.n = RA.n - 1;
  //2.排序
  Sort(&RA);
  }

4.输出哈夫曼编码 。

递归,找到叶子节点,记录路径,左记录0,右记录1,直到输出所有叶子节点 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
void CrateCode(Node *t,string &s) {
  //1.遍历节点,遍历左节点编码为0,右节点则为1,递归,直到输出所有叶子节
  if (t->Left != NULL && t->Right != NULL) {
  s.push_back( '0' ); CrateCode(t->Left, s);
  s.pop_back();
  s.push_back( '1' );CrateCode(t->Right, s);
  s.pop_back();
  }
  else {
  cout << "哈夫曼编码:" ;
  cout << t->C << ":" << s<<endl;
  }
}

以上是对构造哈夫曼树以及生成哈夫曼编码的总结,希望对你们有所帮助! 。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我.

原文链接:https://blog.csdn.net/stephenli300203/article/details/105438016 。

最后此篇关于C++实现哈夫曼树的方法的文章就讲到这里了,如果你想了解更多关于C++实现哈夫曼树的方法的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com