Списки. Реализация списков на базе массива

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

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

В математике список определяется как последовательность элементов определенного типа: X₁, X₂, … X_n, где n> =0. Количество элементов n называется длиной списка, X₁ – первый элемент списка, X_n – последний элемент списка. В случае n =0, список пустой. Важное свойство списка заключается в том, что его элементы можно линейно упорядочить в соответствии с их позицией в списке, т.е., X_i предшествует X_i+1 и следует за X_i-1. Элемент X_i имеет позицию i.

1. Реализация списка:

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

List=record

Element:array[1..100]of integer;

Last:byte;

End;

2. Процедуры обработки списка:

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

Контрольные вопросы:

1. Какие структуры данных называются статическими? Приведите примеры.

2. Какие структуры данных называют динамическими? Приведите примеры.

3. Что такое стек?

4. Опишите реализацию стека на базе массива.

5. Напишите процедуру удаления элемента из стека.

6. Определите эффективность процедур обработки стека.

7. Что такое очередь?

8. Опишите реализацию очереди на базе массива.

9. Определите эффективность процедур обработки очереди.

10. Что такое список?

11. Опишите реализацию списка на базе массива.

12. Какие операции необходимо выполнить, чтобы удалить элемент из списка?

13. Какие операции необходимо выполнить, чтобы вставить элемент в список?

14. Какие операции необходимо выполнить, чтобы вставить элемент в очередь?

15. Определите эффективность процедур обработки линейного списка.

16. Объясните, как можно реализовать очередь на базе двух стеков?