关于哈夫曼表
我们刚刚学二叉树,现在给几个正整数,个数已知,让建一个哈夫曼树,并求出带权路径长度
比如说给一串数5 4 5 6 7 8第一个是数字个数,要求建立一个哈夫曼树并输出带权路径长度,最后输出69,哈夫曼树的原理我懂,但是就是写不出来建立哈夫曼树的函数来,想的头都疼了,请各位救救菜鸟吧....
[解决办法]
看一下优先队列吧!!把所有节点压进去,先取最小两个节点合并生一个节点压进队列,再去两个最小节点。。。。
[解决办法]
LZ给你个链接吧http://zhidao.baidu.com/question/319700597.html 建议看完之后自己写一个。。。。
[解决办法]
结合百度和书本,要画图,试试看!
[解决办法]
#include <stdio.h>#include <string.h>#define n 100#define m 2*n-1typedef struct{ char ch; char bits[9]; int len;}CodeNode;typedef CodeNode HuffmanCode[n+1];typedef struct{ int weight; int lchild,rchild,parent;}HTNode;typedef HTNode HuffmanTree[m+1];int num;void selectHT(HuffmanTree T,int k ,int &s1,int &s2){ int i,j; int min1 = 101; for(i = 1;i <= k;i++) if(T[i].weight < min1&&T[i].parent == 0) { j = i; min1 = T[i].weight; } s1 = j; min1 = 32767; for(i = 1;i <= k;i++) if(T[i].weight < min1&&T[i].parent == 0&&i != s1) { j = i; min1 = T[i].weight; } s2 = j;}int jsq(char *s,int cnt[],char str[]){ //统计各字符串中各种字母的个数以及字符的种类 char * p; int i,j,k; int temp[27]; for(i = 1;i <= 26;i++) temp[i] = 0; for(p = s;*p != '\0';p++) {//统计各种字符个数 if(*p>='A' && *p <= 'Z') { k = *p - 64; temp[k]++; } } j = 0; for(i = 1,j = 0;i <= 26;i++)//统计有多少种字符 if(temp[i] != 0) { j++; str[j] = i + 64; //送对应的字母到数组中 cnt[j] = temp[i]; //存入对应字母权值 } return j;}void CreHuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[]){ int i,s1,s2; for(i = 1;i <= 2*num -1;i++) { HT[i].lchild = 0; HT[i].rchild = 0; HT[i].parent = 0; HT[i].weight = 0; } for(i = 1;i <= num;i++) HT[i].weight = cnt[i]; for(i = num + 1;i <= 2*num -1;i++) { selectHT(HT,i - 1,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; } for(i = 0;i <= num;i++) HC[i].ch = str[i]; i = 1; while(i <= num) { printf("字符%c,次数为:%d\n",HC[i].ch,cnt[i++]); }}void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC){ int c,p,i; char cd[n]; int start; cd[num] = '\0'; for(i = 1;i <= num;i++) { start = num; c = i; while((p = HT[c].parent) > 0) { cd[--start] = (HT[p].lchild == c)?'0':'1'; c = p; } strcpy(HC[i].bits,&cd[start]); HC[i].len = num - start; }}void coding(HuffmanCode HC,char *str){ int i,j; FILE *fp; fp = fopen("codefile.txt","w"); while(*str) { for(i = 1;i <= num;i++) { if(HC[i].ch == *str) { for(j = 0;j < HC[i].len;j++) fputc(HC[i].bits[j],fp); break; } } str++; } fclose(fp);}char * decode(HuffmanCode HC){ FILE *fp; char str[254]; char *p; static char cd[n+1]; int i,j,k = 0,cjs; fp = fopen("codefile.txt","r"); while(!feof(fp)) { cjs = 0; for(i = 0;i < num&&cjs == 0&&!feof(fp);i++) { cd[i] = ' '; cd[i+1] = '\0'; cd[i] = fgetc(fp); for(j = 1;j <= num;j++) { if(strcmp(HC[j].bits,cd) == 0) { str[k] = HC[j].ch; k++; cjs = 1; break; } } } } str[k] = '\0'; p = str; return p;}void main(){ char st[254],*s,str[27]; int cn[27]; HuffmanTree HT; HuffmanCode HC; printf("输入需要编码的字符串(假设均为大写字母):\n"); gets(st); num = jsq(st,cn,str); CreHuffmanTree(HT,HC,cn,str); HuffmanEncoding(HT,HC); coding(HC,st); s = decode(HC); printf("译码后的字符串:"); printf("%s\n",s);}