Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 08.01.2018, 20:48   #1
AnatoliyAnatoliy
Пользователь
 
Регистрация: 08.01.2018
Сообщений: 19
По умолчанию Хеш-таблица, метод цепочек, первичный индекс и вторичный индекс - C#

Добрый вечер! Пытаюсь написать программу, которая будет работать как хеш-таблица. Для вычисления первичного индекса используется символьный ключ (строка преобразуется в int по заданному правилу), а вторичный индекс должен вычисляться методом квадратичных проб. И вот с этим у меня загвоздка. В коде отметил где, насколько я понимаю, должен генерироваться этот вторичный индекс, но ума не приложу как это осуществить. Надеюсь на вашу помощь!

Код:
class Program
{
    static void Main(string[] args)
    { opentable myTable = new opentable();
        myTable.insert(109875, "Anna");
        myTable.insert(103765, "Harry");
        myTable.insert(100364, "Benedict");
        myTable.insert(202120, "Piter");
        myTable.insert(202120, "Piter");
        myTable.insert(202120, "Piter");
 
 
    myTable.print();
 
    Console.ReadKey();
}
} 
//хеш-таблица метод цепочек
class opentable 
{
    class hashnode
    {
        int key;
        string data;
        hashnode next;
        public hashnode(int key, string data)
        {
            this.key = key;
            this.data = data;
            next = null;
        }
        public int getkey()
        {
            return key;
        }
        public string getdata()
        {
            return data;
        }
        public void setNextNode(hashnode obj)
        {
            next = obj;
        }
        public hashnode getNextNode()
        {
            return this.next;
        }
    }
 
    hashnode[] table;
    const int size = 10;
 
    public opentable()
    {
        table = new hashnode[size];
        for (int i = 0; i < size; i++)
        {
            table[i] = null;
        }
    }
    public void insert(int key, string data)
    {
        hashnode nObj = new hashnode(key, data);
        int hash = key % size; // первичный индекс
        while (table[hash] != null && table[hash].getkey() % size != key % size)
        {
            hash = (hash + 1) % size;
        }
        if (table[hash] != null && hash == table[hash].getkey() % size)
        {
           //здесь должен генерироваться вторичный индекс
            nObj.setNextNode(table[hash].getNextNode());
            table[hash].setNextNode(nObj);
            return;
        }
        else
        {
            table[hash] = nObj;
            return;
        }
    }
    public string retrieve(int key)
    {
        int hash = key % size;
        while (table[hash] != null && table[hash].getkey() % size != key % size)
        {
            hash = (hash + 1) % size;
        }
        hashnode current = table[hash];
        while (current.getkey() != key && current.getNextNode() != null)
        {
            current = current.getNextNode();
        }
        if (current.getkey() == key)
        {
            return current.getdata();
        }
        else
        {
            return "nothing found!";
        }
    }
    public void remove(int key)
    {
        int hash = key % size;
        while (table[hash] != null && table[hash].getkey() % size != key % size)
        {
            hash = (hash + 1) % size;
        }
        //a current node pointer used for traversal, currently points to the head
        hashnode current = table[hash];
        bool isRemoved = false;
        while (current != null)
        {
            if (current.getkey() == key)
            {
                table[hash] = current.getNextNode();
                Console.WriteLine("entry removed successfully!");
                isRemoved = true;
                break;
            }
 
            if (current.getNextNode() != null)
            {
                if (current.getNextNode().getkey() == key)
                {
                    hashnode newNext = current.getNextNode().getNextNode();
                    current.setNextNode(newNext);
                    Console.WriteLine("entry removed successfully!");
                    isRemoved = true;
                    break;
                }
                else
                {
                    current = current.getNextNode();
                }
            }
 
        }
 
        if (!isRemoved)
        {
            Console.WriteLine("nothing found to delete!");
            return;
        }
    }
    public void print()
    {
        hashnode current = null;
        for (int i = 0; i < size; i++)
        {
            current = table[i];
            while (current != null)
            {
                Console.Write(current.getdata() + " ");
                current = current.getNextNode();
            }
            Console.WriteLine();
        }
    }
 
}
AnatoliyAnatoliy вне форума Ответить с цитированием
Старый 09.01.2018, 03:46   #2
Black Fregat
Программист
Участник клуба
 
Аватар для Black Fregat
 
Регистрация: 23.06.2009
Сообщений: 1,772
По умолчанию

Мне кажется, Вы путаете два принципиально разных подхода к построению хэш-таблиц. Ваша программа ориентирована на метод цепочек:
Цитата:
Метод цепочек подразумевает то, что в каждую ячейку хеш-таблицы действительно должно быть записано несколько значений. Конечно, «в лоб» это сделать просто невозможно, поэтому в ячейках хранятся не сами адреса элементов (точнее блоков), а указатели на списки адресов. В случае коллизии такой список будет содержать несколько значений.
А от Вас требуется метод открытой адресации:
Цитата:
Метод открытой адресации предполагает несколько иной подход.
Имеется обычная хеш-таблице. В процессе ее заполнения, при получении нового значения, мы его заносим в том случае, если данная ячейка еще не заполнена (например, значение равно нулю). В противном случае предполагается занесение значения в другую ячейку, вычисляемую по какому-либо алгоритму, но если и она оказывается уже заполненной, то вычисляется еще одна ячейка и т.д.
Black Fregat вне форума Ответить с цитированием
Старый 09.01.2018, 15:30   #3
AnatoliyAnatoliy
Пользователь
 
Регистрация: 08.01.2018
Сообщений: 19
По умолчанию

Black Fregat, огромное спасибо за ответ! Прочитал до вашего ответа уже много разных источников о хеш-таблицах. Ваш ответ только подтвердил мою догадку о том, что ошибка именно в поставленной задаче.

Думаю, что имелась ввиду хеш-таблица, построенная по методу цепочек, с хеш-функцией, которая преобразует строку в int по заданному правилу.

А вторичный индекс - просто не для моей задачи, поэтому у меня и получился такой ступор. Еще раз огромное спасибо за ответ!

Пойду доделывать...
AnatoliyAnatoliy вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Хеш-таблица и хеш-функция. Проверка на ввод существующих данных F1nt Общие вопросы C/C++ 0 24.01.2014 09:52
Хеш функция и метод цепочек (На С++ или Delphi) EmrisM Помощь студентам 0 10.11.2012 17:08
Хэш-таблица. Метод цепочек. C++ Playa-RC Помощь студентам 0 10.03.2012 15:07
Метод Insert не перемещает на указанный индекс желаемый таб в TabControl KorPaEv C# (си шарп) 1 20.12.2011 05:42
Индекс не срабатывает GenniY БД в Delphi 4 24.11.2009 15:05