Односвязный список, удаление элемента, C++

#cpp #указатели #список

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

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. Удаляем элемент


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




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

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

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

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

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

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

Ответы

Ответ 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--; // уменьшаем размер списка
    }
}


Ответ 2

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


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


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

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


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

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


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


Ответ 3

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

Mass *temp=HEAD,*prev=NULL;
int i=0;
while(temp && inext;
 }
if(!temp) // Элемент не найден
 {
  return;
 }
if(HEAD==temp)
 {
  HEAD=temp->next;
 } else
 {
  if(prev) prev->next=temp->next;
 }
cout << "Удаляемый элемент: " << *temp;
size--;
free(temp);