Язык С++ и программирование на нем. Рейзлин В.И. - 143 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

145
cout <<” В файле чисел: ” << n << “\n”;
cout <<” Упорядоченный список:\n”;
lst.print ( );
}
В последнем операторе if – else делается проверка p = = lst.first ().
Это необходимо из-за того, что механизм вставки звена в начало списка
и в список после указателя p различен. Различие возникает из-за того,
что у первого элемента нет предыдущего. Иногда для единообразия в
начало списка помещают так называемый заглавный элемент, который
никогда не удаляют, и перед которым никогда не вставляют элемент.
Его информационная часть обычно не используется.
24.2. Двунаправленные и кольцевые списки
Чтобы в списках был удобный способ доступа к предыдущим эле-
ментам, добавим в каждый элемент списка еще один указатель, значе-
нием которого будет адрес предыдущего звена списка:
struct elem{
ETYPE data;
elem * next;
elem * pred;
elem ( ETYPE c, elem * n, elem * p ){ data = c; next = n; pred = p; }
};
С помощью элементов такого типа (рис. 6) можно сформировать
так называемый двунаправленный список (с заглавным элементом):
list
h data data data
next . . .
NULL
pred
NULL
. . .
Заглавный
элемент
Рис. 6. Двунаправленный список
Здесь в поле pred заглавного звена содержится пустой указатель
NULL, означающий, что у заглавного элемента нет предыдущего. Часто
двунаправленные списки обобщают следующим образом (рис. 7, 8): в
качестве значения next последнего звена принимают указатель на за-
главное (или первое) звено, а в качестве значения поля pred заглавного
(соответственно первого) звена – указатель на последнее звено:

Страницы