Алгоритм поиска в несортированном списке слов - 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; } } } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д