c - 递归地在链表末尾插入节点

Question

typedef struct node
{
    int a;
    struct node *next;
}node;
void generate(struct node **head)
{
    int num = 10, i; //the num here is the length
    struct node *temp;

    for (i = 0; i < num; i++)
    {
        temp = (struct node*)malloc(sizeof(struct node));
        temp->a = 10-i;
        if (*head == NULL)
        {
            *head = temp;  //each time add another node to the start
            (*head)->next = NULL;
        }
        else
        {
            temp->next = *head;
            *head = temp;
        }
    }
}
void addSpecific(node* head,int n)
{
    node* temp = NULL;
    if (head->next == NULL)
    {
        temp = (node*)malloc(sizeof(node*)); //allocating memory
        (temp)->a = n;  //adding the wanted value
        (temp)->next = NULL; //making the new node to point to the end
        head->next = temp; //and the previous one to point to temp
    }
    else
    {
        addSpecific(head->next, n); //if this is not the wanted node we need to move to the next node
    }
}
void deleteNode(struct node **head)
{
    struct node *temp;
    while (*head != NULL)
    {
        temp = *head;
        *head = (*head)->next; //going to the next node
        free(temp); //free the allocated memory
    }
}
int main()
{
    struct node *head = NULL;

    generate(&head);
    addSpecific(head, 7);
    display(head);
    deleteNode(&head);
    system("PAUSE");
    return 0;
}

我试图使用递归在末尾插入新节点，但是释放内存(删除)函数进行了扩展，我找不到问题。我尝试了生成函数并在末尾添加了节点，它起作用了，但编译器警告我“堆损坏”。

Answer 1

该函数可以如下所示，如以下演示程序所示

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

typedef struct node
{
    int a;
    struct node *next;
} node;

void addSpecific( node **head, int n )
{
    if ( *head == NULL )
    {
        *head = malloc( sizeof( node ) ); //allocating memory
        ( *head )->a    = n;  //adding the wanted value
        ( *head )->next = NULL; //making the new node to point to the end
    }
    else
    {
        addSpecific( &( *head )->next, n ); //if this is not the wanted node we need to move to the next node
    }
}

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

int main( void ) 
{
    const int N = 10;
    node *head = NULL;

    for ( int i = 0; i < N; i++ ) 
    {
        addSpecific( &head, i );

        display( head );
    }

    return 0;
}

程序输出为

0 
0 1 
0 1 2 
0 1 2 3 
0 1 2 3 4 
0 1 2 3 4 5 
0 1 2 3 4 5 6 
0 1 2 3 4 5 6 7 
0 1 2 3 4 5 6 7 8 
0 1 2 3 4 5 6 7 8 9 

对于函数deleteNode，它可以通过以下方式查找

void deleteNode( node **head )
{
    for ( node *current = *head; current != NULL; )
    {
        node *temp  = current;
        current = current->next; //going to the next node
        free( temp ); //free the allocated memory
    }

    *head = NULL;
}

至于这个函数的实现

void deleteNode( node **head )
{
    while ( *head != NULL )
    {
        node *temp  = *head;
        head = &( *head )->next; //going to the next node
        free( temp ); //free the allocated memory
    }
}

然后它有未定义的行为，因为它尝试访问已删除的结构对象的数据成员。

或者您可以使函数递归。例如

void deleteNode( node **head )
{
    if ( *head != NULL )
    {
        deleteNode( &( *head )->next );
        free( *head );
        *head = NULL;
    }
}