求高人把C++变成C语言！！
#include <iostream>class Huffman
{
public:
void Init();
void Encode(char *d,const char *s);
void Decode(char *d,const char *s);
void Print(const char *s);
void TreePrint();
protected:
void Select(int n,int &s1,int &s2);
int Find(char ch);
int IsValidCode(const char *ch);
void PrintNode(int level, int nodeID);
struct HuffmanTree{
char ch;
unsigned int weight;
unsigned int parent,lchild,rchild;
};
struct HuffmanCode{
char ch;
char code[8];
int size;
};
int CharSet;
HuffmanTree HT[265];
HuffmanCode HC[265];
int CodeLen;
};
#include <iostream>
#include <string>
#include <iomanip>
#include "huffman.h"
using namespace std;
void Huffman::Select(int n, int &s1, int &s2)
{
//寻找权值最小的字符
s1 = 0;
while(HT[s1].parent!=0)
s1++;
for(int i=s1+1; i<n; i++)
{
if( (HT[i].parent==0) && (HT[s1].weight>HT[i].weight) )
s1 = i;
}
//寻找权值次小的字符
s2 = 0;
while ((s2==s1) || (HT[s2].parent!=0))
s2++;
for(i=s2+1; i<n; i++)
{
if( (HT[i].parent==0) && (i != s1) && (HT[s2].weight>HT[i].weight))
s2 = i;
}
}
void Huffman::Init()
{
//初始化HuffmanTree
int n=0,w;
char c;
if(n<=0||n>256)
{
cout<<"请输入字符数(0~256)：";
cin>>n;
}
CharSet=0;
for(int i=0; i<n; i++)
{
cout<<i+1<<"号字符及其权值：";
cin>>c>>w;
if(w<0)
{
i--;
continue;
}
HT[CharSet].ch = c;
HT[CharSet].weight = w;
HT[CharSet].parent = 0;
HT[CharSet].lchild = 0;
HT[CharSet].rchild = 0;
CharSet++;
}
//建立HuffmanTree
int s1,s2;
for (i=CharSet; i<2*CharSet-1; i++)
{
Select(i,s1,s2);
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].parent = 0;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
HT[i].parent = 0;
}
//寻找该字符的编码
int Huffman::Find(char ch)
{
for(int i=0; i<CharSet; i++)
{
if( ch==HC[i].ch )
return i;
}
return -1;
}
//Huffman编码
void Huffman::Encode(char *d, const char *s)
{
for(int i=0; i<CharSet; i++)
{
unsigned int c = i;
unsigned int parent = HT[c].parent;
HC[i].size = 0;
while(parent!=0)
{
HC[i].ch = HT[i].ch;
if( c==HT[parent].lchild)
HC[i].code[HC[i].size++] = '0';
else
HC[i].code[HC[i].size++] = '1';
c = parent;
parent = HT[c].parent;
}
}
//对原文件压缩
char ch = 0;
int bit=0;
CodeLen = 0;
while(*s!='\0')
{
int i = Find(*s);
if(i!=-1)
{
//对该字符重新编码,并写入字符串d中
for(int j=HC[i].size-1; j>=0; j--)
{
ch = ch<<1;
if (HC[i].code[j]=='1')
{
ch = ch | 0x01;
}
bit++;
CodeLen++;
if(bit == 8)
{
*d = ch;
d++;
bit = 0;
ch = 0;
}
}
}
s++;
}
//最后一个字符编码后,不足8bit
if(bit > 0)
{
ch = ch<<(8-bit);
*d = ch;
d++;
}
*d = '\0';
}
//是否有效编码
int Huffman::IsValidCode(const char *ch)
{
const char *t=ch;
for(int i=0; i<CharSet; i++)
{
t = ch;
//编码是逆序存储,因此从后向前按字符比较
for(int j=HC[i].size-1; j>=0; j--)
{
if(*t!=HC[i].code[j])
break;
if(*t=='\0')
break;
t++;
}
if(j==-1)
return i;
}
return -1;
}
void Huffman::Decode(char *d, const char *s)
{
int i=0;
char ch[256]={0};
while(i<CodeLen)
{
for(int j=7; j>=0; j--)
{
if((unsigned char)*s & 1<<j)
strcat(ch,"1");
else
strcat(ch,"0");
//如果发现匹配的编码,则将对应的字符输出
int pos = IsValidCode(ch);
if (pos>=0)
{
*d = HC[pos].ch;
d++;
ch[0] = '\0';
}
i++;
if(i==CodeLen)
break;
}
s++;
}
*d='\0';
}
//将打印二进制编码
void Huffman::Print(const char *s)
{
int count=0;
while(count<CodeLen)
{
for(int i=7;i>=0;i--)
{
if ((unsigned char)*s & (1<<i))
cout<<1;
else
cout<<0;
count++;
if(count==CodeLen) break;
}
s++;
}
// cout<<endl;
}
//前序遍历
void Huffman::PrintNode(int level, int nodeID)
{
if(HT[nodeID].lchild==0 && HT[nodeID].rchild==0)
cout<<setw(level)<<setfill(' ')<<HT[nodeID].ch
<<setw(10-level)<<setfill('-')<<endl;
else
{
cout<<setw(level)<<setfill(' ')<<"#"
<<setw(10-level)<<setfill('-')<<endl;
PrintNode(level+1,HT[nodeID].lchild);
PrintNode(level+1,HT[nodeID].rchild);
}
}
void Huffman::TreePrint()
{
PrintNode(1,2*CharSet-2);
}
#include <iostream>
#include <string>
#include <iomanip>
#include<fstream>
#include "huffman.h"
using namespace std;
void main()
{
//打开文件ToBeTran.txt
ifstream OrgFile;
OrgFile.open("ToBeTran.txt",ios::in);
char *s=new char [100];
if(OrgFile.is_open())
{
while(!OrgFile.eof())
{
OrgFile.read(s,100);
}
char choice='c';
while(choice!='q')
{
cout<<"--------------请选择:\n"
<<"-------------i->初始化\n"
<<"-------------e->载入\n"
<<"-------------d->生成\n"
<<"-------------p->输出\n"
<<"-------------t->输出树\n"
<<"-------------q->退出\n";
cin>>choice;
switch(choice)
{
case 'i':
//建立Huffman树
cout<<"初始化中..."<<endl;
Huffman H;
H.Init();
cout<<"初始化成功!"<<endl;
break;
case 'e':
//编码
cout<<"载入中..."<<endl;
char d[100];
H.Encode(d,s);
cout<<endl;
break;
case 'd':
//译码
char buf[100];
H.Decode(buf,d);
cout<<"译码..."<<endl;
cout<<buf<<endl;
break;
case 'p':
//输出编码
cout<<"输出中..."<<endl;
H.Print(d);
cout<<endl;
break;
case 't':
//输出树
cout<<"输出中..."<<endl;
H.TreePrint();
break;
case 'q':
cout<<"退出!"<<endl;
break;
}
}
}
else
{
cout<<"载入错误！"<<endl;
}
}
