Дихотомический (бинарный) поиск

Этот метод поиска предполагает, что множество хранится, как некоторая отсортированная (например, по возрастанию) последовательность элементов, к которым можно получить прямой доступ посредством индекса. Фактически речь идет о том, что множество хранится в массиве и этот массив отсортирован.

Суть метода заключается в следующем. Областью поиска (l, r) назовем часть массива с индексами от l до r, в которой предположительно находится искомый элемент. Сначала областью поиска будет часть массива (l, r), где l=1, а r=n, то есть вся заполненная элементами множества часть массива. Теперь найдем индекс среднего элемента m=(l+r) div 2. Если Key>A[m], то можно утверждать (поскольку массив отсортирован), что если Key есть в массиве, то он находится в одном из элементов с индексами от m+l до r, следовательно, можно присвоить l=m+1, сократив область поиска. В противном случае можно положить r=m. На этом заканчивается первый шаг метода. Остальные шаги аналогичны.

На каждом шаге метода область поиска будет сокращаться вдвое. Как только l станет равно r, то есть область поиска сократится до одного элемента, можно будет проверить этот элемент на равенство искомому и сделать вывод о результате поиска.

Запишем все сказанное в виде программы:

l := 1; r := n;while (l<>r) dobegin m := (l+r) div 2; if Key>A[m] then l := m+1 else r := m;end;if A[l]=Key then <элемент найден> else <элемент не найден>;

Как уже было сказано, область поиска на каждом шаге сокращается вдвое, а это означает сложность T(log(n)).

Особого внимания здесь заслуживают операции добавления и удаления. Они должны сохранять массив отсортированным (лучше написать операции так, чтобы они не нарушали отсортированности массива, чем каждый раз сортировать его). Рассмотрим сначала добавление.

Чтобы при добавлении массив остался отсортированным, новый элемент должен быть вставлен в массив так, чтобы ему предшествовали меньшие элементы, а за ним следовали большие. То есть элементы, стоящие в месте вставки и за ним до конца массива должны быть сдвинуты на одну позицию в сторону конца массива:

i := n;while (i>=1)and(A[i]>Key) dobegin A[i+1] := A[i]; {сдвигаем} Dec(i);end;A[i+1] := Key;Inc(n);

Такая операция добавления имеет сложность T(n).

Удаление в том виде, в каком оно записано в разделе 2.1. сохраняет массив отсортированным.

Интерполяционный поиск

Рассмотрим еще один метод, имеющий хорошую теоретическую сложность. Как и предыдущий, этот метод предполагает, что множество хранится в массиве и массив отсортирован. Как и предыдущий метод, этот на каждом шаге своей работы сокращает область поиска. Но в отличие от предыдущего метода проба берется не в середине рассматриваемой области.

Пусть имеется область поиска (l, r). Предположим, что элементы множества – целые числа, возрастающие в арифметической прогрессии. Тогда искомый элемент должен находится в массиве (если он вообще там есть) под индексом

(Это следует из свойств арифметической прогрессии)

В этом элементе и будем брать пробу.

l := 1; r := n;while (l<>r) dobegin m := l+(r-l)*(Key-A[l])/(A[r]-A[l]); if Key>A[m] then l := m+1 else r := m;end;if A[l]=Key then <элемент найден> else <элемент не найден>;

Мы сделали очень большое допущение, предположив, что элементы массива представляют собой возрастающую арифметическую прогрессию. В реальности такая ситуация встречается редко. Но этот метод хорошо работает для любых пусть не идеально, но более-менее равномерно распределенных данных. Если же мы имеем дело с неравномерно распределенными данными, то интерполяционный поиск может увеличить число шагов по сравнению с дихотомическим поиском. Теоретическая сложность интерполяционного поиска – T(log(log(n))). Это, конечно, лучше, чем сложность дихотомического поиска, но эти преимущества становятся достаточно заметными лишь при очень больших значениях n. Практически на всех реальных n разница между дихотомическим и интерполяционным поиском по скорости не существенна.

Добавление и удаление можно реализовать так же, как при дихотомическом поиске. К этим операциям предъявляется то же требование: они должны сохранять массива отсортированным.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

Лабораторная работа выполняется на ПЭВМ.

Для получения результата необходимо сделать следующее:

1. Проанализировать исходные данные.

2. Разработать алгоритм и программу решения задачи

3. Произвести отладку программы при необходимости.

4. Создать отчет

КОНТРОЛЬНЫЕ ВОПРОСЫ

· Почему последний из разобранных методов поиска называется интерполяционным?

· Почему при хранении в списке невозможно воспользоваться дихотомическим и интерполяционным поиском?

· Почему операция удаления при хранении множества в списке в среднем в 2 раза медленнее, чем при хранении в неотсортированном массиве?.

Лабораторная работа №3

Динамические структуры

(очередь, список, стек).

Цель работы: Реализовать ввод и динамическую обработку данных. В программе должны быть предусмотрены соответствующие процедуры и функции, корректно обрабатывающие входные данные, распределение динамической памяти в «куче».

Время выполнения 6 часов.

ЗАДАНИЕ

§ Изучить методы работы с динамической и получить сведения о типовых динамических структурах (список, стек);

§ Разработать программу, реализующую работу с динамической структурой.

§ Произвести отладку программы путем ввода исходных данных и проверки корректности полученного результата;

§ Сделать отчет.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Динамическая память.

Динамическая память – это все оперативная память ПК, предоставляемая программе для работы, за вычетом сегмента данных (64 килобайта), стека (16 килобайт) и собственно тела программы. Размер динамической памяти может варьироваться в широких пределах и составляет, как правило, не менее 200-300 килобайт.

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

При работе с оперативной памятью происходит обращение к ее элементарным ячейкам – байтам, каждый из которых имеет свой собственный номер – адрес ячейки.

В языке Turbo Pascal применяется управление динамической памятью через указатели. Указатель – это переменная, значение которой представляет собой адрес байта памяти. В ПК адрес задается совокупностью двух шестнадцатеричных слов, называемых сегментом и смещением.

Сегмент – это участок памяти, имеющий длину 64 Кбайта и начинающийся с физического адреса, кратного 16 (т.е. 0, 16, 32 ,64 и т.д.). Смещение с свою очередь указывает, сколько байт от начала сегмента нужно пропустить, чтобы обратиться к нужному адресу.

Таким образом, по своей внутренней структуре любой указатель представляет собой совокупность двух слов, трактуемых как сегмент и смещение. С помощью указателей можно размещать в памяти любой из известных в Паскале типов данных.

Линейный связанный список

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

Основным преимуществом связанных структур по сравнению с массивами является гибкость структуры. Операции добавления и удаления элементов структуры, а также изменения порядка элементов, выполняются путем изменения связей между элементами и не требуют перемещения самих элементов. В то же время связанные структуры не позволяют выполнить операцию быстрого доступа к элементу по его номеру, которая является основной операцией для массивов. Кроме того, связанные структуры требуют больше памяти для хранения каждого элемента (из-за необходимости хранить связи), но зато позволяют обойтись без предварительного резервирования памяти «по максимуму», как в случае применения массива.

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

Элемент списка:

Элемент (узел) списка можно представить с использованием, например, таких типов данных:

Type

Element = ...;

Link = ^Node;

Node = record

Data: Element;

Next: Link;

Prev: Link;

end;

Здесь тип Element может означать практически что угодно: целое или вещественное число, строку символов, массив, запись, указатель и т.п. Тип Node представляет собой узел списка, а тип Link – связь с другим узлом. В данном случае это указатель на узел. Узел списка состоит из порции данных Data и связей со следующим и предыдущим узлами Next и Prev. Список, содержащий две связи, называется двунаправленным или двусвязным. Если присутствует только одна связь Next, список называется однонаправленным (односвязным).

Для представления списка, достаточно иметь указатель на первый узел (голову) списка. Поэтому список как тип данных не отличается от связи с узлом.

Type

List = Link;

Var

List1, List2: List;

Иногда бывает полезно иметь также указатель на последний элемент списка (хвост). В этом случае правильным будет такое описание типа списка:

Type

List = record

Head: Link; {Голова списка}

Tail: Link; {Хвост списка}

end;

При перемещении по списку нужно иметь способ проверки на достижение конца списка. Чаще всего признаком конца служит специальное значение указателя Next, например, значение nil.

Варианты структуры списков

Выше уже отмечалось, что линейные списки могут быть односвязными и двусвязными. Преимущества односвязных списков заключаются, во-первых, в меньшем расходе памяти, и, во-вторых, в меньшем числе операций при изменениях списка. В то же время большим недостатком односвязных списков является невозможность сделать «шаг назад», т.е. перейти от данного узла к предыдущему. Это затрудняет выполнение даже таких естественных операций, как удаление узла списка по заданному указателю или вставка нового узла перед указанным (хотя легко выполнить удаление или вставку после указанного узла). Двусвязные списки лишены этого недостатка.

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