Односвязный список

Практическая работа №2 «Динамические структуры данных»

Списки

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

Наиболее простыми динамическими структурами данных являются списки.

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

Списки бывают следующих видов:

- Односвязные – каждый элемент списка имеет указатель на следующий;

- Двусвязные – каждый элемент списка имеет указатель на следующий и на предыдущий элементы;

- Циклические – первый и последний элементы списка ссылаются друг на друга, и цепочка представляет собой кольцо.

Основное свойство линейных списков как структур данных: последовательность обхода списка зависит не от физического размещения элементов списка в памяти, а от последовательности их связывания указателями. Точно так же определяется нумерация элементов списка: логический номер элемента в списке – это номер, получаемый им в процессе обхода списка.

Списки – структуры данных с последовательным доступом. Работа со списками осуществляется исключительно через указатели. Каждый из них перемещается по списку (переустанавливается с элемента на элемент), приобретая одну из смысловых интерпретаций – указатель на первый, последний, текущий, предыдущий, новый и иные элементы списка.

Каждый элемент списка представляет собой структуру с двумя полями:

- Информационное поле, которое в общем случае может содержать произвольное количество полей разных типов.

- Указатель на следующий элемент списка, или пустой указатель, если следующего элемента нет.

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

В списках последний элемент содержит указатель NULL для обозначения факта окончания последовательности. Аналогично первый элемент двусвязного списка содержит указатель NULL на предыдущий элемент. В этом случае работа с первым и последним элементом списка имеет свои особенности. В качестве альтернативы может быть предложен циклический список, у которого последний элемент ссылается на первый, а первый ‑ на последний. Даже если данная замкнутая структура используется для представления обычной линейной последовательности, работающие с ним функции являются более простыми.

Односвязный список

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

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

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

По определению, элементы извлекаются из стека в порядке, обратном их добавлению в эту структуру, т.е. действует принцип "последний пришёл ‑ первый ушёл" (LIFO ‑ Last In – First Out).

Основные операции со стеком:

‑ создание первого элемента;

‑ помещение нового элемента в стек;

‑ извлечение элемента из стека.

Для линейного списка, представляющего стек, необходимо будет сохранять top – указатель на вершину стека.

Очередь — упорядоченный набор данных (структура данных), в котором, в отличие от стека, извлечение данных происходит из начала цепочки, а добавление данных — в конец этой цепочки. Очередь также называют структурой данных, организованной по принципу FIFO (First In – First Out).

Для линейного списка, представляющего очередь, необходимо будет сохранять: pbeg – указатель на первый элемент списка, и pend – указатель на последний элемент.

Поиск по сайту: