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 是指向 a 的指针，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

是的，垃圾箱确实可以是空的。bin 是empty和 bin存在之间有一个微妙但重要的区别。您认为 bin 是数组的成员是正确的，因此对于数组中的任何内容，都存在一个 bin 。但是，该垃圾箱不一定必须有任何东西。如果输入列表中没有任何元素碰巧落入该箱中，则它可能根本没有任何内容。ii

如果您将一排玻璃杯放在桌子上，并开始在其中一些玻璃杯中装满水，那么这个问题就有一个很好的物理类比。连续的所有杯子都存在并且定义明确，但它们不必都是空的，尤其是当您开始倒出它们时（就像您在上面的这个 bin 排序示例中所做的那样）。

于 2011-02-05T11:26:07.893 回答