Линейные структуры данных

Линейные структуры данных – линейный список, очередь, стек и дек.

Линейный список - структура данных, состоящая из элементов одного типа, связанных между собой.

Линейные списки реализуются при помощи массивов и связных списков.

Элемент списка содержит две части: основное поле и вспомогательное поле. Основное поле содержит информацию. Например, символ. Вспомогательное поле содержит указатель на следующий элемент. Головной элемент содержит указатель Start. Последний элемент линейного списка хранит указатель NULL. На рисунке 2.1 приведен пример линейного списка.

Рисунок 2.1 – Линейный однонаправленный список

Характеристики линейного списка:

1. Длина списка. Количество элементов в списке.

2. Списки могут быть типизированными или нетипизированными. Если список типизирован, то тип его элементов задан, и все его элементы должны иметь типы, совместимые с заданным типом элементов списка. Обычно списки, реализованные при помощи массивов, являются типизированными.

3. Список может быть сортированным или несортированным.

4. В зависимости от реализации может быть возможен произвольный доступ к элементам списка.

Над списками выполняются операции:

1. Создание первого элемента.

2. Добавление элемента в конец списка.

3. Чтение элемента с заданным ключом.

4. Вставка элемента в заданное место списка.

5. Удаление элемента с заданным ключом.

6. Упорядочивание списка по ключу.

Не нашли, что искали? Воспользуйтесь поиском: