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

Оглавление

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Изображение чисел в позиционной системе счисления 9

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

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

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

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

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

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

2.1.1Целые типы 18

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

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

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

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

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

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

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

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

2.7Указатели 32

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

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

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

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

3.1Массивы 37

3.2Записи 38

3.3Множества 39

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

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

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

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

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

3.5.1Стек 50

3.5.2Очереди 51

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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