А. В. МАЕР, О. С. ЧЕРЕПАНОВ ВВЕДЕНИЕ В CTPYKTYPbl И АЛГОРИТМЬI ОБРАБОТКИ ДАННЬIХ УЧЕБНОЕ ПОСОБИЕ МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждение высшего образования «Курганский государственный университет» А. В. Маер, О. С. Черепанов ВВЕДЕНИЕ В СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ Учебное пособие Курган 2021 (075.8) я73 М 13 Рецензенты: кандидат технических наук, доцент кафедры «Автоматизация и робототехника» ФГБОУ ВО «Омский государственный технический университет» М. С. Пешка; кандидат физико-математических «Оптико-электронных Национальный систем наук, доцент дистанционного исследовательский «Томский кафедры зондирования» государственный университет» Л. Г. Шаманаева. Печатается решению методического совета Курганского государственного университета. Маер А. В., Черепанов О. С. Введение в структуры и алгоритмы обработки данных : учебное пособие/ А. В. Маер, О. С. Черепанов. - Курган : Изд-во Курганского гос. ун-та, 2021. - 107 с. Учебное пособие состоит из пяти глав. Целью учебного пособия является формирование начального представления структурах данных и алгоритмах. В первой главе дается обзор математического аппарата, используемого при анализе алгоритмов. Во второй главе вводится понятие псевдокода. Третья глава посвящена основным структурам данных. В четвертой главе проводится анализ алгоритмов и выполняется их построение с помощью псевдокода. Пятая глава содержит набор заданий для выполнения учебных проектов. Учебное пособие предназначено для студентов направлений , , , . © Курганский государственный университет,2021 © Маер А. В., Черепанов О. С., 2021 СОДЕРЖАНИЕ ВВЕДЕНИЕ .............................................................................................................................. 4 1 НЕКОТОРЫЕ МАТЕМАТИЧЕСКИЕ ОБОЗНАЧЕНИЯ ........................................... 5 1.1 Асимптотические обозначения ............................................................................. 5 1.2 Стандартные функции и обозначения .................................................................. 9 2 ПСЕВДОКОД ..................................................................................................................... 13 3 СТРУКТУРЫ ДАННЫХ ................................................................................................. 16 3.1 Кучи ....................................................................................................................... 18 3.1.1 Сохранение основного свойства кучи ....................................................... 20 3.1.2 Построение кучи ........................................................................................ 21 3 .2 Стеки и очереди .................................................................................................... 23 3.2.1 Стеки ........................................................................................................... 24 3.2.2 Очереди ........................................................................................................ 25 3.3 Связанные списки ................................................................................................. 27 3.4 Корневые деревья ................................................................................................. 29 4 АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ ..................................................................... 32 4.1 Сортировки во внутренней памяти ..................................................................... 33 4.1.1 Сортировка слиянием ................................................................................ 34 4.1.2 Сортировка с помощью кучи .................................................................... 36 4.1.3 Быстрая сортировка ................................................................................. 37 4.1.4 Сортировка подсчетом ............................................................................. 40 4.2 Сортировки во внешней памяти .......................................................................... 42 4.2.1 Прямое слияние ........................................................................................... 43 4.2.2 Естественное слияние ............................................................................... 44 4.2.3 Многопутевое слияние ............................................................................... 46 4.3 Поиск подстрок ..................................................................................................... 47 4.3.1 Простейший алгоритм .............................................................................. 49 4.3.2 Алгоритм Рабина-Карпа ........................................................................... 50 4.3.3 Алгоритм Кнута-Морриса-Пратта ........................................................ 53 4.4 Базовые алгоритмы на графах ............................................................................. 56 4.4.1 Поиск в ширину ........................................................................................... 56 4.4.2 Поиск в глубину ........................................................................................... 59 4.5 Двоичные деревья поиска .................................................................................... 62 5 ЛАБОРАТОРНЫЙ ПРАКТИКУМ ................................................................................ 70 5 .1 Лабораторная работа № 1 .................................................................................... 70 5.2 Лабораторная работа № 2 .................................................................................... 73 5 .3 Лабораторная работа № 3 .................................................................................... 80 5 .4 Лабораторная работа № 4 .................................................................................... 86 5 .5 Лабораторная работа № 5 .................................................................................... 90 5.6 Лабораторная работа № 6 .................................................................................... 95 БИБЛИОГРАФИЧЕСКИЙ СПИСОК ........................................................................... 106 ВВЕДЕНИЕ Учебное пособие подходит в качестве первого знакомства со структурами данных алгоритмами. нем проводится анализ современных и наиболее популярных алгоритмов. При построении алгоритмов использован наиболее эффективный (по мнению авторов) инструмент псевдокод. Описание алгоритмов выполнено максимально просто, чтобы читатель с минимальной подготовкой мог воспользоваться данным учебным пособием. Последний раздел посвящен практическим заданиям, которые можно выполнить после знакомства с теоретической частью пособия. Материал изложен таким образом, студентам-бакалаврам технических специальностей. будет полезен 1 НЕКОТОРЫЕ МАТЕМАТИЧЕСКИЕ ОБОЗНАЧЕНИЯ Анализируя алгоритм, можно стараться найти точное число выполняемых им действий. Но в большинстве случаев игра не стоит свеч, достаточно оценить асимптотику роста времени работы алгоритма при стремлении размера входа к бесконечности. Если у одного алгоритма скорость роста меньше, чем другого, большинстве случаев он будет эффективнее для всех входов, кроме совсем коротких (хотя бывают и исключения). 1.1 Асимптотические обозначения Хотя многих случаях эти обозначения используются неформально, полезно начать с точных определений. В-обозначение. Например, время Т ( п) работы алгоритма на входах длины п есть В(п 2 ). Точный смысл этого утверждения такой: найдутся такие константы с 1 , с 2 > О и такое число п 0 , что с 1 n 2 < Т ( п) < с 2 п 2 при всех п > п 0 . Вообще, если g ( п) - некоторая функция, то запись f(n) = B(g(n)) означает, что найдутся такие с 1 , с 2 > О и такое п 0 , что О < c1 g(n) < f (п) < c2 g(n) для всех п > п 0 (рисунок 1.1). (Запись f(n) = B(g(n)) читается так: «Эф от эн есть тэта от же от эн»). co(n) J(n) f(n) cg(n) ------ n L------ n ~ ~ ~ - -- - n (а) (б) (в) J(n) = 0 (g(n)) nil / (n) = O(g(n)) Пi! J( n) = (g(n) ) Рисунок 1.1-Иллюстрация к определениям f(n) = B(g(n)), f(n) = O(g(n)) и f(n) = fl(g(n)) Разумеется, это обозначение следует употреблять с осторожностью: установив, [ 1 (п) = B(g(n)) заключать, что [ 1 ( п) = [ 2 ( п) ! f 2 (n) = B(g(n)), следует Определение асимптотически fJ(g(n)) предполагает, что функции f(п)и g(n) неотрицательны достаточно больших значений п. Заметим, что если функции f иg строго неотрицательны, положительны, можно исключить определения (изменив константы с 1 и с 2 так, чтобы для малых п неравенство также выполнялось). f (п) = fJ(g(n)), Если асимптотически точной говорят, является g(n) f(n). На самом деле это отношение симметрично: если f(n) = fJ(g(n)), то g(n) = fJ(f (п)). Например, оценкой проверим, (}) n 2 - Зn = fJ(n 2 ). Согласно определению, надо указать положительные константы с 1 , с 2 и число п 0 так, чтобы неравенство c1 n 2 < .!.п - Зn < c2 n выполнялось для всех > п0 . выполнения Разделим второго неравенства < -12 - -п3 < с2 . достаточно Первое будет выполнено, если (например) п 0 = Другой пример использования Видно, положить = 1/2. 7 и с 1 = 1/14. формального определения: покажем, что бn 3 =f=. fJ(n 2 ). В самом деле, пусть найдутся такие с 2 и п 0 , что бn 3 < c2 n 2 для всех п > п 0 . Но тогда п < с 2 /6 для всех > п 0 , что явно не так. Отыскивая асимптотически точную оценку суммы, можем отбрасывать члены меньшего порядка, которые при больших п становятся малыми по сравнению с основным слагаемым. Заметим также, что коэффициент при старшем члене роли не играет (он может повлиять только на выбор констант с 1 и с 2 ). Например, рассмотрим квадратичную функцию f (п) константы > О. = ап + Ьп + с, где а, Ь, с - некоторые Отбрасывая члены младших коэффициент при старшем члене, находим, что f(n) порядков = fJ(n 2 ). Чтобы убедиться в этом формально, можно положить с 1 = а/4, с 2 = 7а/4 и по = 2 * max((lbl/a), c-Jlcl/a)) действительно выполнены). (проверьте, требования Вообще, для любого полинома р(п) степени d с положительным старшим коэффициентом имеем р(п) fJ(nd). Упомянем важный частный случай использования 0-обозна чений: 0(1) обозначает ограниченную функцию, отделенную от нуля некоторой положительной константой значениях аргумента контекста (из при достаточно больших обычно ясно, именно считается аргументом функции). О- и '1-обозначения. Запись f (п) = fJ(g(n)) включает в себя две оценки: верхнюю и нижнюю. Их можно разделить. Говорят, что f(n) = O(g(n)), если найдется такая константа с> О и такое число n 0 , что О < f (п) < cg(n) для всех п > п 0 . Говорят, что f(n) = fl (g ( п)), если найдется такая константа с > О и такое число п 0 , что О< cg(n) < f(n) для всех п > п 0 . Эти записи читаются так: «Эф от эн есть о большое от же от эн», «Эф от эн есть омега большая от же от эн». По-прежнему предполагаем, функции неотрицательны для достаточно больших значений аргумента. Для этих функций выполняются следующие свойства. = fJ(g(n)) Для любых двух функций f(n) и g(n) свойство f(n) выполнено тогда и только тогда, когда f(n) = O(g(n)) и f(n) = fl(g(n)). Для любых двух функций свойства f ( п) = О (g ( п)) и g ( п) = fl (f ( п)) равносильны. Как мы видели, ап 2 + Ьп +с= fJ(n 2) (при положительных а). Поэтому ап 2 + Ьп +с= О(п 2 ). Другой пример: при а> О можно написать ап + Ь = О(п 2 ) (положим с= а+ lbl и п 0 = 1). Заметим, что в этом случае ап + Ь -=f=. fl(n 2 ) и ап + Ь -=f=. fJ(n 2). Асимптотические обозначения внутри формул. Например, (fJ, О и fl) часто употребляются рекуррентное соотношение Т(п) 2Т (~) + fJ(n) для времени работы сортировки слиянием. Здесь fJ(n) обозначает некоторую функцию, про которую нам важно знать лишь, она меньше с1 п больше с2 п некоторых положительных с 1 и с 2 и для всех достаточно больших п. Часто асимптотические обозначения употребляются не вполне формально, хотя подразумеваемый смысл обычно контекста. Например, мы можем написать выражение ясен Lf= 1 O(i), имея в виду сумму h(l) + h(2) + ··· + h(n), где h(i) - некоторая функция, h(i) = O(i). функция от п есть O(n 2). для которой Легко видеть, что сама эта сумма как Типичный пример использования чений - цепочка равенств наподобие асимптотических обозна 2n 2 + Зn + 1 = 2n 2 + В(п) = В(п 2 ). Второе из этих равенств (2n 2 + В(п) = В(п 2 )) понимается при этом так: какова бы ни была функция h(n) = В(п) в левой части, сумма 2n 2 + h(n) есть В(п 2 ). о- и оо-обозначения. Запись f (п) = O(g(n)) означает, что с ростом п отношение f(n)/ g(n) остается ограниченным. Если к тому же limп-ю) f(n) = О, то мы пишем f(n) = o(g(n)), если для всякого g(n) положительного Е > О найдется такое п 0 , что О < f(n) < Eg(n) при всех п > п 0 (тем самым запись f (п) = o(g(n)) предполагает, что f(n) и g(n) неотрицательны для достаточно больших n). Например, 2n = о(п 2 ), но 2n 2 -=!=- о(п 2 ). Аналогичным образом вводится со-обозначение: говорят, что f (п) есть uJ(g(n)) («Эф от эн есть омега малая от же от эн»), если для любого положительного с существует такое п 0 , что О < cg(n) < f (п) при всех п > п 0 . Другими словами, f(n) = uJ(g(n)) означает, что g(n) = o(f (п)). Например, - = uJ(n), но - -=!=- uJ(n 2 ). Сравнение функций. Введенные нами определения обладают некоторыми свойствами транзитивности, рефлексивности симметричности. Транзитивность: f(n) = B(g(n)) и g(n) = B(h(n)) влечет f(n) = B(h(n)), f(n) = O(g(n)) и g(n) = O(h(n)) влечет f(n) = O(h(n)), f (п) = fl(g(n)) и g(n) = fl(h(n)) влечет f (п) = fl(h(n)), f(n) = o(g(n)) и g(n) = o(h(n)) влечет f(n) = o(h(n)), f (п) = uJ(g(n)) и g(n) = uJ(h(n)) влечет f (п) = uJ(h(n)). Рефлексивность: f(n) = B(f (п)), f(n) = O(f (п)), f(n) = fl(f (п)). Симметричность: f(n) = B(g(n)) если и только если g(n) = B(f (п)). Обращение: f(n) = O(g(n)) если и только если g(n) = fl(f (п)). f(n) = o(g(n)) если и только если g(n) = uJ(f (п)). Можно провести такую параллель: отношения функциями f и g подобны отношениям между числами а и Ь: между f (п) = O(g(n)) ~ а < Ь, f (п) = n(g(n)) ~ а > Ь, f (п) = e(g(n)) ~ а = Ь, f (п) = o(g(n)) ~ а < Ь, f (п) = uJ(g(n)) ~ а > Ь. Параллель эта, впрочем, весьма условна: свойства числовых неравенств не переносятся на функции. Например, для любых двух чисел а и Ь всегда или а < Ь, или а < Ь, однако нельзя утверждать, что для любых двух (положительных) функций f(n) = O(g(n) ), или f(n) = n(g(n) ). f(n) самом g(n) или деле, можно проверить, что ни одно из этих двух соотношений не выполнено для f(n) =пи g(n) = n 1 +sinn (показатель степени в выражении для g(n) меняется в интервале от О до 2). Заметим еще, что для чисел а < Ь влечет а< Ь или а= Ь, в то время как для функций f (п) = O(g(n)) не влечет f(n) = o(g(n)) или f(n) = e(g(n) ). 1.2 Стандартные функции и обозначения Монотонность. Говорят, функция f(n) монотонно возрастает, если f(m) < f(n) при m < п. Говорят, что функция f(n) монотонно убывает, если m < п. Говорят, что функция f(n) строго возрастает, если f(m) < f(n) при m < п. Говорят, что функция f (п) строго убывает, если f(m) > f(n) при m f (п) приближения снизу при сверху. Для любого вещественного числах через lxJ мы обозначаем его целую часть, т. е. наибольшее целое число, превосходящее Симметричным rх l обозначает наименьшее целое число, не меньшее х. Очевидно, х -1 < lxJ < х < rxl < х + 1 для любого х. Кроме того, rn/21 + ln/2J = п для любого целого п. Наконец, для любого х и для любых целых положительных а и ь имеем rrx/al/b l = rx/ab l и образом llх / а J/ Ь J = lх / аЬ J (чтобы убедиться в этом, полезно заметить, что для любого z и для целого п свойства п < z и п < Функции хн lxJ их н rx l монотонно возрастают. lzJ равносильны).