Huffman树的应用 （数据结构）

/************************************************************************* > File Name: Huffman树的利用.cpp > Author: zzuspy > Mail: zzuspy@qq.com > Created Time: 2014年12月3日 14:30 ************************************************************************/ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cstdlib> #include <cmath> #include <stack> #include <queue> #define LL long long #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) using namespace std; typedef struct { int weight; int parent, lchild, rchild; }HTNode, *HuffmanTree; typedef char * * HuffmanCode; int s1, s2; void Select(HuffmanTree &HT, int n) { int i, min; for(int i=1; i<=n; i++) { if(HT[i].parent==0) { min = i; break; } } for(i=1; i<=n; i++) { if(HT[i].weight<HT[min].weight && HT[i].parent == 0)min = i; } s1 = min; for(int i=1; i<=n; i++) { if(HT[i].parent==0 && i!=s1) { min = i; break; } } for(int i=1; i<=n; i++) { if(HT[i].parent == 0 && i!=s1 && HT[i].weight<HT[min].weight && HT[i].weight>=HT[s1].weight) min=i; } s2 = min; } void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) { if(n<=1) return; int m = 2 * n - 1, i; HuffmanTree p; HT = (HuffmanTree)malloc( (m + 1) * sizeof(HTNode)); for( p = HT+1, i = 1; i <= n; i++, p++, w++) { p->weight = *w; p->parent = p->lchild = p->rchild = 0; } for(; i <= m; i++, p++) { p->weight = p->parent = p->lchild = p->rchild = 0; } //输出这时候Huffman树 /*for(int i=1; i<=n; i++) { printf("%d %d %d %d ", HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild); }*/ for(i = n + 1; i<=m; i++) { Select(HT, i⑴); //printf("%d %d ", s1, s2); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } HC = (HuffmanCode)malloc( ( n + 1 ) * sizeof(char *)); char *cd = (char *)malloc( n * sizeof(char) ); cd[n⑴] = ''; for(i=1; i<=n; i++) { int start = n - 1; for(int c = i, f = HT[i].parent; f!=0; c=f, f=HT[f].parent) 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 mawen(HuffmanCode &HC, char str[]) { printf(" "); FILE *p; char c; p = fopen("essay","r"); while((c = fgetc(p))!=EOF) { for(int i=0; str[i]!=''; i++) { if(str[i] == c) { printf("%c %s ", c, HC[i+1]); break; } } } fclose(p); printf(" "); } void codetext(char wen[], HuffmanCode &HC, char str[]) { int start = 0; FILE *p; char c; p = fopen("essay","r"); while((c = fgetc(p))!=EOF) { for(int i=0; str[i]!=''; i++) { if(str[i] == c) { strcpy(wen+start, HC[i+1]); start+=strlen(HC[i+1]); break; } } } fclose(p); printf(" "); } void translate(char wen[], int wei[], char str[], HuffmanTree &HT, HuffmanCode &HC, int elem) { int q = 2 * elem - 1, n=0; char *ch; ch = (char*)malloc(100*sizeof(char)); for(int i=0; wen[i]!=''; i++) { if(wen[i] == '0') { *(ch+n) = '0'; *(ch+n+1) = ''; n++; q = HT[q].lchild; if(HT[q].rchild==0 && HT[q].lchild==0) { int i; for(i=0; i<elem; i++) { if(!strcmp(ch, HC[i+1]))break; } printf("%c", str[i]); q = 2 * elem - 1; n = 0; } } else if(wen[i] == '1') { *(ch+n) = '1'; *(ch+n+1) = ''; n++; q = HT[q].rchild; if(HT[q].rchild==0 && HT[q].lchild==0) { int i; for(i=0; i<elem; i++) { if(!strcmp(ch, HC[i+1]))break; } printf("%c", str[i]); q = 2 * elem - 1; n = 0; } } } } int wei[128]; //保存字符数大于0的每一个字符的数目 (即权值) char str[128]; //保存字符数大于0的字符 int elem = 0; //统计后字符数大于0的字符的总数 int statis[128]; //统计文章中各种字符的数目 char wen[1000010]; //用于保存码文 int main() { //打开文件读取字符，再统计每一个字符的个数 FILE *p; char c; p = fopen("essay","r"); while((c = fgetc(p))!=EOF) { printf("%c", c); //输出文章 statis[c]++; } fclose(p); //输出统计后个数大于0的字符 /*for(int i=0; i<128; i++) { if(statis[i]!=0) printf("%c : %d ", i, statis[i]); }*/ //紧缩字符，去掉字符数为0的字符 for(int i=0; i<128; i++) { if(statis[i]!=0) { str[elem] = i; wei[elem] = statis[i]; elem++; } } //输出紧缩后字符及其个数 /*for(int i=0; i<elem; i++) { printf("%c : %d ", str[i], wei[i]); }*/ //printf(" %d ", elem); //个数大于0的字符总数 HuffmanTree HT; HuffmanCode HC; //调用Huffman函数 ，将每一个字符对应的编码存在HC里，HT为你所建立的Huffman树 HuffmanCoding(HT, HC, wei, elem); //输出构造的Huffman树 /*for(int i=1; i<=2*elem⑴; i++) { printf("%d %d %d %d %d ", i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild); }*/ //输出个数大于0的字符及其字符编码 /*for(int i=1; i<=elem; i++) { printf(" %c %s ", str[i⑴], HC[i]); }*/ printf(" "); //调用码文函数 mawen(HC, str); printf(" "); //生成码文 codetext(wen, HC, str); //printf("%s ", wen); //译文 translate(wen, wei, str, HT, HC, elem); return 0; }