Динамическое распределение заголовка связанного списка - C

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

Моя проблема возникает при выделении памяти для узла указателя головы в куче. Кажется, всегда создается дополнительный головной узел со значением данных 0 (0 отсутствует в наборе данных, но потенциально может быть) при использовании malloc.

    struct node* create_sorted_list(struct node *head)
    {
       struct node * curr = head;
       struct node * sorted_head = malloc(sizeof(struct node));

       while(curr != NULL){
          add_item_sorted(sorted_head, curr->data);
          curr=curr->next;
       }   
       return sorted_head;
    }



    struct node* add_item_sorted(struct node *sorted_head, int data)
    {
       struct node * curr = sorted_head;
       struct node * newN;    
       while(curr->next != NULL){

          if(data > curr->next->data){
             curr=curr->next;
          }
          else{
             newN = malloc(sizeof(struct node));
             newN->data = data;
             newN->next = curr->next;
             curr->next = newN;
             return sorted_head; 
          }
       }   
       newN = malloc(sizeof(struct node));
       curr->next = newN;
       newN->data = data;
       return sorted_head;
    }



    int main(int argc, char *argv[])
    { 
        ......
        struct node * sorted_head = create_sorted_list(head);

        //head in this case comes from an unsorted linked list with the 
        //same data values. Using head linked list to make sorted_head.
    }

Мой вывод выглядит примерно так: 0 -> 56 -> 35 -> 98 -> end
Когда это должно быть: 56 -> 35 -> 98 -> конец

У меня есть основания полагать, что дополнительный узел является результатом одного-многих вызовов malloc, однако я не могу найти правильное решение.

Любая помощь приветствуется. Спасибо, парни.

Источник

2 ответа

Решение

Функция create_sorted_list уже неправильно.

В общем head может быть равен NULL, Однако там создано sorted_head в функции, которая не равна NULL.

struct node* create_sorted_list(struct node *head)
    {
       struct node * curr = head;
       struct node * sorted_head = malloc(sizeof(struct node));
       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
       while(curr != NULL){
           //...
       }   
       return sorted_head;
    }

Более того, его данные не инициализируются. Так что, если функция add_item_sorted для такого узла будет вызван доступ к элементу данных next приведет к неопределенному поведению программы.

  struct node* add_item_sorted(struct node *sorted_head, int data)
    {
       struct node * curr = sorted_head;
       struct node * newN;    
       while(curr->next != NULL){
             ^^^^^^^^^^^

И, по крайней мере, вы должны написать

  while(curr != NULL){
      sorted_head = add_item_sorted(sorted_head, curr->data);
      ^^^^^^^^^^^^^^^

Функции могут быть написаны так, как показано в следующей демонстрационной программе

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *next;
};  

struct node* add_item( struct node *head, int data )
{
    struct node *tmp = malloc( sizeof( struct node ) );
    tmp->data = data;
    tmp->next = head;

    return tmp;
}

struct node* add_item_sorted( struct node *sorted_head, int data );

struct node * create_sorted_list( struct node *head )
{
    struct node *sorted_head = NULL;

    for ( ; head != NULL; head = head->next )
    {
        sorted_head = add_item_sorted( sorted_head, head->data );
    }   

    return sorted_head;
}

struct node* add_item_sorted( struct node *sorted_head, int data )
{
    if ( sorted_head == NULL || !( sorted_head->data < data ) )
    {
        struct node *tmp = malloc( sizeof( struct node ) );

        tmp->data = data;
        tmp->next = sorted_head;
        sorted_head = tmp;
    }
    else
    {
       struct node *current = sorted_head;

        while ( current->next != NULL && current->data < data )
        {
            current = current->next;
        }

        struct node *tmp = malloc( sizeof( struct node ) );
        tmp->data = data;
        tmp->next = current->next;
        current->next = tmp;
    }

    return sorted_head;
}

void display( struct node *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d ", head->data );
    }
    printf( "\n" );
}

#define N   10

int main( void ) 
{
    struct node *head = NULL;

    for ( int i = 1; i <= N; i++ ) head = add_item( head, i );

    display( head );

    struct node *sorted_head = create_sorted_list( head );
    display( sorted_head );

    return 0;
}

Выход программы Rge

10 9 8 7 6 5 4 3 2 1 
1 2 3 4 5 6 7 8 9 10
Источник

Я верю, что это происходит потому, что в вашем add_item_sorted функция, вы получаете доступ к списку, как если бы был фиктивный головной узел (вы начинаете с проверки cur->next->dataгде вы должны быть на самом деле проверка cur->data).

Когда ты malloc узел, он может содержать 0 или любое другое значение в его поле данных. Итак, в вашем случае, sorted_head держит 0 в своем поле данных. Теперь, в соответствии с вашим примером, вы пытаетесь вставить значение 56, В add_item_sorted функция, вы сначала пытаетесь получить доступ cur->next->data, который имеет значение NULL. Итак, новый узел вставляется после этого sorted_head.

Источник
Другие вопросы по тегам