0

任何人都可以在这里帮助我，因为我不知道为什么我的排序功能对除头部之外的所有列表进行排序？这是输出：

Forward way: 208 1 87 116 149 238 284 304 327 410 426 523 552 583 625 695 803 848 853 944
Reverse way: 944 853 848 803 695 625 583 552 523 426 410 327 304 284 238 149 116 87 1 208

如您所见，它只是在 208 之后插入，并且即使它对所有列表进行排序，它也会保留 208。这是排序前的实际列表：

Forward way: 208 523 284 410 304 426 583 848 552 803 87 238 1 695 853 149 625 944 327 116
Reverse way: 116 327 944 625 149 853 695 1 238 87 803 552 848 583 426 304 410 284 523 208

这是我的代码：

void list_ins_aft ( node_t *old ,node_t *new )
{

  if ( old->next != NULL )
  {
    old->next->prev = new;
  }
  new->next = old->next;
  new->prev = old ;

  old->next = new ;
}

void list_detach( node_t *n , dlist_t *nlst)
{

  if (n->prev == NULL)
  {
    nlst->head = n->next;
  }
  else 
  {
    n->prev->next = n->next;
  }

  if(n->next == NULL )
  {
    nlst->tail = n->prev;
  } 
  else
  {
    n->next->prev = n->prev;
  }
}


void qsort_segment ( node_t *t1 , node_t *t2 , dlist_t *lst)
{

  /* skip 0 or 1 lengh segment */
  if ( t1 == t2 || t1->next == t2 )
    return;
  /*define pivot and make sure its the first element 
   * so put the less before pivot and bigger after pivot
   * */
  node_t *piv;
  piv = t1->next;
  node_t *s,*b,*temp = piv , *x  = t2 ? t2->next : NULL ;

  for ( s = piv->next ; s != x ; s = b )
  {

    b = s->next ;

    list_detach ( s ,lst ) ;

    if ( s->value < piv->value )
    {
      list_ins_aft(t1 , s );
    }
    else 
    {
      list_ins_aft ( piv , temp == piv ? ( temp = s ) : s );
    }
  }

  /* now sort new segments on right and left sides of pivot the same way */
  qsort_segment ( piv , temp ,lst );
  qsort_segment ( t1 , piv->prev , lst);

}
4

1 回答 1

1

您最初可能将其称为包含指向第一个响应的和指针的qsort_segment(list.head, list.tail, &list);位置。列表中的最后一个元素。listdlist_theadtail

/*define pivot and make sure its the first element 
* so put the less before pivot and bigger after pivot
* */
node_t *piv;
piv = t1->next;

这并不像评论中所说的那样，它将枢轴设置为列表中的第二个元素。考虑到您的递归调用，其意图似乎是t1指向要排序的部分之前的元素，以及t2该部分中的最后一个元素。但是在列表的前面，第一个之前没有元素。所以

    if ( s->value < piv->value )
    {
      list_ins_aft(t1 , s );
    }

确保列表中的第一个节点在整个排序过程中保持不变。

您需要某种方法在列表的前面插入一个元素，无论是list_ins_bef模仿函数list_ins_aft还是显式list_ins_front(node_t *new, dlist_t *lst).

于 2012-09-29T13:38:24.763 回答