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

[KerK]

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

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

[Michael_Rybak]

Что именно тебе не понятно? Алгоритм выполения операций "добавления элемента, удаления, проверки наличия и т.д"?

[KerK]

Что именно тебе не понятно? Алгоритм выполения операций "добавления элемента, удаления, проверки наличия и т.д"?

можно сказать... да, желательно код, хотя бы для добавления элемента...

можно сказать... да, желательно код, хотя бы для добавления элемента...

еще интересует хеш-таблица

и элементы множества - строки ограниченной длины....

Это задание выполняется с использованием указателей?

[volvo]

еще интересует хеш-таблица

Поиск по форуму: "коллиз*" выдаст тебе 3 темы. В одной из них присутствуют ссылки на реализацию Hash-Table с динамическим и с линейным разрешением коллизий (реализация, правда, Паскалевская, но для "разбора полетов" как раз пойдет )

[Michael_Rybak]

И интересно, STL юзать можно?

[Алена]

Вот набросок без использования STL:

#include <string.h>
#include <assert.h>
#include <iostream.h>


class theString {

  friend ostream& operator << (ostream&, const theString&);

public:
  theString();
  theString(int length = 50);
  theString(const char *s);
  theString(const theString &s);

  operator == (const theString &s) {
    return (strcmp(str, s.str) == 0);
  }

private:
  int len;
  char *str;
};

ostream& operator << (ostream &os, const theString &s) {
  os << s.str;
  return os;
}

theString :: theString(int length) {

  str = new char[ (len = length) + 1];
  assert(str != 0);
  str[0] = '\0';

}
theString :: theString(const char *s) {

  str = new char[ (len = strlen(s)) + 1];
  assert(str != 0);
  strcpy(str, s);

}
theString :: theString(const theString &s) {

  str = new char[ (len = s.len) + 1 ];
  assert(str != 0);
  strcpy(str, s.str);

}

/* ***** */

class theSet {

  friend ostream& operator << (ostream&, const theSet&);
public:
  theSet()
  {
  }

  void operator += (const theString &s) {
    if(!info.isPresent(s)) info.append(s);
  }
  void operator -= (const theString &s) {
    info.remove(s);
  }
  int operator == (const theString &s) {
    return info.isPresent(s);
  }
  int operator != (const theString &s) {
    return (!(info.isPresent(s)));
  }

private:

  class List {

    friend ostream& operator << (ostream&, const List&);
  public:
    List() {
      start = 0; finish = 0;
    }
    ~List();

    void append(const theString &s);
    void remove(const theString &s);

    int isPresent(const theString &s);

    void print();

  private:

    class ListItem {
    public:
      ListItem(const theString &s, ListItem *item = 0) :
        value(s), next(item)
        {
        }

      theString value;
      ListItem *next;
    };

    ListItem *start, *finish;
  };

  List info;

};

theSet :: List :: ~List() {

  theSet :: List :: ListItem *pt = start;
  while(pt) {
    ListItem *p = pt;
    pt = pt -> next;
    delete p;
  }
  start = finish = 0;

}

void theSet :: List :: append(const theString &s) {

  theSet :: List :: ListItem *pt;
  pt = new theSet :: List :: ListItem(s);
  assert(pt != 0);

  if(start == 0) start = pt;
  else finish -> next = pt;

  finish = pt;

}
void theSet :: List :: remove(const theString &s) {

  theSet :: List :: ListItem *pt;
  pt = start;
  while(pt && pt -> value == s) {
    theSet :: List :: ListItem *T = pt -> next;
    delete pt;
    pt = T;
  }

  if(!(start = pt)) {
    finish = 0;
    return;
  }

  theSet :: List :: ListItem *prv = pt;
  pt = pt -> next;
  while(pt) {
    if(pt -> value == s) {

      prv -> next = pt -> next;
      if(finish == pt) finish = prv;
      delete pt;
      pt = prv -> next;

    }
    else {
      prv = pt;
      pt = pt -> next;
    }
  }
}
int theSet :: List :: isPresent(const theString &s) {

  if(start == 0) return 0;
  if(start -> value == s || finish -> value == s) return 1;

  theSet :: List :: ListItem *pt;
  pt = start -> next;
  for(; pt && pt != finish; pt = pt -> next)
    if(pt -> value == s) return 1;

  return 0;

}

ostream& operator << (ostream &os, const theSet :: List &lst) {

  os << "[ ";
  for(theSet :: List :: ListItem *pt = lst.start;
      pt; pt = pt -> next) os << pt -> value << " ";
  os << "]" << endl;

  return os;
}

ostream& operator << (ostream &os, const theSet &set) {

  os << set.info;
  return os;
}




int main() {

  theSet my_set;
  my_set += "first";
  my_set += "second";
  my_set += "third";
  my_set += "fourth";

  cout << my_set;
  my_set -= "second";
  cout << my_set;

  if(my_set == "third")
    cout << "present" << endl;

  if(my_set != "_third")
    cout << "not present" << endl;

  return 0;

}

Здесь элементы theSet хранятся в виде односвязного списка, просто замени List на HashTable (ссылку тебе дали выше, реализация - за тобой...), и все... Можно класс theSet сделать шаблонным, кстати, чтоб можно было работать и со строками, и с числами, и вообще со всем, с чем хочется...

Опять же, можно разнести эту программу по разным файлам, я привела "все в одном" только для облегчения тестирования...

[KerK]

Алена спасибо за код...
Я вот тут нашел такую ссылочку http://akoub.narod.ru/practprog/dict/hashtable.htm
Это похоже на то что мне надо?
И возник вопрос:

ht.create(5);
ht.add(new(PString, create('Ivanov')), new(PString, create('student')));
ht.add(new(PString, create('Petrov')), new(PString, create('student')));
ht.add(new(PString, create('Sidorov')), new(PString, create('student')));
ht.add(new(PString, create('Sokolova')), new(PString, create('student')));

или из кода Алены

theSet my_set;
my_set += "first";
my_set += "second";
my_set += "third";
my_set += "fourth";

Это я так понимаю, создаются элементы множества?

...элементами множества являются строки ограниченной длины. - под строками я понимаю какой-то текст, это правильно или нет? Объясните пожалуйста...

Что подразмевается под элементами множества...?

[Алена]

Это я так понимаю, создаются элементы множества?

Это в множества добавляются элементы... Мне почему-то казалось, что перегрузка operator += совершенно прозрачна: есть множество, и если к нему что-то прибавляется, значит, элемент добавляется в множество...

под строками я понимаю какой-то текст, это правильно или нет?

Судя по заданию, да... Что, собственно, в моем коде и делается: добавляется текстовая строка... Насчет ограничения длины - в конструкторе theString можешь наложить ограничение на длину строки, и, скажем, обрезать ее до определенной длины, и в множество будет записываться уже укороченная строка, если длина исходной превышает некоторый предел...

[KerK]

Алена твой исходник не компилируется, выдает ошибку (183,64): 'theSet::List' is not accessible
В чем может быть причина?

[Алена]

Не знаю, у меня прекрасно работает... Ты что же думаешь, я бы выложила, если бы это не компилировалось? А вот тебе было бы неплохо перечитать правила:

2. Точно указывайте язык, название и версию компилятора (интерпретатора).

Извини, я нигде не увидела версии твоего компилятора, поэтому программа отработана на Turbo C++...

[Гость]

Не знаю, у меня прекрасно работает... Ты что же думаешь, я бы выложила, если бы это не компилировалось? А вот тебе было бы неплохо перечитать правила:
Извини, я нигде не увидела версии твоего компилятора, поэтому программа отработана на Turbo C++...

Я не думаю, что ты бы выложила нерабочий код... Я просто спросил, в чем может быть проблема... проблема оказалась в компиляторах...

[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);
}

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

[Алена]

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

Почему же? ЭТО компилируется и на GCC, например... Я не думаю, что будут проблемы с Билдером (только вот в чем проблема, я Билдер не держу, также, как и MSVC, соответственно, проверить не могу... Компилируй, исправляй, если что не работает - к автору...)

Кстати, я подправила чуть-чуть свою первоначальную программу, теперь она должна компилироваться без проблем:

Сообщение отредактировано: Алена - 13.11.2006 11:30