• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C语言实现哈夫曼编码(最小堆,二叉树)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请
// 文件中有通过QT实现的界面
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct HNode *Heap; /* 堆的类型定义 */ typedef struct SData myData; typedef struct SData *HuffmanTree; typedef struct Ans SAns; struct Ans // 存储最终结果 { char ch; // 表示字符 char *s; // 一个字符串, 表示结点的哈夫曼编码 }; struct SData // 哈夫曼树的结构 { int freq; // 结点元素出现的频率 char ch; // 结点元素的字符 HuffmanTree Left, Right; // 此哈夫曼结点的左子树和右子树 }; int i = 0; // 充当遍历哈夫曼树时对结果结构体数组ans赋值的下标 struct HNode // 堆的结构体 { myData *Data; // 存储元素的数组 int Size; // 堆中当前元素个数 int Capacity; // 堆的最大容量 }; typedef Heap MinHeap; // 最小堆 MinHeap CreateHeap(int MaxSize); // 创建最小堆 int IsFull(MinHeap H); // 判断最小堆是否已满 int Insert(MinHeap H, myData X); // 往最小堆中插入元素 int IsEmpty(MinHeap H); // 判断最小堆是否为空 myData DeleteMin(MinHeap H); // 删除最小堆顶的元素, 即最小元素(自定义'小') char* MatchingString(char *s1, char *s2); // 连接不定长的字符串s1和s2, 返回新字符串 char* TraversalHT(myData *d, char *s, SAns *SAnsP); // 递归遍历哈弗曼树, 直到收录所有叶节点的数据 void InsertSort(SAns *ans, int N); // 插入排序 char* binarySearch(SAns *ans, char ch, int end); // 迭代实现的二分查找 int main() { MinHeap heap = CreateHeap(100); char ch; int freq; printf("先输入数字代表权值(大于0),再输入对应的字符,按Ctrl+Z结束\n"); while (scanf("%d %c", &freq, &ch) != EOF) { myData temp = { freq, ch, NULL, NULL }; Insert(heap, temp); // 将输入的数据放在结构体中, 插入到最小堆里 } HuffmanTree T; const int size = heap->Size; // 定义const常量size为初始时刻堆的大小 SAns *ans = (SAns*)malloc(sizeof(SAns)*size); // 通过连续两次取最小堆的堆顶元素, 且先取出的存放在左子树, 后取出的存放在右子树 // 合成一颗二叉树, 再将其插入最小堆中 // 反复进行此操作size-1次, 最终堆顶的元素就是我们所求的哈弗曼树 // 这里说的堆顶并不是指heap->Data[0], 因为heap->Data[0]已用于放置哨兵 for (int j = 1; j < size; j++) { T = (HuffmanTree)malloc(sizeof(myData)); T->Left = (HuffmanTree)malloc(sizeof(myData)); T->Right = (HuffmanTree)malloc(sizeof(myData)); *T->Left = (DeleteMin(heap)); *T->Right = (DeleteMin(heap)); T->freq = T->Left->freq + T->Right->freq; Insert(heap, *T); // printf("%d\n", heap->Data[1].freq); // 输出总频率, 也可以说是权重, 检验结果是否正确 } TraversalHT(&heap->Data[1], "", ans); // 遍历哈弗曼树, 将结果放在ans结构体数组中 // for (int k = 0; k < size; k++) // 检验 // { // printf("%c %s\n", ans[k].ch, ans[k].s); // } // printf("**********************\n"); InsertSort(ans, size); // 对ans数组进行插入排序, 元素的大小取决于字符ch的大小 // for (int k = 0; k < size; k++) // 检验排序的结果 // { // printf("%c %s\n", ans[k].ch, ans[k].s); // } printf("输入需要翻译的字符串:"); char str[100]; // 开一个足够大的字符数组, 用于存放需要翻译的字符串 while (scanf("%s", str) != EOF) { for (int w = 0; w < strlen(str); w++) { // 遍历str, 通过二分查找, 找到与字符对应的哈夫曼编码 printf("%s", binarySearch(ans, str[w], size - 1)); } printf("\n"); printf("输入需要翻译的字符串:"); } return 0; } char* binarySearch(SAns *ans, char ch, int end) { // 经典的二分查找, 算法详细过程省略... int mid; int beg = 0; while (end >= beg) { mid = (beg + end) / 2; if (ans[mid].ch > ch) beg = mid + 1; else if (ans[mid].ch < ch) end = mid - 1; else return ans[mid].s; } return NULL; // 消除warning } void InsertSort(SAns *ans, int N) { // 经典的插入排序, 算法详细过程省略... for (int p = 1; p < N; p++) { SAns temp = ans[p]; int i; for (i = p; i > 0 && ((int)ans[i - 1].ch < (int)temp.ch); i--) ans[i] = ans[i - 1]; ans[i] = temp; } } char* MatchingString(char *s1, char *s2) { // 由于本程序采用C语言编写, 没有内置string类, 且需要连接不定长的字符串s1和s2 // 故先申请一块动态内存, 用于存放结果t // 先将不定长的s1复制到t中, 之后直接通过strcat()函数把s2接在t后面,返回t char *t = (char*)malloc(strlen(s1) + strlen(s2) + 1); if (t == NULL) exit(1); strcpy(t, s1); strcat(t, s2); return t; } char* TraversalHT(myData *d, char *s, SAns *SAnsP) { // 接收参数 d, s, SAnsP, // d代表哈弗曼树结构, s用于存放遍历到此节点时的哈夫曼编码, // SAnsP用于存放通过遍历得到的叶节点的字符和哈夫曼编码所构成的结果 if (d->Left) // 若d存在左子树, 则继续遍历其左子树, 并且在字符串s后面拼接上字符串"0" TraversalHT(d->Left, MatchingString(s, "0"), SAnsP); else { // 不存在左子树, 则必定不存在右子树, 此时只需保存结果, 接着就可以返回NULL结束这次递归 SAns temp = { d->ch, s }; SAnsP[i] = temp; printf("编码: %c %s\n", d->ch, s); i++; // 结果数组下标+1 return NULL; } if (d->Right) // 若d存在右子树, 则继续遍历其右子树, 并且在字符串s后面拼接上字符串"1" TraversalHT(d->Right, MatchingString(s, "1"), SAnsP); return NULL; // 消除warning } MinHeap CreateHeap(int MaxSize) { // 创建容量为MaxSize的空的最小堆 MinHeap H = (MinHeap)malloc(sizeof(struct HNode)); H->Data = (myData *)malloc((MaxSize + 1) * sizeof(myData)); H->Size = 0; H->Capacity = MaxSize; H->Data[0].freq = -1; // 定义"哨兵"为小于堆中所有可能元素的值, 这里可以是-1 //有了哨兵就不必在后续的遍历中的for循环判断条件中加入(...&&i>1),可有效提高效率 return H; } int IsFull(MinHeap H) { return (H->Size == H->Capacity); } int Insert(MinHeap H, myData X) { // 将元素X插入最小堆H,其中H->Data[0]已经定义为哨兵 int i; if (IsFull(H)) { printf("最小堆已满\n"); return 0; } i = ++H->Size; // i指向插入后堆中的最后一个元素的位置 for (; H->Data[i / 2].freq > X.freq; i /= 2) H->Data[i] = H->Data[i / 2]; // 上滤X,最终i就是X的下标 H->Data[i] = X; // 将X插入 return 1; } int IsEmpty(MinHeap H) { return (H->Size == 0); } myData DeleteMin(MinHeap H) { // 从最小堆H中取出键值为最小的元素,并删除一个结点 int Parent, Child; myData MinItem, X; if (IsEmpty(H)) { printf("最小堆已为空\n"); X.freq = -1; return X; //-1表示删除元素失败 } MinItem = H->Data[1]; // 取出根结点存放的最小值 // 用最小堆中最后一个元素从根结点开始向上过滤下层结点 X = H->Data[H->Size--]; // 同时减小当前堆的规模 for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) { Child = Parent * 2; if ((Child != H->Size) && (H->Data[Child].freq > H->Data[Child + 1].freq)) Child++; // Child指向左右子结点的较小者 if (X.freq <= H->Data[Child].freq) break; // 找到了合适位置 else // 下滤X H->Data[Parent] = H->Data[Child]; } H->Data[Parent] = X; return MinItem; }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
收藏的堆排序c++代码发布时间:2022-07-14
下一篇:
c#上传下载ftp(支持断点续传)发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap