Министерство образования Российской Федерации
Институт менеджмента и информационных технологий
Санкт-Петербургский государственный политехнический университет
ПРОЕКТИРОВАНИЕ, АНАЛИЗ И ПРОГРАММНАЯ РЕАЛИЗАЦИЯ СТРУКТУР ДАННЫХ И АЛГОРИТМОВ
Учебное пособие
Череповец
2007
УДК 004.2
Царев В.А., Дробанов А.Ф.
Проектирование,
анализ и программная реализация структур
данных и алгоритмов – Череповец, 2007. –
В учебном пособии приводятся описания различных форм организации данных в программах, методов обработки данных в различных классах задач и осуществляется их сравнительный анализ.
Учебное пособие предназначено для изучения теоретического материала дисциплин «Структуры и алгоритмы и обработки данных» и «Высокоуровневые методы информатики и программирования» студентами различных форм обучения, проходящих подготовку по специальностям 080801 и 230105.
Рецензенты:
Утверждено:
Содержание
1 Алгоритмы 6
2 Алгоритмы сортировок 24
3 Элементарные и нелинейные структуры данных 49
4 Хеширование 91
5 Основные принципы разработки алгоритмов 114
Литература 174
Русскоязычные ресурсы InterNet 175
1 Алгоритмы
1.1 Основные определения: алгоритм, вход, результат; понятие правильного и неправильного алгоритма; псевдокод
Алгоритм – это формально описанная вычислительная процедура, получающая исходные данные (вход) и возвращающая результат (выход). Алгоритмы строятся для решения тех или иных вычислительных задач, при этом они должны удовлетворять следующим противоречащим друг другу требованиям:
Быть простым для понимания, перевода в программный код и отладки;
Эффективно использовать вычислительные ресурсы.
Алгоритм считают правильным (correct), если на любом допустимом входе он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи. В этом случае говорят, что алгоритм решает (solve) данную вычислительную задачу. Неправильный алгоритм для некоторого входа может вообще не остановиться или дать неправильный результат. Алгоритм может быть описан различными способами, в том числе и при помощи псевдокода, принадлежащего более высокому уровню абстракции по сравнению с языками программирования высокого уровня (C#, Pascal, Basic и т.д.). В математическом пакете MathCAD при написании кода функций, определяемых пользователем, используется нотация, напоминающая описываемый ниже псевдокод.
Таблица 1.1 - Соглашения, лежащие в основе псевдокода
|
№ |
Описание |
|
1 |
Отступ от левого поля указывает на уровень вложенности (это позволяет отказаться от применения begin и end) |
|
2 |
Комментарий обозначается символом “►”. |
|
3 |
Циклы while, for, repeat и условные конструкции имеют тот же смысл, что и в языке Pascal. |
|
4 |
Символ “” имеет смысл оператора присваивания. |
|
5 |
Запись i j e обозначает j e; i j или i e. |
|
6 |
Переменная, обозначающая массив или объект, считается указателем на составляющие его данные. |
|
7 |
Все переменные (по-умолчанию) – локальные. |
|
8 |
Оператор доступа к элементу массива пишется в квадратных скобках []. |
|
9 |
Запись “A[1..j]” обозначает A[1], A[2], A[3]..A[j]. |
|
10 |
Доступ к полю (field) объекта (object): field[object]. |
|
11 |
Параметры в подпрограмму передаются по-значению (by value), но при передаче объекта его свойства копируются в виде указателей. Т.е. если в качестве параметра передается объект x, то присваивание x y снаружи заметить нельзя, а f [x] 5 можно. |
В качестве примера, позволяющего оценить различия между псевдокодом и алгоритмическим языком, рассмотрим сортировку вставками.
Листинг 1.1 – Псевдокод алгоритма сортировки вставками
procedure InsertSort(n: integer;
var A: array[1..n] of integer);
var
i, j, Tmp: integer;
begin
for i := 2 to n do begin
{Сохраняем текущий элемент}
Tmp := A[i];
{Сдвигаем элементы, большие, чем текущий}
j := i-1;
while (A[j] > Tmp) and (j > 1) do begin
A[j+1] := A[j];
j := j-1;
end;
{Вставляем текущий элемент}
A[j+1] := Tmp;
end;
end;
Листинг 1.2 – Сортировка вставками