Ошибка сегментации (ядро сброшено) при поиске / удалении связанного списка В C

Question

Итак, я делаю очень базовое c C упражнение со связанным c связанным списком. Я продолжаю получать ошибку сегментации, и я не очень уверен, о чем она может быть.

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

Структура узла:

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

Я добавлю добавление, поиск и удаление, потому что остальная часть кода принадлежит моим профессорам и работает все, это просто проблема, которую я создал.

add

void add_ll( struct Node * anchor, char * word ) {
        // given a pointer to the anchor of the list, and a word, add the word
        // to the list, does not matter where (except don't replace the anchor)
        struct Node * newNode = (struct Node *) malloc(sizeof(struct Node)) ;
        newNode -> word = word;
        newNode -> next = anchor -> next;
        anchor -> next = newNode;
        if(anchor == NULL){
          anchor -> next = NULL;
          anchor -> word = word;
      }
      return ;
  }

find

struct Node * find_ll(struct Node * anchor, char * word) {
        // given a pointer to the anchor of the list, and a word, search
        // the list for the word. return the pointer to the with the word, if found,
        // or NULL if not found
        if (anchor -> word == NULL)
          {
            struct Node * node = new_ll();
            return node;
          }
        while(anchor != NULL)
          {
            if(anchor -> word == word)
              return anchor;
            else
              anchor = anchor -> next;
          }
        return NULL ;
}

удалить

void remove_ll( struct Node * anchor, struct Node * node_to_remove ) {
        // given a list anchor, and a pointer to a node in the list (but not the anchor)
        // do pointer surgery to remove the node, and free it.
        // sanity checks
        assert(node_to_remove) ;
        assert(node_to_remove!=anchor) ;
        while(anchor != NULL)
          {
            struct Node * temp = anchor;
            struct Node * prev = anchor;
            while(temp != NULL && temp != node_to_remove)
              {
                prev = temp;
                temp = temp -> next;
              }
            prev -> next = temp -> next;
            free(temp);
          }
        return ;
}

То, что я пытался увидеть, исправит ли оно, включает изменение

while(temp != NULL && temp -> next != node_to_remove) на while(temp != NULL && temp != node_to_remove)

, если у него есть что-то делать с доступом к информации слишком рано, но это ничего не исправило.

Также это не классная работа в классе, если это влияет на вашу моральную помощь мне!

Так что мой вопрос в основном ... Что вызывает ошибку сегментации, и если это действительно единственная проблема, как я могу go исправить ее? Если вы заметили какие-либо другие ошибки, пожалуйста, укажите на них. Я был бы очень признателен! Если мне не хватает какой-либо информации, я тоже могу ее добавить! Все заголовки методов являются моими профессорами и не должны быть затронуты!

Answer 1

Функция add_ll() прервется, если anchor НЕДЕЙСТВИТЕЛЕН, но в противном случае создаст допустимый список. Я заметил, что он не копирует строку в структуру Node. Это то, что нужно? Кажется странным добавлять новый элемент после заголовка списка. Как правило, самый простой способ - просто создать новый головной узел.

struct Node *add_ll( struct Node *anchor, char *word ) 
{
    // given a pointer to the anchor of the list, and a word, add the word
    // to the list, does not matter where (except don't replace the anchor)
    // returns the new list

    struct Node * new_node = (struct Node *)malloc( sizeof( struct Node ) );
    if ( new_node != NULL )
    {
        new_node->word = word;
        new_node->next = anchor;
    }
    else
    {
        // TODO: Handle Out of memory error
    }

    return new_node;
}

Когда создается новый узел, возможно, с NULL anchor, он создает новый список. Новый пункт всегда добавляется в начало списка:

struct Node *my_list = NULL;
...
my_list = add_ll( my_list, "some string" );

Я не совсем понимаю причины, стоящие за некоторыми частями find_ll(). Зачем создавать новый пустой (?) Узел. Лучшая реализация могла бы быть:

struct Node *find_ll( struct Node *anchor, char *word ) 
{
    // given a pointer to the anchor of the list, and a word, search
    // the list for the word. return the pointer to the Node with the word, if found,
    // or NULL if not found

    struct Node *result = NULL;

    while( anchor != NULL )
    { 
        if ( anchor->word == word )         // Should this be a strcmp()?
        {
            result = anchor;                // found it
            break;
        }
        else
        {
            anchor = anchor->next;          // skip to the next item
        }
    }

    return result;                          // PRO-TIP: return from a single place
}

И remove_ll() - Как это может удалить элемент "head" из списка? Нужно как-то вернуть измененный список.

struct Node *remove_ll( struct Node *anchor, struct Node *node_to_remove ) 
{
    struct Node *result = anchor;

    // given a list anchor, and a pointer to a node in the list (but not the anchor)
    // do pointer surgery to remove the node, and free it.
    // return a pointer to the changed list

    // sanity checks
    assert( anchor );
    assert( node_to_remove );

    // Case where head-node is to be removed
    if ( node_to_remove == anchor )
    {
        // make a new head
        result = anchor->next;                              // snip (of head)
    }
    else
    {
        while( anchor->next != NULL )
        {
            if ( anchor->next == node_to_remove )
            {
                // point to anchor's next-next, removing the node
                anchor->next = node_to_remove->next;   // snip (in body)
            }
            else
            {
                // no match, search ahead
                anchor = anchor->next;
            }
        }
    }
    return result;
}

Таким образом, удаление головы может быть вызвано:

my_list = remove_ll( my_list, head_node );

И у my_list может быть та же самая голова, что и раньше, или 2-й узел.

Answer 2

Ну, если вы не знаете, когда произошла ошибка, я тоже не знаю.

Но я вижу проблему в add:

if(anchor == NULL) {
    anchor -> next = NULL;
    anchor -> word = word;
}

Если anchor равно NULL, тогда установка его свойств сделает sh вашей программой. NULL не является действительным указателем и никогда не должен использоваться.

И в find:

while(anchor != NULL)
{
    if(anchor -> word == word)
        return anchor;
    else
        anchor = anchor -> next;
}

Вы понимаете, что делает anchor->word == word? Если оба указывают на одну и ту же строку, она вернет false, потому что сравнивает указатели. То есть он сравнивает адрес каждой строки. Он вернет true, только если оба указателя указывают на одну и ту же память. Посмотрите на strcmp(), чтобы сравнить строку.

А в remove:

while(anchor != NULL)
{
    struct Node * temp = anchor;
    struct Node * prev = anchor;

    while(temp != NULL && temp != node_to_remove)
    {
        prev = temp;
        temp = temp -> next;
    }
    prev -> next = temp -> next;
    free(temp);
}

Итак, это тоже не совсем правильно. С одной стороны, если temp всегда равен NULL, то temp = temp->next будет обращаться к указателю NULL. Опять же, NULL является недопустимым указателем и никогда не должен использоваться. В общем, я бы полностью переписал это. Я не вижу никакой причины для вложенных циклов. Одного l oop должно быть достаточно. И логику c нужно упростить.