哈夫曼编码, 哈夫曼树
2021/11/1 6:12:08
本文主要是介绍哈夫曼编码, 哈夫曼树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include <stdio.h> #include <stdlib.h> #include <string.h> #define swap(a, b) ({\ __typeof(a) temp = a;\ a = b, b = temp;\ }) typedef struct Node { double freq; char data; Node *lchild, *rchild; } Node; typedef struct Heap { Node **data; int cnt, size; } Heap; void clearHeap(Heap *heap) { free(heap->data); free(heap); return ; } void clear(Node *root) { if (!root) return ; clear(root->lchild); clear(root->rchild); free(root); return ; } Heap *initHeap(int s) { Heap *root = (Heap *)malloc(sizeof(Heap)); root->data = (Node **)malloc(sizeof(Node *) * (s + 5)); root->size = s, root->cnt = 0; return root; } Node *top(Heap *heap) {return heap->data[1];} int empty(Heap *p) {return p->cnt < 1;} void down_maintain(Heap *p) { if (p->cnt < 2) return ; int k; for (int i = k = 1; i << 1 <= p->cnt; i = k) { k = p->data[i]->freq > p->data[i << 1]->freq ? i << 1 : i; i << 1 | 1 <= p->cnt && (k = p->data[k]->freq > p->data[i << 1 | 1]->freq ? i << 1 | 1 : k); if (k == i) break; swap(p->data[i], p->data[k]); } return ; } void up_maintain(Heap *p) { if (p->cnt < 2) return ; for (int i = p->cnt; i ^ 1; i >>= 1) { if (p->data[i]->freq > p->data[i >> 1]->freq) break; swap(p->data[i], p->data[i >> 1]); } return ; } void pop(Heap *heap) { if (empty(heap)) return ; Node *p = top(heap); heap->data[1] = heap->data[heap->cnt--]; down_maintain(heap); return ; } void push(Heap *heap, Node *p) { if (!heap || heap->cnt == heap->size) return ; heap->data[(++heap->cnt)] = p; up_maintain(heap); return ; } Node *getNewNode(Node *lchild, Node *rchild, double freq, char data) { Node *root = (Node *)malloc(sizeof(Node)); root->lchild = lchild, root->rchild = rchild; root->freq = freq, root->data = data; return root; } Node *buildhalfman(Heap *heap) { if (heap->cnt == 1) return top(heap); if (empty(heap)) return top(heap); Node *l, *r; l = top(heap), pop(heap); r = top(heap), pop(heap); push(heap, getNewNode(l, r, l->freq + r->freq, 0)); return buildhalfman(heap); } int getHalfmancode(Node *root, char *buff, int k) { if (!root) return 0; buff[k] = 0; if (root->data) return printf("%s %c %.2lf\n", buff, root->data, root->freq); buff[k] = '0'; getHalfmancode(root->lchild, buff, k + 1); buff[k] = '1'; getHalfmancode(root->rchild, buff, k + 1); return 0; } int main() { int n; double freq; char s[100]; scanf("%d", &n); Heap *heap = initHeap(n); for (int i = 0; i < n; i++) { scanf("%lf%s", &freq, s); push(heap, getNewNode(0, 0, freq, s[0])); } Node *root = buildhalfman(heap); getHalfmancode(root, s, 0); return 0; }
这篇关于哈夫曼编码, 哈夫曼树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南
- 2024-09-26Springboot微服务资料入门教程