用C++编写Huffman码

用C++编写Huffman码

使用说明：首先建立哈夫曼树，输入你的信号源的个数，然后输入每个信号的符号及其相应的频率（最后乘以100不要出现小数的为好）我的输入文件名为Myinput.txt即在C盘下建立文本文档取名为Myinput.txt然后输入你的信号的符号以空格结束，最后按提示选择你需要实现的功能！


#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

typedef struct{
int weight;
int parent;
int lchild;
int rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

int minl(HuffmanTree t,int i);
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n);
void select(HuffmanTree t,int i,int *s1,int *s2);

void main(){
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
cout<<"请输入字符的个数："<<endl;
cin>>n;
char *ch;
ch=(char *)malloc((n+1)*sizeof(char));
w=(int *)malloc(n*sizeof(int));
for (i=0;i<n;i++)
{
cout<<"请输入字符以及对应的权值（中间以空格隔开）："<<endl;
cin>>ch[i+1];
cin>>w[i];
}//给w赋值。
HuffmanCoding(&HT,&HC,w,n);
cout<<"*******哈夫曼树已经建成啦！*********"<<endl;
cout<<"===================================="<<endl;
while (true)
{
cout<<" 1:将哈夫曼树存入Huffmancode文件中"<<endl;
cout<<" 2:从Myinput文件中读取字符然后编码存入codemyinput文件中；"<<endl;
cout<<" 3:从codemyinput读取编码输入到频幕上。"<<endl;
cout<<" 4:将codemyinput读取编码译码后存盘。"<<endl;
cout<<" 0:退出系统！！！！"<<endl;
cout<<" 请输入你的选择："<<endl;
int c;
cin>>c;
if (c==0)
{
cout<<"程序已经结束！谢谢使用！！！"<<endl;
break;
}
while(c>4||c<0)
{
cout<<"你输入有误请重新输入："<<endl;
cin>>c;
}
fstream file;
ofstream outfile;
ifstream printfile;
ifstream codefile;
ofstream textfile;
if(c==1){

file.open("c:\\Huffmancode.txt", ios::out);
if(!file)
{
cout<<"can not open output file."<<endl;
exit(1);
}
for(i=1;i<=n;i++){
file<<ch[i]<<"的编码是："<<HC[i]<<endl;
} //将哈夫曼树存入Huffmancode文件中去、
file.close();
cout<<"哈夫曼树已经存入Huffmancode文件中"<<endl;
cout<<"\n______________________"<<endl;
}
if(c==2){
file.open("c:\\Myinput.txt",ios::in);//从文件Myinput中读取字符。
outfile.open("c:\\codemyinput.txt",ios::out);
//将读取出的字符进行编码存入codemyinput文件中去、
char read;
cout<<"从Myinput文件中读取的数据为："<<endl;
while(!file.eof()){
file.get(read);
cout<<read;
for(i=1;i<=n;i++)
{
if(ch[i]==read)
{
// outfile<<read<<"的哈弗曼编码为：";
outfile<<HC[i];//将对应字符的编码输出到文件中。
break;
}
}
if(i>n)
{
outfile<<read;
}
}//读取文件完毕
outfile.close();
file.close();
cout<<"\n______________________"<<endl;
}
if(c==3){
printfile.open("c:\\codemyinput.txt",ios::in);
int count=0;
char c;
cout<<"\n这些字母对应的哈夫曼编码是："<<endl;
while (!printfile.eof())
{
printfile.get(c);
cout<<c;
if (count%50==0&&count!=0)
{
cout<<endl;
}
count++;
}
cout<<endl;
printfile.close();
}
if(c==4){

codefile.open("c:\\codemyinput.txt",ios::in);

textfile.open("c:\\textfile.txt",ios::out);
int flag=2*n-1;
char read;
codefile.get(read);
while(!codefile.eof())
{
//cout<<read;
if(read=='0'||read=='1')
{
while(true)
{
if(flag>=1&&flag<=n) //判断停止的条件
{
textfile<<ch[flag];
break;
}
else if(read=='0')
{
flag=HT[flag].lchild;
}
else
{
flag=HT[flag].rchild;
}
codefile.get(read);

}
}
else
{
textfile<<read;
codefile.get(read);
}
flag=2*n-1;
}
codefile.close();
textfile.close();
}

}//while循环结束的括号。
}

int minl(HuffmanTree t,int i)
{
int a,j,flag;
int k=1000;
for(a=1;a<=i;a++)
{
if(!t[a].parent)
{
flag=a;
break;
}
}
for(j=a;j<=i;j++)
{
if(t[j].parent==0&&t[j].weight<k)
{
k=t[j].weight;
flag=j;
}
}
t[flag].parent=1; //这是必须的
return flag;
}

void Select(HuffmanTree t,int i,int *s1,int *s2)
{
int j;
*s1=minl(t,i);
*s2=minl(t,i);
if(*s1>*s2)
{
j=*s1;
*s1=*s2;
*s2=j;
}
}

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n){
if(n<=1)
return;
int s1,s2,start;
char *cd=NULL;
int m=2*n-1;
*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
HuffmanTree p;
int i,c,f;
for(p=(*HT)+1,i=1;i<=n;i++,p++,w++){
(*p).weight=*w;
(*p).parent=0;
(*p).rchild=0;
(*p).lchild=0;
}
for(;i<=m;i++,p++){
(*p).weight=0;
(*p).parent=0;
(*p).rchild=0;
(*p).lchild=0;
}
for(i=n+1;i<=m;i++){
Select(*HT,i-1,&s1,&s2);//找出两个权值最小的节点s1,s2.
(*HT)[s1].parent=i;
(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;
(*HT)[i].rchild=s2;
(*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
}
(*HC)=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
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';
}
(*HC)[i]=(char *)malloc((n-start)*sizeof(char));
strcpy((*HC)[i],&cd[start]);
}
free(cd);
}

#include<string.h> #include<stdlib.h> #include<stdio.h> int m,s1,s2; typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表 void Select(HuffmanTree HT,int n) { int i,j; for(i = 1;i <= n;i++) if(!HT[i].parent){s1 = i;break;} for(j = i+1;j <= n;j++) if(!HT[j].parent){s2 = j;break;} for(i = 1;i <= n;i++) if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i; for(j = 1;j <= n;j++) if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j; } void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) { // 算法6.13 // w存放n个字符的权值(均>0)，构造哈夫曼树HT， // 并求出n个字符的哈夫曼编码HC int i, j; char *cd; int p; int cdlen; if (n<=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用 for (i=1; i<=n; i++) { //初始化 HT[i].weight=w[i-1]; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for (i=n+1; i<=m; i++) { //初始化 HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } puts("\n哈夫曼树的构造过程如下所示："); printf("HT初态:\n 结点 weight parent lchild rchild"); for (i=1; i<=m; i++) printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight, HT[i].parent,HT[i].lchild, HT[i].rchild); printf(" 按任意键，继续 ..."); getchar(); for (i=n+1; i<=m; i++) { // 建哈夫曼树 // 在HT[1..i-1]中选择parent为0且weight最小的两个结点， // 其序号分别为s1和s2。 Select(HT, i-1); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; printf("\nselect: s1=%d s2=%d\n", s1, s2); printf(" 结点 weight parent lchild rchild"); for (j=1; j<=i; j++) printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight, HT[j].parent,HT[j].lchild, HT[j].rchild); printf(" 按任意键，继续 ..."); getchar(); } //------无栈非递归遍历哈夫曼树，求哈夫曼编码 cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间 p = m; cdlen = 0; for (i=1; i<=m; ++i) // 遍历哈夫曼树时用作结点状态标志 HT[i].weight = 0; while (p) { if (HT[p].weight==0) { // 向左 HT[p].weight = 1; if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; } else if (HT[p].rchild == 0) { // 登记叶子结点的字符的编码 HC[p] = (char *)malloc((cdlen+1) * sizeof(char)); cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串) } } else if (HT[p].weight==1) { // 向右 HT[p].weight = 2; if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; } } else { // HT[p].weight==2，退回退到父结点，编码长度减1 HT[p].weight = 0; p = HT[p].parent; --cdlen; } } } // HuffmanCoding void main() { HuffmanTree HT;HuffmanCode *HC;int *w,n,i; puts("输入结点数:"); scanf("%d",&n); HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode)); w = (int *)malloc(n*sizeof(int)); printf("输入%d个结点的权值\n",n); for(i = 0;i < n;i++) scanf("%d",&w[i]); HuffmanCoding(HT,HC,w,n); puts("\n各结点的哈夫曼编码:"); for(i = 1;i <= n;i++) printf("%2d(%4d):%s\n",i,w[i-1],HC[i]); getchar(); } 14