专栏首页用户2119464的专栏c++ 哈夫曼树简便构造(数据结构作业篇)

c++ 哈夫曼树简便构造(数据结构作业篇)

// 用最小栈方式构建哈弗曼树

// 定义一个哈夫曼树的节点

struct MinHeapNode {

// One of the input characters

char data;

// Frequency of the character

unsigned freq;

// 哈夫曼的编码值, #号表示无编码

string code_huff = "#";

// Left and right child

MinHeapNode *left, *right;

    MinHeapNode(char data, unsigned freq)

    {

left = right = NULL;

this->data = data;

this->freq = freq;

    }

};

// 定义一个哈弗曼树的存储节点

struct Node {

char data;

string code_huff = "#";

}node[256];

// For comparison of

// two heap nodes (needed in min heap)

struct compare {

bool operator()(MinHeapNode* l, MinHeapNode* r)

    {

return (l->freq > r->freq);

    }

};

// 递归的方式打印哈夫曼编码从树的根部

void printCodes(struct MinHeapNode* root, string str)

{

if (!root)

return;

if (root->data != '$')

    {

cout << root->data << ": " << str << "\n";

        root->code_huff = str;

node[cou].data = root->data;

node[cou].code_huff = root->code_huff;

cou++;

    }

printCodes(root->left, str + "0");

printCodes(root->right, str + "1");

}

// 创建一个哈夫曼树

// data 为字符数组, freq 为对应频数, size 为字符数组元素的个数

struct MinHeapNode* HuffmanCodes(char data[], unsigned int freq[], int size)

{

struct MinHeapNode *left, *right, *top;

// 创建一个根据频数值的最小堆并插入字符数组中所有的字符

priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap;

// 将需要排序的内容压入堆中

for (int i = 0; i < size; ++i)

    {

if (freq[i] != 0)

        minHeap.push(new MinHeapNode(data[i], freq[i]));

    }

// Iterate while size of heap doesn't become 1

while (minHeap.size() != 1) {

// 从最小堆中取出两个最小频数的项目

        left = minHeap.top();

        minHeap.pop();

        right = minHeap.top();

        minHeap.pop();

// 创建树中的和节点, 并连接左右两个子节点, 后再将其压入堆中

        top = new MinHeapNode('$', left->freq + right->freq);

        top->left = left;

        top->right = right;

        minHeap.push(top);

    }

// 输出哈夫曼编码通过已创建的哈弗曼树

printCodes(minHeap.top(), "");

// 返回哈夫曼树的根

return minHeap.top();

}

以上程序中所用到的知识点如下:

  • 头文件精简法

可以用一个文件包含 c++ 所有的头文件 # 用来精简头文件的结构

  • 哈弗曼树的节点个数

# 建立叶节点个数为n,权值为weight的哈夫曼树共有 2n-1个节点

  • priority_queue 的用法

用法: priority_queue<Type, Container, Functional> maxHeap; # Type 为数据类型, Container 为保存数据的容器, Functional 为元素比较方式 # Container 默认用的是 vector, Functional 默认用 operator< # 默认形成大顶堆, 队头元素最大 # 上面程序中传入 compare 比较函数, 实现形成小顶堆, 队头元素最小

  • 堆的操作

入堆操作

用法: Heap.push(参数) # 将参数内容压入堆中

出堆操作

用法: Heap.pop(参数) # 将堆顶内容弹出

堆头

用法: Heap.top() # 表示堆头

  • 函数内的数组元素值改变

用法: 函数名: void str(char a[], int b[]) 使用函数: str(a, b); #可以直接传入数组头, 函数内改变数组元素即改变

  • '\n'是一个字符
  • 不忽略空白符的从文件中读取字符的解决方法

用 file.getline() 来解决

# 根据行的方式来读取

用 file >> noskipws;

# 强制读入每一个字符, 不过滤空白符, 包括换行符  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • js基础练习

    星辉
  • python入门(四) 统计班级同学总成绩(涉及文件)

    星辉
  • 爬虫入门篇(上手即用)

    若有些网址设有反爬机制,请求若没有headers就会报错。 可以通过chrome浏览器的F12-network查看request的headers,将该网页的h...

    星辉
  • Promise: 给我一个承诺,我还你一个承诺

    处理concurrent programming,除了threading/multi-processing外,各家语言都有自己的绝活:erlang/elixir...

    tyrchen
  • 155.Min Stack(Stack-Easy)

        Design a stack that supports push, pop, top, and retrieving the minimum elem...

    Jack_Cui
  • 09. SpringCloud实战项目-初始化项目和添加微服务

    Jackson0714
  • Spring Cloud Configuratin

    Spring cloud Configuation作为SC的基础服务,在全局化配置和统一运维方面起着不可或缺的作用。相信在做Spring项目的时...

    不蜇人的小蜜蜂
  • 腾讯云CDN的加速域名、源站地址与回源host之间的关系

    加速域名是接入腾讯云CDN的域名,例如使用www.yeruchimei.top域名接入CDN,那么加速域名就是www.yeruchimei.top咯。

    HadesMo
  • Ionic:高级的 HTML5 移动APP(Web App)开发框架

    Ionic 是一个用HTML, CSS 跟JS 开发的一个用于移动设备的混合APP 开发框架,采用 Sass与AngularJS 开发。目前,Ionic 仍然处...

    Jeff
  • 第二十八章:SpringBoot使用AutoConfiguration自定义Starter

    恒宇少年

扫码关注云+社区

领取腾讯云代金券