5

Добрый день. Есть вот такой код удаления элемента из списка

void del(int n) // n - позиция удаляемого элемента
{
    // Mass - объекты, которые хранятся в списке
    Mass *temp = HEAD, *helping = temp;

    if ((temp != NULL) && (n <= size) && (n >= 0)) // если по этому номеру что-то лежит и этот элемент внутри списка
    {
        for (int i = 0; i < n; i++)
        {
            helping = temp; // предыдущее значение temp
            temp = temp->Next;
        }

        if (temp == HEAD) // если элемент который надо удалить первый
        {
            helping = temp;
            temp = temp->Next;
            HEAD = temp;
            cout << "Удаляемый элемент: " << *helping;
            free(helping);
            size--; // уменьшаем размер списка
            return;
        }
        else // иначе, если он в середине или конце
        {
            // 0 1 2 3 4
            // вводится, к примеру, 2. т.е. helping = 1, temp = 2;
            free(temp);
            size--;
            // 0 1 .. 3 4
            helping->Next = helping->Next->Next;
            // т.е. теперь 1 указывает не на 2, а на 3.
        }
    }

Начало отрабатывается хорошо, т.е. первый элемент он удаляет, а вот другие элементы почему-то не получается. Думаю над этим уже второй день, голова кипит. Представляю себе алгоритм так:

  1. Удаляем элемент
  2. Смещаем остальные элементы списка (слева к удаляемому или справа?)

или вообще сделать так 1. Удаляем элемент

  1. Проходим весь список пока не наткнемся на удаленный (NULL)
  2. Перебрасываем ссылку с элемента перед удаленным на элемент после удаленного (минуя сам удаленный элемент)
  3. Повторяем п.3 пока не будет нулевых элементов. Учитывая, что конец списка мы не рассматриваем.

Всем огромное спасибо за помощь! Открыл много нового для себя в работе с указателями. Отдельное спасибо

@MichaelPak за указание направления в которую стоит копать и указания конкретной ошибки и подробного объяснения,

@Mike за то, что поругал за использование нерационального алгоритма

@alexolut за то, что подсказал разницу в между ned delete и malloc free

@Vlad from Moscow за подробное решение задачи и классную идею о использовании переменной беззнакового типа (так и сделал в итоге).

Я вам очень благодарен, спасибо большое!

4
  • если другие элементы почему-то не получается может покажите код else // иначе, если он в середине или конце
    – Saidolim
    18 ноя 2015 в 4:45
  • @Saidolim конечно. Добавил в код, но не уверен в правильности рассуждений
    – whalemare
    18 ноя 2015 в 5:04
  • 1
    Если уж код действительно на C++, то лучше использовать new/delete, а не malloc/free.
    – αλεχολυτ
    18 ноя 2015 в 8:19
  • @alexolut большое спасибо! Просто увидел использование free в примере и подцепил к своему коду. Буду знать, что это сишная вещь)
    – whalemare
    18 ноя 2015 в 13:39

3 ответа 3

7

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

  1. Доходишь до элемента, ссылка NEXT которого указывает на удаляемый элемент;
  2. Присваиваешь ссылку NEXT удаляемого элемента ссылке предыдущего элемента;
  3. Удаляешь элемент;
  4. Profit!

Таким образом из такого картины:

           +------+    +------+    +------+  
           |данные|    |данные|    |данные|
    \/\/\->+------+    +------+    +------+
           |      |--->|      |--->|  0   |
           +------+    +------+    +------+

получается такая:

           +------+    +------+    +------+
           |данные|    |удален|    |данные|
    \/\/\->+------+    +------+    +------+
           |      |    |  0   | .->|  0   |
           +------+    +------+ |  +------+
                 \______________|

У тебя же проблема заключается в том, что ты сначала удаляешь элемент, а потом пытаешься найти ссылку на следующий, то есть helping->Next->Next после удаления уже не указывает на 3-ий элемент. Попробуй сначала провести работу с указателями, а уже потом удалить элемент.

1
  • 3
    Отличные иллюстрации )
    – Kromster
    18 ноя 2015 в 5:58
5

2 Раза бегать по цепочке - это перебор. Лучше, двигаясь по цепочке, запоминать предыдущий элемент.

Mass *temp=HEAD,*prev=NULL;
int i=0;
while(temp && i<n)
 {
  i++;
  prev=temp; // Запоминаем предыдущий в цепочке
  temp=temp->next;
 }
if(!temp) // Элемент не найден
 {
  return;
 }
if(HEAD==temp)
 {
  HEAD=temp->next;
 } else
 {
  if(prev) prev->next=temp->next;
 }
cout << "Удаляемый элемент: " << *temp;
size--;
free(temp);
1

В принципе у вас написано все правильно за исключением двух моментов.

Первое - это номер удаляемого элемента не может быть равен size . size всегда на единицу больше, чем номер последнего существующего элемента, так как нумерация элементов у вас начинается с 0.

Поэтому вместо условия

    if ((temp != NULL) && (n <= size) && (n >= 0)) // если по этому номеру что-то лежит и этот элемент внутри списка

вам следует написать

    if ((temp != NULL) && (n < size) && (n >= 0)) // если по этому номеру что-то лежит и этот элемент внутри списка
                          ^^^^^^^^

Вы бы облегчили себе жизнь, если бы переменная size имела беззнаковый целый тип. В этом случае не было бы необходимости проверять, что n >= 0. Вы могли бы size объявить, как имеющую тип unsigned int или, как обычно принято, size_t.

Второе - это вы пытаетесь обратиться к уже удаленному элементу в предложении

helping->Next = helping->Next->Next;

Следовало сначала установить значение поля Next, а лишь затем удалять элемент.

С учетом сказанного функция может выглядеть следующим образом

void del(int n) // n - позиция удаляемого элемента
{
    if ((HEAD != NULL) && (n < size) && (n >= 0)) // если по этому номеру что-то лежит и этот элемент внутри списка
    {
        // Mass - объекты, которые хранятся в списке
        Mass *temp = HEAD, *helping = HEAD;

        for (int i = 0; i < n; i++)
        {
            helping = temp; // предыдущее значение temp
            temp = temp->Next;
        }

        if (temp == HEAD) // если элемент который надо удалить первый
        {
            HEAD = temp->Next;
        }
        else
        {
            helping->Next = temp->Next;
        }
        cout << "Удаляемый элемент: " << *temp;
        free(temp);
        size--; // уменьшаем размер списка
    }
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.