0

基本上是一个动态数组，当满时会进行圆形旋转。您可以访问每个元素，并且可以更改它的值，但是您只能从两端插入和删除。（恒定时间）。大多数方法似乎工作正常，但是在某些“推送”数字上我得到错误的输出。
例如，第一个输入是1,2,3然后我4在最后插入。下一个输出是：2,3,4但是在我5最后插入之后，输出是2, 3, 5

我不知道是什么原因造成的。我在下面发布了整个源代码（至少与必须隐藏错误的测试有关的功能）。文件中有一些文档和一个错误示例，以防我没有清楚地解释事情。

#include <iostream>

using namespace std;

template <typename Object>
class ArrayVector {
private:
  int capacity; // capacity
  int sz; // number of elements
  Object*   a;
  int f; // start of the indexes
  int b; // end of the indexes
public:
  ArrayVector(int initCap);
  ~ArrayVector();

  int size() const { return sz; }
  bool isEmpty() const { return size() == 0; }
  Object elemAtRank(int r);
  void pushBack( const Object& e);
  void pushFront(const Object& e);
  void popBack();
  void popFront();
};

template <typename Object> // constructor
 ArrayVector<Object>::
ArrayVector(int initCap) {
  capacity = initCap;
  sz = 0;
  a  = new Object[capacity];
  f = 0;
  b = 0;
}

 template <typename Object> // gets the element at a certain rank
 Object ArrayVector<Object>:: elemAtRank(int r)
 {
     return a[(f + r) % sz]; // starting position in real array + r % number of elements
 }




template <typename Object>
 void ArrayVector<Object>:: pushBack( const Object& e)
 {
     if(sz == capacity && sz > 0) // if the array is full time to spin it
     {
         if(f == capacity){          // Handles the front.
           f = 0;             // if the front is equal to the capacity
                        // set it to zero, else increment
         }else{
           f++;
         }
         if(b == capacity){     //Handles the back
             b = 0;             //if the back is equal to the capacity
           //  cout<< "SC insert  "<< e << " at  "<< b  <<endl;
             a[b] = e;
         }else{                 // set it to zero, else increment
            a[b] = e;
           // cout<< "SC insert  "<< e << " at  "<< b  <<endl;
            b++;
         }
     }else{

        a[b] = e;
      //  cout<< "insert  "<< e << " at  "<< b  <<endl;
        b++;
         sz++;
     }

 }

 template <typename Object>
  void ArrayVector<Object>:: pushFront( const Object& e)
  {
      if(f == 0){
          f = capacity-1;
      }else{
          f--;
      }
      a[f] = e;
      if(sz< capacity)
          sz++;
  }

int main()
{
    // Fill array and print it
    cout << "Fill with numbers" << endl;
    ArrayVector<int> asd(3);
    asd.pushBack(1);
    asd.pushBack(2);
    asd.pushBack(3);
    for(int i =0; i < asd.size(); i++)
       cout << asd.elemAtRank(i) << endl;
    //Test if it spins
     cout << "BEGIN Spin TEST " << endl;
    asd.pushBack(4);
     cout << "First test is ok" << endl;
    for(int i =0; i < asd.size(); i++)
       cout << asd.elemAtRank(i) << endl;
    // here the error comes
    asd.pushBack(5);
     cout << "On the second iteration things crash and burn" << endl;
for(int i =0; i < asd.size(); i++)
       cout << asd.elemAtRank(i) << endl;
    return 0;
}
4

1 回答 1

0

除了您的插入时间不符合您的要求外，您的问题还在这里：

template <typename Object>
void ArrayVector<Object>:: pushFront( const Object& e)
{
    if(f == 0)
    {
        f = capacity-1;
    }
    else
    {
        f--;
    }
    a[f] = e; // problem lies here!

    if(sz < capacity)
        sz++;
}

您正在弄清楚在哪里进行插入，但您并没有将其他元素推到向量周围；也就是说，您只是在插入点覆盖元素。如果您想将其推到前面，则需要将其他元素分别复制到 1 个位置，然后进行插入。一个更好的解决方案（这将符合您的恒定插入时间要求）是将其实现为双链表。推到最后只需要以下伪代码：

void push_front(const Object& o)
{
    if (size == capacity)
        l.pop_back();
    l.push_front(o);
}

如果你真的必须使用一个连续的内存块，你不会得到恒定时间的插入，但它看起来像这样：

// Assumptions:  0 is always the front, capacity-1 is always the maximum back
template <typename Object>
void ArrayVector<Object>:: pushFront( const Object& e)
{
    // assume capacity > 0, move all the elements to the right one slot
    for (int i = capacity - 1; i > 0; --i)
    {
        a[i] = a[i - 1];
    }

    a[0] = e;

    if(sz < capacity)
        sz++;
}
于 2013-11-06T16:45:41.697 回答