Алгоритм поиска в несортированном списке слов - C#

Узнай цену своей работы

Формулировка задачи:

Имеется неотсортированный список слов, порядка миллиона. Какой лучше использовать алгоритм чтобы найти, допустим, слово "Мир"? Есть ограниченкие - выдать результат не более 10 сек

Решение задачи: «Алгоритм поиска в несортированном списке слов»

textual
Листинг программы
using System.Linq;
using System;
using System.Collections;
using System.Collections.Generic;
 
namespace ConsoleApplication1
{
    public class HTable
    {
        object[] values;
        public int Count = 0;
 
        public HTable(int n)
        {
            values = new object[n];
        }
 
        /// <summary>
        /// Возвращает хеш-код по переданному в него элементу
        /// </summary>
        /// <param name="val">Хешируемый элемент</param>
        /// <param name="collision">Если true, то разрешает коллизии, если False, то ищет пустую ячейку для элемента</param>
        /// <returns></returns>
        private int GetHash(object val, bool collision)
        {
            if (Count == values.Length)
                return -1;
            int x = val.ToString().Aggregate(0, (acc, i) => acc + i) % values.Length; //берем сумму кодов каждого символа в строке и делим на размерность массива
            if (!collision)
            {
                while (values[x] != null) //пока не наткнемся на пустую ячейку, увеличиваем счетчик на 1
                {
                    if (val.ToString() == values[x].ToString()) //если наткнулись на точно такой же элемент, то возвращаем -1, дабы избавиться от одинаковых элементов в таблице
                        return -1;
                    x = x + 1 >= values.Length ? 0 : x + 1; //если x + 1 больше размера таблицы, то присваиваем ему 0, иначе x + 1
                }
                return x;
            }
            else
            {
                int count = 0; 
                while (true)
                {
                    if (count >= Count) //если перебор произвелся больше раз, чем имеется элементов, значит элемент отсутствует
                        return -1;
                    if (values[x] == null) //если ячейка пуста, то увеличиваем x на 1 по тому же принципу
                        x = x + 1 >= values.Length ? 0 : x + 1;
                    else
                        if (values[x].ToString() == val.ToString()) //иначе, если элемент соответствует искомому, то возвращаем его
                            return x;
                        else
                            x = x + 1 >= values.Length ? 0 : x + 1; //иначе снова увеличиваем x
                }
            }
        }
 
        public bool Add(object val)
        {
            int index = GetHash(val, false);
            if (index != -1)
            {
                values[index] = val;
                Count++;
            }
            return index != -1;
        }
 
        public void Delete(object val)
        {
            int index = GetHash(val, true);
            if (index != -1)
                values[index] = null;
        }
 
        public bool Find(object finding, out object result)
        {
            result = null;
            int index = GetHash(finding, true);
            if (index != -1)
            {
                result = values[index];
            }
            return index != -1;
        }
    }
 
    class Program
    {
        static void Main()
        {
            HTable h = new HTable(1000000);
            string obj;
            char choose;
            while (true)
            {
                Console.Clear();
                Console.WriteLine("1.Добавить\n2.Удалить\n3.Поиск\n4.Выход");
                choose = Console.ReadKey().KeyChar;
                Console.Clear();
                switch (choose)
                {
                    case '1':
                        Console.Write("*Добавление*\nВведите значение->");
                        obj = Console.ReadLine();
                        if (obj == "")
                            break;
                        Console.WriteLine("Обеъкт {0}", h.Add(obj) ? "добавлен" : "не добавлен");
                        Console.ReadLine();
                        break;
                    case '2':
                        Console.Write("*Удаление*\nВведите значение->");
                        h.Delete(Console.ReadLine());
                        break;
                    case '3':
                        Console.Write("*Поиск*\nВведите значение->");
                        obj = Console.ReadLine();
                        object result;
                        Console.Write(h.Find(obj, out result) ? result.ToString() + " присутствует" : "Отсутствует");
                        Console.ReadLine();
                        break;
                    case '4':
                        return;
                }
            }
        }
 
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

5   голосов , оценка 4 из 5
Похожие ответы