0

私のソート機能がヘッドを除くすべてのリストをソートしている理由がわからないので、誰か助けてください。出力は次のとおりです。

前方へ：208 1 87 116 149 238 284 304 327 410 426 523 552 583 625 695 803 848 853 944
逆道：944 853 848 803 695 625 583 552 523 426 410 33304284 284 284 238 149 116 87 1 208

ご覧のとおり、208 の後に挿入するだけで、すべてのリストを並べ替えても 208 が保持されます。ソート前の実際のリストは次のとおりです。

前方へ：208 523 284 410 304 426 583 848 552 803 87 238 1 695 853 149 625 944 327 116
逆道：116 327 944 625 149 853 695 1 238 87 803 552 848 583

これが私のコードです：

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);場所としてそれを呼び出しlistます。リストの最後の要素。dlist_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;

これはコメントで述べられていることを行わず、ピボットをリストの2番目の要素に設定します。再帰呼び出しを考慮すると、ソートされるセクションの前の要素と、セクションの最後の要素を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 に答える