Освобождение временного узла из связанного списка - PullRequest
Новая
       49

Освобождение временного узла из связанного списка

0 голосов
/ 09 июля 2020

У меня есть следующая функция для удаления узла из связанного списка в указанной позиции: 

void deleteNodeAt(node *head, int pos) {
    if(head==NULL)
        return;
    node *temp=malloc(sizeof(node));
    int index=0;
    
    while(head!=NULL) {
        if(index==pos-1)
            temp=head;

        if(index==pos) {
            temp->next=head->next;
            head=head->next;
            
            free(temp);
            temp=NULL;
        }   
        else
            head=head->next;

        index++;
    }
}

Он отлично работает, если я не пытаюсь освободить временный узел или если я установил его на NULL, но вызов free (temp) нарушит работу функции. Я не могу понять, что делаю неправильно.

Ответы [ 2 ]

0 голосов
/ 09 июля 2020

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

#define START_OF_LIST  0
void deleteNodeAt(node **phead, int pos)
{
  if (pos < START_OF_LIST || !*phead)
      return;   /* bad pos or empty list, always check input */
  node *prev = *phead;
  if (pos == START_OF_LIST) {
     /* special case - delete head of list */
     *phead = (*phead)->next;
     free(prev);
     return;
  }
  while (1) {
    node * temp = prev->next;
    if (!temp)  /* Not enough elements in list */
        return;
    pos--;
    if(pos == START_OF_LIST) {
       prev->next = temp->next;  /* unlink temp */
       free(temp);
       return;
    }
    prev = temp;  /* On to the next! */
  }
}
0 голосов
/ 09 июля 2020

Сначала я не понимаю, почему вы делаете malloc в коде, который должен освободить узел.

Далее вы освобождаете не тот узел. Узел, который вы хотели освободить, - это head - это не temp.

Попробуйте, например: 

void deleteNodeAt(node *head, int pos)
{
    if(head==NULL)
        return;

    node *temp;
    int index=0;

    while(head!=NULL)
    {
        if(index==pos-1)
            temp=head;

        if(index==pos)
        {
            temp->next=head->next;
       
            free(head);
          
            // Done - the node has been free'd so just return
            return;
        }   

        head=head->next;
        index++;
    }
}

Однако проблема все еще существует.

Рассмотрим это:

Что произойдет, когда pos будет равен нулю (то есть, когда вы попытаетесь удалить текущий head

Ответ: вы будете использовать неинициализированный temp. Это плохо. Кроме того, как вызывающий абонент узнает, что head изменился? Вам понадобится дополнительный код для обработки этого случая.

...