|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Алгоритм удаления элемента в списке по ключуУдалить из списка элемент, информационная часть (ключ) которого совпадает со значением, введенным с клавиатуры. Решение данной задачи проводим в два этапа – поиск и удаление. Изменим алгоритм поиска, т.к. в дальнейшем понадобится дополнительный указатель для удаления и добавим контроль на случай отсутствия в списке искомого элемента. Первый этап – поиск 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); Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.) |