Question

2、哈夫曼树问题。

低传利用哈夫曼编码进行通讯可以大大提高信道利用率，缩短信息传输时间，降输成本，但是，这要求在发送端通过一个编码系统对待传数据进行预先编码；在接受端将传来的数据进行解码（复原）对于双工信道（即可以双向传输的信道），每端都要有一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编译码系统。
[基本要求]：
A：从终端读入字符集大小为n，及n个字符和n个权值，建立哈夫曼树，进行编码并且输出。
B：利用已建好的哈夫曼编码，对键盘输入的密文进行译码。输出字符明文
[测试数据] 用下表中给出的字符集和频度的实际统计数据建立哈夫曼树：
字符 A B C D E F G H I J K L M N
频度 64 13 22 32 103 21 15 47 57 1 5 32 20 57
字符 O P Q R S T U V W X Y Z 空格
频度 63 15 1 48 51 80 23 8 18 1 16 1 168

Answer 1

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>

#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;i<k;i++){
KEY[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;i<N;i++){

HT[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++;i<n;i++){
if((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;i<m;i++){
if((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;i<n;i++){
p=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;j<len;j++){
HC[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;i<N;i++){
printf("%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中最后不要加回车！！！
//输入要规范
//认真琢磨吧