0
В программе, над которой я работаю для окончательного проекта, мне нужно реализовать функции поиска для упорядоченных и неупорядоченных связанных списков. В задании ясно сказано, что есть ожидание функции поиска для каждого типа.Поиск упорядоченных и неупорядоченных связанных списков
Я работал со связанными списками в предыдущих классах, я понимаю разницу между упорядоченными и неупорядоченными, но я ударил стену, пытаясь понять, в чем разница в их поиске. На мой взгляд, оба должны перебирать список до тех пор, пока значение ключа не будет найдено, а затем вернет его. Как они должны отличаться?
В отсортированном списке вы можете остановить поиск раньше, как только значение, которое будет найдено, меньше/больше, чем значение текущего узла. Поскольку порядок сортировки говорит о том, что найденное значение не может присутствовать за пределами этой точки. – kaylum
также для отсортированного списка вы можете использовать некоторый алгоритм, например, двоичный поиск. https://en.wikipedia.org/wiki/Binary_search_algorithm, хотя для связанного списка вам может потребоваться реализовать дополнительные структуры, такие как указатели пропуска. – paradite