Реализовать в виде класса абстрактный тип данных ..., C++ Опции

[KerK]

Помогите разобраться с задачей, хотя бы алгоритм...

Реализовать в виде класса на языке С++ абстрактный тип данных множество с операциями добавления элемента, удаления, проверки наличия и т.д. Для хранения элементов множества использовать хеш-таблицу, элементами множества являются строки ограниченной длины.

[KerK]

А турбо с++ сильно отличается от обычного борландского с++ v.5.02?

Нашел реализацию хэш таблицы на с++...

Hashset.h

//
// class HashSet and auxiliary classes
//
#ifndef HASH_SET_H
#define HASH_SET_H

// An ABSTRACT class representing a key in HashSet
class HashSetKey {
public:
    HashSetKey() {}
    virtual ~HashSetKey() {}    // virtual destructor

    // Abstract class has virtual methods unimplemented

    virtual bool operator==(const HashSetKey&) const = 0;

    virtual int hashValue() const = 0;  // Abstract class

    // The virtual method "clone" must allocate a copy of the object
    // in the dynamic memory. In any derived class Foo it must
    // be always implemented in the following way:
    // virtual Foo* clone() const { return new Foo(*this); }
    //
    virtual HashSetKey* clone() const = 0;

    bool operator!=(const HashSetKey& k) const {
        return !operator==(k);
    }
};

// An ABSTRACT class representing a value of a key in HashSet
class HashSetValue {
public:
    HashSetValue() {}
    virtual ~HashSetValue() {}
    virtual HashSetValue* clone() const = 0;
};

//
// class HashSet implements "Map" or "Dictionary".
// It stores the set of pairs: (key, value).
// All keys are unique (different pairs have different keys).
//
class HashSet {
public:
    class Pair {
    public:
        const HashSetKey* key;
        HashSetValue* value;
        Pair():
            key(0),
            value(0)
        {}
        Pair(const HashSetKey* k, HashSetValue* v):
            key(k),
            value(v)
        {}
    };

private:
    class L1ListHeader {
    public:
        L1ListHeader* next;
        L1ListHeader(): next(0) {}
        L1ListHeader(const L1ListHeader& h): next(h.next) {}
        void link(const L1ListHeader* h) { next = (L1ListHeader*) h; }
    };

    class L1ListElement: public L1ListHeader {
    public:
        Pair pair;
        L1ListElement():
            L1ListHeader(),
            pair()
        {}
        L1ListElement(HashSetKey* k, HashSetValue* v):
            L1ListHeader(),
            pair(k, v)
        {}
        ~L1ListElement() {
            delete pair.key;
            delete pair.value;
        }
    };

    int hashTableSize;
    L1ListHeader* hashTable;
    int numElements;

public:
    HashSet():
        hashTableSize(1021),    // Prime number
        hashTable(new L1ListHeader[hashTableSize]),
        numElements(0)
    {}

    HashSet(int tableSize):
        hashTableSize(tableSize),
        hashTable(new L1ListHeader[hashTableSize]),
        numElements(0)
    {}

    int size() const { return numElements; }

    // Add a pair (key, value) to the set
    void add(const HashSetKey* k, const HashSetValue* v = 0);

    void remove(const HashSetKey* key);

    // Return a value of a key
    HashSetValue* value(const HashSetKey* k) const;
    HashSetValue* operator[](const HashSetKey* k) const {
        return value(k);
    }
    bool contains(const HashSetKey* k) const;

public:
    class iterator {
    private:
        HashSet* set;
        int hash;
        L1ListElement* element;
    public:
        iterator(): set(0), hash(0), element(0) {}
        iterator(HashSet* s, int h);
        iterator& operator++();
        iterator operator++(int) { // Postfix increment operator
            iterator tmp = *this;
            operator++();          // Apply the prefix increment operator
            return tmp;
        }
        iterator& operator--();
        iterator operator--(int) { // Postfix decrement operator
            iterator tmp = *this;
            operator--();          // Apply the prefix decrement operator
            return tmp;
        }
        const Pair& operator*() const {
            return element->pair;
        }
        const Pair* operator->() const {
            return &(operator*());
        }
        bool operator==(const iterator& i) const {
            return (
                set == i.set &&
                hash == i.hash &&
                element == i.element
            );
        }
        bool operator!=(const iterator& i) const {
            return !operator==(i);
        }
    };

    class const_iterator: public iterator {
    public:
        const_iterator():
            iterator()
        {
        }

        const_iterator(const HashSet* s, int h):
            iterator((HashSet*) s, h)
        {
        }

        const_iterator(const iterator& i):
            iterator(i)
        {
        }
    };

public:
    iterator begin();
    iterator end();
    const_iterator begin() const;
    const_iterator end() const;

private:
    // Calculate an index in hash table
    int hashIndex(const HashSetKey* key) const;

    // Find the PREVIOUS list element to element that contains the key.
    // Returns zero if element is not found.
    L1ListHeader* search(const HashSetKey* key) const;
};

#endif /* HASH_SET_H */

Hashset.cpp

#include "HashSet.h"

int HashSet::hashIndex(const HashSetKey* key) const {
    int h = key->hashValue();   // Calculate the hash function
    h &= 0x7fffffff;            // Make it positive
    h %= hashTableSize;         // Restrict it to 0..hashTableSize-1
    return h;
}

void HashSet::add(
    const HashSetKey* key, const HashSetValue* value /* = 0 */
) {
    L1ListHeader* p = search(key);
    if (p != 0) {
        // The key belongs to set, change its value
        L1ListElement* e = (L1ListElement*) p->next;
        delete e->pair.value;
        // Write the new value
        if (value == 0)
            e->pair.value = 0;
        else
            e->pair.value = value->clone();
    } else {
        // Add new element
        int h = hashIndex(key);
        HashSetKey* k = key->clone();
        HashSetValue* v = 0;
        if (value != 0)
            v = value->clone();
        L1ListElement* element = new L1ListElement(k, v);

        // Include the new element in the head of the chain with index h
        element->link(hashTable[h].next);
        hashTable[h].link(element);
        ++numElements;
    }
}

void HashSet::remove(const HashSetKey* key) {
    L1ListHeader* p = search(key);
    if (p != 0) {
        // Element belongs to set
        L1ListElement* e = (L1ListElement*) p->next;
        p->link(e->next);       // Exclude an element from a chain
        delete e;
        --numElements;
    }
}

HashSet::L1ListHeader* HashSet::search(const HashSetKey* key) const {
    int h = hashIndex(key);
    L1ListHeader* p = &(hashTable[h]); // The head of the chain with index h
    L1ListElement* e = (L1ListElement*) p->next; // First element in the chain
    while (e != 0) {
        if (*(e->pair.key) == *key)
            return p;                           // The key is found
        // Go to the next element in chain
        p = e; 
        e = (L1ListElement*) p->next;
    }
    return 0;   // Not found
}

bool HashSet::contains(const HashSetKey* key) const {
    return (search(key) != 0);
}

HashSetValue* HashSet::value(const HashSetKey* k) const {
    const L1ListHeader* h = search(k);
    if (h == 0)
        return 0;
    else
        return ((const L1ListElement*) h->next)->pair.value;
}

HashSet::iterator::iterator(HashSet* s, int h):
    set(s),
    hash(h),
    element(0)
{
    if (set != 0 && 0 <= h && h < set->hashTableSize)
        element = (L1ListElement*) set->hashTable[h].next;
}

HashSet::iterator& HashSet::iterator::operator++() {
    if (element != 0) {
        // Go to the next element in this chain
        element = (L1ListElement*) (element->next);
    }
    if (element == 0) {
        // Go to the next chain
        ++hash;

        // Find out nonempty chain
        while (
            hash < set->hashTableSize &&
            set->hashTable[hash].next == 0
        )
            ++hash;
        if (hash < set->hashTableSize)
            element = (L1ListElement*) (set->hashTable[hash].next);
    }
    return *this;
}

HashSet::iterator HashSet::begin() {
    int h = 0;
    while (h < hashTableSize && hashTable[h].next == 0)
        ++h;
    return iterator(this, h);
}

HashSet::iterator HashSet::end() {
    return iterator(this, hashTableSize);
}

И я так понимаю, это тоже на турбо с++?