急求C++哈夫曼编码代码！

Question

把一串小写字母输出其出现次数，编码等等！非常感谢！

Answer 1

#include<iostream>
#include<string>
using namespace std;
typedef struct
{
int weight;
int flag;
int parent;
int lchild;
int rchild;
}hnodetype;
typedef struct
{
int bit[10];
int start;
char leaf;
}hcodetype;
void huf(char cha[],int m[],int n)
{
int i,j,m1,m2,x1,x2,c,p;
hnodetype *huffnode=new hnodetype[2*n-1];
hcodetype *huffcode=new hcodetype[n],cd;
for(i=0;i<2*n-1;i++)
{
huffnode[i].weight=0;
huffnode[i].parent=0;
huffnode[i].flag=0;
huffnode[i].lchild=-1;
huffnode[i].rchild=-1;
}
for(i=0;i<n;i++)
{
huffnode[i].weight=m[i];
huffcode[i].leaf=cha[i];
}
for(i=0;i<n-1;i++)
{
m1=m2=10000000;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(huffnode[j].weight<=m1&&huffnode[j].flag==0)
{
m2=m1;
x2=x1;
m1=huffnode[j].weight;
x1=j;
}
else if(huffnode[j].weight<=m2&&huffnode[j].flag==0)
{
m2=huffnode[j].weight;
x2=j;
}
}
huffnode[x1].parent=n+i;
huffnode[x2].parent=n+i;
huffnode[x1].flag=1;
huffnode[x2].flag=1;
huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;
huffnode[n+i].lchild=x1;
huffnode[n+i].rchild=x2;
}
for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=huffnode[c].parent;
while(p!=0)
{
if(huffnode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=huffnode[c].parent;
}
cout<<huffcode[i].leaf<<":";
for(j=cd.start+1;j<n;j++)
{
huffcode[i].bit[j]=cd.bit[j];
cout<<cd.bit[j];
}
cout<<endl;
huffcode[i].start=cd.start;
}
delete[] huffcode;
delete[] huffnode;
}
void main()
{
string str;
int i=0,j,n,m[100],h,k=0;
char cha[100];
cout<<"请输入一个字符串"<<endl;
cin>>str;
n=str.length();
cout<<"字符串总共有字符"<<n<<"个"<<endl;
for(i=0;i<n;i++)
{
j=0;h=0;
while(str[i]!=str[j])
j++;
if(j==i)
{
cha[k]=str[i];
cout<<"字符"<<cha[k]<<"出现";
}
else
continue;
for(j=i;j<n;j++)
{
if(str[i]==str[j])
h++;
}
cout<<h<<"次"<<endl;
m[k]=h;
k++;
}
cout<<"每个字符的哈夫曼编码是："<<endl;
huf(cha,m,k);
cin.get();
cin.get();

}

Answer 2

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

typedef struct node
{
int weight;
char ch;
struct node *left,*right;
}NODE;

typedef struct hcode
{
char ch;
int len;
unsigned char code[256];
}hcode;

int comp(const void *a,const void*b)
{
return (*(NODE **)(b))->weight-(*(NODE **)(a))->weight;
}

hcode codes[256]={{0,0,{0}}};
NODE *tree;

NODE *newNode(int weight,char ch,NODE *left,NODE *right)
{
NODE *node;
node=(NODE *)malloc(sizeof(NODE));
node->weight=weight;
node->ch=ch;
node->left=left;
node->right=right;
return node;
}

void count(char *str)
{
char *p=str;
NODE *node,*tmp1,*tmp2;
NODE *nodes[512];
int ch[256]={0};
int c=0,i;
while (*p>0)
{
ch[(int)*p]++;
p++;
}
for(i=0;i<256;i++)
if(ch[i]>0)
{
nodes[c]=newNode(ch[i],i,NULL,NULL);
c++;
printf("%c的权值为:%d\n",(char)i,ch[i]);
}
nodes[c]=newNode(0,0,NULL,NULL);
while (c>0)
{
qsort(nodes,c+1,sizeof(NODE *),comp);
tmp1=nodes[c];
tmp2=nodes[c-1];
node=newNode(tmp1->weight+tmp2->weight,0,tmp1,tmp2);
nodes[c-1]=node;
c--;
}
tree=nodes[0];
}

void convert(NODE *node,int len)
{
static unsigned code[256]={0};
int i;
if(node->left==NULL&&node->right==NULL)
{
for(i=0;i<=len;i++) codes[(int)node->ch].code[i]=code[i] ;
codes[(int)node->ch].len=len;
codes[(int)node->ch].ch=node->ch;
}
if(node->left!=NULL)
{
code[len]=0;
convert(node->left,len+1);
}
if (node->right!=NULL)
{
code[len]=1;
convert(node->right,len+1);
}
return ;
}

void encode(char *src,char *dst)
{
char *ps=src,*pd=dst;
int pb=0,i;
while(*ps>'\0') ps++;
ps=(src-1);
printf("编码后的二进制表示为:\n");
do
{
ps++;
for(i=0;i<codes[(int)*ps].len;i++)
{
printf("%d",codes[(int)*ps].code[i]);
*pd=((*pd)<<1)+codes[(int)*ps].code[i];
pb++;
if(pb>=8){pd++;pb=0;}
}
}while(*ps>'\0');
*pd=*pd<<(8-pb);
*(pd+1)='\0';
}

void decode(char *src,char *dst)
{
char *ps=src,*pd=dst;
int pb=7,ts;
NODE *node=tree;
while (1)
{
if(node->left==NULL&&node->right==NULL)
{
*pd=node->ch;
//printf("%c",node->ch);
if (*pd==0) return ;
pd++;
node=tree;
}
else
{
ts=(*ps)>>pb&0x1;
pb--;
if(pb<0) {pb=7;ps++;}
if (ts==0)
{
node=node->left;
}
else
{
node=node->right;
}
}
}
printf("\n");
}

int main()
{
int i,j;
//char str[1024]="qwertyuiopasdfghjklzxcvbnm1234567890\0";
char str[1024]={0};
char out[1024]={0};
char out2[1024]={0};
printf("请输入要测试的字符串:\n");
gets(str);
printf("输入的字符串为:%s\n长度为:%d\n",str,strlen(str));
count(str);
convert(tree,0);
for(i=0;i<256;i++)
{
if(codes[i].len>0)
{
printf("%c的Huffman编码为:",(char)i);
for(j=0;j<codes[i].len;j++)
printf("%d ",codes[i].code[j]);
printf("\n");
}
}
encode(str,out);
printf("\n编码后的字符串为:%s\n长度为:%d\n",out,strlen(out));
decode(out,out2);
printf("\n解码后的字符串为:%s\n长度为:%d\n",out2,strlen(out2));
return 0;
}

Answer 3