Вставка двойного связного списка с рекурсией в C

Question

Я более или менее просто изучаю C, мне было предоставлено простое задание, которое связано с дважды связанными списками, динамическим распределением данных и рекурсией. Я создал массив из 10 целых чисел, и я пытаюсь поместить эти целые числа в отсортированный дважды связанный список, используя рекурсию. У меня возникают проблемы с вставкой узлов в связанный список; Я думаю, что у меня есть первый узел, но я не уверен, что все остальное имеет смысл. Прямо сейчас я тоже получаю ошибку сегментации ... Спасибо за любую помощь!

#include <stdio.h> 

#include <stdlib.h> 

#define N 10 

typedef struct node_ { 
    int value; 
    struct node_ *next; 
    struct node_ *prev; 
} node; 

void insert(node **head, node *cur, node *p); 
void print_list(node *cur); 


void print_list(node *cur) 
{ 
    if (!cur) { 
    printf("\n"); 
    return; 
    } else { 
    printf("%d ", cur->value); 
    print_list(cur->next); 
    } 
} 

int main(int argc, char *argv[]) 
{ 
    int i; 
    int data[N] = {2, 7, 3, 9, 4, 4, 0, 8, 7, 100}; 
    node *p, *head; 

    head = NULL; 
    for (i = 0; i < N; i++) { 
    p = (node *)malloc(sizeof(node)); 
    p->value = data[i]; 
    insert(&head, head, p); 
    } 

    print_list(head); 
} 

void insert(node **head, node *cur, node *p) 
{ 
    if(*head == NULL) 
    { 
     p->next = (*head); 
//(*head)->prev = p; 
     (*head) = p; 
    } 
    if(p->value < cur->value) 
    { 
     cur->prev->next = p; 
     p->prev = cur->prev; 
     cur->prev = p; 
     p->next = cur; 
    } 
    insert(head, cur, p); 

    //p->next = *head; 
    //*head = p; 
} 

Answer 1

Есть несколько ошибок в вашей рекурсивной insert функции. Это будет ясно в комментариях моего кода:

void insert(node **head, node *cur, node *p) 
{ 
    if(*head == NULL) // the list will contain a single element 
    { 
    p->next = p->prev = NULL; 
    *head = p; 
    return; // we're done for this case! 
    } 
    if(p->value < cur->value) 
    { 
    p->prev = cur->prev; 
    p->next = cur; 
    cur->prev = p; 
    if(cur->prev != NULL) // what if cur is the head? there is no cur->prev! 
     cur->prev->next = p; 
    else 
     *head = p; // p becomes the new head 
    return; // we're done! 
    } 
    if(cur->next == NULL) // if cur is the last in the list, we just insert p after it 
    { 
    cur->next = p; 
    p->next = NULL; 
    p->prev = cur; 
    } 
    else // now we can proceed recursively and check the next element 
    insert(head, cur->next, p); 
} 

Answer 2

Я думаю, что это функция insert сами, который должен выделить новый узел.

Он должен иметь два параметра: указатель на голову и значение, которое нужно добавить.

Вот показательная программа, которая показывает, как эта функция может быть writtem

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

typedef struct node 
{ 
    int value; 
    struct node *next; 
    struct node *prev; 
} node; 

void insert(node **current, int value) 
{ 
    if (*current == NULL || value < (*current)->value) 
    { 
     node *tmp = malloc(sizeof(node)); 
     tmp->value = value; 
     tmp->next = *current; 

     if (*current != NULL) 
     { 
      tmp->prev = (*current)->prev; 
      (*current)->prev = tmp; 
     } 
     else 
     { 
      tmp->prev = NULL; 
     } 

     *current = tmp; 
    } 
    else if ((*current)->next == NULL) 
    { 
     node *tmp = malloc(sizeof(node)); 
     tmp->value = value; 
     tmp->next = (*current)->next; 
     tmp->prev = *current; 
     (*current)->next = tmp; 
    } 
    else 
    { 
     insert(&(*current)->next, value); 
    } 
} 

void print_list(node *current) 
{ 
    if (current == NULL) 
    { 
     printf("\n") ; 
    } 
    else 
    { 
     printf("%d ", current->value); 
     print_list(current->next); 
    } 
}  

#define N 10 

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

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

    for (int i = 0; i < N; i++) 
    { 
     int value = rand() % N; 
     printf("%d ", value); 
     insert(&head, value); 
    } 

    printf("\n"); 

    print_list(head); 

    return 0; 
} 

Выход программы может выглядеть

4 9 0 0 6 7 2 7 3 3 
0 0 2 3 3 4 6 7 7 9 

Конечно вам нужно написать также рекурсивную функцию, которая освободит все выделенные mempry для узлов.