在C++數組中移位元素

Question

我有一個35個插槽的整數數組。我想插入一個值，並且每次插入一個新值時，我都希望第一個值保持尾部，新值成爲頭部。我不能使用鏈表或隊列，我必須使用void函數。我找不出一種算法，但是我想到的所有東西都包含了一個for循環，我只是不知道如何正確實現它。

ArrayList.cpp

#include <iostream> 
#include "ArrayList.h" 
using namespace std; 

ArrayList::ArrayList() { 
    capacity = 8; 
    length = 0; 
    array = new int[capacity]; 
} 

ArrayList::ArrayList(const ArrayList& other) { 
    length = other.length; 
    capacity = other.capacity; 
    array = new int[other.capacity]; 
    for (int i = 0; i <= capacity; i++) 
     array[i] = other.array[i]; 
} 

void ArrayList::add(int item) { 
    if (length <= capacity) { 
     changeCapacityTo(2 * capacity); 
    } 
    length++; 
    array[length++] = item; 
} 

void ArrayList::add(int index, int item) { 
    while (index > capacity || length == capacity) { 
     capacity *= 2; 
    } 

    if (length != 0 && length < index) { 
     length = index; 
    } 

    int temp; 
    int i; 
    for (i = 0; i <= length; i++) { 
     array[index] = item; 
     temp = array[index]; 
     array[index + 1] = temp; 
    } 
    length++; 
} 

int ArrayList::get(int index) const { 
    return array[index]; 
} 

void ArrayList::changeCapacityTo(int newCapacity) { 
    int *newArray = new int[newCapacity]; 
    int numItemsToCopy = length < newCapacity ? length : newCapacity; 
    for (int i = 0; i < numItemsToCopy; i++) 
    newArray[i] = array[i]; 
    delete[] array; 
    array = newArray; 
} 

testArrayList.cpp

#include <iostream> 
#include "ArrayList.h" 
using namespace std; 

void verifyArrayList(ArrayList arrayList) { 
    for(int i = 0; i < 1000; ++i) { 
     int item; 
     int itemToAdd = 2 * i; 
     if((item = arrayList.get(i)) != itemToAdd) 
     cout << "OOPS - Error at index " << i << ": " << item << " should be " 
        << itemToAdd << endl; 
    } 

} 
void printArrayList(ArrayList arrayList) { 
    for(int i = 0; i < arrayList.getLength(); ++i) { 
     int item = arrayList.get(i); 
     cout << i << ":" << item << endl; 
    } 
} 
int main(int argc, char *argv[]) { 
    ArrayList arrayList; 

    const int highIndex = 35; 
    for(int i = highIndex; i > 0; --i) { 
     int itemToAdd = 2 * i; 
     arrayList.add(1, itemToAdd); 

     //cout << "VALUE OF itemToAdd: " << itemToAdd << endl; 
     //cout << endl; 
    } 
    arrayList.add(99); 
    printArrayList(arrayList); 
    cout << "#items = " << arrayList.getLength() << endl; 
    cout << "capacity = " << arrayList.getCapacity() << endl; 

    arrayList.add(2000, 9999); 
    cout << "#items = " << arrayList.getLength() << endl; 
    cout << "capacity = " << arrayList.getCapacity() << endl; 
} 

ArrayList.h

#ifndef ARRAYLIST_H_ 
#define ARRAYLIST_H_ 
#include <iostream> 

class ArrayList { 
public: 
    /* 
    * Initialize list with a capacity of 8 
    */ 
    ArrayList(); 

    /* 
    * Copy constructor 
    */ 
    ArrayList(const ArrayList& other); 
    virtual ~ArrayList() { 
     std::cout << "Destructing ArrayList at " << array << std::endl; 
     delete [] array; 
     array = NULL; 
    } 

    /* 
    * Add item to end of list 
    * @param item item to add to list 
    */ 
    void add(int item); 

    /* 
    * Adds item to list, at index, shifting items as necessary and increasing 
    * capacity of list as necessary. If capacity must increase, it must always 
    * be a power of 2. Note that if index is beyond capacity, capacity must be 
    * increased to allow adding the item at that index. Also, length should 
    * reflect the HIGHEST index (plus one, naturally) at which an item is 
    * stored, even if lower-indexed slots contain undefined values. 
    * 
    * @param item item to add to list 
    */ 
    void add(int index, int item); 

    /* 
    * Return item at index. For now, we assume index is legal. 
    * Later we will throw an exception when index is illegal. 
    * @param index index of item to return 
    * @return item at index 
    */ 
    int get(int index) const; 

    /* 
    * Return capacity 
    * @return capacity 
    */ 
    int getCapacity() const { 
     return capacity; 
    } 

    /* 
    * Return current length 
    * @return current length 
    */ 
    int getLength() const { 
     return length; 
    } 

private: 
    int *array; 
    int length; 
    int capacity; 
    /* 
    * Change capacity to that specified by newCapacity. 
    * @param newCapacity the new capacity 
    */ 
    void changeCapacityTo(int newCapacity); 
}; 

#endif /* ARRAYLIST_H_ */ 

這裏是世界衛生大會t時的輸出應該是這樣的： CORRECT OUTPUT

這裏是我的輸出如下： MY OUTPUT

新功能

我試圖在反向array第35個值複製，轉讓他們到reverseArray，然後將相反的順序分配回數組。下面的代碼不能做我期望的。

void ArrayList::add(int index, int item) { 
while (index > capacity || length == capacity) { 
    capacity *= 2; 
} 

if (length != 0 && length < index) { 
    length = index; 
} 

int temp; 
int i; 
for (i = 0; i <= length; i++) { 
    array[index] = item; 
    temp = array[index]; 
    array[index + 1] = temp; 

} 
length++; 
if(length > 35) { 
    int reverseArray[35]; 
    reverse_copy(array, array + 35, reverseArray); 
    for(int i = 0; i <= 35; i++) { 
     array[i] = reverseArray[i]; 
    } 
} 

}

Answer 1

1. 初始化的指針數組的末尾。
2. 的foreach每一個新的元素，將其設置爲這是由當前指針指向的值，並通過1

減少電流指針如果使用返回void功能，可以通過新的元素值和當前指針作爲參數。並注意檢查當前指針。

Answer 2

這聽起來像是一個功課問題。頭和尾是否指數組[0]和數組[n-1]？如果是這樣，您需要設計一種算法，每次添加新元素時，將所有元素轉換爲索引+1。這是一種明顯的蠻力方法，並且有更高效的解決方案。