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

СТРУКТУРЫ ДАННЫХ
Первые компьютеры создавались для автоматизации вычислений, решения сложных расчетных задач.
С развитием элементной базы стоимость компьютеров и их эксплуатации снизилась. Стало возможно надежное долговременное хранение данных. Получило развитие еще одно направление использования компьютеров – хранение и обработка больших объемов информации.
Работу с большим количеством данных проще автоматизировать, когда данные упорядочены.
Для упорядочивания данных применяются структуры:
Линейные (списки)
Табличные
Иерархические (дерево)

ЛИНЕЙНАЯ СТРУКТУРА
Линейная структура данных (список) – упорядоченная структура, где адрес данного однозначно определяется его номером (индексом) (например, список учебной группы).
В списках новый элемент обычно начинается с новой строки. Если элементы располагаются в строку, нужен знак-разделитель между элементами.
Поиск выполняется по разделителям (чтобы найти пятый элемент, нужно отсчитать четыре разделителя).
Если все элементы списка одной длины, структура называется вектором данных, разделители не требуются.
При длине одного элемента – d, зная номер элемента – n, его начало определяется – d(n-1).

ЛИНЕЙНАЯ СТРУКТУРА
Список - упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения и исключения.
Список, отражающий отношения соседства между элементами, называется линейным.
Если ограничения на длину списка не установлены, то список представляется в памяти в виде связной структуры.
Линейные связные списки являются простейшими динамическими структурами данных.

МАШИННОЕ ПРЕДСТАВЛЕНИЕ СВЯЗНЫХ ЛИНЕЙНЫХ СПИСКОВ
На рисунке приведена структура однонаправленного списка, где поле INFO - информационное поле, данные, NEXT - указатель на следующий элемент списка.
Каждый список должен иметь особый элемент, называемый началом списка или головой списка, который обычно по формату отличен от остальных элементов.
В поле указателя последнего элемента списка находится специальный признак NULL, свидетельствующий о конце списка.

ТАБЛИЧНАЯ СТРУКТУРА
Табличная структура данных – упорядоченная структура, где адрес данного однозначно определяется двумя числами – номером строки и номером столбца, на пересечении которых находится ячейка с искомым элементом.
Если элементы размещаются в строку, нужны два вида разделителей – для элементов в строке и между строками. Поиск элемента можно вести по разделителям.
Если элементы таблицы одной длины, структура называется матрицей данных, разделители не нужны.
При длине одного элемента – d, зная номер строки – m и номер столбца – n, а также число строк и столбцов M и N, найдем адрес его начала
d [N(m – 1) + (n – 1)]

ИЕРАРХИЧЕСКАЯ СТРУКТУРА
Нерегулярные данные, которые трудно представить списком или таблицей, можно задать в иерархической структуре, в которой адрес каждого элемента определяется путем (маршрутом доступа), идущий от вершины структуры к данному элементу.
Пример, почтовые адреса:
Россия\Смоленская область\г. Рудня\ул. Киреева\д. 12

НЕДОСТАТКИ И ПРЕИМУЩЕСТВА СТРУКТУР ДАННЫХ
Линейные и табличные структуры
Преимущества
просты для понимания пользователя;
имеют удобный доступ к элементам - адрес каждого элемента задается числом (линейная) или двумя числами (таблица);
легко упорядочивать – сортировать по любому критерию.
Недостатки:
трудно обновлять (т. е. при добавлении произвольного элемента в упорядоченную структуру списка может происходить изменение адресных данных у других элементов)

НЕДОСТАТКИ И ПРЕИМУЩЕСТВА СТРУКТУР ДАННЫХ
Иерархическая структура
Преимущества
добавление нового элемента не нарушает структуры дерева;
Недостатки:
трудоемкость записи адреса;
сложность упорядочивания.

Вопросы
Какие структуры используются для упорядочивания данных?
Какая структуры данных называется линейной?
Что такое вектор данных?
Как в линейной структуре данных определить начало нового элемента?
Что такое табличная структура данных7
Как в табличной структуре данных определить начало нового элемента?
Что такое матрица данных?
Недостатки и преимущества различных структур данных

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