Информатика и технология программирования

       

Раздел : Структуры данных ( часов)


1. . Понятие структуры данных. Алгоритмическая компонента структуры данных. Статические и дин а мические структуры данных. Структуры данных " в узком смысле" . Упорядоченность. Понятие л о гического номера элемента, ключевого поля. Операции включения, добавления, удаления, поиска по ключу, извлечения по логическому номеру и сортировки структуры данных. Классификация структур данных : массивы, массивы указателей, списки, деревья. Иерархические структуры данных (bk51.doc) (2 часа).

2. . Массивы указателей. Способы формирования массивов указателей - статические, динамические, смешанные. Работа с массивами указателей. Примеры функций включения, исключения, сортиро в ки и поиска. Массив указателей на строки. (bk52.doc) (3 часа).

3. . Списки. Определение элемента списка. Фрагменты алгоритмов работы со списками. Текущий эл е мент, заголовок. Способы формирования списков. Односвязные списки. Операции включения, и с ключения, добавления в список. Сортировка списка - выбор, вставка. Представление очереди и стека односвязным списком (2 часа).

4. . Двусвязные списки. Включение и исключение элемента. Проблема концов списка, циклические списки (1 час).

5. . Рекурсия. Определение рекурсии. Рекурсивные определения, структуры данных, функции. Особе н ности проектирования рекурсивных функций. Рекурсивная функция как процесс. Смысл формал ь ных и фактических параметров, локальных и глобальных переменных и результата функции как х а рактеристик рекурсивного процесса. Проектирование рекурсивных алгоритмов и метод математ и ческой индукции - принцип " локального мышления" . Использование рекурсивных алгоритмах в задачах поиска, основанных на переборе вариантов. Примеры программ движения по лабиринту, расстановки фигур, составления цепочек слов (4 часа).


1. . Деревья как рекурсивные структуры данных. Определение вершины дерева. Рекурсивный характер обхода дерева. Алгоритмы полного обхода дерева, поиска минимального значения, включения на заданную глубину. Нумерация вершин дерева. Способы нумерации. Поиск элемента по логическ о му номеру. Способы организации данных в дереве для сокращения глубины просмотра. ( bk54.doc ) (4 часа).

2. . Двоичное дерево. Включение и поиск в двоичном дереве. Связь двоичного дерева с алгоритмов двоичного поиска. Эффективность поиска в двоичном дереве. Сбалансированность. Извлечение из двоичного дерева по логическому номеру (bk54.doc) (2 часа).

3. . Сравнительная характеристика структур данных. Иерархические структуры данных. Примеры : дву х уровневый массив указателей, список, содержащий массивы указателей, массив заголовков сп и сков. Оптимизация иерархических структур данных ( bk58.doc) (2 часа).

4. . Указатель на функцию. Синтаксис. Смысл указателя на функцию - как средства параметризации части алгоритма обработки данных. Указатель на функцию - формальный параметр. Функция в ы числения определенного интеграла. Итератор. Итераторы foreach, firstthat . Итераторы, основанные на сравнении - сортировка, поиск минимального, двоичный поиск. Примеры (2 часа).



Содержание раздела