Алгоритмизации

• Название: Алгоритмизации
• Дата: 27.09.2022
• Размер: 1.15 Mb.
• Имя файла: 12_100229_1_124427 (1).docx
• Тип: Документы; #700459
• страница: 34 из 67

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

Удалить из списка элемент, информационная часть (ключ) которого совпадает со значением, введенным с клавиатуры.

Решение данной задачи проводим в два этапа – поиск и удаление.

Изменим алгоритм поиска, т.к. в дальнейшем понадобится дополнительный указатель для удаления и добавим контроль на случай отсутствия в списке искомого элемента.

Первыйэтап– поиск

1. 
   Введем дополнительный указатель и присвоим ему значение NULL: Spis *key = NULL;
   
2. 
   Введем с клавиатуры искомое значение i_p(ключ поиска).
   
3. 
   Установим текущий указатель на начало списка: t = begin;
   
4. 
   Начало цикла (выполнять пока t != NULL).
   
5. 
   Сравниваем информационную часть текущего элемента с искомым.
   
   1. 
      Если они совпадают (t -> info = i_p), то (выводим на экран сообщение об успехе);
      

а) запоминаем адрес найденного элемента: key = t;

б) завершаем поиск – досрочный выход из цикла (break);

2. 
   Иначе, переставляем текущий указатель на следующий элемент: t = t -> Next;
   
1. 
   Конец цикла.
   
2. 
   Контроль, если 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-1
kk+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;

5. 
   Освобождаем память, занятую удаленным элементом free(key);