0 
  //element of chain.     
    struct studentRecord 
            {
           int score;
           string* name;

           int operator !=(studentRecord x) const
              {return (score != x.score);}
        };


    // binsort,  theChain is a single linked list of students and its element is student Record

         void binSort(chain<studentRecord>& theChain, int range)
            {// Sort by score.

               // initialize the bins
               chain<studentRecord> *bin;
               bin = new chain<studentRecord> [range + 1];

               // distribute student records from theChain to bins
               int numberOfElements = theChain.size();
               for (int i = 1; i <= numberOfElements; i++)
               {
                  studentRecord x = theChain.get(0);
                  theChain.erase(0);
                  bin[x.score].insert(0,x);
               }

               // collect elements from bins
               for (int j = range; j >= 0; j--)
                  while (!bin[j].empty())
                  {
                     studentRecord x = bin[j].get(0);
                     bin[j].erase(0);  ////////// here
                     theChain.insert(0,x);
                  }

               delete [] bin;
            }

chain<studentRecord>単一の連結リストです。bin ソートでは、bin はbin[arrange +1]要素が であるへのポインタchain<studentRecord>です。コードbin[j].erase(i)はdeleteノードになりますi。bin[j].get(i)node の要素 (つまり、studentRecord) を取得しますi。コードでwhile (!bin[j].empty())はチェーンを空にするために を使っていますが、bin[j] は要素配列なので空にすることはできませんよね？

ありがとう。

4

1 に答える 1

1

はい、ビンは実際に空にすることができます。ビンが空である場合とビンが存在する場合には、微妙ではあるが重要な違いがあります。ビンが配列のメンバーであることは正しいため、配列内の境界内にあるすべての位置にビンが存在します。ただし、そのビンには必ずしも何かが入っている必要はありません。入力リストのどの要素もたまたまそのビンに入らない場合は、何も含まれていない可能性があります。ii

この問題は、テーブルに並べたグラスのいくつかに水を入れ始めた場合とよく似ています。行のすべてのグラスが存在し、明確に定義されていますが、すべてが空である必要はありません。特に、注ぎ始めた場合 (上記のビンの並べ替えの例で行っているように)。

于 2011-02-05T11:26:07.893 に答える