#include<fstream.h>
#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
class element{
friend void Compress();
public:
    operator unsigned long()const{return key;}
    element& operator=(unsigned long y){key=y;return *this;}
public:
    int code;
    unsigned long key;
};

const D=4099,
      codes=4096,
      ByteSize=8,
      excess=4,
      alpha=256,
      mask1=255,
      mask2=15;
int LeftOver,status=0;

ifstream in;
ofstream out;
void Compress();
template <class T,class K>
class SortedChainNode{
//friend SortedChain<T>;
public:
    T data;
    SortedChainNode<T,K> *link;

};
template<class E, class K>
class SortedChain{
public:
    SortedChain(){first=0;}
    ~SortedChain(){};
    bool IsEmpty() const {return first == 0;}
    int Length() const;
    bool Search(const K& k,E& e)const;
    SortedChain<E,K>&Insert(const E& e);
    SortedChain<E,K>& DistinctInsert(const E& e);
        void Output(ostream& out) const;
private:
    SortedChainNode <E,K> *first;
};

template<class E, class K>
bool SortedChain<E,K>::Search(const K& k,E& e)const{
SortedChainNode<E,K> *p=first;
while(p&&p->data<k);
p = p->link;
if(p&&p->data==k){e=p->data;return 1;}
return false;
}


template<class E, class K>
SortedChain<E,K>& SortedChain<E,K>::Insert (const E& e)
{
 SortedChainNode<E,K> *p = first,
 *tp = 0;
 while (p && p->data < e) {
  tp = p;
  p = p->link;
 }

 SortedChainNode<E,K> *q = new SortedChainNode<E,K>;
 q->data = e;

 q->link = p;
 if (tp) tp->link = q;
 else first = q;
 return *this;
}


template<class E, class K>
SortedChain<E,K>& SortedChain<E,K>::DistinctInsert(const E& e){
SortedChainNode<E,K> *p=first,*tp=0;
while(p&&p->data<e);{tp=p;p=p->link;}
if(p&&p->data==e) return *this;
SortedChainNode<E,K> *q=new SortedChainNode<E,K>;
q->data=e;
q->link=p;
if(tp)tp->link=q;
else first=q;
return *this;
}

template<class E, class K>
class ChainHashTable{
public:
ChainHashTable(int divisor=11){D=divisor;
ht=new SortedChain<E,K> [D];}
~ChainHashTable(){delete []ht;}
bool Search(const K& k,E& e)const{
return ht[k%D].Search(k,e);}
ChainHashTable<E,K>& Insert(const E& e){
ht[e%D].DistinctInsert(e);
return *this;
}
void Output()const;
public:
    int D;
    SortedChain<E,K> *ht;

};

void SetFiles(int argc,char* argv[])
{//创建输入输出流
char OutputFile[50],InputFile[50];
//检查是否提供文件名
if(argc>=2)strcpy(InputFile,argv[1]);
else{//没有提供文件名：提示用户输入
cout<<"Enter name of file to compass"<<endl;
cout<<"File name should have no extension"<<endl;
cin>>InputFile;}

//文件名不应有扩展名
if(strchr(InputFile,'.')){
cerr<<"File name has extension"<<endl;
exit(1);}

//以二进制方式打开文件
in.open(InputFile,ios::binary);
if(in.fail()){cerr<<"Cannot open"<<InputFile<<endl;
exit(1);}
strcpy(OutputFile,InputFile);
strcat(OutputFile,".nz");
out.open(OutputFile,ios::binary);
}

void Output(ofstream out,unsigned long pcode)
{//输出8位，余下的位保存在LeftOver中
unsigned char c,d;
if(status){//余下4位
d=(unsigned char)pcode & mask1;
c=(unsigned char)((LeftOver<<excess)|(pcode>>ByteSize));
out.put(c);
out.put(d);
status=0;}
else{
LeftOver=pcode & mask2;
c=(unsigned char)(pcode>>excess);
out.put(c);
status=1;}
}

void Compress(){
ChainHashTable<element,unsigned long> h(D);
element e;
for(int i=0;i<alpha;i++){
e.key=i;
e.code=i;
h.Insert(e);}
int used=alpha;

unsigned char c;
in.get(c);
unsigned long pcode=c;
if(!in.eof()){
do{
in.get(c);
if(in.eof())break;
unsigned long k=(pcode<<ByteSize)+c;

if(h.Search(k,e))pcode=e.code;
else{
Output(out,pcode);
if(used<codes)
{
e.code=used++;
e.key=(pcode<<ByteSize)|c;
h.Insert(e);}
pcode=c;}
}while(1);
Output(out,pcode);
if(status){c=LeftOver<<excess;out.put(c);}
}
out.close();
in.close();
}



void main(int argc,char* argv[])
{
   SetFiles(argc,argv);
   Compress();
}

请看http://bbs.