Question

Huffman编码的实现,用c++编写，要用到map关联容器，谢谢高手指教！

Answer 1

#include"stdio.h"
#include"conio.h"
#include"stdlib.h"
#include"string.h"

#define MAX 32767
#define OK 1
#define ERROR 0
#define N 62 /* 字符集的容量 */

typedef char **HuffmanCode;

typedef struct elemtype /* 字符集的元素结构 */
{
char data;
int weight;
}elemtype;

typedef struct HTNode/* 哈夫曼树的元素结构 */
{
elemtype dt;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;

int WriteDate(HuffmanTree HT,HuffmanCode HC);
void TreePrint(HuffmanTree HT,HuffmanCode HC);

elemtype Char_w[N]={
{' ',186},
{'A',64},{'B',13},{'C',22},{'D',32},
{'E',103},{'F',21},{'G',15},{'H',47},
{'I',57},{'J',1},{'K',5},{'L',32},
{'M',20},{'N',57},{'O',63},{'P',15},
{'Q',1},{'R',48},{'S',51},{'T',80},
{'U',23},{'V',8},{'W',18},{'X',1},
{'Y',16},{'Z',1},
{'a',5},{'b',4},{'c',6},{'d',3},
{'e',13},{'f',2},{'g',5},{'h',7},
{'i',3},{'j',1},{'k',2},{'l',3},
{'m',2},{'n',5},{'o',3},{'p',1},
{'q',1},{'r',4},{'s',1},{'t',4},
{'u',9},{'v',1},{'w',1},{'x',1},
{'y',2},{'z',1},
{',',37},{39,107},/*'39'为单引号的ASCII*/
{'"',27},{'!',2},{'.',45},{';',23},
{'?',15},{':',25},{'\n',50}

};

int Select(HuffmanTree HT,int n,int*s1,int*s2)
{
int sm1,sm2,i;
*s2=*s1=1;
sm1=MAX; sm2=MAX;
for(i=1;i<=n;i++)
{
if(HT[i].parent==0)
if(HT[i].dt.weight<sm1)
{
sm2=sm1;
sm1=HT[i].dt.weight;
*s2=*s1; *s1=i;
}
else if(HT[i].dt.weight<sm2)
{
sm2=HT[i].dt.weight;
*s2=i;
}
}
return OK;
}

int Ch_Find(HuffmanTree HT,char ch,int*n)
{
int i;
if(!HT)return ERROR;
for(i=1;i<=N;i++)
if(HT[i].dt.data==ch){
*n=i;
return OK;
}
return 0;
}

int E_ReadDat(HuffmanTree HT,HuffmanCode HC)
{
char ch; int n; FILE*fp1,*fp2;
if(!(fp1=fopen("inch.txt","r")))return ERROR;
if(!(fp2=fopen("Hcode.txt","w")))return ERROR;
while((ch=fgetc(fp1))!=EOF)//如果文件未结束，则去找与字符ch对应的编码的位置
if(!Ch_Find(HT,ch,&n)){
printf("There's no char like this"); break;
}
else fprintf(fp2,"%s",HC[n]);

fclose(fp1);
fclose(fp2);
printf("Finish Ecoding!\n");
return OK;
}
int D_ReadDat(HuffmanTree HT,HuffmanCode HC)
{
FILE *fp1,*fp2;
char Hc[20],ch;
int j,length=0;
memset(Hc,0,20);
if(!(fp1=fopen("Hcode.txt","r")))return ERROR;
if(!(fp2=fopen("Decoding.txt","w")))return ERROR;
while((ch=getc(fp1))!=EOF)
{
Hc[length++]=ch;
for(j=1;j<=N;j++)
if(strcmp(Hc,HC[j])==0)
{
fprintf(fp2,"%c",HT[j].dt.data);//找到相对应字符，写入fp2所指向的文件
memset(Hc,0,20);
length=0;break;
}

}
fclose(fp1); fclose(fp2);
return OK;
}
int E_HandDat(HuffmanTree HT,HuffmanCode HC)
{
char ch[100];
int n,M,i;
printf("\nwhat do you whant to encoding,please input:\n");
gets(ch);
M=strlen(ch);
for(i=0;i<M;i++) //则去找与字符ch对应的编码的位置
{
if(!Ch_Find(HT,ch[i],&n))
{ printf("There's no char like this"); break;}
else printf("%s",HC[n]);
}
printf("\nFinish Ecoding!\n");
return OK;
}
int D_HandDat(HuffmanTree HT,HuffmanCode HC)
{
char Dcode[1000];
char Hc[20];
int i,j,count=0,length=0,sm=strlen(Dcode);
memset(Hc,0,20);
printf("\n Enter a binary string for decoding:");
gets(Dcode);
while(count!=sm)
for(i=0;i<sm;i++)
{
count++;
Hc[length++]=Dcode[i];
for(j=1;j<=N;j++)
if(strcmp(Hc,HC[j])==0)
{
printf("%c",HT[j].dt.data);//找到相对应字符，写入fp2所指向的文件
memset(Hc,0,20);
length=0;break;
}
}
return OK;
}
int WriteDate(HuffmanTree HT,HuffmanCode HC)
{
FILE*fp1,*fp2;
int i;
if(!(fp1=fopen("HuffmanTree.txt","w"))) return ERROR;
if(!(fp2=fopen("chweight.txt","w"))) return ERROR;
for(i=1;i<=N;i++)
{
fprintf(fp1,"%-3c%-4d%-4d%-4d%-4d%-11s ",HT[i].dt.data,HT[i].dt.weight ,HT[i].parent ,HT[i].lchild ,HT[i].rchild,HC[i] );
fprintf(fp2,"%c:%d ",Char_w[i-1].data,Char_w[i-1].weight);
if(i%2==0)
fprintf(fp1,"%c",'\n');
}

fclose(fp1);
fclose(fp2);
return OK;
}
//求赫夫曼编码的算法实现：
HuffmanCode HuffmanCoding(HuffmanTree HT, int n)
{//根据构造的赫夫曼树HT,并求出n个字符的赫夫曼编码HC.
HuffmanCode HC;
int i,start,f,c;
char*cd;
if(!(HC=(HuffmanCode)malloc((n+1)*sizeof(char*)))) return NULL;
if(!(cd=(char*)malloc(n*sizeof(char)))) return NULL;
cd[n-1]='\0';
for(i=1;i<=n;i++){ //逐个字符求赫夫曼编码
start=n-1; //编码结束符位置
for(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';
if(!(HC[i]=(char*)malloc((n-start)*sizeof(char)))) return ERROR; //为第i个字符编码分配空间
strcpy(HC[i],&cd[start]); //从cd复制编码(串)到HC
}
free(cd); //释放工作空间
return HC;
} //Huffancoding

HuffmanTree Initialization(int n)
{ //读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树
HuffmanTree HT;
int i,m,s1,s2;
m=2*n-1;
if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)))) return NULL;
for(i=1;i<=n;++i)
{
HT[i].dt=Char_w[i-1]; HT[i].parent=0;
HT[i].lchild=0; HT[i].rchild=0;
}
for(;i<=m;++i)
{
HT[i].dt.data='\0';
HT[i].dt.weight=0; HT[i].parent=0;
HT[i].lchild=0; HT[i].rchild=0;
}
for(i=n+1;i<=m;++i)
{//建赫夫曼树在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2；
Select(HT,i-1,&s1,&s2);
HT[s1].parent=i; HT[s2].parent=i;
HT[i].lchild=s1; HT[i].rchild=s2;
HT[i].dt.weight=HT[s1].dt.weight+HT[s2].dt.weight;
}
return HT;
}
void Encoding(HuffmanTree HT,HuffmanCode HC)
{ char ch;
printf(" please select: read form file or input by hand or打印Huffmantree (R or H or P orQ)\n");
ch=getche();
while(ch!='P'&&ch!='R'&&ch!='H'&&ch!='Q')
{
printf("input again:"); ch=getche();
}
switch(ch)
{
case 'R':E_ReadDat(HT,HC);return;
case 'H':E_HandDat(HT,HC);return;
case 'P': TreePrint(HT,HC);return;
case 'Q':return;
}

}
void Decoding(HuffmanTree HT,HuffmanCode HC)
{ int i=0; char ch;
printf(" please select: read form file or input by hand or打印Huffmantree (R or H or P orQ)\n");
ch=getche();
while(ch!='P'&&ch!='R'&&ch!='H'&&ch!='Q')
{
printf("input again:\n"); ch=getche();
}
switch(ch)
{
case 'R':D_ReadDat(HT,HC);return;
case 'H':D_HandDat(HT,HC);return;
case 'P': TreePrint(HT,HC);return;
case 'Q':return;
}
printf("Finish Decoding!\n");
return ;
}

void TreePrint(HuffmanTree HT,HuffmanCode HC)
{
int i;
for(i=1;i<=2*N-1;i++){
printf("%-2c%-4d%-4d%-4d%-4d ",HT[i].dt.data,HT[i].dt.weight ,HT[i].parent ,HT[i].lchild ,HT[i].rchild );
if(i<=N)printf("%s\n",HC[i]);
else printf("\n");
}
}
void main()
{
char ch;
HuffmanTree HT=NULL; /* 哈夫曼树类型 */
HuffmanCode HC=NULL; /* 编码类型 */
HT=Initialization(N);
HC=HuffmanCoding(HT,N);
/* WriteDate(HT,HC);*/
while(ch!='Q') /* 当键入'Q'时程序运行结束 */
{
printf("请选择:E：编码 D：译码 Q：结束程序\n");
ch=getche();
while(ch!='E'&&ch!='D'&&ch!='Q')
{printf("input again:"); ch=getche(); /* 选取功能 */}
switch(ch)
{
case 'E': Encoding(HT,HC);break;/* 求测试数据的编码(Encoding) */
case 'D': Decoding(HT,HC);break; /* 译码(Decoding) */
case 'Q': exit(0); /* 程序结束，返回 */
}
}
}

我有哈弗曼编码你也得看得懂啊

Answer 2

学计算机这关要是过不了就白学了，哥们

Answer 3

好好研究,总会明白的