数据结构之链表散列实现

//二、链表解决溢出问题  
#include <iostream>  
#include<string>   
#include<fstream>  
using namespace std;  
  
template<class K, class E>  
class dictionary  
{  
public:  
    virtual ~dictionary() {}  
    virtual bool empty() const = 0;  
    // return true iff dictionary is empty  
    virtual int size() const = 0;  
    // return number of pairs in dictionary  
    virtual pair<const K, E>* find(const K&) const = 0;  
    // return pointer to matching pair  
    virtual void erase(const K&) = 0;  
    // remove matching pair  
    virtual void insert(const pair<const K, E>&) = 0;  
    // insert a (key, value) pair into the dictionary  
};  
  
template <class K, class E>  
struct pairNode  
{  
    typedef pair<const K, E> pairType;  
    pairType element;  
    pairNode<K, E> *next;  
  
    pairNode(const pairType& thePair) :element(thePair) {}  
    pairNode(const pairType& thePair, pairNode<K, E>* theNext)  
        :element(thePair) {  
        next = theNext;  
    }  
};  
  
template <class K> class Hash1;  
  
template<>  
class Hash1<string>  
{  
public:  
    size_t operator()(const string theKey) const  
    {// Convert theKey to a nonnegative integer.  
        unsigned long HashValue = 0;  
        int length = (int)theKey.length();  
        for (int i = 0; i < length; i++)  
            HashValue = 5 * HashValue + theKey.at(i);  
  
        return size_t(HashValue);  
    }  
};  
  
template<>  
class Hash1<int>  
{  
public:  
    size_t operator()(const int theKey) const  
    {  
        return size_t(theKey);  
    }  
};  
  
template<>  
class Hash1<long>  
{  
public:  
    size_t operator()(const long theKey) const  
    {  
        return size_t(theKey);  
    }  
};  
  
template<class K, class E>  
class sortedChain : public dictionary<K, E>  
{  
public:  
    sortedChain() { firstNode = NULL; cSize = 0; }  
    ~sortedChain();  
  
    bool empty() const { return cSize == 0; }  
    int size() const { return cSize; }  
    pair<const K, E>* find(const K&) const;  
    void erase(const K&);  
    void insert(const pair<const K, E>&);  
    void output(ostream& out) const;  
  
protected:  
    pairNode<K, E>* firstNode;  // pointer to first node in chain  
    int cSize;                 // number of elements in dictionary  
};  
  
template<class K, class E>  
sortedChain<K, E>::~sortedChain()  
{// Destructor.  Delete all nodes.  
    while (firstNode != NULL)  
    {// delete firstNode  
        pairNode<K, E>* nextNode = firstNode->next;  
        delete firstNode;  
        firstNode = nextNode;  
    }  
}  
  
template<class K, class E>  
pair<const K, E>* sortedChain<K, E>::find(const K& theKey) const  
{// Return pointer to matching pair.  
 // Return NULL if no matching pair.  
    pairNode<K, E>* currentNode = firstNode;  
  
    // search for match with theKey  
    while (currentNode != NULL &&  
        currentNode->element.first != theKey)  
    {  
        currentNode = currentNode->next;  
    }  
    // verify match  
    if (currentNode != NULL && currentNode->element.first == theKey)  
        // yes, found match  
    {  
        cout << size() << endl;  
        return ¤tNode->element;  
    }  
    // no match  
    else{  
        cout << "Not Found" << endl;  
        return NULL;  
    }  
}  
  
template<class K, class E>  
void sortedChain<K, E>::insert(const pair<const K, E>& thePair)  
{// Insert thePair into the dictionary. Overwrite existing  
 // pair, if any, with same key.  
    pairNode<K, E> *p = firstNode,  
        *tp = NULL; // tp trails p  
  
// move tp so that thePair can be inserted after tp  
    while (p != NULL && p->element.first < thePair.first)  
    {  
        tp = p;  
        p = p->next;  
    }  
  
    // check if there is a matching pair  
    if (p != NULL && p->element.first == thePair.first)  
    {// replace old value  
        cout << "Existed" << endl;  
        p->element.second = thePair.second;  
        return;  
    }  
  
    // no match, set up node for thePair  
    pairNode<K, E> *newNode = new pairNode<K, E>(thePair, p);  
  
    // insert newNode just after tp  
    if (tp == NULL) firstNode = newNode;  
    else tp->next = newNode;  
    cSize++;  
    return;  
}  
  
template<class K, class E>  
void sortedChain<K, E>::erase(const K& theKey)  
{// Delete the pair, if any, whose key equals theKey.  
    pairNode<K, E> *p = firstNode,  
        *tp = NULL; // tp trails p  
  
// search for match with theKey  
    while (p != NULL && p->element.first < theKey)  
    {  
        tp = p;  
        p = p->next;  
    }  
  
    // verify match  
    if (p != NULL && p->element.first == theKey)  
    {// found a match  
       // remove p from the chain  
        if (tp == NULL) firstNode = p->next;  // p is first node  
        else tp->next = p->next;  
  
        delete p;  
        cSize--;  
        cout << size() << endl;  
    }  
    else  
        cout << "Delete Failed" << endl;  
}  
  
template<class K, class E>  
void sortedChain<K, E>::output(ostream& out) const  
{// Insert the chain elements into the stream out.  
    for (pairNode<K, E>* currentNode = firstNode;  
        currentNode != NULL;  
        currentNode = currentNode->next)  
        out << currentNode->element.first << " "  
        << currentNode->element.second << "  ";  
}  
  
// overload <<  
template <class K, class E>  
ostream& operator<<(ostream& out, const sortedChain<K, E>& x)  
{  
    x.output(out); return out;  
}  
  
template<class K, class E>  
class HashChains : public dictionary<K, E>  
{  
public:  
    HashChains(int theDivisor = 11)  
    {  
        divisor = theDivisor;  
        dSize = 0;  
  
        // allocate and initialize Hash table array  
        table = new sortedChain<K, E>[divisor];  
    }  
  
    ~HashChains() { delete[] table; }  
  
    bool empty() const { return dSize == 0; }  
    int size() const { return dSize; }  
  
    pair<const K, E>* find(const K& theKey) const  
    {  
        return table[Hash(theKey) % divisor].find(theKey);  
    }  
  
    void insert(const pair<const K, E>& thePair)  
    {  
        int homeBucket = (int)Hash(thePair.first) % divisor;  
        int homeSize = table[homeBucket].size();  
        table[homeBucket].insert(thePair);  
        if (table[homeBucket].size() > homeSize)  
            dSize++;  
    }  
  
    void erase(const K& theKey)  
    {  
        table[Hash(theKey) % divisor].erase(theKey);  
    }  
  
    void output(ostream& out) const  
    {  
        for (int i = 0; i < divisor; i++)  
            if (table[i].size() == 0)  
                cout << "NULL" << endl;  
            else  
                cout << table[i] << endl;  
    }  
  
  
protected:  
    sortedChain<K, E>* table;  // Hash table  
    Hash1<K> Hash;              // maps type K to nonnegative integer  
    int dSize;                 // number of elements in list  
    int divisor;               // Hash function divisor  
};  
  
  
// overload <<  
template <class K, class E>  
ostream& operator<<(ostream& out, const HashChains<K, E>& x)  
{  
    x.output(out); return out;  
}  
/*void readtext() 
{ 
 
    ifstream infile; 
    infile.open("car5.in", ios::in); 
    int n; int m; 
    infile >> n; 
    infile >> m; 
    //cout << n << m; 
    HashChains<int, int> z(n); 
    pair<int, int> p; 
    int opt, x; 
     
    for (int i = 0; i < m; i++) 
    { 
        infile >> opt; infile >> x; 
        switch (opt) 
        { 
        case(0): 
            p.first = x; 
            p.second = x; 
            z.insert(p); 
            break;  
        case(1): 
            z.find(x); 
            break; 
        case(2): 
            z.erase(x); 
            break; 
        default: 
            break; 
        } 
    } 
}*/  
int main()  
{  
    int n, opt, m, x;  
    cin >> n; cin >> m;  
    HashChains<int, int> z(n);  
    pair<int, int> p;  
    int i;  
    for (i = 0; i < m; i++)  
    {  
        cin >> opt; cin >> x;  
        switch (opt)  
        {  
        case(0):  
            p.first = x;  
            p.second = x;  
            z.insert(p);  
            break;  
        case(1):  
            z.find(x);  
            break;  
        case(2):  
            z.erase(x);  
            break;  
        default:  
            break;  
        }  
    }  
    //cout << z << endl;  
    return 0;  
//  readtext();  
}