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

Записи, содержащие указатель, позволяют формировать в ОП линейные и нелинейные связанные структуры. К линейным относятся стеки, очереди, списки, к нелинейным – деревья и сети.

Стеки, очереди и списки реализуют линейные бесприоритетные структуры по организации накопления, чтения данных и удаления элементов связанной структуры.

Общие их черты:

- все элементы связанной структуры представляют собой последовательность элементов, связанных между собой в цепь с помощью указателей;

- максимальное число элементов структуры ограничено объёмом ОП;

- ОП для элементов связанной структуры выделяется и освобождается динамически;

- последовательность элементов имеет начало цепи (указатель имеет значение nil) и конец (вершину), которую обычно адресует указатель стека, очереди, списка.

Отличия:

- в стеке включаются и исключаются элементы только с одного конца;

- в очереди элементы включаются только в конец очереди, а исключаются с другого конца только из её начала (вершины);

- в списке элементы упорядочены по определённому признаку - одному из элементов записи, включаются и исключаются элементы в любом месте, поиск места в списке производится, как правило, по признаку, по которому список упорядочен.

Схема взаимосвязи элементов в цепи связанных структур

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

Замечание Стек – LIFO (Last In ®First Out).

Очередь - FIFO (First In ®First Out).

Список

Определение Список –это соединение элементов в порядке убывания или возрастания ключевого признака одного из элементов записи, из которой состоит список.

Каждый элемент списка может быть достаточно сложной структуры.

Базовые операции над списком:

1. добавление нового элемента в список;

2. удаление из списка элемента, заданного поисковым признаком;

3. поиск в списке и вывод заданного элемента;

4. чтение и вывод всех элементов списка;

5. уничтожение списка путем освобождения ОП, занимаемой его элементами.

Схема перемещения указателей вдоль списка для подключения нового элемента

Выбор ключа: NZ – номера зачёток.