![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Удалить из списка элемент, информационная часть (ключ) которого совпадает со значением, введенным с клавиатуры.
Решение данной задачи проводим в два этапа – поиск и удаление.
Первый этап – поиск
Алгоритм поиска аналогичен просмотру списка с начала. Введем дополнительный указатель и присвоим ему значение 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. Если удаляемый элемент находится в середине списка, нужно обеспечить связь предыдущего и следующего элементов (см. рис. 3.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. Освобождаем память, занятую удаленным элементом.
Рис. 3.1
Алгоритм освобождения памяти, занятой двунаправленным списком,аналогичен рассмотренному алгоритму для стека (см. лаб. работу № 2).
Дата публикования: 2015-02-22; Прочитано: 498 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!