Вопрос №19. Дек. Описание, набор операций, реализации а) на основе массива; б) на основе двусвязного списка

Операторы:

l Сделать дек пустым;

l Дек пуст/не пуст?

l Добавить элемент в начало/конец дека;

l Показать начало или конец дека;

l Удалить элемент из начала/конца дека.

Вопрос №20. L1-список. Описание, набор операций, реализация а) на основе массива; б) на основе односвязного списка; в) на основе односвязного списка с буферным элементом в начале или в конце; г) на основе кольцевого односвязного списка с буферным элементом.

Операторы:

l Сделать список пустым;

l Список пуст/не пуст?

l Установить указатель в начало списка;

l Указатель в конце списка?

l Передвинуть указатель на один элемент вправо;

l Добавить элемент по положению указателя;

l Показать элемент по положению указателя;

l Удалить элемент по положению указателя.

Однонаправленный список чаще всего реализуется динамически, так как это тот АТД, размеры которого могут меняться с течением времени. Для того чтобы однонаправленный список реализовать нужно завести структуру (struct), которая бы отображала элемент списка.

Как правило в этой структуре одно поле отводится для хранения значения элемента списка:

l Одно поле – однонаправленный;

l Два поля – двунаправленный;

l Более двух полей – мультинаправленный.

Хранят адреса других элементов списка.

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

Перемещение по списку осуществляется в соответствии с системой указателей.

Вопрос №21. L2-список. Описание, набор операций, реализация а) на основе массива; б) на основе двусвязного списка; в) на основе двусвязного списка с буферным элементом в начале или в конце, или с двумя буферными элементами; г) на основе кольцевого двусвязного списка с буферным элементом.

Указатель может двигаться как вправо, так и влево.

Операторы:

l Сделать список пустым;

l Список пуст/не пуст?

l Установить указатель в начало/конец списка;

l Указатель в начале/конце списка?

l Передвинуть указатель на один элемент;

l Добавить элемент по положению указателя;

l Показать элемент по положению указателя;

l Удалить элемент по положению указателя.