C++数据结构与算法——哈希表实现（链式法）

• • 文件结构
  • 字典类
  • • 概念
    • 代码
  • 哈希类
  • • 概念
    • 代码
  • 有序链表
  • • 概念
    • 代码
  • 哈希表实现
  • • 概念
    • 代码
  • 测试主函数
  • • 代码
    • 输出

//dictionary.h
template
class dictionary
{
public:
    virtual ~dictionary(){}//虚析构函数
    //纯虚函数
    virtual bool empty() const = 0;
    virtual int size() const = 0;
    virtual std::pair* find(const K& theKey)const = 0;
    virtual void erase(const K& theKey) = 0;
    virtual void insert(const std::pair& thePair) = 0;
};

//hash.h
#pragma once
#include 
//hash类
template class hash;

template<>
class hash
{
public:
    std::size_t operator() (const std::string theKey) const{
        unsigned long hashValue = 0;
        int length = (int)theKey.length();
        for(int i = 0; i < length; i++){
            hashValue = hashValue * 5 + theKey.at(i);
        }
        return std::size_t(hashValue);
    }
};

template<>
class hash
{
public:
    std::size_t operator() (const int theKey) const{
        return std::size_t(theKey);
    }
};

template<>
class hash
{
public:
    std::size_t operator() (const long theKey) const{
        return std::size_t(theKey);
    }
};

//sortedChain.h
#pragma once
#include 

//pairNode
template
struct pairNode{
    std::pair element;
    pairNode* next;
    pairNode(const std::pair& thePair)
        :element(thePair) {}
    pairNode(const std::pair& thePair, pairNode* theNext)
        :element(thePair) { this->next = theNext; }
};

//sortedChain类
template
class sortedChain
{
private:
    pairNode* firstNode;
    int dSize;
public:
    sortedChain();
    ~sortedChain();
    bool isEmpty() const;
    int size() const;
    std::pair* find(const K& theKey) const;
    void insert(const std::pair& thePair);
    void erase(const K& theKey);
    void printChain(std::ostream &out) const;
};

template
sortedChain::sortedChain(){
    this->firstNode = nullptr;
    this->dSize = 0;
}

template
sortedChain::~sortedChain(){
    pairNode* tempNode;
    while(this->firstNode){
        tempNode = this->firstNode->next;
        delete this->firstNode;
        this->firstNode = tempNode;
    }
}

template
bool sortedChain::isEmpty() const{
    return this->dSize == 0;
};

template
int sortedChain::size() const{
    return this->dSize;
};

template
std::pair* sortedChain::find(const K& theKey) const{
    pairNode* tempNode = firstNode;

    //遍历
    while((tempNode != nullptr) 
        && (tempNode->element.first != theKey)){
            tempNode = tempNode->next;
    }

    //找到了
    if((tempNode != nullptr) 
        && (tempNode->element.first == theKey)){
            return &tempNode->element;
    }

    //没找到
    return nullptr;
};

template
void sortedChain::insert(const std::pair& thePair){
    pairNode* afterInsertNode = this->firstNode;
    pairNode* beforeInsertNode = nullptr;
    //遍历
    while((afterInsertNode != nullptr) 
        && (afterInsertNode->element.first < thePair.first)){
            beforeInsertNode = afterInsertNode;
            afterInsertNode = afterInsertNode->next;
    }
    //如果找到键已经存在的pairNode
    if((afterInsertNode != nullptr)
        && (afterInsertNode->element.first == thePair.first)){
            afterInsertNode->element.second = thePair.second;
            return;
    }
    //如果键还不存在，插入新节点
    pairNode* insertNode = new pairNode(thePair, afterInsertNode);
    if(beforeInsertNode == nullptr){//如果在头节点插入
        this->firstNode = insertNode;
    }else{
        beforeInsertNode->next = insertNode;
    }
    this->dSize++;
};

template
void sortedChain::erase(const K& theKey){
    pairNode* eraseNode = this->firstNode;
    pairNode* beforeEraseNode = nullptr;

    //遍历
    while((eraseNode != nullptr)
        &&(eraseNode->element.first < theKey)){
            beforeEraseNode = eraseNode;
            eraseNode = eraseNode->next;
    }
    //找到了
    if((eraseNode != nullptr)
        && (eraseNode->element.first == theKey)){
        //如果删除的是头节点
        if(beforeEraseNode == nullptr){
            this->firstNode = eraseNode->next;
        }else{
            beforeEraseNode->next = eraseNode->next;
        }
        delete eraseNode;
        this->dSize--;
    }
};

template
void sortedChain::printChain(std::ostream& out) const{
    for(pairNode* tempNode = this->firstNode; tempNode != nullptr; tempNode = tempNode->next){
       	out << "key: " << tempNode->element.first;
       	out << ", value: " << tempNode->element.second;
       	out << "  ";
    }
    out << std::endl;
};

template
std::ostream& operator<<(std::ostream& out, const sortedChain& theChain){
    theChain.printChain(out);
    return out;
}

//hashChains.h
#pragma once
#include "dictionary.h"
#include "hash.h"
#include "sortedChain.h"

template
class hashChains : public dictionary
{
private:
    sortedChain* table;
    hash myHash;//将关键字映射为一个整数
    int dSize;//哈希表大小
    int divisor = 11;//哈希函数的除数

public:
    hashChains(int theDivisor);
    ~hashChains();
    bool empty() const override;
    int size() const override;
    std::pair* find(const K& theKey)const override;
    void erase(const K& theKey) override;
    void insert(const std::pair& thePair) override;
    void printHashChain(std::ostream& out) const;
};

template
hashChains::hashChains(int theDivisor){
    this->divisor = theDivisor;
    this->dSize = 0;
    this->table = new sortedChain[theDivisor];
}

template
hashChains::~hashChains(){
    if(this->table){
        delete[] this->table;
    }
}

template
bool hashChains::empty() const{
    return (this->dSize == 0);
}

template
int hashChains::size() const{
    return this->dSize;
}

template
std::pair* hashChains::find(const K& theKey)const{
    int bucketIndex = myHash(theKey) % this->divisor;
    return this->table[bucketIndex].find(theKey);
}

template
void hashChains::erase(const K& theKey){
    int bucketIndex = myHash(theKey) % this->divisor;
    return this->table[bucketIndex].erase(theKey);
}

template
void hashChains::insert(const std::pair& thePair){
    int bucketIndex = myHash(thePair.first) % this->divisor;
    //如果新增
    if(!this->table[bucketIndex].find(thePair.first)){
        this->dSize++;
    }
    this->table[bucketIndex].insert(thePair);
}

template
void hashChains::printHashChain(std::ostream& out) const{
    for(int i = 0; i < this->divisor; ++i){
        if(this->table[i].isEmpty()){
            std::cout << "NULL" << std::endl;
        }else{
            std::cout << this->table[i];
        }
    }
}

template
std::ostream& operator<<(std::ostream& out, const hashChains& theHashChains){
    theHashChains.printHashChain(out);
    return out;
}

//main.cpp
#include 
#include 
#include "hashChains.h"

using namespace std;
int main(){
    hashChains myHashChains1(11);
    myHashChains1.insert(pair("abc", 2));
    myHashChains1.insert(pair("def", 3));
    myHashChains1.insert(pair("ghi", 4));
    myHashChains1.insert(pair("jkl", 5));
    myHashChains1.insert(pair("mno", 6));
    myHashChains1.insert(pair("pqrs", 7));
    myHashChains1.insert(pair("tuv", 8));
    myHashChains1.insert(pair("wxyz", 9));

    hashChains myHashChains2(11);
    myHashChains2.insert(pair(1, 1));
    myHashChains2.insert(pair(2, 2));
    myHashChains2.insert(pair(3, 3));
    myHashChains2.insert(pair(5, 5));
    myHashChains2.insert(pair(11, 11));
    myHashChains2.insert(pair(13, 13));
    myHashChains2.insert(pair(10, 10));

    cout << myHashChains1 << endl << endl;
    cout << myHashChains2 << endl;

    return 0;
}

一个sortedChain在同一行显示。