Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

Ведущее звено этого списка создаётся следующим набором операторов.
Link2 *L2 = new Link2; L2->next = NULL;
L2->prev = NULL;

100

По операторам создания ведущего звена можно судить о том, является список одно- или двусвязным, линейным или коль- цевым. Нулевые значения указателей next и prev являются признаком линейного списка.
Графически состояние списка после создания ведущего зве- на может быть отображено следующим образом:

Рис. 9.3 — Ведущее звено пустого двусвязного линейного списка

Преимущества двусвязного списка:

• 
  есть возможность перестроить поврежденный список;
  
• 
  проще выполняются некоторые операции (например, уда- ление).
  

2. 
   Операции с двусвязным списком
   

Всё, что касалось операций добавления звена и его удаления для односвязного списка, справедливо и для двусвязного. Так же должен соблюдаться правильный порядок проведения (или уда- ления) связей между звеньями, но таких операций стало больше, т.к. должны обрабатываться два указателя. Кроме того, каждая из операций обладает дополнительными особенностями:

1. 
   При добавлении нового звена в пустой список, т.е. содер- жащий только ведущее звено (см. предыдущий рисунок), или при добавлении звена в конец списка (для пустого списка обе эти си- туации совпадают) необходимо проверять наличие звена, которое будет следующим за добавляемым (для пустого списка или конца списка такого звена нет, а значит nem и указателя, обозначаю- щего связь). Такая же проверка должна выполняться при удале- нии звена.
   
2. 
   Возможность перемещаться по списку в обоих направле- ниях позволяет напрямую задавать удаляемое звено (а не ему предшествующее, как в односвязном списке). Следствием этого является упрощение как операции удаления, так и операции по-
   

101
HCKII. ]3H HOHCKé QOCTIITOUHO nouyuiiTh TOJIhKO HCKOMOé 3BéHO.

Qo6IIBJIéHHé 3BéHlI B H]3t3H3BOnsHym no3HIJHIO 3£t Bepy riM 3Bé-
HOM.

void Insert2(Link2* St, int data)

Link2* q = new Link2; // 1 Bb QexeHxe MaMR Tx

M OQ 3BeHO
q—>data data; // 2 BuoD QaHHBX
q->next = it->next; // 3 MpO BeQeHwe CBH3w OT
HOBOPO 3BeHa BMe dQ
q— >prev = St; // 4 MpozeQeHxe CBS3x OT HOBO—
TO 3BeHa Ha3aQ
St— >neXt Q; tt b OBeQeHMe CBS3M OT M e—
QLIUy+erO 3BeHa K HOBo>y
if (q->next) // MpO BepKa Haeuuun cneAyruero

3BeHa


q— >next— >prev = q; // 6 MpoeeQeHxe CBS3x

or cxeUyruero sBeHa K HOzovy
@tlJIéHHé 3BéHII Hs Jlio6oro MeCTII CHHCKII 311 Bepy riM 3BéHOM.

void Delete2(Link2* del)

del->prev->next = del->next; // 1 Odpadoixa

CBR 3I4 BMe %Q
if (del->next)
del->next->prev = del->prev; // 2 Odpadoi-
KG CBR 3DI Ha3aQ
delete del; // 3 Oc eO%Om QeHxe MavST w

HOHCK B pBycBo3HOM CHHGKé.

Key)
int Search2(Link2* Start, Link2*& Find, int

Link2* Cur=Start->next; int Success = 0;

102

while (Cur && !Success) if (Cur->data == Key)
Find = Cur; Success = 1; break;

Cur = Cur->next; return Success;

Эта процедура поиска фактически является (за исключением типа данных Lin k2 вместо Lin k1) процедурой «обычного» по— иска (т.е. не для удаления) в односвязном списке.

Операция просмотра списка в прямом направлении ничем не отличается от просмотра односвязного списка.

2.