Форум программистов, компьютерный форум CyberForum.ru

Удаление нескольких элементов из односвязного списка - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Hugo_Boss
1 / 1 / 0
Регистрация: 29.01.2013
Сообщений: 46
22.06.2013, 23:22     Удаление нескольких элементов из односвязного списка #1
Всем привет!

Собственно, сабж: есть односвязный список с повторяющимися элементами. Мне надо удалить определенные элементы. Есть функция, но она удаляет только первый такой элемент.

Скажите, пожалуйста, как мне реализовать эту затею?

Премного благодарен за помощь.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void deleteElem(int val)
{
  Node *current = head;
  Node *prev = nullptr;
 
  while (current && current->value != val)
    {
      prev = current;
      current = current->next;
    }
 
    if (current)
    {
      if (prev)
      {
        prev->next = current->next;
      }
      else
        head = current->next;
      delete current;
 
  }
Структура одного элемента:

C++
1
2
3
4
5
struct Node 
  {
    int value;
    Node *next;
  }
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ksandro
31 / 31 / 1
Регистрация: 15.04.2011
Сообщений: 81
23.06.2013, 00:57     Удаление нескольких элементов из односвязного списка #2
C++
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
void deleteElements(int val)
{
    Node *current = head;
    Node *prev = nullptr;
 
    while(current)
    {
        if(current->value == val)
        {
            if(prev)
            {
                prev->next = current->next;
            }
            else
            {
                head = current->next;
            }
            Node tmp = current->next;
            delete current;
            current = tmp;
        }
        else
        {
            prev = current;
            current = current->next
        }
    }
}
вот как-то так.... я не компилировал и не проверял что работает, так что у меня могут быть ошибки....
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
23.06.2013, 01:07     Удаление нескольких элементов из односвязного списка #3
Цитата Сообщение от Hugo_Boss Посмотреть сообщение
Мне надо удалить определенные элементы.
технология этого дела проста
допустим нужно удалить пятый элемент
доходим до него с голова
смотрим на что он указывает (на шестой)
идем к четвертому элементу
и подменяем указатель на пятый на указатель на шестой
при этом запоминаем указатель на пятый
все элемента больше нет в списке, но он все еще болтается в памяти
и здесь нам понадобится указатель на пятый(который сохранен) по нему удаляем элемент из памяти

во вставке тоже нет ничего сложного
создаем объект
запоминаем указатель на него
идем до четвертого
считываем на что он указывает
записываем это в только что созданный
а в четвертом в указатель записываем указатель на только что созданный обект
Hugo_Boss
1 / 1 / 0
Регистрация: 29.01.2013
Сообщений: 46
23.06.2013, 07:00  [ТС]     Удаление нескольких элементов из односвязного списка #4
@ksandro, Круто, спасибо - я разобрался, в чем дело.
Из ошибок: в одном месте пропущена ;.

И здесь:
Цитата Сообщение от ksandro Посмотреть сообщение
C++
1
Node tmp = current->next;
Надо, естественно, так:
C++
1
Node *tmp = current->next;
@ValeryS, Да я в принципе понимаю технологии что вставки, что удаления - просто до меня не доходило, как надо удалять несколько элементов из списка за 1 проход.
Yandex
Объявления
23.06.2013, 07:00     Удаление нескольких элементов из односвязного списка
Ответ Создать тему
Опции темы

Текущее время: 05:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru