c++ - C++ 中的 IntSetArray 实现

Question

我试图在 C++ 中实现 IntSetArray，它编译得很好，但结果是错误的，第一个 300 是好的，其他数字低于零，一些非常奇怪的数字。例如 -8231313 类似这样的东西) 怎么了？这是代码

#include <iostream>
using namespace std;
int quantity=10;
class  Set
{
private :
    int n,*x;
public:
    Set(int maxval){
        x=new int[quantity+1];
        n=0;
        x[0]=maxval;

    }
    int size(){ return n;}
    void insert(int t){

         for (int i=0;x[i]<t;i++)
         {

              if (x[i]==t)
                   return ;
               for (int j=n;j>=i;j--)
                   x[j+1]=x[j];
               x[i]=t;
         }

               n++;




    }

     void display()
     {
           for (int i=0;i<n;i++){
               cout<<x[i]<<"  "<<"\n";
           }
     }



};

int main(){

    Set s(300);
    s.insert(123);
    s.insert(45);
    s.insert(89);
    s.insert(50);
    s.insert(13);
    s.insert(19);
    s.display();

     return 0;
}

Answer 1

想一想第一次尝试插入内容时会发生什么。 x[0] 包含 300 和 t，您要插入的是 123。

insert 方法中的第一条语句是这样的:

     for (int i=0;x[i]<t;i++)

当 x 的第 i 元素小于 t 时，此 for 循环递增 i。但是x的第0个元素是300，不小于123，所以循环根本不会执行。由于在构造函数中您只初始化了 x 的第一个元素，因此其余部分具有永远不会更改的垃圾值。

我认为您很可能不希望第二个循环位于第一个循环内。看起来你试图用外循环做的是找到 x 中值大于或等于 t 的第一个位置，然后内循环移动一切都下来并插入 t。那么你应该做的是:

void insert(int t){

     int i; // Declare this outside the first loop so that it
            // remains accessible afterwords

     for (i=0;x[i]<t;i++)
     {
       // Do nothing; the whole point is to increment i
     }

     // Now i contains the first index of x where x[i] >= t
     // So now do the shift and insert:

     if (x[i]==t)
       return ;

     for (int j=n;j>=i;j--)
       x[j+1]=x[j];

     x[i]=t;
     n++;
}

另一种可能更容易理解的写法:

     int i;
     for (i=0;x[i]<t;i++)
     {
       // Do nothing; the whole point is to increment i
     }

这是:

     int i = 0;
     while (x[i] < t) ++i;