使用递归将元素添加到有序双链表中

Question

我想通过使用递归函数将新节点添加到我的有序双链表中。我写了这样的功能，但没有用。我认为问题出在先前元素上的指针。

int create_and_add_node(struct dll_node **front, int number){
    struct dll_node *new_node = (struct dll_node *)malloc(sizeof(struct dll_node));

    if(!new_node)
        return -1;
    new_node->data = number;
    new_node->next = (*front);
    new_node->prev = (*front)->prev;
    *front = new_node;
    return 0;
}

int add_node(struct dll_node **front, int number){
    if(*front != NULL && (*front)->data < number)
        return add_node(&(*front)->next, number);
    else
        return create_and_add_node(front, number);
}

Answer 1

int create_and_add_node(struct dll_node **front, int number){
    struct dll_node *new_node = (struct dll_node *)malloc(sizeof(struct dll_node));

    if(!new_node)
        return -1;
    new_node->data = number;
    new_node->next = (*front);
    new_node->prev = (*front)->prev;
    *front = new_node;
    return 0;
}

此功能不起作用，因为它不会更新(*front)->prev和(*front)->prev->next。应该是

int create_and_add_node(struct dll_node **front, int number){
    struct dll_node *new_node = (struct dll_node *)malloc(sizeof(struct dll_node));

    if(!new_node)
        return -1;
    new_node->data = number;
    new_node->next = (*front);
    new_node->prev = (*front)->prev;
    (*front)->prev->next=new_node;       /* Added line. This line updates (*front)->prev->next */
    (*front)->prev=new_node;       /* Added line. This line updates (*front)->prev */
    *front = new_node;
    return 0;
}

Answer 2

这个任务乍一看并不简单。

如果定义了双向链接列表，则这样的列表应具有两个指针：第一个指针指向列表的头节点，第二个指针指向列表的最后一个节点。否则，定义双向链表没有太大意义。

因此，按顺序在列表中插入节点的递归函数应处理两个指针，以正确更新列表。

下面有一个演示程序，显示了如何为双向链接列表实现这种递归功能。

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

struct dll_node
{
    int data;
    struct dll_node *next;
    struct dll_node *prev;
};

struct dll_list
{
    struct dll_node *head;
    struct dll_node *tail;
};

int add_node( struct dll_node **head, struct dll_node **tail, int number )
{
    if ( *head == NULL )
    {
        *head = malloc( sizeof( struct dll_node ) );
        int success = *head != NULL;

        if ( success )
        {
            ( *head )->data = number;
            ( *head )->next = NULL;
            ( *head )->prev = *tail == NULL ? NULL : *tail;
            *tail = *head;
        }

        return success;
    }
    else if ( number < ( *head )->data )
    {
        struct dll_node *new_node = malloc( sizeof( struct dll_node ) );
        int success = *head != NULL;

        if ( success )
        {
            new_node->data = number;
            new_node->next = *head;
            new_node->prev = ( *head )->prev;
            ( *head )->prev = new_node;
            *head = new_node;
        }

        return success;
    }
    else
    {
        return add_node( &( *head )->next, tail, number );
    }
}

int add_data( struct dll_list *list, int number )
{
    return add_node( &list->head, &list->tail, number  );
}

void display( struct dll_list *list )
{
    for ( struct dll_node *current = list->head; current != NULL; current = current->next )
    {
        printf( "%d -> ", current->data );
    }

    puts( "null" );
}

void reverse_display( struct dll_list *list )
{
    for ( struct dll_node *current = list->tail; current != NULL; current = current->prev )
    {
        printf( "%d -> ", current->data );
    }

    puts( "null" );
}

int main(void) 
{
    struct dll_list list = { .head = NULL, .tail = NULL };

    const int N = 10;

    srand( ( unsigned int )time( NULL ) );

    for ( size_t i = 0; i < N; i++ )
    {
        add_data( &list, rand() % N );
    }

    display( &list );
    reverse_display( &list );

    return 0;
}

程序输出可能看起来像

0 -> 4 -> 5 -> 6 -> 6 -> 6 -> 7 -> 8 -> 9 -> 9 -> null
9 -> 9 -> 8 -> 7 -> 6 -> 6 -> 6 -> 5 -> 4 -> 0 -> null