使用递归向有序双向链表添加元素

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);
}

struct dll_node的定义是

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

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 ( int 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

使用递归向有序双向链表添加元素

Add element to ordered doubly linked list using recursive

c

recursion

data-structures

doubly-linked-list