C语言实现哈夫曼树要代码
编程这些的东西,有没有知道的人啊
求大家告知,带带我
4条回答 默认 最新
- Kwan的解忧杂货铺@新空间代码工作室 2024-04-25 10:09关注
上午好☀️☀️☀️️
本答案参考ChatGPT-3.5C语言实现哈夫曼树需要进行以下步骤:
-
定义结构体Node,表示哈夫曼树中的节点,包含权值和左右子节点指针。
-
定义哈夫曼树的数据结构HuffmanTree,包含一个Node类型的指针数组nodes和一个int类型的变量size,表示节点数量。
-
实现一个比较函数,用于在构建哈夫曼树时按权值比较节点大小。
-
实现一个创建节点的函数createNode,用于根据权值创建一个节点。
-
实现一个构建哈夫曼树函数buildHuffmanTree,用于根据给定的权值数组构建哈夫曼树。
-
实现一个编码函数encodeHuffman,将指定的字符编码成哈夫曼编码。
-
实现一个解码函数decodeHuffman,将指定的哈夫曼编码解码成字符。
以下是C语言实现哈夫曼树的代码示例:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_CODE_LEN 256 // 结构体Node,表示哈夫曼树中的节点 typedef struct { int weight; // 节点权值 int parent; // 父节点下标 int left; // 左子节点下标 int right; // 右子节点下标 } Node; // 哈夫曼树的数据结构HuffmanTree typedef struct { Node *nodes; // 节点数组 int size; // 节点数量 } HuffmanTree; // 比较函数,用于按权值比较节点大小 int compareNode(const void *a, const void *b) { int aw = ((Node *)a)->weight; int bw = ((Node *)b)->weight; return aw - bw; } // 创建节点的函数 Node *createNode(int weight, int parent, int left, int right) { Node *node = (Node *)malloc(sizeof(Node)); node->weight = weight; node->parent = parent; node->left = left; node->right = right; return node; } // 构建哈夫曼树的函数 void buildHuffmanTree(HuffmanTree *tree, int *weights, int size) { int i, j, k, m1, m2; Node *nodes = (Node *)malloc(sizeof(Node) * size * 2); for (i = 0; i < size; i++) { nodes[i] = *createNode(weights[i], -1, -1, -1); } for (i = size; i < size * 2 - 1; i++) { m1 = m2 = size; for (j = 0; j < i; j++) { if (nodes[j].parent == -1) { if (nodes[j].weight < nodes[m1].weight) { m2 = m1; m1 = j; } else if (nodes[j].weight < nodes[m2].weight) { m2 = j; } } } nodes[m1].parent = i; nodes[m2].parent = i; nodes[i] = *createNode(nodes[m1].weight + nodes[m2].weight, -1, m1, m2); } tree->nodes = nodes; tree->size = size; } // 编码函数,将指定的字符编码成哈夫曼编码 void encodeHuffman(HuffmanTree *tree, char *codeTable[MAX_CODE_LEN], char *str, char *code) { int i, j, k; int len = strlen(str); for (i = 0; i < len; i++) { for (j = 0; j < tree->size; j++) { if (tree->nodes[j].weight == str[i]) { k = j; while (tree->nodes[k].parent != -1) { code[strlen(code)] = k == tree->nodes[tree->nodes[k].parent].left ? '0' : '1'; k = tree->nodes[k].parent; } for (j = strlen(code) - 1; j >= 0; j--) { codeTable[str[i]][strlen(codeTable[str[i]])] = code[j]; } code[strlen(code)] = 0; break; } } } } // 解码函数,将指定的哈夫曼编码解码成字符 void decodeHuffman(HuffmanTree *tree, char *codeTable[MAX_CODE_LEN], char *code, char *str) { int i, j, k, len; len = strlen(code); k = tree->size * 2 - 2; for (i = 0; i < len; i++) { if (code[i] == '0') { k = tree->nodes[k].left; } else { k = tree->nodes[k].right; } if (tree->nodes[k].left == -1 && tree->nodes[k].right == -1) { str[strlen(str)] = tree->nodes[k].weight; k = tree->size * 2 - 2; } } } int main() { int weights[] = {5, 6, 7, 8, 9, 10}; HuffmanTree tree; buildHuffmanTree(&tree, weights, sizeof(weights) / sizeof(weights[0])); char *codeTable[MAX_CODE_LEN] = {0}; int i, len; char code[MAX_CODE_LEN] = {0}; char str[MAX_CODE_LEN] = "hello world"; for (i = 0; i < MAX_CODE_LEN; i++) { codeTable[i] = (char *)malloc(sizeof(char) * MAX_CODE_LEN); codeTable[i][0] = 0; } encodeHuffman(&tree, codeTable, str, code); printf("Huffman Encoding:\n"); for (i = 0; i < MAX_CODE_LEN; i++) { if (codeTable[i][0] != 0) { printf("%c:%s\n", i, codeTable[i]); } } char *encoded = (char *)malloc(sizeof(char) * MAX_CODE_LEN * strlen(str)); encoded[0] = 0; len = strlen(str); for (i = 0; i < len; i++) { strcat(encoded, codeTable[str[i]]); } printf("Encoded String: %s\n", encoded); char *decoded = (char *)malloc(sizeof(char) * MAX_CODE_LEN); decoded[0] = 0; decodeHuffman(&tree, codeTable, encoded, decoded); printf("Decoded String: %s\n", decoded); return 0; }
注:以上代码仅为示例,实际使用时需要进行一定的修改和适应。
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报 -
悬赏问题
- ¥15 关于stm32hal库驱动ft6336触摸屏遇到的问题
- ¥15 需要手写数字信号处理Dsp三个简单题 不用太复杂
- ¥15 数字信号处理考试111
- ¥100 关于#audobe audition#的问题,如何解决?
- ¥15 allegro17.2生成bom表是空白的
- ¥15 请问一下怎么打通CAN通讯
- ¥20 如何在 rocky9.4 部署 CDH6.3.2?
- ¥35 navicat将excel中的数据导入mysql出错
- ¥15 rt-thread线程切换的问题
- ¥15 高通uboot 打印ubi init err 22