 |
Понятие структур данных и алгоритмов
|
|
|
|
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1. CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ
1.1. Понятие структур данных и алгоритмов
1.2. Информация и ее представление в памяти
1.2.1. Природа информации
1.2.2. Хранение информации
1.3. Системы счисления
1.3.1. Непозиционные системы счисления
1.3.2. Позиционные системы счисления
1.3.3. Изображение чисел в позиционной системе счисления
1.3.4. Перевод чисел из одной системы счисления в другую
1.4. Классификация структур данных
1.5. Операции над структурами данных
1.6. Структурность данных и технология программирования
2. ПРОСТЫЕ СТРУКТУРЫ ДАННЫХ
2.1. Числовые типы
2.1.1. Целые типы
2.1.2. Вещественные типы
2.1.3. Десятичные типы
2.1.4. Операции над числовыми типами
2.2. Битовые типы
2.3. Логический тип
2.4. Символьный тип
2.5. Перечислимый тип
2.6. Интервальный тип
2.7. Указатели
2.7.1. Физическая структура указателя
2.7.2. Представление указателей в языках программирования
2.7.3. Операции над указателями
3. СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
3.1. Векторы
3.2. Массивы
3.2.1. Логическая структура
3.2.2. Физическая структура
3.2.3. Операции
3.2.4. Адресация элементов с помощью векторов Айлиффа
3.2.5. Специальные массивы
3.3. Множества
3.3.1. Числовые множества
3.3.2. Символьные множества
3.3.3. Множество из элементов перечислимого типа
3.3.4. Множество от интервального типа
3.3.5. Операции над множествами
3.4. Записи
3.4.1. Логическое и машинное представление записей
3.4.2. Операции над записями
3.5. Записи с вариантами
3.6. Таблицы
3.7. Операции логического уровня над статическими структурами. Поиск
3.7.1. Последовательный или линейный поиск
3.7.2. Бинарный поиск
3.8. Операции логического уровня над статическими структурами. Сортировка
3.8.1. Сортировки выборкой
3.8.2. Сортировки включением
3.8.3. Сортировки распределением
3.8.4. Сортировки слиянием
|
|
|
4. ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
4.1. Характерные особенности полустатических структур
4.2. Стеки
4.2.1. Логическая структура стека
4.2.2. Машинное представление стека и реализация операций
4.2.3. Стеки в вычислительных системах
4.3. Очереди FIFO
4.3.1. Логическая структура очереди
4.3.2. Машинное представление очереди FIFO и реализация операций
4.3.3. Очереди с приоритетами
4.3.4. Очереди в вычислительных системах
4.4. Деки
4.4.1. Логическая структура дека
4.4.2. Деки в вычислительных системах
4.5. Строки
4.5.1. Логическая структура строки
4.5.2. Операции над строками
4.5.3. Представление строк в памяти
5. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ
5.1. Связное представление данных в памяти
5.2. Связные линейные списки
5.2.1. Машинное представление связных линейных списков
5.2.2. Реализация операций над связными линейными списками
5.2.3. Применение линейных списков
5.3. Мультисписки
5.4. Нелинейные разветвленные списки
5.4.1. Основные понятия
5.4.2. Представление списковых структур в памяти
5.4.3. Операции обработки списков
5.5. Язык программирования LISP
5.6. Управление динамически выделяемой памятью
6. НЕЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ
6.1.Графы
6.1.1. Логическая структура, определения
6.1.2. Машинное представление оpгpафов
6.2. Деревья
6.2.1. Основные определения
6.2.2. Логическое представление и изображение деревьев
6.2.3. Бинарные деревья
6.2.4. Представление любого дерева, леса бинарными деревьями
6.2.5. Машинное представление деревьев в памяти ЭВМ
6.2.6. Основные операции над деревьями
6.2.7. Приложения деревьев
6.2.8 Деревья Хаффмена (деревья минимального кодирования)
6.2.9 Деревья при работе с арифметическими выражениями
6.2.10 Формирование таблиц символов
6.2.11 Сбалансированные деревья
ЛИТЕРАТУРА
ВВЕДЕНИЕ
Они служат базовыми элементами любой машинной
программы. В организации структур данных и
процедур их обработки заложена возможность
проверки правильности работы программы.
Никлас Вирт
|
|
|
Без понимания структур данных и алгоритмов невозможно создать сколько-нибудь серьезный программный продукт. И слова эпиграфа служат тому подтверждением. Поэтому главная задача данного учебного пособия заключалась в следующем:
· показать все разнообразие имеющихся структур данных, представление их в памяти на физическом уровне, т.е., "как это сделано внутри", и на логическом уровне, т.е., как эти структуры реализованы в языках программирования;
· выполняемые над ними операции физического и логического уровней;
· показать значение структурного подхода к разработке алгоритмов, продемонстрировать порядок разработки алгоритмов наиболее, по мнению авторов, интересных задач.
Нельзя сказать, что такие вопросы не рассматривались в литературе, но с полной уверенностью можно отметить, что так сконцентрированно, так подробно и в доступной для понимания форме, с таким количеством демонстрационных примеров ни в каком из известных нам изданий этого не сделано.
В пособии приводится классификация структур данных, обширная информация о физическом и логическом представлении структур данных всех классов памяти ЭВМ: простых, статических, полустатических, динамических; исчерпывающая информация об операциях над всеми перечисленными структурами. Приведено достаточно большое количество алгоритмов выполнения особенно важных операций, реализованных в виде процедур и функций, написанных на Turbo Pascal, которые могут быть применены как "заготовки" в самостоятельных разработках студентов и программистов.
CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ
Понятие структур данных и алгоритмов
Структуры данных и алгоритмы служат теми материалами, из которых строятся программы. Более того, сам компьютер состоит из структур данных и алгоритмов. Встроенные структуры данных представлены теми регистрами и словами памяти, где хранятся двоичные величины. Заложенные в конструкцию аппаратуры алгоритмы - это воплощенные в электронных логических цепях жесткие правила, по которым занесенные в память данные интерпретируются как команды, подлежащие исполнению. Поэтому в основе работы всякого компьютера лежит умение оперировать только с одним видом данных - с отдельными битами, или двоичными цифрами. Работает же с этими данными компьютер только в соответствии с неизменным набором алгоритмов, которые определяются системой команд центрального процессора.
|
|
|
Задачи, которые решаются с помощью компьютера, редко выражаются на языке битов. Как правило, данные имеют форму чисел, литер, текстов, символов и более сложных структур типа последовательностей, списков и деревьев. Еще разнообразнее алгоритмы, применяемые для решения различных задач; фактически алгоритмов не меньше чем вычислительных задач.
Для точного описания абстрактных структур данных и алгоритмов программ используются такие системы формальных обозначений, называемые языками программирования, в которых смысл всякого предложения определется точно и однозначно. Среди средств, представляемых почти всеми языками программирования, имеется возможность ссылаться на элемент данных, пользуясь присвоенным ему именем, или, иначе, идентификатором. Одни именованные величины являются константами, которые сохраняют постоянное значение в той части программы, где они определены, другие - переменными, которым с помощью оператора в программе может быть присвоено любое новое значение. Но до тех пор, пока программа не начала выполняться, их значение не определено.
Имя константы или переменной помогает программисту, но компьютеру оно ни о чем не говорит. Компилятор же, транслирующий текст программы в двоичный код, связывает каждый идентификатор с определенным адресом памяти. Но для того чтобы компилятор смог это выполнить, нужно сообщить о "типе" каждой именованной величины. Человек, решающий какую-нибудь задачу "вручную", обладает интуитивной способностью быстро разобраться в типах данных и тех операциях, которые для каждого типа справедливы. Так, например, нельзя извлечь квадратный корень из слова или написать число с заглавной буквы. Одна из причин, позволяющих легко провести такое распознавание, состоит в том, что слова, числа и другие обозначения выглядят по-разному. Однако для компьютера все типы данных сводятся в конечном счете к последовательности битов, поэтому различие в типах следует делать явным.
|
|
|
Типы данных, принятые в языках программирования, включают натуральные и целые числа, вещественные (действительные) числа (в виде приближенных десятичных дробей), литеры, строки и т.п.
В некоторых языках программирования тип каждой константы или переменной определяется компилятором по записи присваиваемого значения; наличие десятичной точки, например, может служить признаком вещественного числа. В других языках требуется, чтобы программист явно задал тип каждой переменной, и это дает одно важное преимущество. Хотя при выполнении программы значение переменной может многократно меняться, тип ее меняться не должен никогда; это значит, что компилятор может проверить операции, выполняемые над этой переменной, и убедиться в том, что все они согласуются с описанием типа переменной. Такая проверка может быть проведена путем анализа всего текста программы, и в этом случае она охватит все возможные действия, определяемые данной программой.
В зависимости от назначения языка программирования защита типов, осуществляемая на этапе компиляции, может быть более или менее жесткой. Так, например, язык PASCAL, изначально являвшийся прежде всего инструментом для иллюстрирования структур данных и алгоритмов, сохраняет от своего первоначального назначения весьма строгую защиту типов. PASCAL-компилятор в большинстве случаев расценивает смешение в одном выражении данных разных типов или применение к типу данных несвойственных ему операций как фатальную ошибку. Напротив, язык C, предназначенный прежде всего для системного программирования, является языком с весьма слабой защитой типов. C-компиляторы в таких случаях лишь выдают предупреждения. Отсутствие жесткой защиты типов дает системному программисту, разрабатывающуему программу на языке C, дополнительные возможности, но такой программист сам отвечает за правильность свох действий.
Структура данных относится, по существу, к "пространственным" понятиям: ее можно свести к схеме организации информации в памяти компьютера. Алгоритм же является соответствующим процедурным элементом в структуре программы - он служит рецептом расчета.
Первые алгоритмы были придуманы для решения численных задач типа умножения чисел, нахождения наибольшего общего делителя, вычисления тригонометрических функций и других. Сегодня в равной степени важны и нечисленные алгоритмы; они разработаны для таких задач, как, например, поиск в тексте заданного слова, планирование событий, сортировка данных в указанном порядке и т.п. Нечисленные алгоритмы оперируют с данными, которые не обязательно являются числами; более того, не нужны никакие глубокие математические понятия, чтобы их конструировать или понимать. Из этого, однако, вовсе не следует, что в изучении таких алгоритмов математике нет места; напротив, точные, математические методы необходимы при поиске наилучших решений нечисленных задач при доказательстве правильности этих решений.
|
|
|
Структуры данных, применяемые в алгоритмах, могут быть чрезвычайно сложными. В результате выбор правильного представления данных часто служит ключом к удачному программированию и может в большей степени сказываться на производительности программы, чем детали используемого алгоритма. Вряд ли когда-нибудь появится общая теория выбора структур данных. Самое лучшее, что можно сделать,- это разобраться во всех базовых "кирпичиках" и в собранных из них структурах. Способность приложить эти знания к конструированию больших систем - это прежде всего дело инженерного мастерства и практики.
|
|
|
