Тема 10. Примеры программирования. Примеры алгоритмов.

Сортировка обменами(пузырьком). Шаг сортировки состоит в проходе снизу вверх по массиву. После первого прохода по массиву “сверху” оказывается самый легкий(минимальный)элемент-отсюда аналогия с пузырьками. Следующий проход делается до второго сверху элемента, т о, второй по величине элемент поднимается на правильную позицию и т д. Сортировка выбором. Нужно найти элемент массива, имеющий наименьшее значение, переставить его с первым элементом, затем проделать тоже самое, начав со второго элемента и т д .Сортировка простыми вставками. Просматривается массив и каждый новый элемент a[i] вставляется на подходящее место в уже упорядоченную совокупность a[1],…,a[i-1]. Это место определяется последовательным сравнением a[i] с упорядоченными элементами a[1],..,a[i-1]. Т. о. в начале массива вырастает отсортированная последовательность. Алгоритмы поиска. Задача найти элемент и его координаты с указанным значением в массиве решается алгоритмом линейного поиска, когда последовательно проходится весь массив и текущий элемент массива сравнивается с искомым элементом. В случае совпадения запоминается индекс(ы) найденного элемента. Поиск подстроки в тексте(строке).Алгоритм грубой силы. Задача поиска заключается в том, чтобы определить, содержит ли строка заданный образец и указать место(индекс) в строке, если совпадение найдено. Алгоритм Бойера-Мура. На первом шаге строится таблица смещений для искомого образца. Далее совмещается начало строки и образца и начинается проверка с последнего символа образца. Если же символы совпадают, производится сравнение, начиная с последнего символа образца и т д.Если все символы образца совпали с наложенными символами строки, значит найдена подстрока и поиск окончен. Бинарный(двоичный)поиск. Бинарный поиск используется в том случае, если массив, в котором осуществляется поиск, уже упорядочен. Поиск начинается всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, то нужно перейти к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. В результате каждой проверки вдвое сужается область поиска. Динамические структуры данных характеризуются непостоянством и непредсказуемостью размера структуры в процессе ее обработки. Для установления связи между элементами динамической структуры используются указатели, через которые устанавливаются явные связи между элементами. Элемент динамической структуры состоит из двух полей: 1) информационного поля или поля данных, в котором содержатся те данные, ради которых и создается структура;

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

К динамическим структурам, используемым в программировании, относятся:

1)линейные списки 2)стек 3)очередь, дек 4)деревья

Линейные списки. Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным. Длина списка равна числу элементов, содержащихся в списке, список нулевой длины называется пустым списком.

При работе с линейными списками используются следующие основные операции: создание списка; добавление нового элемента в список; в голову списка, в хвост списка; удаление элемента из списка; обход списка с целью его обработки; поиск узла в списке; переход на узел в списке по номеру от начала и другие операции

Создание цикла. 1)выделить память 2)обнулить указатели на предыдущий и последующий элементы 3) определить указатели на голову, хвост и текущий элемент списка 4) внести в информационную часть списка данные При удалении узла из списка нужно рассмотреть следующие ситуации: 1)удаляемый узел является головой списка 2)удаляемый узел является хвостом списка 3) удаляемый узел единственный в списке 4)удаляемый узел не является ни головой, ни хвостом, ни единственный в списке. Алгоритм обхода списка:1)выполнять в цикле2)обработать текущий узел3)перейти к следующему узлу 4)до тех пор пока указатель на следующий узел станет пустым. Стеком называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним.

Стек должен поддерживать следующие операции:

push-добавить в верхушку стека новый элемент;pop-извлечь из верхушки стека элемент; isEmpty - проверка, пуст ли стек;top-узнать значение верхушки стека.

size-узнать количество элементов в стеке;clear-очистить стек. Обратная польская запись(ОПЗ)-способ записи выражений в так называемом постфиксном виде. Алгоритм Дейкстры:1)исходная строка просматривается посимвольно 2) если встречается символ операция, то эта операция при определенных условиях помещается в стек 3)Если встречаются символы операндов, то они из входной строки поступают сразу в выходную строку

4)если встречается открывающаяся скобка, то она всегда помещается в стек

5)закрывающаяся скобка ни в стек, ни в выходную строку не помещается.

Очередью называется структура данных, в которой элементы кладутся в конец, а извлекаются из начала. Т о, первым из очереди будет извлечен тот элемент, который будет добавлен раньше говорит. Деком называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дерево-конечное множество Т, состоящее из одного или более узлов таких, что:1)имеется один узел, называемый корнем дерева 2)остальные узлы, исключая корень, содержатся попарно в m≥0 попарно пересекающихся множествах T1, T2,..Tn, каждое из которых в свою очередь является деревом. Обход дерева-последовательный обход всех узлов дерева. Существуют три способа обхода:обход с префиксным порядком, обход с инфиксным порядком, обход с суффиксным порядком.