АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. RS-триггеры на логических элементах
  2. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  3. Абсолютная полнота элемента леса
  4. Алгоритм
  5. Алгоритм MD4
  6. Алгоритм RC6
  7. Алгоритм RSA
  8. Алгоритм Брезенхема для окружности
  9. Алгоритм Брезенхема.
  10. Алгоритм взятия мазка из носа и зева.
  11. Алгоритм вибіркового методу
  12. Алгоритм вставки элемента в список после элемента с указанным ключом

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

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

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

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

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);


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.)