Структуры и алгоритмы обработки данных. Ключарев А.А - 27 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

27
Для ускорения подобных операций целесообразно применять пере-
ходы между элементами списка в обоих направлениях. Это реализуется
с помощью линейных двунаправленных списков.
1.2.6.2. Линейный двунаправленный список
В этом линейном списке любой элемент имеет два указателя, один из
которых указывает на следующий элемент в списке или является пустым
указателем у последнего элемента, а второй – на предыдущий элемент в
списке или является пустым указателем у первого элемента (рис. 3).
…
Указатель на список
nil
nil
Рис. 3. Линейный двунаправленный список
Основные операции, осуществляемые с линейным двунаправленным
списком те же, что и с однонаправленным линейным списком:
– вставка элемента;
– просмотр;
– поиск;
– удаление элемента.
Следует обратить внимание на то, что в отличие от однонаправлен-
ного списка здесь нет необходимости обеспечивать позиционирование
какого-либо указателя именно на первый элемент списка, так как бла-
годаря двум указателям в элементах можно получить доступ к любому
элементу списка из любого другого элемента, осуществляя переходы в
прямом или обратном направлении. Однако часто бывает полезно иметь
указатель на заголовок списка.
Для описания алгоритмов этих основных операций используем сле-
дующие объявления:
type
PElement = ^TypeElement;{указатель на тип элемента}
TypeElement = record {тип элемента списка}
Data: TypeData; {поле данных элемента}
Next, {поле указателя на следующий элемент}
Last: PElement; {поле указателя на предыдующий элемент}

Страницы