Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

Теперь посмотрим, как получить доступ к элементам списка. В массиве для непосредственного обращения к любому элементу можно применять индекс массива. Это называется произвольным доступом. В связном списке необходимо начинать с начала списка и затем переходить от узла к узлу до тех пор, пока не будет достигнут желаемый узел; это называется n о еле д овател ън ым доступом.

Рис. 1 7.9. Вспшвка элемента в массив

глава 17

Последовательный доступ может быть также реализован и в массиве. Для упорядоченного перемещения по массиву достаточно инкрементировать его индекс. В одних ситуациях последовательного доступа вполне достаточно. Например, если требуется отобразить каждый элемент в списке, то последовательный доступ прекрасно подойдет В других ситуациях, как будет показано далее, наличие произвольного доступа дает огромное преимущество.

Предположим, что в списке необходимо найти конкретный элемент. Один из возможных алгоритмов предусматривает старт поиска с начала списка и последовательный просмотр его элементов; это называется последовательным поиском. Если элементы не упорядочены каким-либо образом, то последовательный поиск — это практически все, что можно предпринять. Если искомый элемент в списке отсутствует, придется просмотреть все элементы, прежде чем можно будет утверждать об этом. (Здесь может помочь параллельное программирование, т.к. разные процессоры могут выполнять поиск в разных частях списка одновременно.)

Последовательный поиск можно улучшить, предварительно отсортировав список. Эго позволяет прервать поиск, если искомый элемент не найден по достижении элемента, который должен был бы следовать за искомым. Например, предположим, что мы выполняем поиск элемента Susan в списке, упорядоченном по алфавиту, и через некоторое время наталкиваемся на элемент Sylvia, так и не найдя элемента Susan. В этом месте поиск можно прервать, поскольку элемент Susan, если бы присутствовал в списке, то он предшествовал бы элементу Sylvia В среднем этот метод может вдвое сократить время поиска элементов, отсутствующих в списке.

В случае упорядоченного списка для поиска можно использовать намного более эффективный метод двоичного поиска.. Вот как он работает. Для начала назовем искомый элемент списка целевым и предположим, что список упорядочен по алфавиту. Затем выберем элемент, расположенный посередине списка, и сравним его с целевым элементом. Если эти два элемента равны, поиск завершен. Если элемент списка в алфавитном порядке предшествует целевому элементу, то целевой элемент, если он

Расширенное представление данных 763

присутствует в списке, должен находиться во второй половине. Если элемент списка следует за целевым, то целевой элемент должен располагаться в первой половине. В любом случае правила поиска уменьшают количество просматриваемых элементов вдвое. Затем этот метод применяется снова. То есть мы выбираем элемент, расположенный посередине остающейся половины списка. Как и ранее, метод либо находит элемент, либо вдвое уменьшает размер просматриваемого списка. Эти действия продолжаются до тех пор, пока элемент не будет найден или пока не будет исключен весь список (рис. 17.11). Описанный метод весьма эффективен. Для примера предположим, что список содержит 127 элементов. При использовании последовательного поиска обнаружение элемента либо установление его отсутствия в списке требовало бы в среднем 64 операции сравнения. В то же время двоичный поиск требовал бы выполнения не более 7 сравнений. Первая операция сравнения уменьшает количество возможных совпадений до 63, вторая — до 31 и т.д., пока шестое сравнение не уменьшит число возможных элементов до 1. После этого седьмая операция сравнения определяет, является ли остающийся элемент целевым.

Рис. 17.11. Двоичный поигж элемента Susan

764 глава 17

В общем случае n сравнений позволяют обработать массив, содержащий 2"-1 элементов, поэтому преимущество применения двоичного поиска по сравнению с последовательным поиском становится все более явным по мере увеличения длины списка.

Реализовать двоичный поиск в массиве довольно просто, т.к. для определения средней точки в любом списке или его части можно использовать индекс массива. Для этого нужно сложить индексы начального и конечного элементов части списка и разделить результат на 2.