Добавить элемент в упорядоченный двусвязный список с помощью рекурсии - PullRequest
Новая
       75

Добавить элемент в упорядоченный двусвязный список с помощью рекурсии

1 голос
/ 07 мая 2020

Я хочу добавить новый узел в свой упорядоченный двусвязный список с помощью рекурсивной функции. Я написал такую ​​функцию, но она не работает. Я думаю, проблема связана с указателем на предыдущий элемент. 

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

Ответы [ 2 ]

1 голос
/ 08 мая 2020

Задача непростая, как кажется на первый взгляд.

Если вы определили двусвязный список, то у такого списка должно быть два указателя: первый, указывающий на головной узел list и второй, указывающий на последний узел списка. В противном случае нет большого смысла определять двусвязный список.

Таким образом, рекурсивная функция, которая вставляет узлы по порядку в список, будет иметь дело с двумя указателями для правильного обновления списка.

Ниже - это демонстрационная программа, которая показывает, как такая рекурсивная функция может быть реализована для двусвязного списка. 

#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
0 голосов
/ 07 мая 2020 
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;
}
...