- •Предисловие
- •Основы программирования
- •Понятие алгоритма.
- •Алгоритм Евклида.
- •Задача о поездах и мухе
- •Вместо лирического отступления
- •Этапы подготовки задачи для решения на компьютере
- •Примеры разработки алгоритмов
- •Решение квадратного уравнения.
- •Вычисление интегралов
- •Обработка результатов эксперимента
- •Решение системы линейных алгебраических уравнений
- •Введение в язык программирования Pascal
- •Основные элементы языка
- •Переменные. Стандартные типы.
- •Операции отношения
- •Раздел описаний переменных
- •Выражения. Порядок выполнения операций.
- •Константы
- •Комментарии в программе
- •Операторы
- •2.1.7.1. Оператор присваивания
- •2.1.7.2. Операторы ввода/вывода
- •2.1.7.3. Операторы инкремента и декремента
- •Среда разработки Lazarus
- •Русский язык в консольных приложениях
- •Первая программа
- •Открытие существующего проекта
- •Другие способы создания консольных приложений
- •Типовой пустой проект
- •Операции с целыми числами
- •Вместо лирического отступления 2
- •Стандартные функции с целыми аргументами
- •Операции с вещественными числами (тип real).
- •Форматирование вывода
- •Одновременное использование вещественных и целых чисел.
- •Другие стандартные функции с вещественными аргументами
- •Булевы переменные
- •Условные операторы.
- •2.1.22.1 Оператор if …. then
- •2.1.22.2. Оператор if …then ... else
- •Операторы цикла
- •2.1.23.1. Оператор цикла с предусловием
- •2.1.23.2. Оператор цикла с постусловием
- •2.1.23.3. Оператор цикла с параметром.
- •2.1.23.4. Второй вариант оператора цикла с параметром
- •Оператор выбора case
- •Организация простейшего контроля ввода данных.
- •Вычисление сумм сходящихся рядов
- •Реализация некоторых алгоритмов главы 1.
- •Программа решения задачи о поездах и мухе
- •Программа вычисления определенного интеграла
- •Более сложные элементы языка
- •Общая структура Паскаль – программы
- •Процедуры и функции
- •3.1.1.1 Структура процедуры
- •3.1.1.2. Структура функции
- •3.1.1.3 Глобальные и локальные переменные
- •3.1.1.4 Способы передачи параметров
- •3.1.1.5 Процедуры завершения
- •Еще раз о типах данных
- •Классификация типов данных
- •3.2.1.1 Целый тип
- •3.2.1.2. Интервальный тип
- •3.2.1.3. Перечислимый тип
- •3.2.1.4. Множества
- •3.2.1.5. Логический тип
- •3.2.1.6. Вещественный тип
- •3.2.1.7. Указатели
- •Обработка символьной информации в Паскале
- •Символьные и строковые типы данных.
- •3.3.1.1. Тип Char
- •3.3.1.2. Функции для работы с символами
- •3.3.1.3. Тип String
- •3.3.1.4. Строковые процедуры и функции
- •Массивы
- •Динамические массивы
- •Программа решения системы линейных алгебраических уравнений методом Гаусса
- •3.4.1.1. Вариант 1 – с goto
- •3.4.1.2. Вариант 2 – без goto
- •3.4.1.3. Вариант 3 – наилучшая реализация
- •Модули в Паскале
- •Структура модуля
- •Системные модули
- •3.5.2.1. Модуль CRT
- •Файлы
- •Тип данных – запись
- •Файловые типы
- •Процедуры для работы с файлами
- •3.6.3.1. Общие процедуры для работы с файлами всех типов
- •3.6.3.2. Процедуры для работы с текстовыми файлами
- •3.6.3.3. Процедуры для работы с типизированными файлами
- •3.6.3.4. Процедуры для работы с нетипизированными файлами
- •3.6.3.5. Организация контроля ввода/вывода при работе файлами
- •3.6.3.6. Создание простой базы данных с типизированными файлами.
- •Алгоритмы сортировки
- •Обменная сортировка (метод "пузырька")
- •Сортировка выбором
- •Сортировка вставками
- •Метод быстрой сортировки
- •Алгоритмы поиска
- •Поиск в массивах
- •Вставка и удаление элементов в упорядоченном массиве
- •Динамические структуры данных
- •Представление в памяти компьютера динамических структур.
- •Реализация стека с помощью массивов
- •Указатели
- •Стандартные операции с линейными списками
- •Реализация динамических структур линейными списками
- •4.3.6.1. Реализация стека
- •4.3.6.2. Реализация очереди с помощью линейного списка
- •4.3.6.3. Реализация двоичного дерева с помощью линейного списка
- •Сортировка и поиск с помощью двоичного дерева
- •Три источника и три составные части ООП.
- •Классы и объекты.
- •Обращение к членам класса.
- •Инкапсуляция
- •Спецификаторы доступа.
- •Свойства.
- •Наследование
- •Полиморфизм
- •Раннее связывание.
- •Позднее связывание.
- •Конструкторы и деструкторы.
- •Элементы графического интерфейса
- •Различия между консольными и графическими приложениями
- •Визуальное программирование в среде Lazarus
- •Создание графического приложения
- •Форма и ее основные свойства
- •Компоненты
- •Обработчики событий
- •Простейшие компоненты
- •6.3.5.1. Компонент TLabel
- •6.3.5.2. Кнопки TButton, TBitBtn и TSpeedButton
- •6.3.6.1. Компонент TEdit
- •6.3.6.2. Компонент TLabeledEdit
- •6.3.7.1. Компонент TMaskEdit
- •Специальные компоненты для ввода чисел
- •Тестирование и отладка программы
- •Компоненты отображения и выбора данных
- •6.3.10.1. Компонент TMemo
- •6.3.10.2. Компонент TStringGrid
- •6.3.10.3. Компоненты выбора
- •Компонент TListBox
- •Компонент TComboBox
- •Компоненты выбора – переключатели
- •6.3.10.4. Компоненты отображения структурированных данных
- •Компонент TTreeView
- •Компонент TListView
- •Организация меню. Механизм действий - Actions
- •6.3.11.1. Компонент TMainMenu
- •6.3.11.2. Компонент TToolBar
- •6.3.11.3. Компонент TActionList
- •6.3.11.4. Создание приложений с изменяемыми размерами окон
- •Послесловие
- •Литература
- •Алфавитный указатель
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
inc(SizeOfArray);
Предлагаю вам самостоятельно написать процедуру вставки в массив только уникального элемента, т.е. если в исходном массиве уже имеется такой элемент, то вставка не производится.
4.3. Динамические структуры данных
При описании некоторых задач применяются абстрактные структуры дан-
ных, в частности графы. |
|
|
Ориентированный граф – |
это система из двух множеств G (X, U) , |
где |
X - множество элементов, называемых вершинами, а U - определенное |
на |
|
множестве X отношение (т.е. |
U X X ), элементы которого называются ду- |
гами или ребрами. Если a и b - вершины, то (a, b) - ребро. Говорят, что ребро направлено от a к b .
Неориентированный граф – это такой граф, в котором отсутствует ориен-
тация ребер, т.е. (a, b) (b, a) .
Если каждому ребру поставить в соответствие некоторое число, то это
взвешенный граф.
Вершины графа или его ребра (или те и другие) могут быть помечены. В
качестве меток могут использоваться символы или числа. |
|
||
a |
b |
a |
b |
c |
d |
c |
d |
Рис. 4.14. Примеры графов
Путем в графе называется последовательность вершин, связанных между
331
4.3 Динамические структуры данных
____________________________________________________________________
собой ребрами. Две вершины связаны между собой, если существует путь от одной вершины до другой.
Граф называется связным, если все пары вершин связаны. Будем говорить,
что граф пуст, если в нем нет вершин (а, следовательно, и ребер).
Рассмотрим теперь графы специального вида, называемыми деревьями.
Деревом называется связный граф, в котором:
1)имеется единственная особая вершина, называется корнем, в которую не заходит ни одно ребро;
2)во все остальные вершины (иначе называемых листьями, а также узлами)
заходит только одно ребро, а исходит сколько угодно ребер;
3)нет циклов (т.е. замкнутых петель)
корень
Рис. 4.15. Пример дерева
На рисунках корень указывают с помощью наглядного расположения, ко-
гда корень изображается самой верхней вершиной. С помощью дерева мы мо-
жем представить родословную некоторого человека.
Фред
Джон Пам Дэвид Элизабет
Габриэл Сью |
Йэн Бабби |
Билл Том Эрик
Рис. 4.16. Родословная человека по имени Фред
Этой родословной соответствует дерево вида:
332
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
Рис. 4.17. Дерево, соответствующее родословной Фреда
Поэтому вершины нижних уровней называют еще потомками или сыновь-
ями.
Одно из первых применений деревьев в программировании это трансляция арифметических выражений. Пусть имеется некоторое арифметическое выра-
жение: X+Y*Z-A*B+C/D
При переводе этого выражения на внутренний язык компилятор строит де-
рево вида:
+
–
+
* * /
X Y Z A B C D
Рис. 4.18. Дерево, построенное компилятором при разборе выражения
Любая иерархическая структура может быть представлена в виде дерева.
Рассмотрим упрощенную структуру типичного университета.
333
4.3 Динамические структуры данных
____________________________________________________________________
Ректор
|
|
|
|
|
|
|
|
|
|
|
|
|
|
проректор по |
|
проректор по эко- |
|
|
проректор по науке |
|
проректор по |
|
кадры |
||||
учебной работе |
|
номике |
|
|
и внешним связям |
|
АХЧ |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
факультеты |
бухгалтерия |
экономический |
|
учебные корпу- |
преподаватели |
|
|
|
отдел |
|
са, общежитие |
и сотрудники |
|
|
|
|
|
|
|
|
кафедры
студенты
Рис. 4.19. Структура типичного университета
Нарисовать соответствующее дерево предоставляется самому читателю.
Количество ребер выходящих из любой вершины называется степенью узла или степенью вершины. Если из вершины не выходит ни одного ребра,
степень такой вершины равна нулю.
Важнейшим классом деревьев, чаще всего используемых в программиро-
вании являются так называемые двоичные или бинарные деревья. Двоичным деревом называется такое дерево, из каждой вершины которого выходит не бо-
лее двух ребер, т.е. в степень двоичного дерева не превышает двух. Строгое би-
нарное дерево состоит только из узлов, имеющих степень два или степень ноль.
Нестрогое бинарное дерево содержит узлы со степенью равной 0, 1 или 2.
В бинарном дереве на каждом уровне n может быть не более 2n-1 вершин.
Бинарное дерево называется полным, если в строгом бинарном дереве на каждом n-м уровне содержатся все 2n-1 вершин, рис. 4.20.
334
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
Рис. 4.20. Бинарное (двоичное) дерево
Наиболее часто используемые действия над деревьями – это обход дерева.
Обходя дерево, мы можем что-то делать с вершиной, которую обходим, на пример, печатать номер вершины. Различают 3 способа обхода дерева:
|
1 |
2 |
5 |
|
3 |
4 |
6 |
7 |
|
|
Рис. 4.21. Обход дерева
1)обход сверху, при этом сначала обрабатывают корень, затем левое подде-
рево, и затем правое поддерево. Тогда будут напечатаны 1, 2, 3, 4, 5, 6, 7;
2)обход слева. Здесь сначала обрабатывают левое поддерево, затем корень,
затем правое поддерево. Будут напечатаны 3, 2, 4, 1, 6, 5, 7;
3)обход снизу. Здесь обрабатываются сначала левое поддерево, затем пра-
вое поддерево, затем корень. Будут напечатаны 3, 4, 2, 6, 7, 5, 1.
Обход слева часто используется в алгоритмах сортировки, при работе с таблицами.
Рассмотрим еще одну информационную структуру – стек.
Стек это динамическая структура, приспособленная для того, чтобы до-
бавлять элементы в стек и извлекать их оттуда по определенным правилам – очередной элемент в стек можно поместить или взять только через специальное место, называемое верхушкой стека. В верхушке стека находится всегда эле-
335
4.3 Динамические структуры данных
____________________________________________________________________
мент, помещенный в него последним. Стек работает по принципу «последним
пришел, первым ушел» ("Last In – First Out", LIFO).
Лицам мужского пола, возможно, будет легче понять принцип работы сте-
ка, если они представят себе обойму пистолета. Патрон, помещенный в обойму последним, первым уйдет в цель. Особам женского пола более приятно будет ассоциировать стек со стопкой тарелок. Тарелка, помещенная в стопку послед-
ней, первой пойдет в "дело".
Рассмотрим процесс помещения в стек трех элементов a, b, c. Первона-
чально стек пусть будет пустым. На рисунке 4.22 показаны последовательные
состояния стека при добавлении элементов a, b, c. |
|
|
|
||||||
|
|
|
|
|
|
|
|
верхушка |
|
|
|
a |
|
верхушка |
|
|
b |
|
|
|
|
|
|
|
|
|
a |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c верхушка
b
a
Рис. 4.22. Последовательные состояния стека при добавлении элементов
Таким образом, последний добавленный в стек элемент с оказывается в верхушке стека. Применение стека рассмотрим на примере составления алго-
ритма обхода двоичного дерева слева.
336