21xrx.com
2024-12-31 19:03:55 Tuesday
登录
文章检索 我的文章 写文章
C++实现给定vector的哈夫曼编码值
2023-06-23 05:14:48 深夜i     --     --
C++ vector 哈夫曼编码

哈夫曼编码是一种常见的数据压缩技术，它可以将数据从一种表示形式转换为另一种更紧凑的表示形式。在这种编码技术中，频率较高的字符会被分配较短的编码，而较少频繁出现的字符会被分配较长的编码。在C++中，可以通过使用vector数据结构来实现给定vector的哈夫曼编码值。

首先，我们需要定义一个结构体来保存每个字符以及它出现的频率。该结构体可以定义如下：

struct node

  char character;

  int frequency;

;

接下来，我们需要定义一个函数来统计vector中每个字符的出现频率。该函数可以定义如下：

vector calculateFrequency(vector inputVector) {

  map frequencyMap;

  for(auto it = inputVector.begin(); it != inputVector.end(); it++) {

    frequencyMap[*it]++;

  }

  vector frequencyVector;

  for(auto it = frequencyMap.begin(); it != frequencyMap.end(); it++) {

    node tempNode = it->second;

    frequencyVector.push_back(tempNode);

  }

  return frequencyVector;

}

在上述代码中，我们使用了map数据结构来记录每个字符的出现频率，并初始化了一个空的vector来保存结果。接下来，我们遍历map，并将字符和它的频率存储在结构体中，并将结果添加到vector中返回。

接下来，我们需要定义一个函数来构建哈夫曼树。该函数可以定义如下：

node buildHuffmanTree(vector frequencyVector) {

  priority_queue , [](node a, node b) return a.frequency > b.frequency; > pq;

  for(auto it = frequencyVector.begin(); it != frequencyVector.end(); it++) {

    pq.push(*it);

  }

  while(pq.size() > 1) {

    node first = pq.top();

    pq.pop();

    node second = pq.top();

    pq.pop();

    node combined = {'\0', first.frequency + second.frequency};

    combined.left = make_shared (first);

    combined.right = make_shared (second);

    pq.push(combined);

  }

  return pq.top();

}

在上述代码中，我们使用了优先队列数据结构来排序每个结构体，然后将它们连接成一个树形结构。最终，我们返回创建的哈夫曼树。

最后，我们需要定义一个函数来生成每个字符的编码。该函数可以定义如下：

void generateEncodedValues(const shared_ptr & root, string code, map & encodedValues) {

  if(!root) {

    return;

  }

  if(root->character != '\0') {

    encodedValues[root->character] = code;

    return;

  }

  generateEncodedValues(root->left, code + "0", encodedValues);

  generateEncodedValues(root->right, code + "1", encodedValues);

}

在上述代码中，我们使用了递归算法来遍历哈夫曼树，并生成每个字符的哈夫曼编码。最终，我们返回一个包含每个字符和它的编码值的映射表。

在使用上述函数的时候，我们可以像下面的代码一样调用它们：

vector inputVector = {'a', 'b', 'a', 'c', 'a', 'd'};

vector frequencyVector = calculateFrequency(inputVector);

node huffmanTree = buildHuffmanTree(frequencyVector);

map encodedValues;

generateEncodedValues(make_shared (huffmanTree), "", encodedValues);

在上述代码中，我们创建了一个包含字符'a', 'b', 'a', 'c', 'a', 'd'的vector，并通过调用calculateFrequency函数生成了一个包含每个字符和它的频率的结构体数组。接下来，我们通过调用buildHuffmanTree函数来构建了一个哈夫曼树，并通过调用generateEncodedValues函数来生成了每个字符的哈夫曼编码。最终，我们得到一个包含每个字符和它的哈夫曼编码的映射表，并可以在后续的数据压缩中使用它们。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复