课程设计哈夫曼编码系统_hafumanxitong csdn

#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<math.h>
#include<vector>
#include<iomanip>
#include<map>
using namespace std;
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXBIT 100
int n;
string str;
map<string,string>bianma1;
map<char,string>bianma2;
typedef struct 
{
    int bit[MAXBIT];
    int start;
} HCodeType; 
typedef struct
{
char ch;
int weight;
int parent,lchild,rchild;
}HNodeType;


void HaffmanTree(HNodeType HuffNode[])
{
int m1,m2,x1,x2,len,str_pinlv[52]; //大小写字母共52个
cout<<"请输入待编码的字符串（大/小写英文字母且不含空格）："<<endl;
cin>>str;
len=str.length();
memset(str_pinlv,0,sizeof(str_pinlv));
for(int i=0;i<len;i++)
{//统计字符出新的频率
if(str[i]>='a'&&str[i]<='z')
str_pinlv[str[i]-'a']++;
else if(str[i]>='A'&&str[i]<='Z')
str_pinlv[str[i]-'A'+26]++;
}
n=0;
for(int i=0;i<52;i++)
{//统计出现的字母种类数
if(str_pinlv[i]!=0)
n++;
}
for(int i=0;i<2*n-1;++i)
{//初始化
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
system("cls");
cout<<endl<<"     字符       频度"<<endl;
for(int i=0,j=0;j<52;++j)
{//初始化节点权值
if(str_pinlv[j]!=0)
{
if(j<26)
{
HuffNode[i].ch=(char)(j+'a');
HuffNode[i++].weight=str_pinlv[j];
cout<<"      "<<(char)(j+'a')<<"          "<<str_pinlv[j]<<endl;
}
else
{
HuffNode[i].ch=(char)(j+'A'-26);
HuffNode[i++].weight=str_pinlv[j];
cout<<"      "<<(char)(j+'A'-26)<<"          "<<str_pinlv[j]<<endl;
}

}
}
for(int i=0;i<n-1;++i)
{
m1=m2=MAXVALUE;
x1=x2=0;
for(int j=0;j<n+i;++j)
{
if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if(HuffNode[j].weight<m2&&HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
}
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
//cout<<HuffNode[x1].ch<<"和"<<HuffNode[x2].ch<<"的双亲是："<<n+i<<endl;
}
cout<<endl<<" 创建哈弗曼树成功！ =^_^= "<<endl<<endl;
system("pause");
}


int Send()
{//统计字符频度，建立哈弗曼树，记录编码
string str1="";
HNodeType huffnode[MAXLEAF];
HCodeType HuffCode[MAXLEAF],  cd;
HaffmanTree(huffnode);
for (int i=0; i < n; i++)
    {
        cd.start = n-1;
        int c = i;
        int p = huffnode[c].parent;
        while (p != -1)   /* 父结点存在 */
        {
            if (huffnode[p].lchild == c)
                cd.bit[cd.start] = 0;
            else
                cd.bit[cd.start] = 1;
            cd.start--;        /* 求编码的低一位 */
            c=p;                    
            p=huffnode[c].parent;    /* 设置下一循环条件 */
        } /* end while */
        
        /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
        for (int j=cd.start+1; j<n; j++)
        { HuffCode[i].bit[j] = cd.bit[j];}
        HuffCode[i].start = cd.start;
    } /* end for */
    
    /* 输出已保存好的所有存在编码的哈夫曼编码 */
system("cls");
cout<<endl<<"    哈弗曼编码如下： "<<endl<<endl;
    for (int i=0; i<n; i++)
    {
printf ("%c 的哈弗曼编码是: ", huffnode[i].ch);
        for (int j=HuffCode[i].start+1; j < n; j++)
        {   
str1+=(char)(HuffCode[i].bit[j]+'0');
printf ("%d", HuffCode[i].bit[j]);

}
bianma1[str1]=huffnode[i].ch;
bianma2[huffnode[i].ch]=str1;
str1="";
        printf ("\n");
    }
system("pause");
system("cls");
cout<<endl<<"原来字符串的编码是："<<endl;
for(int i=0;i<str.length();i++)
cout<<bianma2[str[i]];
cout<<endl;
system("pause");
return 0;
}
void Receive()
{
string str3,str4="";
system("cls");
cout<<"请输入需要破译的代码（只含有0和1且不含空格）："<<endl;
cin>>str3;
for(int i=0;i<str3.length();i++)
{
str4+=str3[i];
if(bianma1[str4]!="")
{
cout<<bianma1[str4];
str4="";
}
}
if(str4!="")
cout<<endl<<"Sorry,译码失败！"<<endl;
cout<<endl;
}
int main()
{
system("color 37");
Send();
Receive();
}


/*
iloveyou


1110010110000110010011
*/