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 本身。

它应该有两个参数：指向头的指针和一个要添加的值。

这是一个演示程序，展示了如何编写该函数

#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

当然你还需要编写一个递归函数来释放所有为节点分配的内存。

C中递归的双向链表插入

Doubly Linked List Insertion With Recursion in C

c

recursion

linked-list

doubly-linked-list

insertion-sort