哈夫曼树压缩代码

#include <iostream>

#include <fstream>

#include <vector>

#include <string>

#include <algorithm>


struct THalfNode
{
 char c;
 int weight;
 struct THalfNode *left;
 struct THalfNode *right;
 THalfNode();
 static FreeTree(THalfNode *root);
 static DisplayTree(THalfNode *root, int ident, std::ostream& ostrm);
};
struct THalfTab
{
 char c;
 std::string code;
 bool operator == (char cmp);
 bool operator == (const std::string& s);
};
THalfNode * CreateHalfMan(std::istream &ins);
std::vector<THalfNode *>::iterator GetMinHalf(std::vector<THalfNode *>& halfNodes);
void CreateHalfTable(THalfNode *root, std::vector<THalfTab>& halfTab, std::string code);
void EncodeFile(std::istream& inf, std::ostream& ouf, std::vector<THalfTab>& halfTab); 
std::string GetCode(std::vector<THalfTab>& halfTab, char c);
void DecodeFile(std::istream& halfFileI, std::ostream& onf, std::vector<THalfTab>& halfTab);
char GetChar(std::vector<THalfTab>& halfTab, const std::string& s);
unsigned char bitone[8] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};
unsigned char bitzero[8] = {0xFE, 0xFD, 0xFB, 0xF7, 0xEF, 0xDF, 0xBF, 0x7F};
///////////////////

bool THalfTab::operator == (char cmp)
{
 return this->c == cmp;
}
bool THalfTab::operator == (const std::string& s)
{
 return this->code == s;
}
THalfNode::THalfNode()
:c(0), left(NULL), right(NULL), weight(1)
{}
THalfNode::FreeTree(THalfNode *root)
{
 if (root)
 {
   FreeTree(root->left);
   FreeTree(root->right);
   delete root;
 }
}
THalfNode::DisplayTree(THalfNode *root, int ident, std::ostream& ostrm)
{
 if (root)
 {
   DisplayTree(root->left, ident + 1, ostrm);
   int i;
   for(i = 0; i < ident; ++i)
    ostrm << "\t";
   ostrm << root->c << " * " << root->weight << "\n";
   DisplayTree(root->right, ident + 1, ostrm);
 }
}
std::string GetCode(std::vector<THalfTab>& halfTab, char c)
{
 std::vector<THalfTab>::iterator it;
 it = std::find(halfTab.begin(), halfTab.end(), c);
 if (it != halfTab.end())
   return it->code;
 else
   return "";
}
int main()
{
 std::ifstream inf("hafman.cpp", std::ios_base::binary);
 std::ofstream log("log.txt");
 std::vector<THalfTab> halfTab;
 std::ofstream halfFileO("halfFile", std::ios_base::binary);
 std::ifstream halfFileI;
 std::ofstream onf("halfman.txt", std::ios_base::binary);
 THalfNode *root = CreateHalfMan(inf); 
 THalfNode::DisplayTree(root, 0, log);
 CreateHalfTable(root, halfTab, "");
 int i;
 for(i = 0; i < halfTab.size(); ++i)
   std::cout << i << "\t" << halfTab[i].c << "\t" << halfTab[i].code << "\n";
 THalfNode::FreeTree(root);
 inf.close();
 std::ifstream inf2("hafman.cpp", std::ios_base::binary);
 EncodeFile(inf2, halfFileO, halfTab);
 halfFileO.close();
 halfFileI.open("halfFile", std::ios_base::binary);
 DecodeFile(halfFileI, onf, halfTab);
}
THalfNode * CreateHalfMan(std::istream &ins)
{
 if (!ins.good())
   return NULL;
 //Get all the nodes

 std::vector<THalfNode *> halfNodes;
 std::vector<THalfNode *>::iterator halfIt;
 THalfNode *p = new THalfNode;
 p->weight = 1;
 ins.read(&(p->c), 1);
 while(ins.good())
 {
   for(halfIt = halfNodes.begin(); halfIt != halfNodes.end(); ++halfIt)
    if ((*halfIt)->c == p->c)
     break;
   if (halfIt == halfNodes.end())
    halfNodes.push_back(p);
   else
   {
    ++((*halfIt)->weight);
    delete p;
   }
   p = new THalfNode;
   p->weight = 1;
   ins.read(&(p->c), 1);
 }
 //Create HalfMan

 std::vector<THalfNode *>::iterator min1, min2;
 while(halfNodes.size() > 1)
 {
   THalfNode *n = new THalfNode;
   n->c = 4;
  
   min1 = GetMinHalf(halfNodes);
   n->weight = (*min1)->weight;
   n->left = *min1;
   halfNodes.erase(min1, min1 + 1);
   min2 = GetMinHalf(halfNodes);
   n->weight += (*min2)->weight;
   n->right = *min2;  
   halfNodes.erase(min2, min2 + 1);
   halfNodes.push_back(n);
 }
 return *halfNodes.begin();
}
std::vector<THalfNode *>::iterator GetMinHalf(std::vector<THalfNode *>& halfNodes)
{
 std::vector<THalfNode *>::iterator halfIt, halfMin = halfNodes.begin();
 for(halfIt = halfNodes.begin(); halfIt != halfNodes.end(); ++halfIt)
 {
   if ((*halfIt)->weight < (*halfMin)->weight)
    halfMin = halfIt;
 }
 return halfMin;
}
void CreateHalfTable(THalfNode *root, std::vector<THalfTab>& halfTab, std::string code)
{
 THalfTab ht;
 if (root->left != NULL)
   CreateHalfTable(root->left, halfTab, code + "0");
 if (root->right != NULL)
   CreateHalfTable(root->right, halfTab, code + "1");
 if (root->left == NULL && root->right == NULL)//Leave node

 {
   ht.c = root->c;
   ht.code = code;
   halfTab.push_back(ht);
 }
}
void EncodeFile(std::istream& inf, std::ostream& ouf, std::vector<THalfTab>& halfTab)
{
 if (!inf.good())
   return;
 if (!ouf.good())
   return;
 char c;
 unsigned char buf = 0;
 int p = 0;
 std::string code;
 inf.read(&(c), 1);
 while(inf.good())
 {
   code = GetCode(halfTab, c);
   int i;
   for(i = 0; i < code.size(); ++i)
   {
    if (p == 8)
    {
     p = 0;
     ouf.write((char *)&buf, 1);
     buf = 0;
    }
    if (code[i] == '1')
     buf = buf | bitone[p]; 
    else if (code[i] == '0')
     buf = buf & bitzero[p];
    else
     return;
    ++p;
   }
   inf.read(&(c), 1);
 }
 ouf.write((char *)&buf, 1);//如果buf没有填满，那么存在问题

}
void DecodeFile(std::istream& halfFileI, std::ostream& onf, std::vector<THalfTab>& halfTab)
{
 unsigned char buf;
 char c;
 std::string code;
 int i;
 halfFileI.read((char *)&buf, 1);
 while(halfFileI.good())
 {
   for(i = 0; i < 8; ++i)
   {
    if ((buf & bitone[i]) > 0)
     code = code + "1";
    else
     code = code + "0";
    c = GetChar(halfTab, code);
    if (c != 0)
    {
     code = "";
     onf.write(&c, 1);
    }
   }
   halfFileI.read((char *)&buf, 1);
 }
}
char GetChar(std::vector<THalfTab>& halfTab, const std::string& s)
{
 std::vector<THalfTab>::iterator it;
 it = std::find(halfTab.begin(), halfTab.end(), s);
 if (it != halfTab.end())
   return it->c;
 else
   return 0;
}