Циклические (кольцевые) списки.

Описательные алгоритмы основных действий над линейными списками.

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

Динамические структуры данных

V. Структуры и организация данных

ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ (PASCAL)

Поставщик Производитель Товар

 

ООО”Восход” ООО”Рассвет”Арматура

 

ООО”Север” ООО”Юг” Блоки

 

это

 

ООО Восход

 

поставляет

 

сделал это

 

заказ ООО Рассвет это

 

производит

 

это арматура это товар

 

это

 

блоки поставляет ООО Юг

 

производит

 

ООО Север находится

 

Северо-западный округ

 

 

Рис. 5.29. Иллюстрация отличий базы данных от базы знаний

 

 

Тема:

1. Получение доступа к k-му элементу списка для считывания и/или изменения его значения:

· перейти на первый элемент, который становится текущим;

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

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

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

2. Вставка нового элемента списка после k-го элемента:

• произвести переход на k-ыйэлемент;
• сохранить адрес k-огоэлемента в указатель;
• создать новый элемент;
• установить ссылки на новый элемент и с него на последующий.

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

3. Удаление k-го элемента списка:

· произвести переход на k-ый элемент;

· переадресовать ссылки предыдущего и последующего элементов так, чтобы текущий элемент исключался;

· удалить из памяти k-ый элемент.

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

4. Упорядочивание элементов списка:к спискам применимы все способы сортировки, применяемые к массивам; удобно иметь номер элемента списка как поле элемента списка.

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

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

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