Алгоритм удаления элемента в списке по ключу

Алгоритм поиска аналогичен просмотру списка с начала. Введем дополнительный указатель и присвоим ему значение NULL: Spis2 *key = NULL. Введем с клавиатуры искомое значение i_p (ключ поиска).

1. Установим текущий указатель на начало списка: t = begin;

2. Начало цикла (выполнять пока t! = NULL).

3. Сравниваем информационную часть текущего элемента с искомым, если они совпадают (t -> info = i_p), то запоминаем адрес найденного элемента: key = t; (если ключ поиска уникален, то завершаем поиск – break).

4. Переставляем текущий указатель на следующий элемент: t = t -> next;

5. Конец цикла.

Выполняем контроль, если key = NULL, т.е. искомый элемент не найден, то сообщаем о неудаче и этап удаления не выполняем (return).

Если элемент найден (key! = NULL), то выполняем удаление элемента из списка в зависимости от его местонахождения.

1. Если удаляемый элемент находится в начале списка, т.е. key равен begin, то первым элементом списка становится второй элемент:

а) указатель начала списка переставляем на следующий (второй) элемент:

begin = begin -> next;

б) адресу prev присваиваем значение NULL, т.е. теперь предыдущего нет begin -> prev = NULL;

2. Если удаляемый элемент в конце списка, т.е. key равен end, то последним элементом в списке должен стать предпоследний:

а) указатель конца списка переставляем на предыдущий элемент: end = end -> prev;

б) обнуляем адрес next нового последнего элемента

end -> next = NULL;

3. Если удаляемый элемент находится в середине списка, нужно обеспечить связь предыдущего и следующего элементов (см. рис. 4.1):

а) от k -го элемента с адресом key обратимся к предыдущему (k –1)-му элементу, адрес которого key-> prev, и в его поле next [(key-> prev)-> next] запишем адрес (k +1)-го элемента, значение которого key-> next:

(key -> prev) -> next = key -> next;

б) аналогично, в поле prev (k +1)-го элемента, с адресом key-> next запишем адрес (k –1)-го элемента:

(key -> next) -> prev = key -> prev;

4. Освобождаем память, занятую удаленным элементом.

Рис. 4.1. Схема удаления внутреннего элемента