У меня есть домашнее задание, и я не знаю, с чего начать и что делать.По сути, мне нужно организовать примерно 1 миллион точек, используя «Пространственное хеширование», и использовать хеш-таблицу, чтобы найти две точки, которые находятся ближе всего друг к другу, и вернуть расстояние.
Особенности назначения: Найти ближайшийпара точек быстро, вы разделите единичный квадрат, содержащий точки, на сетку ab × b квадратных «ячеек», каждая из которых представляет 2D-квадрат размером 1 / b × 1 / b.Каждая точка должна быть «хеширована» в ячейке, содержащей ее.Например, если вы сохраняете координату x точки в «двойной» переменной с именем x, то (int) (x * b) будет масштабировать координату вверх на b и округлять до ближайшего целого числа;результат (в диапазоне 0. ... b − 1) может использоваться как один из индексов в вашем двумерном массиве ячеек.Другой индекс рассчитывается таким же образом, только используя их координаты.После хеширования каждую точку нужно сравнивать только с другими точками в ее ячейке, и 8 ячеек, непосредственно окружающих ее ячейку - это должно привести к гораздо меньшему количеству сравнений, чем если бы мы просто сравнивали каждую точку с любой другой точкой.Вам нужно будет выбрать соответствующее значение 1 основной части этого лабораторного упражнения.Возможно, вы захотите рассмотреть, каковы опасности при установке b слишком низко или слишком высоко.Внутри сетка ячеек должна храниться как двумерный массив указателей на связанные списки, причем каждый связанный список содержит набор точек, принадлежащих одной ячейке.Массив ячеек должен быть динамически размещен (с помощью новой команды) и впоследствии отменен в конце вашей программы (с помощью команды удаления).Это означает, что, поскольку каждая ячейка таблицы сама является указателем на узел связанного списка, переменная верхнего уровня, представляющая двумерный массив указателей, будет иметь тип «Node ***» (с тремя *!), предполагая, что «Node» - это имя структуры, представляющей узел в ваших связанных списках.
Ваша программа должна состоять из следующих основных шагов:
- Выделить и инициализировать 2D-массивуказателей на связанные списки.
- Чтение входного файла, вставка каждой точки в соответствующий связанный список на основе ячейки, в которую он отображается.
- Для каждой точки сравните ее со всеми точками в пределахего ячейка и 8 соседних ячеек;запомните наименьшее расстояние, полученное в ходе этого процесса.
- Отмена выделения 2D-массива и связанных списков.
- Распечатка минимального расстояния.Часть этой лабораторной работы также включает в себя определение правильного выбора значения b.Пожалуйста, включите в комментарий в своем коде краткое описание того, почему вы считаете, что ваш выбор b - хороший.