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

В случае представления строки массивом вставка строки S1 в строку S2, начиная с позиции N, может быть выполнена следующим образом:

- часть строки S2, начиная с символа N, сдвигается вправо на длину строки S1

- строка S1 копируется в освободившееся пространство

Таким образом, операция вставки связана с физическим переме­ще­нием данных, объем которых может быть значительным. В случае использования списочной организации, операция вставки сводится к изменению нескольких указателей. На рис. 6 изображена операция вставки строки "ИЦ" в слово "КОРА" так, чтобы получилось слово "КОРИЦА". Пунктиром изобра­жены связи после выполнения операции.

Рис. 6 Вставка в список

Рассмотрим операции вставки и удаления узлов.

NODE *InsertNode(NODE *p){

// функция выполняет вставку нового узла вслед за

// узлом p и возвращает указатель на новый узел

NODE *x;

x=new NODE;

x->Next=p->Next;

p->Next=x;

return x;

}

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

NODE *InsertNode(NODE **p){

// функция выполняет вставку нового узла вслед за

// *p и возвращает указатель на новый узел

NODE *x;

x=new NODE;

x->Next=*p;

*p=x;

return x;

}

Теперь, если требуется выполнить вставку узла вслед за узлом, на который указывает указатель z, следует обратиться к функции:

S=InsertNode(&(z->Next));

А для вставки узла в начало списка, на который указывает указатель q, следует использовать обращение:

q=InsertNode(&q);

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

Для удаления узла односвязного списка необходимо знать указатель на его предшественника:

bool DeleteNode(NODE *p){

// функция удаляет узел, следующий за p

// и возвращает true в случае успеха

NODE *t;

if(p->Next==NULL)return false;

t=p->Next;

p->Next=t->Next;

delete t;

return true;

}

Рассмотрим следующую простую задачу, иллюстрирующую технику работы с односвязным линейным списком. Проходя список:

- удалить все вхождения символа ‘Ы‘,

- заменить всюду '?' на '!'

- после каждого вхождения символа 'А' добавить символ 'Б'.

Поскольку предстоит выполнение удалений, в алгоритме будут использованы два рабочих указателе – на текущий элемент и на его предшественника. На начало списка указывает NODE *h. Первый узел списка не обрабатывается (см. далее "голова списка").

NODE *p1, *p2, *x;

for(p1=h,p2=p1->Next; p2!=NULL;p1=p1->Next,p2=p1->Next){

switch(p2->Letter){

case ‘Ы’:

p1->Next=p2->Next;

delete p2;

break;

case ‘?’:

p2->Letter=’!’

break;

case ‘А’:

x=new NODE;

x->Letter=’Б’;

x->Next=p2->Next;

} // switch

} // for