IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> Реализовать в виде класса абстрактный тип данных ..., C++
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


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

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


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Что именно тебе не понятно? Алгоритм выполения операций "добавления элемента, удаления, проверки наличия и т.д"?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


Цитата(Michael_Rybak @ 9.11.2006 15:25) *

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


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

Цитата(KerK @ 9.11.2006 15:58) *

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


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

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

Это задание выполняется с использованием указателей?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Цитата
еще интересует хеш-таблица
Поиск по форуму: "коллиз*" выдаст тебе 3 темы. В одной из них присутствуют ссылки на реализацию Hash-Table с динамическим и с линейным разрешением коллизий (реализация, правда, Паскалевская, но для "разбора полетов" как раз пойдет yes2.gif )
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


И интересно, STL юзать можно? smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Вот набросок без использования 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 сделать шаблонным, кстати, чтоб можно было работать и со строками, и с числами, и вообще со всем, с чем хочется...

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


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  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";


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

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

Что подразмевается под элементами множества...?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






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

Цитата
под строками я понимаю какой-то текст, это правильно или нет?
Судя по заданию, да... Что, собственно, в моем коде и делается: добавляется текстовая строка... Насчет ограничения длины - в конструкторе theString можешь наложить ограничение на длину строки, и, скажем, обрезать ее до определенной длины, и в множество будет записываться уже укороченная строка, если длина исходной превышает некоторый предел...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


Алена твой исходник не компилируется, выдает ошибку (183,64): 'theSet::List' is not accessible
В чем может быть причина?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






Не знаю, у меня прекрасно работает... Ты что же думаешь, я бы выложила, если бы это не компилировалось? А вот тебе было бы неплохо перечитать правила:
Цитата
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
Извини, я нигде не увидела версии твоего компилятора, поэтому программа отработана на Turbo C++...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






Цитата(Алена @ 12.11.2006 10:23) *

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


Я не думаю, что ты бы выложила нерабочий код... Я просто спросил, в чем может быть проблема... проблема оказалась в компиляторах...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


А турбо с++ сильно отличается от обычного борландского с++ 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);
}


И я так понимаю, это тоже на турбо с++?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гость






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

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

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


Прикрепленные файлы
Прикрепленный файл  test.txt ( 3.81 килобайт ) Кол-во скачиваний: 290
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 17:47
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name