链表头部动态分配——C

Question

我正在使用 C 语言进行一个小型学习项目，但在实现将保存数据集的第一个数据值的头节点时遇到了麻烦。我应该采用一个未排序的链表并使用它来实现一个排序的链表。它应该像下面的例子一样分成两个函数。

我的问题出现在为堆上的头指针节点分配内存时。使用 malloc 时，它似乎总是创建一个数据值为 0 的额外头节点（0 不在数据集中，但可能在数据集中）。

    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 -> end

我有理由相信多出的节点是一对多调用malloc的结果，但是我找不到正确的解决方案。

感谢任何帮助。谢谢你们。

Answer 1

函数 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

Answer 2

我相信它正在发生，因为在你的 add_item_sorted 函数中，你正在访问列表，就好像有一个虚拟头节点（你开始检查 cur->next->data，你实际上应该在哪里检查 cur->data).

当您 malloc 一个节点时，它可能在其数据字段中持有 0 或任何其他值。因此，在您的情况下，sorted_head 在其数据字段中持有 0。现在，根据您的示例，您尝试插入值 56。在 add_item_sorted 函数中，您首先尝试访问 cur->next->data，它是 NULL。因此，在 sorted_head.

之后插入一个新节点

链表头部动态分配——C

Linked List Head Dynamic Allocation -- C

c

linked-list

data-structures

singly-linked-list