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

Добавление звена в произвольную позицию за ведущим звеном.

void Insert1(Link1* link, int data) // link —

звено, за которым вставляется новое

Link1* q = new Linkl; // 1 Выделение памяти not новое звено

q— >data data; // 2 Ввод данных
q->next = link->next; // 3 Провеиение связи от нового звена к слеАуюwему

link->next q;
от ”старого" звена у новому
// 4 ПровеUение связи

Возможность перемещаться по односвязному списку только в одном направлении приводит к тому, что при удалении звена приходится задавать не реально удаляемое звено, а предшест- вующее ему. Это делается для того, чтобы можно было скоррек- тировать связь для предшествующего звена, добраться до которо- го от удаляемого иначе невозможно.

Удаление звена из любого места списка за ведущим звеном.

void Delete1(Link1* link) // link - звено, преАшествуюиее уАаляемому

Link1* q;

if (link->next) // Проверка на нали- чие звена, слеАуюwего за link, то же, что и if(link->next!=NULL)

95

q link->next // 1 Запоминание удаляемого звена для операции delete
link->next = q->next; // 2 Провеиение но- вой связи в обход удаляемого звена
delete q; // 3 Освобождение памяти

Одной из наиболее простых операций со всеми типами спи- сков является их прохождение, т.е. поочерёдное получение дос- тупа ко всем элементам. Приведём процедуру, реализующую эту операцию для просмотра списка (другие варианты использова- ния прохождения — поиск данных и сохранение списка в файл). В случае перемещения по двусвязному списку в «прямом» направ- лении эта процедура является одинаковой цяя одно- и двусвязно-

ГО Л fIHi?ЙH bf X CПИGKOB.
Просмотр односвязного линейного списка.

void Show(Link1* link)

L iп k1 *q = 1iп k —> n ex L ; // Учитывается наличие

"пустого” ведущего звена
while (q) //илн while(q!=NULL)

спит < + q— >da L a << ' ' ; // или другая операция q q—> n ex L ; // Переход по списку

cout << endl;

Jfoucк в списке является вариантом операции просмотра и отличается тем, что:

1. 
   вместо операции вывода на экран ( cou L << q—+ daLa) используется операция сравнения искомых данных с хранящими- ся в звеньях списка;
   
2. 
   если искомые данные найдены, нет необходимости пере- мещаться по списку дальше.
   

96
Поиск в односвязным списках имеет следующую особен- ность. Если он выполняется в сочетании с удалением, то резуль- татом поиска может (или должно) быть не то звено, в котором содержатся искомые данные, а предшествующее ему. В итоге для поиска в списке могут потребоваться либо две различные процедуры «обычная» и находящая предыдущее звено, либо одна универсальная, позволяющая найти оба звена — с искомыми данными и предшествующее ему. Рассмотрим в качестве примера именно этот вариант.
Универсальная процедура поиска (находит звено с ключом поиска и предшествующее ему).

int Search(Link1* Start, //Точка началапонска

Link1*& Find, / Указатель для звенас нс-
комымиданнымп
Гinkl* а Pred, // Указатель для предыдущего звена
in L K ey ) // Ключ поиска


Liпk 1 * Cur = SCan— >nex L ; // Текущее звено
Pred = SCan ; // Предыдущее звено ("отстаёт" на 1
шаг от текущего)

лен в 0)

int Success
ycпexa поиска (установ-

while (Cur && !Success) //Операцпя логпяесхое ”И”

if (Cur->data == Key) / ашяи

Find Cur ; // Запоминание найденного звена Suooess = 1 ; // Установка в 1 признака успеха break; // Выход из цикла при удачном поиске

Pred = Cur; //Меремещениепредыдущегозвена Cur = Cur->next; // Мереходпоспискувперёд

return Success;

97

Следует отметить, что возможны разные (в том числе более короткие) варианты реализации такого алгоритма, например, без переменной Success (вместо неё используется указатель Find, который до начала поиска должен получить значение NULL и со- хранить его при неудачном поиске).
Процедура, которая находит только искомое звено, является более простой, — в ней не нужен указатель Pred и все операторы,
В КОТО]ЭЬІХ ОН ИСПОЛЬЗ ТСЯ.
Похожая процедура применяется для односвязного кольце- вой списка. Отличие её от рассмотренного примера заключается в условии продолжения цикла в операторе w hi 1е:
while(Cur != Start && !Success) // Для кольце— вого списка