指向双链接列表中的错误位置？

Question

我的双链表有两个虚拟节点，头部和尾部。addToFirst函数对我来说非常适合，但是当我尝试使用与addToBack相同的算法时，它会一直为我打印虚拟节点。为什么会这样？

DList *init( )
{
   head = ( DList * ) malloc( sizeof( DList ) );
   if ( head == NULL ) {
      prtError( "Insufficient memory!" );
      return( NULL );
   }
   
   tail = ( DList * ) malloc( sizeof( DList ) );
   if ( tail == NULL ) {
      prtError( "Insufficient memory!" );
      return( NULL );
   } 
     
   head->data = -1;
   tail->data = -1;   
   head->next = tail;
   head->prev = NULL;  
   tail->next = NULL; 
   tail->prev = head;
   return ( head );  /* indicates no error */ 
}

/* print function */ 
void prtList( )
{
   DList *p;
   for ( p = head->next; p != tail; p = p->next )
        printf( "%4d", p->data );
   printf( "\n");
}

DList *insertFirst( int d )
{
                
   /***** ADD YOUR CODE HERE *****/
   DList *first = ( DList * ) malloc( sizeof( DList ) );
   printf("FF");
   if ( first == NULL ) {
      prtError( "Insufficient memory!" );
      return( NULL );
   }
   /* 2. put in the data  */
    first->data = d;
 
    /* 3. Make next of new node as head and previous as NULL */
    first->next = (head)->next;
    first->prev = NULL;
 
    /* 4. change prev of head node to new node */
    if ((head) != NULL)
        (head)->prev = first;
 
    /* 5. move the head to point to the new node */
    (head)->next = first;

   return first;        // replace this line with your code
}

DList *insertLast( int d )
{

   DList *last = ( DList * ) malloc( sizeof( DList ) );
   printf("LL");
   if ( last == NULL ) {
      prtError( "Insufficient memory!" );
      return( NULL );
   }
   /* 2. put in the data  */
    last->data = d;
 
    /* 3. Make next of new node as head and previous as NULL */
    last->prev = tail->prev;
    last->next = NULL;
 
    /* 4. change prev of head node to new node */
    if ((tail) != NULL)
        (tail)->next = last;
 
    /* 5. move the head to point to the new node */
    (tail) = last;
    //if I try with (tail)->prev = last; then the outputs were empty.


   return last; // replace this line with your code          

}

预期结果：

LL  5
LL  5  10
LL  5  10  15
LL  5  10  15  20
LL  5  10  15  20  25
LL  5  10  15  20  25  30
LL  5  10  15  20  25  30  35
LL  5  10  15  20  25  30  35  40
LL  5  10  15  20  25  30  35  40  45
LL  5  10  15  20  25  30  35  40  45  50
FF   5   5  10  15  20  25  30  35  40  45  50
FF  10   5   5  10  15  20  25  30  35  40  45  50
FF  15  10   5   5  10  15  20  25  30  35  40  45  50
FF  20  15  10   5   5  10  15  20  25  30  35  40  45  50
FF  25  20  15  10   5   5  10  15  20  25  30  35  40  45  50
FF  30  25  20  15  10   5   5  10  15  20  25  30  35  40  45  50
FF  35  30  25  20  15  10   5   5  10  15  20  25  30  35  40  45  50
FF  40  35  30  25  20  15  10   5   5  10  15  20  25  30  35  40  45  50
FF  45  40  35  30  25  20  15  10   5   5  10  15  20  25  30  35  40  45  50
FF  50  45  40  35  30  25  20  15  10   5   5  10  15  20  25  30  35  40  45  50

我的结果：

LL  -1
LL  -1   5
LL  -1   5  10
LL  -1   5  10  15
LL  -1   5  10  15  20
LL  -1   5  10  15  20  25
LL  -1   5  10  15  20  25  30
LL  -1   5  10  15  20  25  30  35
LL  -1   5  10  15  20  25  30  35  40
LL  -1   5  10  15  20  25  30  35  40  45
FF   5  -1   5  10  15  20  25  30  35  40  45
FF  10   5  -1   5  10  15  20  25  30  35  40  45
FF  15  10   5  -1   5  10  15  20  25  30  35  40  45
FF  20  15  10   5  -1   5  10  15  20  25  30  35  40  45
FF  25  20  15  10   5  -1   5  10  15  20  25  30  35  40  45
FF  30  25  20  15  10   5  -1   5  10  15  20  25  30  35  40  45
FF  35  30  25  20  15  10   5  -1   5  10  15  20  25  30  35  40  45
FF  40  35  30  25  20  15  10   5  -1   5  10  15  20  25  30  35  40  45
FF  45  40  35  30  25  20  15  10   5  -1   5  10  15  20  25  30  35  40  45
FF  50  45  40  35  30  25  20  15  10   5  -1   5  10  15  20  25  30  35  40  45

Answer 1

我怀疑这个问题是通过你的虚拟元素引入的。我更多地使用单链接列表，而不是双向列表。但在这种情况下，我有一个头部指针，它不在列表中。当列表为空时，则为空。这需要特殊的案例html" target="_blank">代码来检查每次插入时列表的头是否为空。因为插入是稍微不同的。

所以我倾向于你们的情况是，头和尾都是空的。然后，当添加第一个元素时，head和tail被设置为指向同一个元素。元素的next和prev将被设置为null。因为之前或之后都没有元素。

然而，我认为对于双向链表（通常被称为双链表）有一个更干净的解决方案。在该解决方案中，只有一个“虚拟”条目。同时充当头部和尾部。嗯-

因为我怀疑这是一个编码练习，所以我没有为您编写代码。相反，这有助于理解其中的逻辑。

Answer 2

这里有几个错误。我建议你重新复习一下基础知识。下面是对代码的快速修复。确保理解每个变化。

DList *insertFirst( int d )
{
                
   /***** ADD YOUR CODE HERE *****/
   DList *first = ( DList * ) malloc( sizeof( DList ) );
   printf("FF");
   if ( first == NULL ) {
//      prtError( "Insufficient memory!" );
      return( NULL );
   }
   /* 2. put in the data  */
    first->data = d;
 
    /* 3. Make next of new node as head and previous as NULL */
    first->next = (head)->next;
    first->prev = head;
 
    head->next->prev=first;
    (head)->next = first;

   return head;        // replace this line with your code
}

DList *insertLast( int d )
{

   DList *last = ( DList * ) malloc( sizeof( DList ) );
   printf("LL");
   if ( last == NULL ) {
//      prtError( "Insufficient memory!" );
      return( NULL );
   }
   /* 2. put in the data  */
    last->data = d;
 
    /* 3. Make next of new node as head and previous as NULL */
    last->prev = tail->prev;
    last->next = tail;
    tail->prev->next=last;
    tail->prev=last;
   return head; // replace this line with your code 
}```