哈夫曼树算法的原理与实现

本来这篇文章应该在5月的时候写完的,但是由于这几个月都有些事情断断续续地打断我写文章。现在废话不多说直接进入主题,哈夫曼树其实并不是想象中那么难,如果是只看它的介绍的话你会觉得完全不知道这是一颗怎样的树。它只不过是队列和树的结合使用罢了,大概就是先按权重排序,然后压入队列,再两两抽入结合成新的树,再压入队列。这里的列队要优先列队才行,因为只有优先列队才满足先进先出的特点,这样我们就能很方便地每次取出权重最小的2个元素。只要我们不断地重复这个过程,就能实现一颗哈夫曼树。

可能看到这里,你会发现我并没有说明哈夫曼树的作用。那什么是哈夫曼树呢?哈夫曼树就是一颗以权重排列树结点的树,这样的树还叫最优二叉树。从它的第二个名称“最优二叉树”就能知道,这种树的效率是最优的。因为我们要实现的是权重高的结点可以用最短的路径访问,权重低的结点会被放在最下层的地方,所以这样可以大大地提升访问的效率。

主要原理就是:

下面是实现的代码:

[友情提示]

建议先看完上面的实现原理,再看下面的实现代码。其实看懂了原理就能写代码,不需要看我坑爹逻辑写的代码。如果你看懂了原理,但真的不会写代码,请往下看。

Base.h 算法的通用头文件,这个文件主要声明列队和树所要使用的结点结构体。因为考虑通用性的问题,所以我用一个结构体做了两种数据结构都通用的结点。

#pragma once
#ifndef _Base_H_
#define _Base_H_

struct Node{
    int Index;
    char Data;
    Node *pNext;

    Node *pLeft;
    Node *pRight;

};

#endif

PriorityQueue.h 优先列队的头文件,我写的这个列队算法除了基本的操作之外,还有一个比较基础的排序算法(过去的文章有说到排序算法的实现)。

#pragma once
#ifndef _PriorityQueue_H_
#define _PriorityQueue_H_

#include "Base.h"

class PriorityQueue{
public:
    PriorityQueue() : pHead(nullptr){}
    ~PriorityQueue();

    void Add(Node *pTmp);
    Node* Delete();
    void Show();
    void Sort();
    bool IsLast();

private:
    Node *pHead;
};

#endif

PriorityQueue.cpp 优先列队的源文件

#include <iostream>
#include "PriorityQueue.h"

void PriorityQueue::Add(Node *pTmp){
    Node *pNew = new Node, *p = this->pHead;
    pNew->Index = pTmp->Index;
    pNew->Data = pTmp->Data;
    pNew->pNext = pTmp->pNext;

    pNew->pLeft = pTmp->pLeft;
    pNew->pRight = pTmp->pRight;

    if(this->pHead == nullptr){
        this->pHead = pNew;
    }else{
        if(pNew->pLeft != nullptr || pNew->pRight != nullptr){    //part1 树元素
            if(pNew->Index < p->Index){
                pNew->pNext = p;
                p = pNew;
            }else{
                while(p){
                    if(p->pNext != nullptr){
                        if(pNew->Index < p->pNext->Index){
                            pNew->pNext = p->pNext;
                            p->pNext = pNew;
                            break;
                        }
                    }else{
                        p->pNext = pNew;
                        break;
                    }

                    p = p->pNext;
                }

            }

        }else{  //part2 只是一个普通的队列元素
            while(p){
                if(p->Data == pNew->Data){
                    p->Index++;
                    break;
                }

                if(p->pNext == nullptr){
                    p->pNext = pNew;
                    break;
                }

                p = p->pNext;
            }

        }
    }
}

Node* PriorityQueue::Delete(){
    if(this->pHead != nullptr){
        Node *p = this->pHead->pNext, *tmp = new Node;
        tmp->Index = this->pHead->Index;
        tmp->Data = this->pHead->Data;
        tmp->pNext = nullptr;

        tmp->pLeft = this->pHead->pLeft;
        tmp->pRight = this->pHead->pRight;

        delete this->pHead;
        this->pHead = nullptr;

        this->pHead = p;
        return tmp;

    }else{
        return nullptr;
    }

}

void PriorityQueue::Show(){
    Node *p = this->pHead;

    while(p){
        std::cout << p << "\t" << p->Index << "\t" << p->Data << "\t" << p->pNext << std::endl;

        p = p->pNext;
    }

    std::cout << std::endl;
}

void PriorityQueue::Sort(){
    if(this->pHead != nullptr){
        Node *i = this->pHead, *p = nullptr;
        
        while(i){
            p = i;

            while(p){
                if(p->Index < i->Index){
                    Node *pTmp = new Node;
                    pTmp->Data = i->Data;
                    pTmp->Index = i->Index;
                    
                    i->Data = p->Data;
                    i->Index = p->Index;

                    p->Data = pTmp->Data;
                    p->Index = pTmp->Index;
                }

                p = p->pNext;
            }

            i = i->pNext;
        }

    }
}

bool PriorityQueue::IsLast(){
    if(this->pHead != nullptr){
        return false;
    }else{
        return true;
    }
}

PriorityQueue::~PriorityQueue(){
    delete this->pHead;
    this->pHead = nullptr;
}

HuffmanTree.h 赫夫曼树算法的头文件

#pragma once
#ifndef _HuffmanTree_H_
#define _HuffmanTree_H_

#include "Base.h"
#include "PriorityQueue.h"

class HuffmanTree{
public:
    HuffmanTree(char *str);

    void QueueAction();
    void TreeAction();

    void ShowTree();

private:
    void createTree(Node *pTree);
    void showTree(Node *pTree);

private:
    char *str;
    PriorityQueue queue;
    Node *pTree;

};

#endif

HuffmanTree.cpp 赫夫曼树算法的头文件

#include <iostream>
#include "HuffmanTree.h"

HuffmanTree::HuffmanTree(char *str) : pTree(nullptr){
    this->str = str;
}

void HuffmanTree::QueueAction(){
    int i = 0;

    while(this->str[i] != '\0'){
        int num = this->str[i];

        if(num != 0){
            Node *pTmp = new Node;
            pTmp->Index = 1;
            pTmp->Data = num;
            pTmp->pNext = pTmp->pLeft = pTmp->pRight = nullptr;

            this->queue.Add(pTmp);
        }
        
        i++;
    }

    this->queue.Show();
    this->queue.Sort();
    this->queue.Show();
}

void HuffmanTree::TreeAction(){
    while(!this->queue.IsLast()){
        this->createTree(this->pTree);
    }
}

void HuffmanTree::ShowTree(){
    this->showTree(this->pTree);
}

//////////////////////////////////////////////////////////////////////////
// 私有方法
//////////////////////////////////////////////////////////////////////////

void HuffmanTree::showTree(Node *pTree){
    if(pTree){
        std::cout << pTree << "\t" << pTree->Index << "\t" << pTree->Data << "\t" << pTree->pLeft << "\t" << pTree->pRight << std::endl;
        this->showTree(pTree->pLeft);
        this->showTree(pTree->pRight);
    }
}

void HuffmanTree::createTree(Node *pTree){
    Node *pLeft = this->queue.Delete();
    Node *pRight = this->queue.Delete();

    if(pLeft != nullptr && pRight != nullptr){
        Node *pNew = new Node;
        pNew->Index = pLeft->Index + pRight->Index;
        pNew->pLeft = pLeft;
        pNew->pRight = pRight;
        pNew->pNext = nullptr;

        this->queue.Add(pNew);
    }else{
        this->pTree = pLeft;
    }
}

Main.cpp 程序的主文件

#include <iostream>
#include "HuffmanTree.h"

using namespace std;

int main(){
    //HuffmanTree tree("f88999EEEEAAAAAbbbbbb333333333eeeeeeeeeee");
    HuffmanTree tree("e89AbEb3ee33b33e99EAf8eAAbee333eEEAe3bbee");  //打乱顺序的元素
    tree.QueueAction();
    tree.TreeAction();
    tree.ShowTree();

    system("pause");
    return 0;
}

这坑终于填完了,这月还会更新文章。

标签:算法, 原理, 实现, , 哈夫曼

该文章由 Shiqi Qiu 原创并发布在 被遗忘的曙光 技术博客

转载请标明来源:http://blog.fdawn.com/CPP/27.html

仅有 1 条评论

  1. Clara

    I enjoy you because of each of your hard work on this site. My daughter delights in going through internet research and it is easy to understand why. A lot of people know all about the lively manner you deliver reliable tips and tricks via your web site and as well boost from the others on this issue then our child is always becoming educated so much. Have fun with the rest of the new year. You’re the one performing a fabulous job.

添加新评论