15.4.4. Алгоритм поиска элемента в списке по ключу
Ключом может быть любое интересующее значение (в зависимости от поставленной задачи). Поэтому уточним задачу: найдем конкретное значение info в списке и его порядковый номер.
1. Введем с клавиатуры ключ поиска, т.е. искомое значение i_p.
2. Установим текущий указатель на начало списка:
t = begin;
3. Счетчик элементов k = 1;
4. Начало цикла (выполнять пока t != NULL, т.е. не дойдем до конца).
5. Сравниваем информационную часть текущего элемента с искомым:
а) если они совпадают (t->info=i_p), выводим на экран элемент, его номерkи завершаем поиск (break);
б) иначе, переставляем текущий указатель на следующий элемент и увеличиваем счетчик kна 1:
t=t->Next;
k++;
6. Конец цикла.
15.4.5. Алгоритм удаления элемента в списке по ключу
Удалить из списка элемент, информационная часть (ключ) которого совпадает со значением, введенным с клавиатуры.
Решение данной задачи проводим в два этапа – поиск и удаление.
Изменим алгоритм поиска, т.к. в дальнейшем понадобится дополнительный указатель для удаления и добавим контроль на случай отсутствия в списке искомого элемента.
Первый этап – поиск
1. Введем дополнительный указатель и присвоим ему значение NULL:
Spis *key = NULL;
2. Введем с клавиатуры искомое значение i_p(ключ поиска).
3. Установим текущий указатель на начало списка:
t = begin;
4. Начало цикла (выполнять пока t != NULL).
5. Сравниваем информационную часть текущего элемента с искомым.
5.1. Если они совпадают (t->info=i_p), то (выводим на экран сообщение об успехе);
а) запоминаем адрес найденного элемента:
key=t;
б) завершаем поиск – досрочный выход из цикла (break);
5.2. Иначе, переставляем текущий указатель на следующий элемент:
t=t->Next;
6. Конец цикла.
7. Контроль, если key=NULL, т.е. искомый элемент не найден, то сообщаем о неудаче и этап удаления не выполняем (returnилиexit) .
Второй этап – удаление
1. Если найден элемент для удаления, т.е. key != NULL, то удаляем элемент из списка в зависимости от его местонахождения.
2. Если удаляемый элемент находится в начале списка, т.е. key = begin, то создаем новый начальный элемент:
а) указатель начала списка переставляем на следующий (второй) элемент:
begin=begin->Next;
б) указателю Prevэлемента, который был вторым, а теперь стал первым присваиваем значениеNULL, т.е. предыдущего нет:
begin->Prev=NULL;
3. Если удаляемый элемент в конце списка, т.е. keyравенend, то:
а) указатель конца списка переставляем на предыдущий элемент, адрес которого в поле Prevпоследнего (end):
end=end->Prev;
б) обнуляем указатель на следующий (Next) элемент нового последнего элемента
end->Next=NULL;
4. Если удаляемый элемент находится в середине списка, нужно обеспечить связь предыдущего и последующего элементов:
а) от 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;
5. Освобождаем память, занятую удаленным элементом free(key);