книги / Технологии разработки объектно-ориентированных программ на язык C++. Основы структурного программирования на алгоритмическом языке C++

int mas[6];

for (int i = 0; i < 6; i++)

// Перенос элементов в массив mas[i] = qu.pop();

qu.pop(); // Удаление девятого элемента qu.pop(); // Удаление десятого элемента for (int i = 0; i < 6; i++)

// Перенос элементов в массив qu.push(mas[i]);

cout << "Очередь после удаления: "; qu.print(); // Печать очереди

for (int i = 0; i < 6; i++)

// Перенос элементов в массив mas[i] = qu.pop();

for (int i = 0; i < 3; i++)

// Добавление первой половины из массива qu.push(mas[i]);

for (int i = 0; i < 3; i++)

// Добавление новых элементов qu.push(rand()%10 + 1);

for (int i = 3; i < 6; i++)

// Добавление второй половины из массива qu.push(mas[i]);

cout << "Очередь после добавления: "; qu.print(); // Печать очереди

return 0;

}

Пример выполнения работы программы:

9 9 7 1 2 9 8 9 8 7

Очередь после удаления: 7 1 2 9 8 9 Очередь после добавления: 7 1 2 2 7 6 9 8 9

Задание для самостоятельной работы:

Реализовать очередь из n элементов (вводится пользователем) тремя способами. Написать программу, которая удаляет все четные элементы и добавляет три новых элемента в конец и в начало очереди.

171

Глава 15. СОРТИРОВКА И ПОИСК

15.1. Поиск в линейных структурах

Полный перебор – простейший алгоритм поиска. Массив просматривается последовательно от первого до последнего элемента. Худший случай – слова нет в массиве, тогда вывод можно сделать после просмотра всего массива.

Достоинство – простота реализации. Недостаток – длительное время работы программы.

Алгоритм последовательного поиска:

Шаг 1. Начальное значение переменной цикла i = 0.

Шаг 2. Если значение элемента массива x[i] равно значению ключа key, по которому ищут переменную, то возвращется значение, равное номеру искомого элемента, и алгоритм завершает работу. В противном случае значение переменной цикла увеличивается на единицу: i = i + 1.

Шаг 3. Если i < k, где k – число элементов массива х, то выполняется шаг 2, в противном случае – работа алгоритма завершена

ивозвращается значение, равное –1. При наличии в массиве нескольких элементов со значением key алгоритм находит только первый из них (с наименьшим индексом) [25].

Далее рассмотрим код программы на C++:

int SeqSearch(int *mas, int size, int key) { for (int i = 0; i < size; i++) {

// Просматриваются все элементы в цикле if (m[i] == key)

//Если находится элемент со значением key, return i;

//Возвращается его индекс

}

return –1;

// Если элемент не найден, то возвращается –1

}

172

15.2. Поиск в упорядоченных структурах

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

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

Например:

Шаг 1. Определить номер среднего элемента массива mid =

=(ri + le) / 2, где ri и le – это текущие границы множества.

Шаг 2. Если значение элемента, находящегося посередине массива, равно искомому, то элемент считается найденным, его номер фиксируется и алгоритм завершает работу.

Шаг 3. Если искомое значение больше значения элемента, находящегося посередине массива, то этот элемент становится новой левой границей, и далее поиск будет производиться на этой половине, иначе же текущий элемент становится новой правой границей. Затем необходимо вернуться к шагу 1.

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

Например, в массиве целых чисел a = {1, 3, 3, 3, 3, 3, 3, 9, 18} с ключом key = 3 совпадет элемент с порядковым номером 4, который не относится ни к первому, ни к последнему (рис. 15.1).

Рассмотрим код для данного вида поиска:

//Описание функции бинарного поиска

int BinSearch(int *mas, int size, int key){ /* Указатель на массив, количество

173

элементов и ключ */

bool flag = false; // Найден ли необходимый элемент? int ri = size – 1, le = 0; // Начальные границы

int mid = (ri + le) / 2; // Среднее значение

while ( !flag && ri >= le ){ /* Пока элемент не найден или не просмотрен весь массив

*/

if (key == x[mid])// Если это искомое значение flag = true; // Элемент найден

else if (key < x[mid]) // Иначе смещаем границы ri = mid – 1; // Новая правая граница

else

le = mid + 1; // Или новая левая граница mid = (ri + le) / 2; // Новое среднее значение

}

if (flag) return mid; // Если элемент найден, возвращаем его номер

else return –1; // Иначе –1

}

Рис. 15.1. Демонстрация алгоритма бинарного поиска

В процессе работы алгоритма бинарного поиска фрагмент будет стабильно уменьшаться в два раза. Ввиду этого достоинством данного алгоритма является достаточно большая скорость выполнения поиска по сравнению с алгоритмом последовательного поиска. Недостаток же заключается в том, что бинарный поиск может применяться только на упорядоченном множестве [25].

174

15.3. Поиск в массивах

Существуют задачи, в которых приходится производить поиск

вопределенном множестве и на определенных условиях. Для таких случаев существует еще один метод поиска – поиск с возвратом.

Поиск с возвратом – общий метод нахождения решений задачи,

вкотором реализуется полный перебор всех возможных вариантов

внекотором множестве Z.

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

Метод поиска с возвратом является универсальным: легко проектировать и программировать алгоритмы решения задач с использованием этого метода. Однако время нахождения решения может быть очень велико даже при небольшом количестве исходных данных. Исходя из этого при проектировании таких алгоритмов обязательно нужно оценивать время их работы на конкретных данных.

Примером использования алгоритма поиска с возвратом является задача о восьми ферзях.

Задача: расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого (рис. 15.2).

Рис. 15.2. Пример одного из решений задачи

175

Алгоритм решения:

Необходимо реализовать две функции: поставить ферзя и убрать ферзя. Первая будет ставить в заданную клетку ферзя, а во все остальные отмечать, что они находятся под боем. Вторая аналогично будет убирать ферзя и клетки шахматной доски, находящиеся под боем. Помимо этого должна быть функция, которая выбирает, куда поставить ферзей, которая поочередно проходит линии и ставит ферзей так, чтобы они находились не под боем. Но если на ка- кой-то линии функция уже не может поставить ферзя, то она возвращается на шаг назад, убирает предыдущего ферзя и пытается поставить его на другое место. И так до тех пор, пока все ферзи не займут места [25].

Код программы на C++:

for (int x = 0; x < 8; ++x) {

// Устанавливаем клетки, где ферзь бьет

foo = j – i + x;

if (foo >= 0 && foo < 8) ++board[x][foo];

foo = j + i – x;

if (foo >= 0 && foo < 8)

// Аналогично предыдущей функции убираем ферзя и клетки боя void reset_queen(int i, int j) {

for (int x = 0; x < 8; ++x) {

176

--board[x][foo]; foo = j + i – x;

if (foo >= 0 && foo < 8)

bool result = false;

for (int j = 0; j < 8; ++j) { // Для каждой линии по очереди

if (board[i][j] == 0) { // Если клетка пустая и не под боем

setQueen(i, j); // Ставим ферзя if (i == 7)

/*

Если это восьмой столбик (в массивах номера от 0 до 7, поэтому это последний столбик)

*/

result = true; // То все расставлено else { // Иначе надо продолжать

//Запускаем функцию для следующего столбика

if (!(result = tryQueen(i + 1)))

/*

Если не получилось поставить в следующий столбик

*/

reset_queen(i, j); }

//Убираем этого ферзя и продолжаем пытаться

}

if (result) // Если все поставлено break; // Закончить цикл на

текущей линии

177

}

return result;

}

int main() {

for (int i = 0; i < 8; ++i) // Сначала обнуляем все

постановки ферзя for (int i = 0; i < 8; ++i) { // Выводим все содер

жимое доски for (int j = 0; j < 8; ++j) {

if (board[i][j] == –1)

cout <<"[]"; // Так выводится ферзь

else

cout <<". "; // А так пустые клетки

}

cout << endl;

}

system("pause");

}

15.4. Поиск подстроки в строке

Существует три основных способа поиска подстроки в строке. Рассмотрим каждый из них.

Прямой поиск в строке

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

Основная идея алгоритма заключается в посимвольном сравнении строки с подстрокой. Вначале происходит сравнение первого символа строки с первым символом подстроки, второго символа строки со вторым символом подстроки и т.д. Если произошло совпадение всех символов, то подстрока найдена. Иначе производится сдвиг подстроки на одну позицию вправо и повторяется посимволь-

178

ное сравнение, т.е. сравнивается второй символ строки с первым символом подстроки, третий символ строки со вторым символом подстроки и т.д. Сдвиги происходят до тех пор, пока подстрока не будет найдена или не дойдет до конца строки [2].

Рис. 15.3. Алгоритм прямого поиска

Данный алгоритм занимает много времени. Код программы на C++:

int search(char *str, char *obr) { // На вход строка и подстрока

int sl, ssl; int res = –1;

sl = strlen(str); // Считаем длину строки ssl = strlen(obr); // И длину подстроки

if (sl == 0) // Проверка, есть ли строка и подстрока cout <<"Неверно задана строка\n";

else if (ssl == 0)

cout <<"Неверно задана подстрока\n"; else // Если все верно

for (int i = 0; i < sl – ssl + 1; i++)

// Проходим по очереди

179

for (int j = 0; j < ssl; j++) if (obr[j] != str[i + j])

//Начинаем сравнение break;

//Если не совпало, текущий цикл прервать

else if (j == ssl – 1) {

// Если это был последний символ в подстроке

res = i;

// То строка найдена break;

}

return res;

// Возвращаем позицию начала строки

}

Алгоритм Кнута, Морриса и Пратта

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

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

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

Пример для ababcaba приведен на рис. 15.4.

180