1

http://publications.gbdirect.co.uk/c_book/chapter6/structures.htmlの例6.7を見ています

（便宜上ここに貼り付けました）

struct list_ele *
sortfun( struct list_ele *list )
{

      int exchange;
      struct list_ele *nextp, *thisp, dummy;

      /*
       * Algorithm is this:
       * Repeatedly scan list.
       * If two list items are out of order,
       * link them in the other way round.
       * Stop if a full pass is made and no
       * exchanges are required.
       * The whole business is confused by
       * working one element behind the
       * first one of interest.
       * This is because of the simple mechanics of
       * linking and unlinking elements.
       */

      dummy.pointer = list;
      do{
              exchange = 0;
              thisp = &dummy;
              while( (nextp = thisp->pointer)
                      && nextp->pointer){
                      if(nextp->data < nextp->pointer->data){
                              /* exchange */
                              exchange = 1;
                              thisp->pointer = nextp->pointer;
                              nextp->pointer =
                                      thisp->pointer->pointer;
                              thisp->pointer->pointer = nextp;
                      }
                      thisp = thisp->pointer;
              }
      }while(exchange);

      return(dummy.pointer);
}

基本的な考え方はわかりますが、そこで何が起こっているのか本当に説明できません。誰かがそのソート関数で何が起こっているのかをより深く、しかし簡単な方法で説明できますか？

一般的ないくつかの質問：

  • なぜdummy.pointer = list;必要なのですか？dummy次に、関数の最後にが返されますが、なぜリストはまだソートされているのですか？
  • コメントThe whole business is confused by working one element behind the first one of interest.はどういう意味ですか？
4

2 に答える 2

2

アルゴリズムは、リストを調べて、各リスト項目とその次の項目を調べます。それらが故障している場合、それらは入れ替わります。その後、このプロセスが繰り返されます。最終的には、場違いなものはなく、切り替えられるものもありません。その時点で、すべての作業が完了します（exchangedゼロのままで示されます）。言い換えれば、最後にリストを調べたとき、何も交換されません。

ダミーは、リスト自体を追跡するために使用されます（最初の2つのリスト項目が入れ替わった場合に備えて）。これが使用されます（リスト内の元の最初のアイテムを比較するための偽の最初のアイテムとしても機能するため、リストへの単純なポインターの代わりに使用されます。これにより、結果リストの特殊なケースが不要になります。最初のアイテムが元のリストの最初のアイテムと異なります。

1、2、3、および4項目のリストについては、紙に書き留めてください。次に、それがどのように機能するかを確認します。作業を終えたら、アルゴリズムを開始して実行するためにリストを配置してみてください。次に、リスト内の2つの項目を交換して、もう一度実行します。

混乱しているビジネス全体についてのコメントに関して、私見に言及しているのは、2つを交換するために単一リンクリスト内の3つのノードを追跡する必要があるという事実だけです。リストにアイテムACBがある場合（そしてリストをABCにすることが目標である場合）、BとCを交換するときは、Aにもアクセスできる必要があります。つまり、「次のノード」ポインターをCからBに変更する必要があります。

于 2012-06-09T20:09:48.443 に答える
2

dummyリストの先頭に最初に設定されるローカル変数です。一時変数thispはを指すように設定されているdummyため、更新されると、が指す内容dummyも更新されます。したがって、dummy.pointer最終的には、ソートされたリストの新しい始まりである要素を指します。 listは引き続きリストの元の先頭を指すため、ヘッドポインターを更新できるように、値が返されます。

nextp混乱させるとは、現在の要素（または）ではなく、関心のある要素がであるという意味だと思いますthisp。つまり、現在の要素を前の要素と比較するのではなく、リスト内の次の要素を現在の要素と比較しています。紛らわしいと思いますが、あまりわかりません。

注：これはバブルソートです。より良いソートアルゴリズムは、 http：//www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.htmlに実装されたマージソートです。

于 2012-06-09T20:06:34.263 に答える