Структуры данных и основные алгоритмы их обработки

Т.Н. Варфоломеева

СТРУКТУРЫ ДАННЫХ  
И ОСНОВНЫЕ АЛГОРИТМЫ 
ИХ ОБРАБОТКИ 

Учебное пособие 

2-е издание, стереотипное

Москва 
Издательство «ФЛИНТА» 
2023

УДК 004 
ББК  65.29:32.97 
В18 

Рецензент

канд. техн. наук, доцент МГТУ им. Г.И. Носова 
С.А. Повитухин 

В18 

Варфоломеева Т.Н.
Структуры данных и основные алгоритмы их обработки : учебное 
пособие / Т.Н. Варфоломеева. — 2-е изд., стер. — Москва : 
ФЛИНТА, 2023. — 159 с. —  ISBN 978-5-9765-3691-3. — Текст : 
электронный.

Даны основные сведения о 
структурах данных, рассмотрены 
алгоритмы работы с различными структурами данных. В пособии 
произведен подбор упражнений для отработки навыков по использованию 
алгоритмов.  
Оно адресовано студентам очного и заочного отделений высших 
учебных заведений, обучающихся по направлениям подготовки: 38.03.05 
Бизнес-информатика; 
09.03.03 
Прикладная 
информатика; 
44.03.05 
Педагогическое 
образование 
(профиль 
программы 
Информатика 
и 
экономика). Может быть полезно всем изучающим основы алгоритмизации 
и программирования. 

УДК 004 
ББК  65.29:32.97 

        ISBN 978-5-9765-3691-3
© Варфоломеева Т.Н., 2017 
 © Издательство «ФЛИНТА», 2017 

Оглавление
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ..............................................................4

1. ОСНОВНЫЕ ПОНЯТИЯ И СВОЙСТВА СТРУКТУР ДАННЫХ.................................4
2. СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ ............................................................10

2.1. Простая переменная..............................................................................10
2.2. Массивы .................................................................................................20
Разбор задач на одномерные массивы.......................................................44
Тестовые задания ........................................................................................49
Разбор задач на двумерные массивы .........................................................55
Тестовые задания ........................................................................................57

3. ПОЛУДИНАМИЧЕСКИЕ И ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ .................69

3.1. Стеки.......................................................................................................70
3.2. Очередь ..................................................................................................77
3.3. Списки....................................................................................................80
3.4. Таблицы..................................................................................................84
3.5. Графы .....................................................................................................88
3.6. Деревья...................................................................................................97

ОСНОВНЫЕ АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ...............................118

1. ПОЛУЧИСЛЕННЫЕ АЛГОРИТМЫ ..................................................................118
2. КОМБИНАТОРНЫЕ АЛГОРИТМЫ ..................................................................124

2.1. Размещения с повторениями..............................................................125
2.2. Перестановки.......................................................................................125
2.3. Сочетания.............................................................................................126
2.4. Композиции и разбиения целых чисел .............................................127

СИНТАКСИЧЕСКИЕ АЛГОРИТМЫ. ЛЕКСИКОГРАФИЧЕСКИЙ ПОИСК. 

МЕТОДЫ ГРАММАТИЧЕСКОГО РАЗБОРА.............................................134

1. ОСНОВНЫЕ ПРИНЦИПЫ ФОРМАЛЬНОЙ ГРАММАТИКИ ................................135
2. АНАЛИЗ ПРЕДЛОЖЕНИЙ..............................................................................138

Тестовые задания.............................................................................................142

Список используемой литературы.................................................................157

ИНФОРМАЦИОННЫЕ СТРУКТУРЫ

1. Основные понятия и свойства структур данных

Задачи, решаемые на ПК, являются математическими моделями процессов 

или явлений реальной жизни. В математической модели находят отражение 

наиболее существенные связи между реальными объектами. Модели реальных 

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

обработки которых и описывается с помощью алгоритмов.

Df: Структуры данных - совокупность элементов информации, находящих-

ся в определенной, заранее заданной взаимосвязи.

Существует следующая общая классификация данных:

• статически размещаемые данные (статические данные);

• динамически размещаемые данные (динамические данные).

Df: Статические структуры - такие структуры, размеры которых не могут

изменяться в ходе выполнения программы.

Df: Динамические структуры - такие структуры, размеры которых могут 

изменяться в процессе работы программы.

Свойства структур данных

1. Структуры делятся на линейные и нелинейные. В линейных структурах

элементы не зависят друг от друга. К линейным структурам относятся массивы, 

стек, очередь, некоторые виды таблиц. В нелинейных структурах связь между 

элементами определяется отношениями подчинения или какими-либо логиче-

скими условиями. К нелинейным структурам относятся деревья, графы, списки.

2. Структуры делятся на структуры фиксированного и переменного разме-

ра. Структуры фиксированного размера после создания не позволяют включать 

или исключать записи, а позволяют лишь их корректировать. Примером структу-

ры такого типа является массив. Структуры переменного размера позволяют 

включать и исключать записи. В процессе обработки они динамически изменя-

ются (очередь).

3. Структуры делятся на структуры с произвольным доступом к элементам 

и с последовательным доступом к строго определенному элементу. Примером 

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

очередь, стек. 

4. Структуры данных могут быть однородными и неоднородными. В одно-

родных структурах все записи являются элементами одного типа. В неоднород-

ных структурах элементы одной записи могут быть структурами разных типов 

(модель классного журнала).

Выбор структуры данных определяет совокупность типовых алгоритмов, 

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

шем при рассмотрении каждой информационной структуры будем приводить 

связанные с ней типовые алгоритмы обработки.

Анализ сложности и эффективности алгоритмов

Структуры данных

статические
динамические

Линейные

списки

Нелинейные

списки

графы

деревья

стек

таблица

очередь

С ограниченным 
доступом к эле-

ментам

однонаправлен-

ный

закольцован-

ный

двунаправлен-

ный

Без ограничения доступа 
к элементам

массивы

простая переменная

Эффективность алгоритма является очень важной его характеристикой. Ка-

залось, что рост скорости вычислений уменьшит значение эффективности алго-

ритмов. Однако это не так. Если две программы реализуют идентичные функции, 

но различными алгоритмами, то та, которая использует меньший объем памяти, 

характеризуется большей пространственной эффективностью. Иногда память 

становится доминирующим фактором в оценке эффективности программ. Однако 

в последнее время в связи с быстрым ее удешевлением эта составляющая эффек-

тивности постепенно теряет свое значение. На сегодняшний день ограничения по 

времени является доминирующим фактором, определяющим пригодность кон-

кретного алгоритма для практики.

Вопросы эффективности настолько важны, что их исследование выдели-

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

Рассмотрим основные понятия, связанные с анализом  сложности алгорит-

мов.  

Под трудоёмкостью алгоритма для данного конкретного входа – (N), бу-

дем понимать количество «элементарных» операций, совершаемых алгоритмом 

для решения конкретной проблемы в данной формальной системе.

Оценка функции трудоемкости алгоритма называется сложностью алго-

ритма и позволяет определить предпочтения в использовании того или иного ал-

горитма для больших значений размерности исходных данных.

В самом широком смысле понятие эффективности связано со всеми вы-

числительными ресурсами, необходимыми для работы алгоритма. 

В узком смысле под «самым эффективным» алгоритмом понимается са-

мый быстрый. 

Критерии эффективности алгоритма:

Временная эффективность (или временная сложность) программы по со-

ответствующему алгоритму, определяется временем, необходимым для ее вы-

полнения. 

Пространственная эффективность (емкость) измеряется количеством 

памяти, требуемой для выполнения программы соответствующего алгоритма.

Трудоемкость основных алгоритмических конструкций в общем виде сво-

дится к следующим положениям:

Конструкция «Следование»

Трудоемкость конструкции «Следование» есть сумма трудоемкостей бло-

ков, следующих друг за другом.

Конструкция «Ветвление»

Общая трудоемкость конструкции «Ветвление» требует анализа вероятно-

сти выполнения переходов на блоки «Then» и «Else» и определяется как:

Конструкция «Цикл»

После сведения конструкции к элементарным операциям ее трудоемкость 

определяется как:

условие

st2
st1

нет
да

вход

выход

Рассмотрим анализ временной сложности типового алгоритма поиска мак-

симального элемента и его номера (см. блок-схему ниже). Проанализируем вре-

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

ко раз выполнится каждый шаг алгоритма.

max :=x[1];

n_max = 1; k := 2

k<=n

max :=x[k];
n_max =k;

x[k] >mах

k =k + 1
M5

M4

M3

M2

M1

выход

да
нет

да
нет

вход

В приведенной таблице известны все величины, кроме А. Проанализируем 

величину А, анализ состоит в нахождении min значения А для оптимистов, max -

для пессимистов, среднего для сторонника теоретико-вероятного подхода. Пред-

положим, что все x[k] различны и что все n! перестановок этих величин одинако-

во вероятны. Пусть n=3, тогда равновероятна каждая из следующих шести воз-

можностей:

Amin=0, при mах=x[1]

Amax=n-1, при x[1]<x[2]< ...<x[n]

Aср=(0+1+0+1+1+2)/6=5/6

Временная сложность алгоритма:

Vmin=М1+М2+М3+М4+М5=1+N+(N-1)+0+(N-1)=3N-1

Vmax=М1+М2+М3+М4+М5=1+N+(N-1)+(N-1)+(N-1)=4N-2

Vср=М1+М2+М3+М4+М5=1+N+(N-1)+5/6+(N-1)=3N-0,16

Время работы алгоритма удобно выражать в виде функции от одной пере-

менной, характеризующей «размер» индивидуальной задачи, т.е. объем входных 

данных, требуемых для описания задачи.

2. Статические структуры данных

2.1. Простая переменная

Простые переменные описываются структурами, состоящими из одного 

элемента, поэтому каждая простая переменная характеризуется одним значени-

ем. При отображении на память ПК имени простой переменной ставится в соот-

ветствие номер ячейки памяти, в которой хранится значение этой переменной.

Существует целый ряд типовых алгоритмов, в которых используется про-

стая переменная. В основном это задачи целочисленной арифметики. Рассмот-

рим эти алгоритмы.

Выделение цифр в числе.

Введем обозначения объектов алгоритма:

n -целое число, подлежащее обработке;

sum - сумма цифр в числе;

kol - количество цифр в числе;

temp - переменная для хранения исходного числа.

1. Определение количества цифр числа
2. Определение суммы цифр числа

n<>0

kol=kol+1
n=n div 10

нет

да

начало

kol=0

n

конец

kol

n<>0

sum=sum+ n mod 10,

n=n div 10

нет

да

начало

sum=0

n

конец

sum

ввод (n)
kol:=0
нц пока n<>0

kol:=kol+1
n:=n div 10

кц
вывод (kol)

Writeln (‘Введите целое число’);
Readln (n);
kol:=0;
write (‘Подсчитываем количество цифр в числе’);
while n<>0 do

begin
kol:=kol+1; {подсчет цифры}
n:=n div 10;{уменьшение числа на один разряд}
end;

writeln (‘kol=’, kol);

ввод (n)
sum:=0
нц пока n<>0

sum:=sum+n mod 10
n:=n div 10

кц
вывод (sum)

Writeln(‘Введите целое число’);
readln(n);
sum:=0;
while n<>0 do

begin
sum:=sum+n mod 10; {суммирование цифр числа}
n:=n div 10; {уменьшение числа на один разряд}
end;

writeln (‘sum=‘, sum)