Удаление узла, добавленного в конец связанного списка в C - PullRequest
Новая
       10

Удаление узла, добавленного в конец связанного списка в C

0 голосов
/ 03 сентября 2018

У меня есть связанный список, где каждый узел хранит слово и число. Я могу добавить узлы вверху списка (push), в центре списка (insertAfter) и в конце списка (append). Теперь я добавил функцию для удаления узлов, где он будет принимать символ, он будет искать этот символ в списке и удалять узел, который хранит этот символ.

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

Tl; dr deleteNode работает с узлами, созданными с помощью push, но не с узлами, созданными с помощью append или insertAfter.

Я получаю ошибку segmentation fault, поэтому у меня нет конкретной ошибки от компилятора. Я пытаюсь отладить его, запустив разные части кода, но все еще не могу найти проблему. 

struct Node
{
  int data;
  char *word;
  struct Node *next;
};


void push(struct Node** head_ref, int new_data, char *new_word)
{
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    new_node->data  = new_data;


    new_node->word= malloc(strlen(new_word));
    strcpy(new_node->word, new_word);

    new_node->next = (*head_ref);

    (*head_ref)    = new_node;
}

/* Given a node prev_node, insert a new node after the given 
   prev_node */
void insertAfter(struct Node* prev_node, int new_data, char *new_word)
{

    if (prev_node == NULL)
    {
      printf("the given previous node cannot be NULL");
      return;
    }

    struct Node* new_node =(struct Node*) malloc(sizeof(struct Node));

    new_node->data  = new_data;

    new_node->word= malloc(strlen(new_word));
    strcpy(new_node->word, new_word);

    new_node->next = prev_node->next;
    prev_node->next = new_node;
}


void append(struct Node** head_ref, int new_data, char *new_word)
{

    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    struct Node *last = *head_ref;  


    new_node->data  = new_data;

    new_node->word= malloc(strlen(new_word));
    strcpy(new_node->word, new_word);

    new_node->next = NULL;


    if (*head_ref == NULL)
    {
       *head_ref = new_node;
       return;
    }


    while (last->next != NULL)
        last = last->next;


    last->next = new_node;
    return;
}



void deleteNode(struct Node **head_ref, char *word)
{

    struct Node* temp = *head_ref, *prev;
    if (strcmp(word, (*head_ref)->word)==0)
    {
        *head_ref = temp->next;   // Changed head
        free(temp);               // free old head
        return;
    }



    while (strcmp(word, (*head_ref)->word)!=0)
    {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;


    prev->next = temp->next;

    free(temp);  // Free memory

}

Ответы [ 3 ]

0 голосов
/ 03 сентября 2018

Кроме того, что было сказано @ 4386427, вы не выделяете достаточно места для своих строк: 

new_node->word= malloc(strlen(new_word));

Обратите внимание, что библиотечная функция C size_t strlen(const char *str) вычисляет длину строки до, но не включая завершающий нулевой символ. Поэтому я бы предпочел: 

new_node->word= malloc(strlen(new_word) + 1);
new_node->word[strlen(new_word)] = '\0';

Это может вызвать проблемы с памятью. ;)

Или лучше, используйте calloc, поэтому вторая строка будет ненужной: 

new_node->word= calloc(strlen(new_word) + 1, sizeof(char));
0 голосов
/ 04 сентября 2018

Ответы у вас в порядке, но только для записи, после достаточной практики это должно выглядеть примерно так: 

void deleteNode(struct Node **pplist, char *word)
{
    for (struct Node *n = *pplist; n; n=*(pplist = &(n->next)))
    {
        if (!strcmp(n->word,word))
        {
            *ppnode = n->next;
            free(n->word);
            free(n);
            break;
        }
    }
}

Дело в том, что вы можете просто перемещать указатель на указатель узла по списку, а не рассматривать голову как особый случай.

Точно так же вы можете добавить как: 

void append(struct Node** pplist, int new_data, char *new_word)
{
    for(; *pplist; pplist=&((*pplist)->next));
    push(pplist, new_data, new_word);
}

и insert_after(prev... это просто push(&(prev->next)...

0 голосов
/ 03 сентября 2018

Эта часть выглядит странно: 

while (strcmp(word, (*head_ref)->word)!=0)
{
    prev = temp;
    temp = temp->next;
}

В strcmp вы используете head_ref, но в теле вы обновляете temp для перехода к следующему элементу.

Вы намеревались сделать: 

while (strcmp(word, temp->word)!=0)
{
    prev = temp;
    temp = temp->next;
}

Далее, вероятно, следует проверить, что temp равен NULL. Как: 

while (temp && strcmp(word, temp->word)!=0)
...