1. Пользуйтесь тегами кода. - [code] ... [/code] 2. Точно указывайте язык, название и версию компилятора (интерпретатора). 3. Название темы должно быть информативным. В описании темы указываем язык!!!
Помогите разобраться с задачей, хотя бы алгоритм...
Реализовать в виде класса на языке С++ абстрактный тип данных множество с операциями добавления элемента, удаления, проверки наличия и т.д. Для хранения элементов множества использовать хеш-таблицу, элементами множества являются строки ограниченной длины.
Поиск по форуму: "коллиз*" выдаст тебе 3 темы. В одной из них присутствуют ссылки на реализацию Hash-Table с динамическим и с линейным разрешением коллизий (реализация, правда, Паскалевская, но для "разбора полетов" как раз пойдет )
Здесь элементы theSet хранятся в виде односвязного списка, просто замени List на HashTable (ссылку тебе дали выше, реализация - за тобой...), и все... Можно класс theSet сделать шаблонным, кстати, чтоб можно было работать и со строками, и с числами, и вообще со всем, с чем хочется...
Опять же, можно разнести эту программу по разным файлам, я привела "все в одном" только для облегчения тестирования...
Это в множества добавляются элементы... Мне почему-то казалось, что перегрузка operator += совершенно прозрачна: есть множество, и если к нему что-то прибавляется, значит, элемент добавляется в множество...
Цитата
под строками я понимаю какой-то текст, это правильно или нет?
Судя по заданию, да... Что, собственно, в моем коде и делается: добавляется текстовая строка... Насчет ограничения длины - в конструкторе theString можешь наложить ограничение на длину строки, и, скажем, обрезать ее до определенной длины, и в множество будет записываться уже укороченная строка, если длина исходной превышает некоторый предел...
Не знаю, у меня прекрасно работает... Ты что же думаешь, я бы выложила, если бы это не компилировалось? А вот тебе было бы неплохо перечитать правила: Извини, я нигде не увидела версии твоего компилятора, поэтому программа отработана на Turbo C++...
Я не думаю, что ты бы выложила нерабочий код... Я просто спросил, в чем может быть проблема... проблема оказалась в компиляторах...
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;
// 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: // 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 }
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); }
Почему же? ЭТО компилируется и на GCC, например... Я не думаю, что будут проблемы с Билдером (только вот в чем проблема, я Билдер не держу, также, как и MSVC, соответственно, проверить не могу... Компилируй, исправляй, если что не работает - к автору...)
Кстати, я подправила чуть-чуть свою первоначальную программу, теперь она должна компилироваться без проблем: