Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углубленный курс, 4 часа в неделю)



Урок 4
Структура информации (простые структуры). Деревья. Графы
§4. Структура информации




Содержание урока

Зачем структурировать информацию?

Знакомые структуры данных

Иерархия (дерево)

Графы

Вопросы и задания

Задачи

Практическая работа № 1 «Оформление документа»

Практическая работа № 2 «Структуризация информации (таблица, списки)»

Практическая работа № 3 «Структуризация информации (деревья)»

Практическая работа № 4 «Графы»


Знакомые структуры данных


С некоторыми структурами данных вы уже знакомы. Например, на уроках математики вы изучали множество — некоторый набор элементов. Чтобы определить множество, мы должны перечислить все его элементы (например, множество, состоящее из Васи, Пети и Коли) или определить характерный признак, по которому элементы включаются в это множество (например, множество драконов с пятью зелёными хвостами или множество точек, в которых функция принимает положительные значения).

Множество может состоять из конечного числа элементов (множество букв русского алфавита), бесконечного числа элементов (множество натуральных чисел) или вообще быть пустым (множество слонов, живущих на Северном полюсе). Множества, с которыми работает компьютер, не могут быть бесконечными, потому что его память конечна.

В документах множество часто оформляют в виде маркированного списка, например:

• процессор;
• память;
• устройства ввода;
• устройства вывода.

В таком списке порядок элементов не важен, от перестановки элементов множество не меняется (рис. 1.9).

Рис. 1.9

Рис. 1.9

Линейный список состоит из конечного числа элементов, которые должны быть расположены в строго определённом порядке.

В отличие от множества элементы в списке могут повторяться. Список обычно упорядочен (отсортирован) по какому-то правилу, например по алфавиту, по важности, по последовательности действий и т. д. В тексте он часто оформляется как нумерованный список, например:

1) надеть носки;
2) надеть ботинки;
3) выйти из дома.

Переставить местами элементы такого списка нельзя (это будет уже другой список). Список можно задать перечислением элементов, с первого до последнего: (надеть носки, надеть ботинки, выйти из дома), а также представить в виде цепочки связанных элементов (рис. 1.10).

Рис. 1.10

Рис. 1.10

Ещё одна знакомая вам структура — таблица. С помощью таблиц устанавливается связь между несколькими элементами. Например, в табл. 1.2 элементы в каждой строке связаны между собой — это свойства некоторого объекта (человека).

Именно так хранится информация в базах данных: строка таблицы, содержащая информацию об одном объекте, называется записью, а столбец (название свойства) — полем.

Возможен и другой вариант таблицы, когда роли строк и столбцов меняются. В первом столбце записываются названия свойств, а данные в каждом из следующих столбцов описывают свойства какого-то объекта. Например, табл. 1.3 содержит характеристики разных марок автомашин.



Следующая страница Иерархия (дерево)



Cкачать материалы урока







Наверх