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

1Структуры данных и алгоритмы 3

1.1Понятие структур данных и алгоритмов 3

1.2Информация и ее представление в памяти 5

1.2.1Природа информации 5

1.2.2Хранение информации 6

1.3Системы счисления 7

1.3.1Непозиционные системы счисления 7

1.3.2Позиционные системы счисления 8

1.3.3Изображение чисел в позиционной системе счисления 8

1.3.4Перевод чисел из одной системы счисления в другую 9

1.4Классификация структур данных 10

1.5Операции над структурами данных 12

1.6Структурность данных и технология программирования 14

2Простые структуры данных 17

2.1Числовые типы 17

2.1.1Целые типы 17

2.1.2Вещественные типы 19

2.1.3Десятичные типы 23

2.1.4Операции над числовыми типами 25

2.2Битовые типы 26

2.3Логический тип 27

2.4Символьный тип 28

2.5Перечислимый тип 29

2.6Интервальный тип 29

2.7Указатели 31

2.7.1Физическая структура указателя 31

2.7.2Представление указателей в языках программирования 33

2.7.3Операции над указателями. 33

3Основные структуры данных 36

3.1Массивы 36

3.2Записи 37

3.3Множества 38

3.4Динамические структуры данных 39

3.4.1Линейные списки 39

3.4.2Циклические списки 44

3.4.3Мультисписки 47

3.5Представление стека и очередей в виде списков 48

3.5.1Стек 48

3.5.2Очереди 50

4Задачи поиска в структурах данных 53

4.1Линейный поиск 53

4.2Поиск делением пополам (двоичный поиск) 54

4.3Поиск в таблице 56

4.3.1Прямой поиск строки 57

4.3.2Алгоритм Кнута, Мориса и Пратта 58

4.3.3Алгоритм Боуера и Мура 61

5Методы ускорения доступа к данным 64

5.1Хеширование данных 64

5.1.1Методы разрешения коллизий 65

5.1.2Переполнение таблицы и рехеширование 70

5.1.3Оценка качества хеш-функции 73

5.2Организация данных для ускорения поиска по вторичным ключам 75

5.2.1Инвертированные индексы 76

5.2.2Битовые карты 77

6Представление графов и деревьев 79

6.1Бинарные деревья 79

6.2Представление бинарных деревьев 81

6.3Прохождение бинарных деревьев 86

6.4Алгоритмы на деревьях 88

6.4.1Сортировка с прохождением бинарного дерева 88

6.4.2Сортировка методом турнира с выбыванием 89

6.4.3Применение бинарных деревьев для сжатия информации 92

6.4.4Представление выражений с помощью деревьев 94

6.5Представление сильноветвящихся деревьев 96

6.6Применение сильноветвящихся деревьев 97

6.7Представление графов 103

6.8Алгоритмы на графах 104

1. Структуры данных и алгоритмы

   1. Понятие структур данных и алгоритмов

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

Задачи, которые решаются с помощью компьютера, редко выражаются на языке битов. Как правило, данные имеют форму чисел, литер, текстов, символов и более сложных структур типа последовательностей, списков и деревьев. Еще разнообразнее алгоритмы, применяемые для решения различных задач; фактически алгоритмов не меньше чем вычислительных задач.

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

Имя константы или переменной помогает программисту, но компьютеру оно ни о чем не говорит. Компилятор же, транслирующий текст программы в двоичный код, связывает каждый идентификатор с определенным адресом памяти. Но для того чтобы компилятор смог это выполнить, нужно сообщить о "типе" каждой именованной величины. Человек, решающий какую-нибудь задачу "вручную", обладает интуитивной способностью быстро разобраться в типах данных и тех операциях, которые для каждого типа справедливы. Так, например, нельзя извлечь квадратный корень из слова или написать число с заглавной буквы. Одна из причин, позволяющих легко провести такое распознавание, состоит в том, что слова, числа и другие обозначения выглядят по-разному. Однако для компьютера все типы данных сводятся в конечном счете к последовательности битов, поэтому различие в типах следует делать явным.

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

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

В зависимости от назначения языка программирования защита типов, осуществляемая на этапе компиляции, может быть более или менее жесткой. Так, например, язык PASCAL, изначально являвшийся прежде всего инструментом для иллюстрирования структур данных и алгоритмов, сохраняет от своего первоначального назначения весьма строгую защиту типов. PASCAL-компилятор в большинстве случаев расценивает смешение в одном выражении данных разных типов или применение к типу данных несвойственных ему операций как фатальную ошибку. Напротив, язык C, предназначенный прежде всего для системного программирования, является языком с весьма слабой защитой типов. C-компиляторы в таких случаях лишь выдают предупреждения. Отсутствие жесткой защиты типов дает системному программисту, разрабатывающуему программу на языке C, дополнительные возможности, но такой программист сам отвечает за правильность свох действий.

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

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

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