(数据结构)Huffman树和编码
#include <STDIO.H>#include <stdlib.h>#include <string.h>typedef unsigned int unint;#define MAX 1000;typedef struct{unint weight;unint parent, lchild, rchild;}HTNode, *HuffmanTree;typedef char ** HuffmanCode;void Select(HuffmanTree &HT, unint n, unint &s1num, unint &s2num){unint tempMin, tempNum;unint i;unint s1, s2;s1 = s2 = MAX;for(i = 1; i <= n; i++)if( (0 == HT.parent) && (HT.weight < s2) ){s2 = HT.weight;s2num = i;if(s2 < s1){tempMin = s2;s2 = s1;s1 = tempMin;tempNum = s2num;s2num = s1num;s1num = tempNum;}}if (0 == HT.lchild){tempNum = s2num;s2num = s1num;s1num = tempNum;}}void HuffmanCoding( HuffmanTree &HT, HuffmanCode &HC, unint *w, unint n ){// w存放n个字符的权值(均>0)，构造Huffman树HT，并求出n个字符的Huffman编码HC。unint m, i, start, c, s2, s1, f;HuffmanTree p;char *cd;if (n <= 1)return;m = 2 * n - 1;HT = (HuffmanTree) malloc ( (m + 1) * sizeof(HTNode) );// 0号单元未用for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++w){//*p = { *w, 0, 0, 0 };p->weight = *w;p->parent = 0;p->lchild = 0;p->rchild = 0;}for (; i <= m; ++i, ++p){//*p = { 0, 0, 0, 0};p->weight = 0;p->parent = 0;p->lchild = 0;p->rchild = 0;}for (i = n+1; i <= m; ++i)// 建Huffman树{Select(HT, i - 1, s1, s2);// 在HT选择parent为0且weight最小的两个结点，其序号分别为s1和s2。HT.parent = i;HT.parent = i;HT.lchild = s1;HT.rchild = s2;HT.weight = HT.weight + HT.weight;}//----从叶子到根逆向求每个字符的Huffman编码------------HC = (HuffmanCode) malloc ( (n + 1) * sizeof(char *) );// 分配n个字符编码的头指针向量cd = (char *) malloc (n * sizeof(char));// 分配求编码的工作空间cd = '\0';// 编码结束符for (i = 1; i <= n; ++i)// 逐个字符求Huffman编码{start = n - 1;for (c = i, f = HT.parent; f != 0; c = f, f = HT.parent)// 从叶子到根逆向求编码if (c == HT.lchild)cd[-- start] = '0';elsecd[-- start] = '1';HC = (char *) malloc ( (n - start) * sizeof(char) );// 为第i个字符编码分配空间strcpy(HC, &cd);// 从cd复制编码(串)到HCprintf("%s\n",HC);free(HC);}free(HT);// 释放工作空间free(cd);free(HC);}int main(){HuffmanTree HT;HuffmanCode HC;unint w={5, 29, 7, 8, 14, 23, 3, 11};unint n = 8;HuffmanCoding(HT, HC, w, n);return 0;} 不清楚有木有错~http://www.agoit.com/images/smiles/icon_cry.gif求大牛带
页:
[1]