Прямоугольные структуры. Массивы

Лекция 6 (2010.03.17)

Повторение темы «Структуры данных»

Лекция 1

Cтруктуры данных

Основные понятия

Задача для ЭВМ = вычислительная часть + обработка информации.

· Информация – совокупность сведений или знаний.

· Данные - информация, пригодная для обработки.

· Система – совокупность взаимосвязанных объектов, подчиненных определенной (единой) цели.

· Автоматизированные информационные системы (АИС) - системы обработки данных.

· Базы данных (БД) - совокупность взаимосвязанных данных.

· Структура - взаимосвязь отдельных элементов.

· Запись - совокупность (группа) элементов (полей).

Эффективность обработки данных зависит от формы представления (типы данных), взаимосвязи отдельных элементов (структур данных), последовательности действий (алгоритма).

Три уровня абстракции описания структур данных:

Ø Набор функциональных спецификаций;

Ø Логическое описание (типы данных);

Ø Физическое представление.

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

Линейные	Нелинейные
Прямоугольные	Структуры ряда	Списковые	Древовидные	Графы	Мульти графы
Массивы, таблицы	Строки, очереди, стеки, деки	Линейный список	n-дерево, бинарное дерево, дерево двоичного поиска

Указатель - адрес начала записи.

Обозначения и договоренности

Множества.

Множество записей - простейшая вырожденная структура данных, характеризуемая отсутствием взаимосвязи между элементами множества (записями). В языке Паскаль логическое описание и физическое представление множества берет на себя транслятор (тип данных множество предопределен в языке, описатель set of T). Операции над множествами сведены в таблицу.

Имя операции	Функциональные спецификации	Аргументы	Результат	Описание
Создать	®U		Æ	Создается пустое множ
Включить	T´U®U	t, u	{xÎTïxÎu или x=t}	К u добавляется t, если он не принадлежит u
Принадлежит?	T´U®Boolean	t, u	Истина, если tÎu,	Принадлежит ли элемент t множеству u?
Исключить	T´U®U	t, u	{xÎTïxÎu и x¹t}	Удалить элемент t из множества u
Пусто?	U®Boolean	u	Истина, если u=Æ	Пусто ли множество u?
Объединение	U´U®U	u1, u2	{xÎTïxÎu1 или xÎu2}	Объединение u1 и u2
Пересечение	U´U®U	u1, u2	{xÎTïxÎu1 и xÎu2}	Пересечение u1 и u2
Разность	U´U®U	u1, u2	{xÎTïxÎu1 и xÏu2}	Разность u1 и u2
Дополнение	U®U	u	{xÎTï xÏu}	Дополнение к u

Здесь Т – базовый тип множества, U – тип множество, t – данное базового типа (t:T или tÎT), u, u1, u2 – данные типа U.

Прямоугольные структуры. Массивы

Массив - конечное упорядоченное множество элементов (записей) одного типа.

Над массивом определены следующие операции:

Ø создание массива (это делает транслятор),

Ø инициализация элемента,

Ø чтение значение элемента

Задача. Записать функциональные спецификации для структуры данных «массив».

Создание массива ®М,

Инициализация массива М´I´T®М,

Чтение значения элемента массива М´I®T.