Помогите разобраться с задачей, хотя бы алгоритм...
Реализовать в виде класса на языке С++ абстрактный тип данных множество с операциями добавления элемента, удаления, проверки наличия и т.д. Для хранения элементов множества использовать хеш-таблицу, элементами множества являются строки ограниченной длины.
Что именно тебе не понятно? Алгоритм выполения операций "добавления элемента, удаления, проверки наличия и т.д"?
И интересно, 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;
}
Алена спасибо за код...
Я вот тут нашел такую ссылочку 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";
Это я так понимаю, создаются элементы множества?
...элементами множества являются строки ограниченной длины. - под строками я понимаю какой-то текст, это правильно или нет? Объясните пожалуйста...
Что подразмевается под элементами множества...?
Алена твой исходник не компилируется, выдает ошибку (183,64): 'theSet::List' is not accessible
В чем может быть причина?
Не знаю, у меня прекрасно работает... Ты что же думаешь, я бы выложила, если бы это не компилировалось? А вот тебе было бы неплохо перечитать правила:
А турбо с++ сильно отличается от обычного борландского с++ 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 */
#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);
}