Линейные списки

Линейные связанные структуры.

Описание интерфейсов для статического и динамического массивов

Понятие массив используется на уровне постановки задачи: за­дается или должно быть сформировано множество однотипных данных.

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

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

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

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

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

Набор базисных операцийнад динамическими множествами:

1. создание пустого множества;

2. переход к первому, последнему, следующему или предыдущему элементу множества (этот элемент становится текущим) – получение доступа к k -му элементу множества;

3. извлечение значения текущего элемента – считывание значения;

4. замена значения текущего элемента;

5. добавление элемента в начало, в конец или перед/после текущего элемента – вставка нового элемента множества;

6. удаление k -го элемента множества;

7. объединение в одно множество двух или более подмножеств;

8. разбиение множества на два или более подмножеств;

9. создание копии множества;

10. определение количества элементов множества;

11. нахождение максимального и минимального элементов множества;

12. упорядочивание элементов множества;

13. поиск элемента множества с данным значением.

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

Особенности линейных списков:

· списки состоят из элементов одного и того же типа;

· cвязь между элементами и доступ к элементам списка осуществляется при помощи указателей, поэтому, кроме информационных данных, каждый элемент списка должен иметь указатели на последующий или/и предшествующий элемент списка;

· количество элементов списка заранее не задаётся, оно может изменяться в процессе выполнения программы;

· размер одного элемента списка не может превышать 64 Кбайт;

· при описании списка используется рекурсия;

· доступ к элементам списка последовательный.

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