哈夫曼编码算法 |
您所在的位置：网站首页 › 霍夫曼编码效率计算公式 › 哈夫曼编码算法 |
哈夫曼编码算法
|
哈夫曼树
哈夫曼树, 即带权路径最小的树, 权值最小的结点远离根结点, 权值越大的结点越靠近根结点 图解 左孩子路径编码为 0, 右孩子路径编码为 1 图解 定义一个哈夫曼树 //定义一个哈夫曼树 typedef struct { //定义权值 unsigned int weight; unsigned int parent, lchild, rchild; }HTNode, *HuffmanTree;定义存放哈夫曼编码的空间 //存放哈夫曼编码 typedef char** HuffmanCode;创建一个哈夫曼树 //创建一个哈夫曼树 void CreateHuffmanTree(HuffmanTree* HT, int* w, int n) { int m = 0; //结点的总数(⊙﹏⊙) HuffmanTree adjust = NULL; //定义一个调整指针, 存放即时指向结点 int i = 0; //即时调整索引 //存放两个最小值 int s1 = 0; int s2 = 0; //判断输入是否合理 if (n exit(-1); } //初始化叶子结点, 第一个结点为空 for (adjust = *HT + 1, i = 1; i adjust->parent = 0; } for (i = n + 1; i unsigned int f_min = 100; int flag = 0; //用来记录已遍历过的结点 for (int i = 1; i f_min = (HT + i)->weight; flag = i; } } //给选中的结点置 1, 下次不需要再遍历 (HT + flag)->parent = 1; return flag; } //挑选 2 个权值最小的结点 void Select(HuffmanTree* HT, int n, int* s1, int* s2) { int tmp = 0; //临时变量 *s1 = Min(*HT, n); *s2 = Min(*HT, n); //目的是 s1 的权值要不大于 s2 的权值 if ((*HT + *s1)->weight > (*HT + *s2)->weight) { tmp = *s1; *s1 = *s2; *s2 = tmp; } }构造哈夫曼编码 void HuffmanCoding(HuffmanTree HT, HuffmanCode* HC, int n) { //动态开辟内存空间存放所有非叶子节点的编码 *HC = (HuffmanCode)malloc((n + 1) * sizeof(char*)); if (!*HC) { exit(-1); } //动态分配内存空间暂时存放某个结点的哈夫曼编码 char* cd = (char*)malloc(n * sizeof(char)); if (!cd) { exit(-1); } //求 n 个非叶子节点的哈夫曼编码 *(cd + n - 1) = '\0'; int start = 0; //用来存放编码起始位置 for (int i = 1; i if ((HT + f)->lchild == c) { *(cd + --start) = '0'; } else { *(cd + --start) = '1'; } } //根据该结点编码字符串的长度在指定位置动态开辟存放编码的空间 *(*HC + i) = (char*)malloc((n - start) * sizeof(char)); //将暂存编码空间中的编码字符串拷贝到地址空间去 strcpy(*(*HC + i), cd + start); } //释放暂存编码字符串的空间 free(cd); }遍历叶子结点 从上到下, 从左到右 void Traverse(HuffmanTree HT, int n) { //遍历叶子结点 HuffmanTree p = HT + 2 * n - 1; int i = 0; while ((p - HT > 0) && (p - HT break; } if (p->lchild rchild) { i = p->lchild; printf("%u ", (HT + i)->weight); p = HT + p->rchild; } else { i = p->rchild; printf("%u ", (HT + i)->weight); p = HT + p->lchild; } } printf("%u ", p->weight); printf("\n"); }遍历哈夫曼编码 //遍历哈夫曼编码 void TraverseCoding(HuffmanCode HC, int n) { for (int i = 1; i for (int i = 1; i HuffmanTree HT = NULL; HuffmanCode HC = NULL; //存放权值 int* w = 0; int n = 0; //叶子结点个数 printf("请输入叶子结点的个数:"); scanf("%d", &n); //动态分配内存空间存放权值 w = (int*)malloc(n * sizeof(int)); if (!w) { exit(-1); } printf("请输入权值:"); for (int i = 0; i printf("OK\n"); } system("pause"); return 0; }效果图 愿本篇文章能对大家有所帮助, 欢迎大家的评论和建议 |
图(3)即为哈夫曼树
即 A 的编码: 0 D 的编码: 10 B 的编码: 110 C 的编码: 111
【本文地址】
今日新闻 |
推荐新闻 |