Структуры и алгоритмы обработки данных. Часть I. Учебное пособие А.Н. БАУШЕВ

Настоящее пособие представляет собой первую часть планируемого кафедрой «Информационные и вычислительные системы» трёхчастного учебного пособия по изучению дисциплины «Структуры и алгоритмы обработки данных» для различных направлений подготовки бакалавров.

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

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

Из множества структур данных, встречающихся на практике, автор включил в класс «элементарных» наиболее простые: стек, очередь и список. Более сложные структуры данных и алгоритмы для работы с ними будут рассмотрены во второй части пособия. С неформальной точки зрения, структура данных – это множество (данных), элементы которого снабжены множеством ссылок либо на другие данные (элементы множества), либо (и) на элементы некоторого другого множества – множества признаков (или характеристик) рассматриваемого элемента, либо (и) на другие структуры данных или их элементы. Простота или сложность структуры данных определяется, по существу, простотой или сложностью ссылочной модели, описывающей структуру ссылок для каждого элемента данных. Чем проще ссылочная модель, тем проще решается задача поддержания структуры данных при выполнении основных операций на этих структурах, каковыми являются добавление элемента, поиск элемента, удаление элемента, замена элемента.

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

В современных научных статьях и монографиях, посвящённых алгоритмам ([1], [2]), алгоритмы описываются в псевдокодах. Использование псевдокодов вызвано желанием авторов подчеркнуть независимость изучаемых объектов (алгоритмов и структур данных) от языков программирования. Однако в учебной практике такой подход неудобен, поскольку для реализации алгоритмов так или иначе приходится использовать какой-либо язык программирования. Поэтому в данном пособии для описания алгоритмов используется язык программирования системы MATLAB, на котором студенты выполняют лабораторные задания. Этот язык прост и прозрачен и, кроме того, не требует объявления типов переменных. Поэтому программы, написанные на нём и не использующие специфических возможностей системы MATLAB, можно, при желании, рассматривать как псевдокоды алгоритмов.

Настоящее пособие написано на основании многолетнего опыта преподавания дисциплины «Структуры и алгоритмы обработки данных» преподавателями кафедры «Информационные и вычислительные системы» ПГУПС. Автор выражаeт благодарность проф. А.Д. Хомоненко, который является инициатором написания данного пособия, и который предоставил автору презентации своих лекций по этой дисциплине.