//   作者 华北科技学院 信息与计算科学

//   时间 2011-6-15

//Lm.cpp

#include "MyHuffmanCoding.h" 

int main() 

{

    int sel=1;

    HuffmanCoding h; 

    while(sel)

    {

        cout<<"********哈夫曼树实现文件压缩*********"<     cout<<"## 1.文件压缩; ##"<     cout<<"## 2.文件解压; ##"<     cout<<"## 0.退出. ##"<     cout<<"********哈夫曼树实现文件压缩*********"<     cout<<"请按键选择操作:";

        cin>>sel;

        switch(sel)

        {

        case 1:h.code();break;

        case 2:h.decode();break;

        case 0:break;

        }

    }

    system("PAUSE"); 

    return 0; 

}

//MyHuffman.h 构建哈夫曼树

#ifndef HUFFTREE_H 

#define HUFFTREE_H 

class SAList;//由于HuffTree类要用到SAList类，此处即为虚定义

class HuffTreeNode; //由于HuffTree类要用到HuffTreeNode类，此处即为虚定义 

class HuffTree //哈夫曼树的声明

{ 

public: 

    HuffTreeNode *subRoot; 

    HuffTree(); 

    HuffTree(unsigned char val, unsigned long int freq); 

    HuffTree(HuffTree* l, HuffTree* r); 

    HuffTree* buildHuffTree(SAList *sal, SAList *copy ); 

}; 

class SAList //有序表类的声明

{

    int fence; 

    int maxSize; 

    int listSize; 

public: 

    SAList(int size = 0); 

    ~SAList(); 

    HuffTree* *listArray; 

    void setStart(); 

    void next(); 

    int getLength(); 

    bool insert(HuffTree* item); //排序插入 

    HuffTree* remove(); 

    bool lessThan(HuffTree* x, HuffTree* y); 

}; 

class HuffTreeNode //哈弗曼树结点的类声明 

{ 

public: 

    unsigned char value; 

    unsigned long int weight; 

    unsigned int leftOrRight; //若为左儿子，则值为0，若为右儿子，则值为1 

    HuffTreeNode *parent; 

    HuffTreeNode *leftChild; 

    HuffTreeNode *rightChild; 

    bool isLeaf; 

};  

#endif

//MyHuffmancoding.h

#ifndef HUFFMANCODING_H 

#define HUFFMANCODING_H 

#include

#include

#include "MyHuffman.h" 

struct Link //栈结构 

{ 

    unsigned int element; 

    Link *next; 

    Link(const unsigned int &elemval, Link *nextval = NULL); 

    Link(Link *nextval = NULL ); 

}; 

struct LStack 

{ 

    Link* top; 

    int size; 

    LStack() { size = 0; top = NULL; } 

    ~LStack() { clear(); } 

    void clear(); 

    bool push(const unsigned int &item); 

    bool pop(unsigned int &it); 

};  

struct Buffer //缓冲区 

{ 

    unsigned char byte; //表示字节，每个字节由8个位组成 

    unsigned int bits; //表示位（比特） 

    void clear(); //清空缓存区 

}; 

struct Save //临时保存叶子结点的数域 

{ 

    unsigned char ch; 

    unsigned long int val; 

}; 

class HuffmanCoding 

{ 

private: 

    SAList *list, *copy;//有序表 

    HuffTree* tree; //哈夫曼树 

    Buffer buffer; //缓存区 

    LStack *stack; //栈 

    Save save; //临时保存叶子结点的数域 

    FILE *sourceFile; //表示源文件 

    FILE *targetFile; //表示目标文件 

    unsigned long int total; //表示要进行编码的文件的总字节数 

    unsigned long int ch[257]; //表示可以编码的所有字符，其下标表示对应的字符，对应下标的数组值表示该字符的权值 

    unsigned int numOfLeaf; //表示需要建立叶子结点的个数 

public: 

    void code(); //对文件内容进行编码 

    void decode(); //对文件内容进行译码 

    void buildSAList(); //建立有序表,并将建立有序表的信息保存到目标文件 

    void write(unsigned int c); //利用建立的缓存，向目标文件中输出字符 

    void exportSAList(); //压缩文件中导出有序表 

    unsigned int read(); //利用建立的缓存，从压缩文件提取字符 

}; 

#endif

//MyHuffman.cpp 哈夫曼树的实现 

#include

#include "MyHuffman.h"  

SAList::SAList(int size) //有序表类的声明

{

    maxSize = size; 

    listSize = fence = 0; 

    listArray = new HuffTree*[maxSize]; 

} 

SAList::~SAList()

{delete []listArray;} 

void SAList::setStart() 

{fence = 0;} 

void SAList::next() 

{ 

if(fence <= listSize)

        ++fence; 

} 

int SAList::getLength() 

{return listSize;}  

bool SAList::insert(HuffTree* item)//排序插入 

{ 

    if (listSize == maxSize) 

        return false; 

    HuffTree *current; 

for (fence=0; fence    { 

        current = listArray[fence]; 

        if(!lessThan(current, item)) 

           break; 

    } 

for (int i=listSize; i>fence; i--)

    { 

        listArray[i] = listArray[i-1]; 

    } 

    listArray[fence] = item; 

    ++listSize; 

    return true; 

} 

HuffTree* SAList::remove() 

{ 

    if(listSize == fence) 

    { 

       return NULL; 

    } 

    HuffTree *temp = listArray[fence]; 

for(int i=fence; i    { 

       listArray[i] = listArray[i+1]; 

    } 

    --listSize; 

    return temp; 

} 

bool SAList::lessThan(HuffTree* x, HuffTree* y) 

{ 

return x->subRoot->weight < y->subRoot->weight;

} 

HuffTree::HuffTree() //哈夫曼树的实现 

{ 

    subRoot = new HuffTreeNode; 

subRoot->weight = 0;

} 

HuffTree::HuffTree(unsigned char val, unsigned long int freq) 

{ 

    subRoot = new HuffTreeNode; 

subRoot->value = val;

subRoot->weight = freq;

subRoot->isLeaf = true;

} 

HuffTree::HuffTree(HuffTree* l, HuffTree* r) 

{ 

    subRoot = new HuffTreeNode; 

subRoot->leftChild = l->subRoot;

subRoot->rightChild = r->subRoot;

subRoot->leftChild->parent = subRoot->rightChild->parent = subRoot;

subRoot->weight = l->subRoot->weight + r->subRoot->weight;

subRoot->isLeaf = false;

} 

HuffTree* HuffTree::buildHuffTree(SAList *sal, SAList *copy) 

{ 

    HuffTree *temp1, *temp2, *temp3; 

    temp1 = temp2 = temp3 = new HuffTree; 

for(int i=sal->getLength(); i>1; i--)

    { 

sal->setStart();

temp1 = sal->remove();

temp2 = sal->remove();

temp1->subRoot->leftOrRight = 0;

temp2->subRoot->leftOrRight = 1;

       temp3 = new HuffTree(temp1, temp2); 

if(temp1->subRoot->isLeaf)

copy->insert(temp1);

if(temp2->subRoot->isLeaf)

copy->insert(temp2);

sal->insert(temp3);

    } 

    return temp3; 

}

//MyHuffmancoding.cpp 哈夫曼结点的实现

#include

#include

#include "MyHuffmanCoding.h" 

Link::Link(const unsigned int &elemval, Link *nextval) 

{

    element = elemval; 

    next = nextval; 

} 

Link::Link( Link *nextval) 

{ 

    next = nextval; 

} 

void LStack::clear() 

{ 

    while(top != NULL)

    { 

       Link *temp = top; 

top = top->next;

       delete temp; 

    } 

    size = 0; 

} 

bool LStack::push(const unsigned int &item) 

{ 

    top = new Link(item, top); 

    size++; 

    return true; 

} 

bool LStack::pop(unsigned int &it) 

{ 

    if(size == 0) 

        return false; 

it = top->element;

    Link *temp = top; 

top = top->next;

    size--; 

    delete temp; 

    return true; 

} 

void Buffer::clear() 

{ 

    bits = 0; 

    byte = 0; 

} 

void HuffmanCoding::code() 

{ 

    char *sourceFileName = new char[]; 

    char *targetFileName = new char[]; 

    total = 0; 

    numOfLeaf = 0; 

cout << "请输入源文件的文件名："; 

cin >> sourceFileName;

    sourceFile = fopen(sourceFileName, "rb"); 

    while (sourceFile == NULL) 

    { //判断源文件是否存在，不存在则要求用户重新输入 

cout << "您输入的源文件不存在！" << "\\n请重新输入："; 

cin >> sourceFileName;

       sourceFile = fopen(sourceFileName, "rb"); 

    } 

    fgetc(sourceFile);  

    if (feof(sourceFile)) 

    { //判断文件内容是否为空，若为空则退出程序

cout << "文件内容为空！"; 

       system("PAUSE"); 

       exit(-1); 

    } 

cout << "请输入目标文件的文件名："; 

cin >> targetFileName;

    targetFile = fopen(targetFileName, "wb"); 

    while (targetFile == NULL) 

    { //判断目标文件是否可以建立 

cout << "目标文件无法建立！" << "\\n请重新输入："; 

cin >> targetFileName;

       targetFile = fopen(targetFileName, "wb"); 

    } 

cout << "文件压缩中...\n\\n"; 

    buildSAList(); //建立有序表，并保存编码信息 

tree = tree->buildHuffTree(list, copy); //利用已建立的有序表，建立哈夫曼树 

    //开始编码，并将编码后的内容输出到目标文件 

    rewind(sourceFile); //将文件指针重新指向文件内容起始处 

    unsigned char tempChar = fgetc(sourceFile); //取文件内容的下一个字符 

    unsigned int tempInt; 

    HuffTreeNode *tempTreeNode; 

    stack = new LStack(); 

    buffer.clear(); //清空缓存区 

    //当文件内容全部被扫描完，循环结束 

    while (!feof(sourceFile)) 

    { //搜索匹配tempChar的叶子的值 

for (int i=0; i< copy->getLength(); i++)

       { 

if (tempChar == copy->listArray[i]->subRoot->value)

           { 

stack->clear();

tempTreeNode = copy->listArray[i]->subRoot;

while (tempTreeNode != tree->subRoot)

               { 

stack->push(tempTreeNode->leftOrRight);

tempTreeNode = tempTreeNode->parent;

               }//end while 

while (stack->pop(tempInt))

               { 

                   write(tempInt); 

               } 

               break; 

           }//end if 

       }//end for 

       tempChar = fgetc(sourceFile); 

    }//end while 

if (buffer.bits > 0)

    { //如果缓存区还有剩余的位，则添加0到缓存区，直到够满8个位建立个字符，并向目标文件写入该字符 

for (unsigned int i=buffer.bits; i<8; i++)

          write(0); 

    } 

cout << "文件压缩完毕" <    delete stack; 

    delete list; 

    fclose(sourceFile); //关闭文件流 

    fclose(targetFile); 

} 

void HuffmanCoding::decode() 

{ 

    char *sourceFileName = new char[]; 

    char *targetFileName = new char[]; 

    total = 0; 

    numOfLeaf = 0; 

cout << "\\n请输入压缩文件的文件名："; 

cin >> sourceFileName;

    sourceFile = fopen(sourceFileName, "rb");  

    while (sourceFile == NULL) 

    { //判断源文件是否存在，不存在则要求用户重新输入

cout << "您输入的压缩文件不存在！" << "\\n请重新输入："; 

cin >> sourceFileName;

       sourceFile = fopen(sourceFileName, "rb"); 

    } 

    fgetc(sourceFile);  

    if (feof(sourceFile)) 

    { //判断文件内容是否为空，若为空则退出程序

cout << "文件内容为空！"; 

       system("PAUSE"); 

       exit(-1); 

    } 

cout << "请输入目标文件的文件名："; 

cin >> targetFileName;

    targetFile = fopen(targetFileName, "wb");  

    while (targetFile == NULL) 

    { //判断目标文件是否可以建立

cout << "目标文件无法建立！" << "\\n请重新输入："; 

cin >> targetFileName;

       targetFile = fopen(targetFileName, "wb"); 

    } 

cout << "文件解压中...\n\\n"; 

    rewind(sourceFile); //将源文件指针重新指向文件起始处 

    exportSAList(); //导出叶子结点有序表 

tree = tree->buildHuffTree(list, copy); //利用已建立的有序表，建立哈夫曼树 ,译码开始 

    buffer.clear(); //清空缓存区 

    unsigned int tempInt; 

    HuffTreeNode *tempTreeNode; 

while (total > 0)

    { 

tempTreeNode = tree->subRoot;

while(!tempTreeNode->isLeaf)

        { 

            tempInt = read(); 

            if(tempInt == 0) 

            { 

tempTreeNode = tempTreeNode->leftChild;

            } 

            else 

            { 

tempTreeNode = tempTreeNode->rightChild;

            } 

        } 

fputc(tempTreeNode->value, targetFile);

        total--; 

    } 

cout << "文件解压完毕" << endl<    delete list; 

    fclose(sourceFile); 

    fclose(targetFile); 

} 

//按字符扫描源文件，统计源文件出现的字符及其权值 

//利用统计出的字符和和其权值建立叶子结点有序表，并将统计出的信息保存到目标文件 

void HuffmanCoding::buildSAList() 

{ 

    unsigned char tempChar; 

    HuffTree *temp; 

for (int i=0; i<257; i++) //初始化储存字符的数组 

      ch[i] = 0; 

    rewind(sourceFile); //将文件指针重新指向文件内容起始处 

    tempChar = fgetc(sourceFile); //取文件内容的下一个字符 

    while (!feof(sourceFile)) 

    { //当文件内容全部被扫描完，循环结束 

       ++ch[tempChar]; 

       ++total; 

       tempChar = fgetc(sourceFile); 

    } 

for(int j=0; j<257; j++) //计算应该建立的叶子结点总数 

    { 

if(ch[j] > 0)

         numOfLeaf++; 

    } 

    //将源文件的字符总数及叶子结点总数保存到目标文件 

    fwrite(&total, sizeof(unsigned long int), 1, targetFile); 

    fwrite(&numOfLeaf, sizeof(unsigned int), 1, targetFile);  

    list = new SAList(numOfLeaf); //建立叶子结点有序表

    copy = new SAList(numOfLeaf); 

    //依次扫描ch，将权值不为0的字符插入到叶子结点有序表中 

    //并将此字符及其权值保存到目标文件 

for(int k=0; k<257; k++)

    { 

if(ch[k] > 0)

       { 

          temp = new HuffTree(k, ch[k]); 

list->insert(temp);

          save.ch = k; 

          save.val = ch[k]; 

          fwrite(&save, sizeof(save), 1, targetFile); 

       } 

    } 

} 

void HuffmanCoding::write(unsigned int c) //利用建立的缓存，向目标文件中输出字符 

{ 

    ++buffer.bits; 

buffer.byte = (buffer.byte << 1) + c; //将byte左移一位，并在末位加上c 

    if (buffer.bits == 8) 

    { //如果byte的8个位都被写满，则向目标文件输出byte，并清空缓存区 

       fputc(buffer.byte, targetFile); 

       buffer.clear(); 

    } 

} 

void HuffmanCoding::exportSAList() //从压缩文件中导出叶子结点有序表 

{ 

    HuffTree *temp; 

    fread(&total, sizeof(unsigned long int), 1, sourceFile); 

    fread(&numOfLeaf, sizeof(unsigned int), 1, sourceFile); 

    list = new SAList(numOfLeaf); 

for(int i=0; i    { 

       fread(&save, sizeof(save), 1, sourceFile); 

       temp = new HuffTree(save.ch, save.val); 

list->insert(temp);

    } 

}  

unsigned int HuffmanCoding::read() //从压缩文件中读取一个比特

{ 

    if(buffer.bits == 0) 

    { 

        buffer.bits = 8; 

        buffer.byte = fgetc(sourceFile); 

    } 

if(buffer.byte & (1<<(buffer.bits-1)))

    { 

        buffer.bits--; 

        return 1; 

    } 

    else

    { 

        buffer.bits--; 

        return 0; 

    } 

}下载本文