VPF::Реализация Хэш таблицы - Форум программистов

Romksuper

Дата 31.3.2010, 18:09 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 31.3.2010

Репутация: нет
Всего: нет

Всем привет, кто-нить знает что-нибудь по вот такой задаче (цитирую условие):
"Реализовать и протестировать конкретный класс динамической структуры данных, содержащий строки. Класс должен содержать интерфейс АТД для добавления, удаления и поиска элементов, а так же содержать:
1. перегруженный конструктор
2. диструктор
3.перегружаемые операции
4. обьявление и реализация дружественных функций"????
в моем случае структура данных ----- ХЭШ ТАБЛИЦА. реализовать на С++, среда разработки-вижуал студио. Кто0нибудь знает как это все можно сделать, а то если честно я в этом деле "дубик". Буду благодарен за помощь_)))

Добавлено через 7 минут и 23 секунды
smile

GoldFinch

Дата 31.3.2010, 18:27 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 6
Всего: 26

Romksuper, сходи в википедии про реализацию хеш таблицы прочитай, чтоли

Romksuper

Дата 31.3.2010, 18:43 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 31.3.2010

Репутация: нет
Всего: нет

ЭЭЭЭЭЭЭЭЭЭЭЭх, да еслиб там что-то понятно было..........

GoldFinch

Дата 31.3.2010, 19:00 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 6
Всего: 26

ну чтож поделать, если вы ни в чем разбираться не хотите %)

Romksuper

Дата 5.4.2010, 19:04 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 31.3.2010

Репутация: нет
Всего: нет

Код

enum ErrorType
  {invalidArraySize, memoryAllocationError, indexOutOfRange};

char *errorMsg[] =
{
    "Неверный размер массива", "Ошибка при выделении памяти",
    "Неверный индекс: "
};

template <class T> 
class Array
{
  private:
    // Динамически занимаемый массив.
    T*  alist;
    // Размер массива.
        int size;

        // Обработчик ошибок.
        void Error(ErrorType error,int badIndex=0) const;

    public:
        // Конструкторы и деструктор.
        Array(int sz = 50);
        Array(const Array<T>& A);   
        ~Array(void);

        // Оператор присвоения 
        Array<T>& operator= (const Array<T>& rhs);
        // Оператор индексации
        T& operator[](int i);
        // Оператор приведения к void
        operator T* (void) const;

        int ListSize(void) const;   // считать размер
        void Resize(int sz);        // изменить размер
};
// печатает сообщение, соответствующее ошибке
template <class T>
void Array<T>::Error(ErrorType error, int badIndex) const
{
    cerr << errorMsg[error];
    if (error == indexOutOfRange)
        cerr << badIndex;
    cerr << endl;
    exit(1);
}

// конструктор
template <class T>
Array<T>::Array(int sz)
{
    // проверка правильности заданного размера
    if (sz <= 0) 
        Error(invalidArraySize);
    // запоминаем размер и выделяем память под массив
    size = sz;
    alist = new T[size];    
    // проверяем, что система выделила запрошенную память 
    if (alist == NULL)
        Error(memoryAllocationError);
}

// деструктор
template <class T>
Array<T>::~Array(void)
{ 
    delete [] alist;
}

// конструктор копирования
template <class T>
Array<T>::Array(const Array<T>& X)
{
    // присвоить размер объекта X текущему объекту
    int n = X.size;

    size = n;

    // выделить память под массив и проверить, что она выделена
    alist = new T[n];           // allocate dynamic array
    if (alist == NULL)
        Error(memoryAllocationError);
    
    // скопировать элементы массива из Х
    T* srcptr = X.alist;    // начальный адрес X.alist
    T* destptr = alist;     // начальный адрес alist
    // копируем элементы массива
    while (n--)
        *destptr++ = *srcptr++;
}

// оператор присвоения. Присвоить rhs текущему объекту
template <class T>
Array<T>& Array<T>::operator= (const Array<T>& rhs)
{
    // запоминаем размер rhs
    int n = rhs.size;

    // если размеры не совпадают, перезанимаем память
    if (size != n)
    {
        delete [] alist;        // освобождаем ранее занятую память
        alist = new T[n];       // занимаем память под новый массив
        if (alist == NULL)
            Error(memoryAllocationError);
        size = n;
    }
 
    // Копируем элементы массива из rhs в текущий объект
   T* destptr = alist;
   T* srcptr = rhs.alist;
    while (n--) 
        *destptr++ = *srcptr++;

    // возвращаем ссылку на текущий объект
    return *this;
}

// оператор индексирования
template <class T>
T& Array<T>::operator[] (int n)
{
   // проверяем границы массива
   if (n < 0 || n > size-1)
      Error(indexOutOfRange,n);
   // возвращаем ссылку на запрошенный элемент массива
   return alist[n];
}

// оператор приведения указателя
template <class T>
Array<T>::operator T* (void) const
{
    // возвращаем значение скрытого поля alist
    return alist;
}

template <class T>
int Array<T>::ListSize(void) const
{
    return size;
}

// оператор изменения размеров массива
template <class T>
void Array<T>::Resize(int sz)
{
    // Проверяем заданный размер
    if (sz <= 0) 
        Error(invalidArraySize);
    // ничего не делать, если размер не изменился
    if (sz == size)
        return;
    // занимаем память
    T* newlist = new T[sz];
    if (newlist == NULL)
        Error(memoryAllocationError);

    // Рассчитываем количество элементов, 
    // копируемых из старого массива в новый.
    // Запоминаем в n значение sz (обрезаем массив), если sz <= size
    // иначе запоминаем size
    int n = (sz <= size) ? sz : size;

    // копируем n элементов из старого массива в новый
    T* srcptr = alist;      // начальный адрес старого массива
    T* destptr = newlist;   // начальный адрес нового массива
    // Копируем элементы массива.
    while (n--)
        *destptr++ = *srcptr++;
    
    // Уничтожаем старый массив.
    delete[] alist;

    // Изменяем значение alist так, чтобы оно указывало на новый массив
    alist = newlist;
    // Запоминаем новый размер массива.
    size = sz;
}

кто-нить может обьяснить доступным человеческим языком........................................................

Ozerich

Дата 5.4.2010, 22:22 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 164
Регистрация: 2.8.2009
Где: Минск, Беларусь

Репутация: 4
Всего: 5

Цитата

кто-нить может обьяснить доступным человеческим языком.........................................................................................................................................

А там и так всё в комментариях написано. Что еще не понятно?

--------------------

C++(STL) / DHTML(CSS) / Javascript / PHP Developer

bsa

Дата 7.4.2010, 17:31 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Romksuper, ты вообще хоть представляешь себе, что такое хэш-таблица? А то нет никакого смысла объяснять как работает программа, пока ты не поймешь, что вообще нужно.
В двух словах, хэшем называется некий код, который уникально (в идеале) идентифицирует объект. И значение кода зависит исключительно от состояния объекта. Простейшим примером хэша может служить контрольная сумма и более продвинутый ее вариант CRC. Сейчас используются более надежные алгоритмы вычисления хэшей.
Применительно к нашему случаю, значение хэша зависит от содержимого строки. Если в строке меняется хоть один символ, то хэш тоже меняется.
Таблица является контейнером, который содержит пары хэш+строка. Причем эти пары отсортированы по хэшу.
Почти все операции (кроме удаления и итераций) с этой таблицой начинаются с получения хэша из строки. Так как все элементы в ней отсортированы, то можно осуществлять бинарный поиск по хэшу. А после нахождения требуемого хэша сравнивать строки (в жизни возможна ситуация, когда для двух разных строк получается одинаковый хэш). Операция добавления организуется через поиск места вставки нового хэша в контейнер.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »