Задача выбора. Задан линейный список целых, различных по значению чисел B=, требуется найти элемент, имеющий i-тое наибольшее значение в порядке убывания элементов. При i=1 задача эквивалентна поиску максимального элемента, при i=2 поиску элемента с вторым наибольшим значением. Поставленная задача может быть получена из задачи поиска j-того минимального значения заменой i=n-j+1 и поиском i-того максимального значения. [...]
Методы вычисления адреса. Пусть в каждом из М элементов массива Т содержится элемент списка (например целое положительное число). Если имеется некоторая функция H(V), вычисляющая однозначно по элементу V его адрес – целое положительное число из интервала [0,M-1],то V можно хранить в массиве T с номером H(V) т.е. V=T(H(V)). При таком хранении поиск любого элемента происходит [...]
Этот способ удобен при индексном хранении списка. Предполагается, что исходный упорядоченный список B длины N разбит на M подсписков B1,B2,…,Bm длины N1,N2,…,Nm, таким образом, что B=B1,B2,..,Bm. Для нахождения ключа V, нужно сначала определить первый из списков Bi, i=1,M, последний элемент которого больше V, а потом применить последовательный поиск к списку Bi. Хранение списков Bi может [...]
Для упорядоченных линейных списков существуют более эффективные алгоритмы поиска, хотя и для таких списков применим последовательный поиск. Бинарный поиск состоит в том, что ключ V сравнивается со средним элементом списка. Если эти значения окажутся равными, то искомый элемент найден, в противном случае поиск продолжается в одной из половин списка. Нахождение элемента бинарным поиском осуществляется очень [...]
Задача поиска. Пусть заданы линейные списки: список элементов В=<К1,К2,К3,…,Кn> и список ключей V= (в простейшем случае это целые числа). Требуется для каждого значения Vi из V найти множество всех совпадающих с ним элементов из В. Чаще всего встречается ситуация когда V содержит один элемент, а в В имеется не более одного такого элемента. Эффективность некоторого [...]
