关于哈夫曼编码的一道题假定用于通信的报文仅由8个字母：a,b,c,d,e,f,g,h组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4.试为这8个字母设计哈夫曼编码,给出相应的哈夫曼树,原电文压缩

关于哈夫曼编码的一道题假定用于通信的报文仅由8个字母：a,b,c,d,e,f,g,h组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4.试为这8个字母设计哈夫曼编码,给出相应的哈夫曼树,原电文压缩
关于哈夫曼编码的一道题
假定用于通信的报文仅由8个字母：a,b,c,d,e,f,g,h组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4.试为这8个字母设计哈夫曼编码,给出相应的哈夫曼树,原电文压缩存储的总空间?并给出报文“abefhgeadcbb”的总码数?

关于哈夫曼编码的一道题假定用于通信的报文仅由8个字母：a,b,c,d,e,f,g,h组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4.试为这8个字母设计哈夫曼编码,给出相应的哈夫曼树,原电文压缩
下面是我写的一个程序,希望能满意.
#include
using namespace std;
struct htnode
{
char ch;
int weight;
int parent;
int lchild,rchild;
};
class huffmantree
{
public:
void code(char str1[],int w[],int n);
void uncode(char str1[],char str2[],int n);
private:
htnode ht[3000];
void creathuffmantree(char str1[],int w[],int n);
void select(int pos,int &r1,int &r2);
};
void huffmantree::select(int pos,int &r1,int &r2)
{
r1=r2=0;
for(int i=1;i

Huffman编码：数据通信用的二进制编码
编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列.
例 要传输的字符集 D={C,A,S,T, ; }
字符出现频率 w={ 2,4, 2, 3, 3}
T : 00
;...

全部展开

Huffman编码：数据通信用的二进制编码
编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列.
例 要传输的字符集 D={C,A,S,T, ; }
字符出现频率 w={ 2,4, 2, 3, 3}
T : 00
; : 01
A : 10
C : 110
S : 111
例 电文是{CAS;CAT}
其编码 “11010111011101000”

收起

始终用权值最小的两个数相加的双亲结点权值.
以此类推可很容易得出哈夫曼树的编码。

#include
#include
#include
#include
#include
#define ERROR 0;
#define OK 1;
typedef int Status;
typedef struct{ ...

全部展开

#include
#include
#include
#include
#include
#define ERROR 0;
#define OK 1;
typedef int Status;
typedef struct{
unsigned int weight;
int key;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char * * HuffmanCode;
int **KEY;
int N;
Status GetData(){
FILE *fp;
int key[100][2];
int ch,k,i,tem;
char str[16];
fp=fopen("data.txt","r");
k=0;
while(!feof(fp)){
ch=fgetc(fp);
i=0;
while(ch!=' '){
str[i]=ch;
i++;
ch=fgetc(fp);
}
str[i]='\0';
//printf("%d\n",strcmp(str,"空格"));
if(!strcmp(str,"空格")){
key[k][0]=' ';
}
else{
key[k][0]=str[0];
}
ch=fgetc(fp);
tem=0;
while(ch!='\n'&&ch!=EOF){
tem=tem*10+ch-'0';
ch=fgetc(fp);
}
key[k][1]=tem;
//printf("%c,%d\n",key[k][0],key[k][1]);
k++;
}
KEY=(int * *)malloc(k*sizeof(int *));
if(!KEY){
return ERROR;
}
for(i=0;iKEY[i]=(int*)malloc(2*sizeof(int));
if(!KEY[i]){
return ERROR;
}
KEY[i][0]=key[i][0];
KEY[i][1]=key[i][1];
}
N=k;
fclose(fp);
return OK;
}
Status InitHuffmanTree(HuffmanTree &HT){
int i;
HT=(HTNode *)malloc((2*N-1)*sizeof(HTNode));
if(!HT){
return ERROR;
}
for(i=0;iHT[i].weight=KEY[i][1];
HT[i].key=KEY[i][0];
HT[i].parent=-1;
HT[i].lchild=-1;
HT[i].rchild=-1;
}
for(;i<2*N-1;i++){
HT[i].parent=-1;
}
return OK;
}
void Select(HuffmanTree &HT,int n,int &fi,int &si){
int i=0,tem;
if(n>=2){
while(((HT+i)->parent)!=-1){
i++;
}
fi=i;
i++;
while((HT+i)->parent!=-1){
i++;
}
si=i;
if((HT+fi)->weight>(HT+si)->weight){
tem=fi;
fi=si;
si=tem;
}
for(i++;iif((HT+i)->parent==-1){
if((HT+i)->weight<(HT+fi)->weight){
si=fi;
fi=i;
}
else{
if((HT+i)->weight<(HT+si)->weight){
si=i;
}
}
}
}
}
}
int HuffmanTreeAllReady(HuffmanTree HT,int m){
int sum=0,i;
for(i=0;iif((HT+i)->parent==-1){
sum++;
}
if(sum>1){
return 0;
}
}
return 1;
}
void CreateHuffmanTree(HuffmanTree &HT,int n){
int s1,s2;
while(!HuffmanTreeAllReady(HT,n)){
Select(HT,n,s1,s2);
HT[n].parent=-1;
HT[n].lchild=s1;
HT[n].rchild=s2;
HT[n].weight=HT[s1].weight+HT[s2].weight;
HT[s1].parent=n;
HT[s2].parent=n;
n++;
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n){
char * str;
int len=0,tem,i,j;
unsigned int p;
str=(char *)malloc(n*sizeof(char));
for(i=0;ip=i;
len=0;
while((tem=HT[p].parent)!=-1){
if(HT[tem].lchild==p){
str[len]='0';
}
else{
str[len]='1';
}
len++;
p=tem;
}
HC[i]=(char *)malloc((len+1)*sizeof(char));
if(HC[i]){
for(j=0;jHC[i][j]=str[len-1-j];
}
HC[i][len]='\0';
str[len]='\0';
}
//printf("%d,%d\n",HC[i][0],len);
}
}
void OutputHuffmanCode(HuffmanCode HC){
int i;
for(i=0;iprintf("%c -> %s\n",KEY[i][0],HC[i]);
}
}
void Coding(HuffmanCode HC){
FILE *fp,*fq;
int ch,t;
fp=fopen("加密明文.txt","r");
fq=fopen("加密密文.txt","w+");
ch=fgetc(fp);
while(ch!=EOF){
if(ch==' '){
t=0;
}
else{
t=ch-'A'+1;
}
fputs(HC[t],fq);
//printf("%c",ch);
//printf("%s",HC[t]);
ch=fgetc(fp);
}
fclose(fp);
fclose(fq);
printf("OK\n");
}
void Decoding(HuffmanTree HT,int N){
FILE *fp,*fq;
int ch,t;
fq=fopen("解密明文.txt","w+");
fp=fopen("解密密文.txt","r");
ch=fgetc(fp);
while(ch!=EOF){
t=2*N-2;
while(HT[t].lchild!=-1&&HT[t].rchild!=-1){
if(ch=='0'){
t=HT[t].lchild;
}
else{
t=HT[t].rchild;
}
//printf("%c",ch);
ch=fgetc(fp);
}
//printf("%c",ch);
fputc(HT[t].key,fq);
//printf("%c",HT[t].key);
//printf("%s",HC[t]);
//ch=fgetc(fp);
}
fclose(fp);
fclose(fq);
printf("OK\n");
}
int main(){
HuffmanTree HT;
HuffmanCode HC;
int n,i,j,a,b,x;
GetData();
HC=(char * *)malloc((N)*sizeof(char *));
InitHuffmanTree(HT);
CreateHuffmanTree(HT,N);
HuffmanCoding(HT,HC,N);
//for(i=0;i<2*N-1;i++){
// printf("%d,%d,%d,%c,%d,%d\n",i,HT[i].parent,HT[i].weight,HT[i].key,HT[i].lchild,HT[i].rchild);
//}
printf("选项:1.输出哈夫曼编码 2.输入明文得到密文 3.输入密文得到明文 0.退出\n");
printf("输入选项:");
while(scanf("%d",&x),x){
switch(x){
case 1 :{
OutputHuffmanCode(HC);
break;
}
case 2 :{
Coding(HC);
}
case 3 :{
Decoding(HT,N);
}
}
printf("输入： 1.输出哈夫曼编码 2.输入明文得到密文 3.输入密文得到明文 0.退出\n");
printf("输入选项：");
}
return 0;
}
//我很少做注释，抱歉；
//data。txt中最后不要加回车！！！
//输入要规范
//认真琢磨吧

收起