[数据结构与算法]数据结构算法与应用-C++语言描述 circularArrayList (待解决)

circularArrayList.cpp

#include <iostream>
#include <sstream>
#include <algorithm>
#include <iterator>

//数据结构算法与应用-C++语言描述 circularArrayList

//ex31. 假设用公式 ( 5-3 ) 来表示线性表。分别用变量 first 和 last 表示线性表首元素和尾元素的
//      位置。
//      1 ) 开发一个类 circularArrayList，它与 circularArrayList 类似。实现所有的方法。在删除和插人方
//      法中，对位于删除或插和人元素的左面或右面的元素，有选择地决定向左移动或向右移
//      动，以此提高方法的性能。
//      2 ) 计算每一个方法的复杂度。
//      3 ) 测试你的代码。


using namespace std;
//线性表一数组

//抽象数据类型
template<class T>
class linearList
{
public:
    virtual ~linearList() {}
    //返回true，当且仅当线性表为空
    virtual bool empty() const = 0;
    //返回线性表的元素个数
    virtual int size() const = 0;
    //返回索引为 theIndex 的元素
    virtual T &get(int theIndex) const = 0;
    //返回元素 theElement 第一次出现时的索引
    virtual int indexOf(const T &theElement) const = 0;
    //删除索引为 theIndex 的元素
    virtual void erase(int theIndex) = 0;
    //把 theElement 插入线性表中索引为 theIndex 的位置上
    virtual void insert(int theIndex, const T &theElement) = 0;
    //把线性表插入输出流 out
    virtual void output(ostream &out) const = 0;
};

template<class T>
void circularCopy(T *start, T *end, T *initial, int arrayLength, T *dest)
{
    int size = end - start;
    size = size >= 0 ? size : size + arrayLength;
    for (int i = 0; i < size; i++)
    {
        dest[i] = *(initial + ((i + (start - initial)) % arrayLength));
    }
}


//改变一个一维数组长度
template<class T>
void changeLength1D(T *&a, int oldLength, int newLength)
{
    if (newLength < 0)
        throw logic_error("new length must be >= 0");

    //新数组
    T *temp = new T[newLength];

    //需要复制的元素个数
    int number = min(oldLength, newLength);
    copy(a, a + number, temp);

    //释放老数组的内存空间
    delete [] a;
    a = temp;
}



//circularArrayList 的类定义
template<class T>
class circularArrayList : public linearList<T>
{
public:
    //构造函数，复制构造函数和析构函数
    circularArrayList(int initialCapacity = 10);
    circularArrayList(const circularArrayList<T> &);
    ~circularArrayList() {delete[] element;}

    //ADT 方法
    bool empty() const override { return listSize == 0; }
    int size() const override { return listSize; }
    T &get(int theIndex) const override;
    int indexOf(const T &theElement) const override;
    void erase(int theIndex) override;
    void insert(int theIndex, const T &theElement) override;
    void output(ostream &out) const override;

    //其他方法
    int capacity() const { return arrayLength; }
    //ex5. 编写一个方法 circularArrayList<T>::trimToSize，它使数组的长度等于 max{listSize,1}。
    //这个方法的复杂度是多少?” 测试你的代码。
    circularArrayList<T> &trimToSize();

    //ex6. 编写方法 circularArrayList<T>::setSize，它使线性表的大小等于指定的大小。若线性表开始的大小
    //小于指定的大小，则不增加元素。若线性表开始的大小大于指定的大小，则删除多余的元
    //素。这个方法的复杂度是多少? 测试你的代码。
    circularArrayList<T> &setSize(int length);

    //ex7. 重载操作符[]，使得表达式 x加返回对线性表第i个元素的引用。
    //若线性表没有第i个元则抛出异常语句 x[i]=y 和 y= x[i]] 按以往预期的方式执行。
    //测试你的代码。
    T &operator[](int i);

    //ex8. 重载操作符 ==，使得表达式 x==y 返回 true，当上且仅当两个用数组描述的线性表x
    //和y 相等(即对所有的 i，两个线性表的第i 个元素相等 )。测试你的代码。
    bool operator==(const circularArrayList<T> &right) const;

    //ex9.
    bool operator!=(const circularArrayList<T> &right) const;

    //ex10. 重载操作符 <，使得表达式 x<y 返回 true，当且仅当用数组描述的线性表 x 按字典顺序小
    //于用数组描述的线性表v ( 见练习 8 )。测试你的代码。
    bool operator<(const circularArrayList<T> &right) const;

    //ex11. 编写方法 circularArrayList<T>::push_back，它把元素 theElement 插到线性表的右端。不要利用
    //insert 方法。方法的时间复杂度是多少?测试你的代码。
    void push_back(const T &theElement);

    //ex12. 编写方法 circularArrayList<T>::pop_back，它把线性表右端的元素删除。不要利用 erase 方法。方
    //法的时间复杂度是多少? 测试你的代码。
    T &pop_back();

    //ex13. 编写方法 circularArrayList<T>::swap(theLisb，它交换线性表的元素 *this 和 theList。方法的时间
    //复杂度是多少? 测试你的代码。
    circularArrayList<T> &swap(circularArrayList<T> &theList);

    //ex14. 编写方法 circularArrayList<T>::reserve(theCapacity)，它把数组的容量改变为当前容量和 theCapacity
    //的较大者。测试你的代码。
    circularArrayList<T> &reserve(int theCapacity);

    //ex15. 编写方法 circularArrayList<T>::set(theIndex,theElement)，它用元素 theElement 替换索引为 theIndex
    //的元素。若索引 theIndex 超出范围，则抛出异常。返回原来索引为 theIndex 的元素。测试
    //你的代码。
    T set(int theIndex, const T &theElement);

    //ex16. 编写方法 circularArrayList<T>::clear，它使线性表为空。方法的复杂度是多少?” 测试你的代码。
    circularArrayList<T> &clear();

    //ex17. 编写方法 circularArrayList<T>::removeRange，它删除指定索引范围内的所有元素。方法的复杂度
    //是多少?测试你的代码。
    circularArrayList<T> &removeRange(int startIndex, int endIndex);

    //ex18. 编写方法 circularArrayList<T>::lastInexOf，它的返回值是指定元素最后出现时的索引。如果这样
    //的元素不存在，则返回 -1。方法的复杂度是多少? 测试你的代码。
    int lastIndexOf(const T &theElement) const;

    //ex20. 类 circularArrayList ( 程序 5-1 ) 的缺点是，它不减少数组 element 的长度。
    //1: 编写类 circularArrayList 的一个新版本。如果在删除之后，线性表的大小降至 arrayLength/4 以
    //  下，就创建一个新的数组，长度为 max{arrayLength/2，initialCapacity}。然后将老表
    //  中的元素复制到新表。
    //2 ( 选择性练习 ) 从空表开始，考察大小为地的线性表的操作序列。假设当初始容量等于
    //  或超过线性表大小的最大值时，总的执行步数是f(n)。证明，如果起始容量为1，而且
    //  在插入和删除操作中，可以按照上面和 5.3 节所述的方式改变数组长度，那么执行步
    //  数最多为 cf(n)，其中 c 是某个常数。
    circularArrayList<T> &decreaseArray(int capacity);

    ///ex33. 1 ) 编写方法 circularArrayList<T>::reverse，它原地颠倒线性表元素的顺序 ( 即在数组 element 中
    //      完成操作，不创建新的数组 )。颠倒顺序之前，线性表的第 k 个元素是 element[k]，站
    //      倒之后，线性表的第 k 个元素是 element[listSize-k-1]。不要利用 STL 函数 reverse。
    //      2 ) 方法应具有 listSize 的线性复杂度。证明这个性能。
    //      3 ) 设计测试数据，测试方法的正确性。
    //      4 ) 编写另一个原地颠倒 circularArrayList 对象的方法。它不是 circularArrayList 的成员函数，不能访问
    //      circularArrayList 的数据成员。不过，这个方法可以调用 circularArrayList 的成员函数。
    //      5 ) 计算方法的复杂度
    //      6 ) 使用大小分别为 1000、5000 和 10 000 的线性表，比较两个颠倒顺序算法的运行时间
    circularArrayList<T> &reverse();

    //ex23.1) 编写方法 circularArrayList<T>::leftShift(i)，它将线性表的元素向左移动i个位置。如果
    //      x=[0,1,2,3,4]，那么 x.leftShift(2) 的结果是 x=[2,3,4]。
    //      2 ) 计算方法的复杂度。
    //      3 ) 测试你的代码-
    circularArrayList<T> &leftShift(int shift);

    //ex24. 在一个循环移动的操作中,线性表的元素根据给定的值，按顺时针方向移动。例如，
    //x=[0,1,2,3,4]，循环移动 2 的结果是 x=[2,3,4,0,1]。
    //      1 ) 描述一下如何利用 3 次逆转操作完成循环移动。每一次逆转操作都可以将线性表的一
    //      部分或全部逆转。
    //      2 ) 编写方法 circularArrayList<T>::circularShiftt)，它将线性表的元素循环移动i个位置。方法应
    //      具有线性表长度的线性复杂度。
    //      3 ) 测试你的代码。
    circularArrayList<T> &circularShift(int shift);

    //ex25. 调用语句 x.half，可以将 x 的元素隔一个删除一个。如果 xsize() 是 7, xelement[]=[2,13,4.5,17,8,29]，
    //      那么 x.half() 的结果是 x.size() 是 4,x.element[]=[2,4.17,9]。如果 x.size() 是 4,x.element[]=[2,13,4.5]，
    //      那么 x.half() 的结果是 x.size() 是 2，x.element[]=[2,4]。如果 x 为空，那么 x.half() 的结果也是X 为空。
    //      1 ) 编写方法 circularArrayList<T>::half()。不能利用类 circularArrayList 的其他方法。复杂度应该为O(listSize)
    //      2 ) 证明方法的复杂度为 O(listSize)。
    //      3 ) 测试你的代码。
    circularArrayList<T> &half();

    ///ex34.令 a 和b 是类 circularArrayList 的两个对象。
    //      1 ) 编写方法 circularArrayList<T>::meld(ab)，它生成一个新的线性表，从 a 的第 0 个元素开始，
    //      交替地包含a 和 b的元素。如果一个表的元素取完了，就把另一个表的剩余元素附加
    //      到新表中。调用语句 c.meld(a,b) 使 成为合并后的表。方法应具有两个输入线性表大
    //      小的线性复杂度。
    //      2 ) 证明方法具有 a 和b 大小之和的线性复杂度。
    //      3 ) 测试你的代码。

    circularArrayList<T> &meld(circularArrayList<T> &a, circularArrayList<T> &b);

    ///ex35.令a 和b 是类 circularArrayList 的两个对象。假设它们的元素从左到右非递减有序。
    //      1 ) 编写方法 circularArrayList<T>::merge(a,b)，它生成一个新的有序线性表，包含a 和 的所有元
    //      素。归并后的线性表是调用对象 *this。不要利用 STL 本数 merge。
    //      2 ) 计算方法的复杂度。
    //      3 ) 测试你的代码。
    circularArrayList<T> &merge(circularArrayList<T> &a, circularArrayList<T> &b);

    ///ex36. 1 ) 编写方法 circularArrayList<T>::split(lab)，它生成两个线性表a 和b。a 包含 *this 中索引为偶
    //      数的元素，b 包含其余的元素。
    //    2 ) 计算方法的复杂度。
    //    3 ) 测试你的代码。
    circularArrayList<T> &split(circularArrayList<T> &a, circularArrayList<T> &b);
public:
    class iterator
    {
    public:
        // C++ 的typedef 语句实现双向迁代器
        typedef bidirectional_iterator_tag iterator_category;
        typedef T value_type;
        typedef ptrdiff_t difference_type;
        typedef T *pointer;
        typedef T &reference;

        //构造函数
        iterator(T *thePosition = 0) { position = thePosition; }

        //解引用操作符
        T &operator*() const { return *position; }
        T *operator->() const { return &*position; }


        //迭代器的值增加
        iterator &operator++() //前加
        {
            ++position;
            return *this;
        }
        iterator operator++(int) //后加
        {
            iterator old = *this;
            ++position;
            return old;
        }

        //迭代器的值减少
        iterator &operator--() //前减
        {
            --position;
            return *this;
        }

        iterator operator--(int) //后减
        {
            iterator old = *this;
            --position;
            return old;
        }

        //测试是否相等
        bool operator!=(const iterator right) const
        {
            return position != right.position;
        }

        bool operator==(const iterator right) const
        {
            return position == right.position;
        }
        //27. 扩展迭代器类 circularArrayList::iterator ( 程序 5-11 )，使得它成为随机访问迭代器。利用 STL 的
        //    排序函数对一个线性表排序，以测试这个和迭代器类。
        T &operator[](int i)
        {
            return *(position + i);
        }

        ptrdiff_t operator-(const circularArrayList<T>::iterator &right) const
        {
            return position - right.position;
        }

        T &operator-(const ptrdiff_t &diff) const
        {
            return *(position - diff);
        }

        T &operator+(const ptrdiff_t &diff) const
        {
            return *(position + diff);
        }

    protected:
        T *position; //指向表元素的指针
    };

    iterator begin() { return iterator(element); }
    iterator end() { return iterator(element + listSize); }

protected:
    //索引 theIndex 无效，则抛出异常
    void checkIndex(int theIndex) const;
    //改变容量大小
    void changeArraySize(int capacity);
    //扩容
    void increaseArray(int capacity);

    //存储线性表元素的一维数组
    T *element = NULL;
    //一维数组的容量
    int arrayLength = 0;
    //线性表的元素个数
    int listSize = 0;
    //初始容量
    int initialCapacity = 10;
    //起始位置
    int first = 0;
    //最后位置
    int last = 0;
};

//类 circularArrayList 的构造函数
template<class T>
circularArrayList<T>::circularArrayList(int initialCapacity)
{
    //构造函数
    if (initialCapacity < 1)
    {
        ostringstream s;
        s << "Initial capacity = " << initialCapacity << " must be > 0";
        throw logic_error(s.str());
    }
    arrayLength = initialCapacity;
    initialCapacity = initialCapacity;
    element = new T[arrayLength];
    listSize = 0;
    first = 0;
    last = 0;
}

template<class T>
circularArrayList<T>::circularArrayList(const circularArrayList<T> &theList)
{
    //复制构造函数
    arrayLength = theList.arrayLength;
    initialCapacity = theList.initialCapacity;
    listSize = theList.listSize;
    element = new T[arrayLength];
    circularCopy(theList.element + theList.first, theList.element + theList.last + 1, theList.element, theList.arrayLength, element);
    first = 0;
    last = listSize;
}

//方法 checkIndex的时间复杂度是 (1),
template<class T>
void circularArrayList<T>::checkIndex(int theIndex) const
{
    //确定索引theIndex在0 和 listSize - 1之间
    if (theIndex < 0 || theIndex >= listSize)
    {
        //字符串输出流对象
        ostringstream s;
        s << "index = " << theIndex << " size = " << listSize;
        throw logic_error(s.str());
    }
}

//方法 get的时间复杂度是 (1),
template<class T>
T &circularArrayList<T>::get(int theIndex) const
{
    //返回索引为 theIndex 的元素
    //若此元素不存在，则抛出异常
    checkIndex(theIndex);
    return element[theIndex];
}

//indexOf 的时间复杂度是 O(max{listSize,1})
template<class T>
int circularArrayList<T>::indexOf(const T &theElement) const
{
    for (int i = 0; i < listSize; i++)
    {
        if (element[(i + first) % arrayLength] == theElement)
        {
            return i;
        }
    }
    return -1;
}

/*
 删除一个元素为了从线性表中删除索引为 theIndex 的元素，
 首先要确定线性表包含这个元素，然后删除这个元素。
 若没有这个元素，则抛出类型为异常

 如果没有索引 theIndex 的元素，
 就抛出异常,erase 时间复杂度是 O(1)。如果有这个元素，
 那么要移动的元素个数是 listSize-theIndex
 时间复杂度是 O(listSize-theIndex)
*/
template<class T>
void circularArrayList<T>::erase(int theIndex)
{
    //删除其索引为 theIndex 的元素
    //如果该元素不存在，则抛出异常
    checkIndex(theIndex);
    if (theIndex >= (listSize + 1) / 2)
    {
        for (int i = theIndex; i < listSize - 1; i++)
        {
            element[(i + first) % arrayLength] = element[(i + first + 1) % arrayLength];
        }
        element[last - 1].~T();
        last--;
        last = (last + arrayLength) % arrayLength;
    }
    else
    {
        for (int i = theIndex; i > 0; i--)
        {
            element[(i + first) % arrayLength] = element[(i + first - 1 + arrayLength) % arrayLength];
        }
        element[first].~T();
        first++;
        first %= arrayLength;
    }

    listSize--;
    if (listSize < arrayLength / 4)
        decreaseArray(arrayLength / 2);
}


template<class T>
void circularArrayList<T>::insert(int theIndex, const T &theElement)
{
    //在索引 theIndex 处插入元素 theElement
    //确定索引theIndex在0 和 listSize 之间
    if (theIndex < 0 || theIndex > listSize)
    {
        //字符串输出流对象
        ostringstream s;
        s << "index = " << theIndex << " size = " << listSize;
        throw logic_error(s.str());
    }

    //有效索引，确定数组是否已满
    if (listSize == arrayLength - 1)
    {
        //数组空间已满，数组长度倍增
 		increaseArray(2 * arrayLength);
    }

    //把元素向后移动
   	if(theIndex >= (listSize + 1) / 2)
   	{
   		for(int i = listSize; i > theIndex; i--)
   		{
            element[(i + first) % arrayLength] = element[(i + first - 1 + arrayLength) % arrayLength];
   		}
        last++;
        last %= arrayLength;
   	}
   	else //把元素向前移动
   	{
        for(int i = 0; i < theIndex; i++)
        {
            element[(i + first - 1 + arrayLength) % arrayLength] = element[(i + first) % arrayLength];
        }
        first--;
        first = (first + arrayLength) % arrayLength;
   	}
   	
    element[(theIndex + first) % arrayLength] = theElement;
    listSize++;
}

//输出函数 output 和重载 <<
template<class T>
void circularArrayList<T>::output(ostream &out) const
{
    //把线性表插入输出流
    for (int i = 0; i < listSize; i++)
    {
        cout<< element[(i + first) % arrayLength] << " ";
    }
}

//重载 <<
template<class T>
ostream &operator<<(ostream &out, const circularArrayList<T> &x)
{
    x.output(out);
    return out;
}

//扩容
template<class T>
void circularArrayList<T>::increaseArray(int capacity)
{
    if (capacity <= arrayLength)
    {
        cout << "input capacity <= arrayLength";
        return;
    }
    changeArraySize(capacity);
    arrayLength = capacity;
}


//ex5. 编写一个方法 circularArrayList<T>::trimToSize，它使数组的长度等于 max{listSize,1}。
//这个方法的复杂度是多少?” 测试你的代码。
template<class T>
circularArrayList<T> &circularArrayList<T>::trimToSize()
{
    if (listSize == arrayLength) return *this;
    int oldLength = arrayLength;
    arrayLength = max(listSize, 1);
    changeLength1D(element, oldLength, arrayLength);
    return *this;
}

//ex6. 编写方法 circularArrayList<T>::setSize，它使线性表的大小等于指定的大小。若线性表开始的大小
//小于指定的大小，则不增加元素。若线性表开始的大小大于指定的大小，则删除多余的元
//素。这个方法的复杂度是多少? 测试你的代码。
template<class T>
circularArrayList<T> &circularArrayList<T>::setSize(int length)
{
    if (length < 0 || length > listSize)
        return *this;
    listSize = length;
    return *this;
}

//ex7. 重载操作符[]，使得表达式 x加返回对线性表第i个元素的引用。
//若线性表没有第i个元则抛出异常语句 x[i]=y 和 y= x[i] 按以往预期的方式执行。
//测试你的代码。
template<class T>
T &circularArrayList<T>::operator[](int i)
{
    checkIndex(i);
    return element[i];
}

//ex8. 重载操作符 ==，使得表达式 x==y 返回 true，当上且仅当两个用数组描述的线性表x
//和y 相等(即对所有的 i，两个线性表的第i 个元素相等 )。测试你的代码。
template<class T>
bool circularArrayList<T>::operator==(const circularArrayList<T> &right) const
{
    if (right.listSize != listSize) return false;
    for (int i = 0; i < listSize; i++)
    {
        if (element[i] != right.element[i]) return false;
    }
    return true;
}

//ex9.
template<class T>
bool circularArrayList<T>::operator!=(const circularArrayList<T> &right) const
{
    if (*this == right)
    {
        return false;
    }
    else
    {
        return true;
    }
}

//ex10. 重载操作符 <，使得表达式 x<y 返回 true，当且仅当用数组描述的线性表 x 按字典顺序小
//于用数组描述的线性表v ( 见练习 8 )。测试你的代码。
template<class T>
bool circularArrayList<T>::operator<(const circularArrayList<T> &right) const
{
    int minSize = min(size(), right.size());

    for (int i = 0; i < size(); i++)
    {
        if (element[i] < right.element[i]) return true;
    }
    if (size() < right.size()) return true;
    return false;
}

//ex11. 编写方法 circularArrayList<T>::push_back，它把元素 theElement 插到线性表的右端。不要利用
//insert 方法。方法的时间复杂度是多少?测试你的代码。
template<class T>
void circularArrayList<T>::push_back(const T &theElement)
{
    if (arrayLength == listSize)
        increaseArray(2 * arrayLength);
    element[listSize++] = theElement;
}

//ex12. 编写方法 circularArrayList<T>::pop_back，它把线性表右端的元素删除。不要利用 erase 方法。方
//法的时间复杂度是多少? 测试你的代码。
template<class T>
T &circularArrayList<T>::pop_back()
{
    if (listSize == 0)
    {
        throw logic_error("circularArrayList is empty");
    }
    T &theElement = element[--listSize];

    if (listSize < arrayLength / 4)
        decreaseArray(arrayLength / 2);

    return theElement;
}

//ex13. 编写方法 circularArrayList<T>::swap(theLisb，它交换线性表的元素 *this 和 theList。方法的时间
//复杂度是多少? 测试你的代码。
template<class T>
circularArrayList<T> &circularArrayList<T>::swap(circularArrayList<T> &theList)
{
    std::swap(listSize, theList.listSize);
    std::swap(arrayLength, theList.arrayLength);
    std::swap(element, theList.element);
    return *this;
}

//ex14. 编写方法 circularArrayList<T>::reserve(theCapacity)，它把数组的容量改变为当前容量和 theCapacity
//的较大者。测试你的代码。
template<class T>
circularArrayList<T> &circularArrayList<T>::reserve(int theCapacity)
{
    if (theCapacity <= arrayLength) return *this;
    changeLength1D(element, arrayLength, theCapacity);
    arrayLength = theCapacity;
    return *this;
}

//ex15. 编写方法 circularArrayList<T>::set(theIndex,theElement)，它用元素 theElement 替换索引为 theIndex
//的元素。若索引 theIndex 超出范围，则抛出异常。返回原来索引为 theIndex 的元素。测试
//你的代码。
template<class T>
T circularArrayList<T>::set(int theIndex, const T &theElement)
{
    checkIndex(theIndex);
    T tmp = element[theIndex];
    element[theIndex] = theElement;
    return tmp;
}

//ex16. 编写方法 circularArrayList<T>::clear，它使线性表为空。方法的复杂度是多少?” 测试你的代码。
template<class T>
circularArrayList<T> &circularArrayList<T>::clear()
{
    for (int i = 0; i < size(); i++)
    {
        element[i].~T();
    }
    listSize = 0;
    decreaseArray(initialCapacity);
    arrayLength = initialCapacity;
    return *this;
}

//ex17. 编写方法 circularArrayList<T>::removeRange，它删除指定索引范围内的所有元素。方法的复杂度
//是多少?测试你的代码。
template<class T>
circularArrayList<T> &circularArrayList<T>::removeRange(int startIndex, int endIndex)
{
    checkIndex(startIndex);
    checkIndex(endIndex);
    int count = endIndex - startIndex + 1;
    copy(element + endIndex, element + listSize, element + startIndex);

    for (int i = startIndex + count; i < listSize; i++)
        element[i].~T();

    listSize -= count;

    if (listSize < arrayLength / 4)
    {
        decreaseArray(arrayLength / 2);
    }
    return *this;
}

//ex18. 编写方法 circularArrayList<T>::lastInexOf，它的返回值是指定元素最后出现时的索引。如果这样
//的元素不存在，则返回 -1。方法的复杂度是多少? 测试你的代码。
template<class T>
int circularArrayList<T>::lastIndexOf(const T &theElement) const
{
    for (int i = listSize - 1; i >= 0; i--)
    {
        if (element[i] == theElement)
            return i;
    }
    return -1;
}


//ex20. 类 circularArrayList ( 程序 5-1 ) 的缺点是，它不减少数组 element 的长度。
//1: 编写类 circularArrayList 的一个新版本。如果在删除之后，线性表的大小降至 arrayLength/4 以
//  下，就创建一个新的数组，长度为 max{arrayLength/2，initialCapacity}。然后将老表
//  中的元素复制到新表。
//2 ( 选择性练习 ) 从空表开始，考察大小为地的线性表的操作序列。假设当初始容量等于
//  或超过线性表大小的最大值时，总的执行步数是f(n)。证明，如果起始容量为1，而且
//  在插入和删除操作中，可以按照上面和 5.3 节所述的方式改变数组长度，那么执行步
//  数最多为 cf(n)，其中 c 是某个常数。
template<class T>
circularArrayList<T> &circularArrayList<T>::decreaseArray(int capacity)
{
    if (capacity > arrayLength || capacity < 0) 
    {
    	cout<<"capacity > arrayLength || capacity < 0"<<endl;
    	return *this;
    }
    if (capacity < initialCapacity) capacity = initialCapacity;
    if (capacity == arrayLength) 
    {
    	cout<<"capacity > arrayLength || capacity < 0"<<endl;
		return *this;
    }
    changeArraySize(capacity);
    return *this;
}


///ex33. 1 ) 编写方法 circularArrayList<T>::reverse，它原地颠倒线性表元素的顺序 ( 即在数组 element 中
//      完成操作，不创建新的数组 )。颠倒顺序之前，线性表的第 k 个元素是 element[k]，站
//      倒之后，线性表的第 k 个元素是 element[listSize-k-1]。不要利用 STL 函数 reverse。
//      2 ) 方法应具有 listSize 的线性复杂度。证明这个性能。
//      3 ) 设计测试数据，测试方法的正确性。
//      4 ) 编写另一个原地颠倒 circularArrayList 对象的方法。它不是 circularArrayList 的成员函数，不能访问
//      circularArrayList 的数据成员。不过，这个方法可以调用 circularArrayList 的成员函数。
//      5 ) 计算方法的复杂度
//      6 ) 使用大小分别为 1000、5000 和 10 000 的线性表，比较两个颠倒顺序算法的运行时间
template<class T>
circularArrayList<T> &circularArrayList<T>::reverse()
{
    for (int i = 0; i < listSize / 2; i++)
    {
//        std::swap(element[i], element[listSize - i - 1]);
        std::swap(element[(i + first) % arrayLength], element[(listSize - i - 1 + arrayLength) % arrayLength]);
    }
    return *this;
}

//ex23.1) 编写方法 circularArrayList<T>::leftShift(i)，它将线性表的元素向左移动i个位置。如果
//      x=[0,1,2,3,4]，那么 x.leftShift(2) 的结果是 x=[2,3,4]。
//      2 ) 计算方法的复杂度。
//      3 ) 测试你的代码-
template<class T>
circularArrayList<T> &circularArrayList<T>::leftShift(int shift)
{
    if (shift < 0 || shift > listSize)
    {
        ostringstream s;
        s << "shift shift < 0 || shift > listSize";
        throw logic_error(s.str());
    }

    copy(element + shift, element + listSize, element);
    listSize -= shift;

    for (int i = listSize - shift; i < listSize; i++)
    {
        element[i].~T();
    }

    if (listSize < arrayLength / 4)
    {
        changeLength1D(element, arrayLength, arrayLength / 2);
    }

    return *this;
}

//ex24. 在一个循环移动的操作中,线性表的元素根据给定的值，按顺时针方向移动。例如，
//x=[0,1,2,3,4]，循环移动 2 的结果是 x=[2,3,4,0,1]。
//      1 ) 描述一下如何利用 3 次逆转操作完成循环移动。每一次逆转操作都可以将线性表的一
//      部分或全部逆转。
//      2 ) 编写方法 circularArrayList<T>::circularShiftt)，它将线性表的元素循环移动i个位置。方法应
//      具有线性表长度的线性复杂度。
//      3 ) 测试你的代码。
template<class T>
circularArrayList<T> &circularArrayList<T>::circularShift(int shift)
{
    if (shift < 0)
    {
        ostringstream s;
        s << "circularShift shift < 0";
        throw logic_error(s.str());
    }

    shift %= listSize;

    reverse();
    std::reverse(element, element + listSize - shift);
    std::reverse(element + listSize - shift, element + listSize);
    return *this;
}

//ex25. 调用语句 x.half，可以将 x 的元素隔一个删除一个。如果 xsize() 是 7, xelement[]=[2,13,4.5,17,8,29]，
//      那么 x.half() 的结果是 x.size() 是 4,x.element[]=[2,4.17,9]。如果 x.size() 是 4,x.element[]=[2,13,4.5]，
//      那么 x.half() 的结果是 x.size() 是 2，x.element[]=[2,4]。如果 x 为空，那么 x.half() 的结果也是X 为空。
//      1 ) 编写方法 circularArrayList<T>::half()。不能利用类 circularArrayList 的其他方法。复杂度应该为O(listSize)
//      2 ) 证明方法的复杂度为 O(listSize)。
//      3 ) 测试你的代码。
template<class T>
circularArrayList<T> &circularArrayList<T>::half()
{
    if (listSize <= 1) return *this;

    for (int i = 1; i < (listSize + 1) / 2; i++)
    {
        element[i] = element[i * 2];
    }

    int oldSize = listSize;
    listSize = (listSize + 1) / 2;

    for (int i = listSize; i < oldSize; i++)
    {
        element[i].~T();
    }

    if (listSize < arrayLength / 4)
    {
        changeLength1D(element, arrayLength, arrayLength / 2);
    }
    return *this;
}

///ex34.令 a 和b 是类 circularArrayList 的两个对象。
//      1 ) 编写方法 circularArrayList<T>::meld(ab)，它生成一个新的线性表，从 a 的第 0 个元素开始，
//      交替地包含a 和 b的元素。如果一个表的元素取完了，就把另一个表的剩余元素附加
//      到新表中。调用语句 c.meld(a,b) 使 成为合并后的表。方法应具有两个输入线性表大
//      小的线性复杂度。
//      2 ) 证明方法具有 a 和b 大小之和的线性复杂度。
//      3 ) 测试你的代码。

template<class T>
circularArrayList<T> &circularArrayList<T>::meld(circularArrayList<T> &a, circularArrayList<T> &b)
{
    if (a.listSize == 0 && b.listSize == 0) return *this;
    int minSize = a.listSize < b.listSize ? a.listSize : b.listSize;
    int maxSize = a.listSize > b.listSize ? a.listSize : b.listSize;
    int newLength = a.listSize > b.listSize ? a.arrayLength : b.arrayLength;
    circularArrayList<T>* maxList = a.listSize > b.listSize ? &a : &b;

    if (maxSize + minSize > arrayLength)
    {
        newLength = a.arrayLength + b.arrayLength;
    }
    increaseArray(newLength);
    listSize = maxSize + minSize;
    for (int i = 0; i < minSize; i++)
    {
        element[i * 2] = a.element[(i + a.first) % a.arrayLength];
        element[i * 2 + 1] = b.element[(i + b.first) % b.arrayLength];
    }
    for (int i = minSize; i < maxSize; i++)
    {
        element[minSize + i] = maxList->element[(i + maxList->first) % maxList->arrayLength];
    }
    return *this;
}

///ex35.令a 和b 是类 circularArrayList 的两个对象。假设它们的元素从左到右非递减有序。
//      1 ) 编写方法 circularArrayList<T>::merge(a,b)，它生成一个新的有序线性表，包含a 和 的所有元
//      素。归并后的线性表是调用对象 *this。不要利用 STL 本数 merge。
//      2 ) 计算方法的复杂度。
//      3 ) 测试你的代码。
template<class T>
circularArrayList<T> &circularArrayList<T>::merge(circularArrayList<T> &a, circularArrayList<T> &b)
{
    if (a.listSize == 0 && b.listSize == 0) return *this;
    int minSize = a.listSize < b.listSize ? a.listSize : b.listSize;
    int maxSize = a.listSize > b.listSize ? a.listSize : b.listSize;
    int newLength = a.listSize > b.listSize ? a.arrayLength : b.arrayLength;
    if (minSize == 0) return *this;

    if (maxSize + minSize > arrayLength)
    {
        newLength = a.arrayLength + b.arrayLength;
    }
    listSize = maxSize + minSize;
    increaseArray(newLength);
    int index = 0, aindex = 0, bindex = 0;
    cout << listSize << endl;
    for (int i = 0; i < listSize; i++)
    {
        if (aindex < a.size() && bindex < b.size())
        {
            if (a.element[(aindex + a.first) % a.arrayLength] <= b.element[(bindex + b.first) % b.arrayLength])
                element[index] = a.element[((aindex++) + a.first) % a.arrayLength];
            else
                element[index] = b.element[((bindex++) + b.first) % b.arrayLength];
        }
        else
        {
            if (aindex < a.size() && bindex >= b.size())
                element[index] = a.element[((aindex++) + a.first) % a.arrayLength];
            else if (aindex >= a.size() && bindex < b.size())
                element[index] = b.element[((bindex++) + b.first) % b.arrayLength];
        }
    }
    return *this;
}

//30. 1 ) 编写方法 circularArrayList<T>::split(lab)，它生成两个线性表a 和b。a 包含 *this 中索引为偶
//      数的元素，b 包含其余的元素。
//    2 ) 计算方法的复杂度。
//    3 ) 测试你的代码。
template<class T>
circularArrayList<T> &circularArrayList<T>::split(circularArrayList<T> &a, circularArrayList<T> &b)
{
    if (listSize == 0)
    {
        cout << "listSize == empty";
        return *this;
    }

    a.increaseArray(listSize);
    b.increaseArray(listSize);

    int index, aindex = 0, bindex = 0;
    for (int i = 0; i < listSize; i++)
    {
        if (i % 2 == 0)
        {
            a.element[aindex++] = element[i];
        }
        else
        {
            b.element[bindex++] = element[i];
        }
    }
    a.listSize = (listSize + 1) / 2;
    b.listSize = listSize / 2;

    return *this;
}

//改变容量大小
template <class T>
void circularArrayList<T>::changeArraySize(int capacity)
{
    //新数组
    T *temp = new T[capacity];
	circularCopy(&(element[first]), &(element[last]), element, arrayLength, temp);

    //释放老数组的内存空间
	delete[]element;
	element = temp;

	arrayLength = capacity;
	first = 0;
	last = listSize;
}



int main()
{
    // 创建两个容量为 100 的线性表
    linearList<double> *x = (linearList<double> *)new circularArrayList<int>(100);
    circularArrayList<double> y(100);

    //利用容量的缺省值创建一个线性表
    circularArrayList<char> z;

    //用线性表Y 复制创建一个线性表
    circularArrayList<double> w(y);

    ///
    circularArrayList<double> list;
    cout << "----------------------insert start--------------------" << endl;
    cout << "list capacity = " << list.capacity() << endl;
    cout << "list size = " << list.size() << endl;
    for (int i = 0; i < 50; i++)
    {
        list.insert(0, i);
    }

    cout << "list capacity = " << list.capacity() << endl;
    cout << "list size = " << list.size() << endl;
    cout << list << endl;
    cout << "----------------------insert end--------------------" << endl;
    cout << "----------------------拷贝构造 start--------------------" << endl;
    circularArrayList<double> list5(list);
    cout << "list capacity = " << list.capacity() << endl;
    cout << "list size = " << list.size() << endl;
    cout << list << endl;
    cout << "----------------------拷贝构造 end--------------------" << endl;
    cout << "----------------------indexOf start--------------------" << endl;
    
    for(int i = 0;i<10;i++)
    {
    	list5.insert(50,i+50);
    }
    for(int i = 0;i < 60;i++)
    {
    	std::cout<<list5.indexOf(i)<<" ";
    }
    cout<<endl;
    cout << "----------------------indexOf end--------------------" << endl;
    cout << "----------------------erase start--------------------" << endl;
    cout << "list capacity = " << list.capacity() << endl;
    cout << "list size = " << list.size() << endl;
    cout << list << endl;
    for(int i = 0; i < 20; i++)
    {
    	list.erase(10);
    }
    cout << "list capacity = " << list.capacity() << endl;
    cout << "list size = " << list.size() << endl;
    cout << list << endl;
    cout << "----------------------erase end--------------------" << endl;
#if 0
    cout << "----------------------test trimToSize start--------------------" << endl;
    cout << "list capacity = " << list.capacity() << endl;
    cout << "list size = " << list.size() << endl;
    list.trimToSize();
    cout << "trimToSize " << endl;
    cout << "list capacity = " << list.capacity() << endl;
    cout << "list size = " << list.size() << endl;
    cout << "----------------------test trimToSize end--------------------" << endl;
    ///
    cout << "----------------------setSize trimToSize start--------------------" << endl;
    list.setSize(50);
    cout << "setSize " << endl;
    cout << "list capacity = " << list.capacity() << endl;
    cout << "list size = " << list.size() << endl;
    cout << list << endl;
    cout << "----------------------setSize trimToSize end--------------------" << endl;

    cout << "----------------------operator [] trimToSize start--------------------" << endl;
    cout << "list[10] = " << list[10] << endl;
    list[10] = 100;
    cout << "list[10] = " << list[10] << endl;
    cout << "----------------------operator [] trimToSize end--------------------" << endl;

    cout << "----------------------operator == trimToSize start--------------------" << endl;
    circularArrayList<double> list1;
    for (int i = 0; i < 3; i++)
    {
        list1.insert(0, i);
    }
    cout << (list1 == list) << endl;
    circularArrayList<double> list2;
    list2.insert(0, 2);
    list2.insert(1, 1);
    list2.insert(2, 0);
    cout << (list1 == list2) << endl;
    cout << "----------------------operator == end--------------------" << endl;
    cout << "----------------------operator != start--------------------" << endl;
    cout << (list1 != list) << endl;
    cout << (list1 != list2) << endl;
    cout << "----------------------operator != end--------------------" << endl;
    cout << "----------------------operator < start--------------------" << endl;
    cout << (list1 < list) << endl;
    cout << (list1 < list2) << endl;
    cout << "----------------------operator < end--------------------" << endl;
    cout << "----------------------push_back start--------------------" << endl;
    list1.trimToSize();
    cout << list1 << endl;
    cout << list1.capacity() << endl;
    list1.push_back(111);
    list1.push_back(111);
    list1.push_back(111);
    cout << list1 << endl;
    cout << list1.capacity() << endl;
    cout << "----------------------push_back end--------------------" << endl;
    cout << "----------------------pop_back start--------------------" << endl;
    cout << list1 << endl;
    cout << list1.capacity() << endl;
    cout << list1.pop_back() << endl;
    cout << list1.pop_back() << endl;
    cout << list1.pop_back() << endl;
    cout << list1 << endl;
    cout << list1.capacity() << endl;
    cout << "----------------------pop_back end--------------------" << endl;
    cout << "----------------------swap start--------------------" << endl;
    cout << list << endl;
    cout << list1 << endl;
    cout << "--------------------------" << endl;
    list1.swap(list);
    cout << list << endl;
    cout << list1 << endl;
    cout << "--------------------------" << endl;
    list1.swap(list);
    cout << list << endl;
    cout << list1 << endl;
    cout << "----------------------swap end--------------------" << endl;
    cout << "----------------------reserve start--------------------" << endl;
    std::cout << list1.capacity() << endl;
    list1.reserve(20);
    std::cout << list1.capacity() << endl;
    cout << "----------------------reserve end--------------------" << endl;
    cout << "----------------------set start--------------------" << endl;
    cout << list << endl;
    cout << list.set(3, 100.0);
    cout << list << endl;
    cout << "----------------------set end--------------------" << endl;
    cout << "----------------------clear start--------------------" << endl;
    for (int i = 0; i < 10; i++)
    {
        list2.insert(0, i);
    }
    cout << list2.capacity() << endl;
    cout << list2 << endl;
    list2.clear();
    cout << list2 << endl;
    cout << list2.capacity() << endl;
    cout << "----------------------clear end--------------------" << endl;
    cout << "----------------------removeRange start--------------------" << endl;
    for (int i = 0; i < 10; i++)
    {
        list2.insert(0, i);
    }
    cout << list2 << endl;
    cout << list2.size() << endl;
    list2.removeRange(0, 3);
    cout << list2 << endl;
    cout << list2.size() << endl;
    list2.removeRange(3, 5);
    cout << list2 << endl;
    cout << "----------------------removeRange end--------------------" << endl;
    cout << "----------------------lastIndexOf start--------------------" << endl;
    list2.insert(0, 10);
    list2.insert(1, 10);
    list2.insert(2, 10);
    cout << list2 << endl;
    cout << list2.lastIndexOf(10) << endl;
    cout << list2 << endl;
    cout << "----------------------lastIndexOf end--------------------" << endl;
#endif
    cout << "----------------------reverse start--------------------" << endl;
    cout << list5 << endl;
    list5.reverse();
    cout << list5 << endl;
    cout << "----------------------reverse end--------------------" << endl;
#if 0
    cout << "----------------------leftShift start--------------------" << endl;
    cout << list2 << endl;
    list2.leftShift(4);
    cout << list2 << endl;
    cout << "----------------------leftShift end--------------------" << endl;
    cout << "----------------------circularShift start--------------------" << endl;
    list2.clear();
    for (int i = 0; i < 10; i++)
    {
        list2.insert(0, i);
    }
    cout << list2 << endl;
    list2.circularShift(1);
    cout << list2 << endl;
    list2.circularShift(1);
    cout << list2 << endl;
    list2.circularShift(1);
    cout << list2 << endl;
    list2.circularShift(32);
    cout << list2 << endl;
    cout << "----------------------circularShift end--------------------" << endl;
    cout << "----------------------half start--------------------" << endl;
    cout << list2 << endl;
    list2.half();
    cout << list2 << endl;
    cout << "----------------------half end--------------------" << endl;
    cout << "----------------------iterator start--------------------" << endl;
    cout << list2 << endl;
    cout << (*list2.begin()) << endl;
    circularArrayList<double>::iterator iter;
    cout << "size = " << list2.size() << endl;
    for (iter = list2.begin(); iter != list2.end(); iter++)
    {
        cout << *iter << " ";
    }
    cout << endl;
    for (auto value : list2)
    {
        cout << value << " ";
    }
    cout << endl;

//  std::sort<circularArrayList<double>::iterator>(list2.begin(),list2.end(),std::less);

    cout << (*list2.end()) << endl;
    cout << list2 << endl;
    cout << "----------------------iterator end--------------------" << endl;
#endif
    cout << "----------------------meld start--------------------" << endl;
    circularArrayList<double> list4;
    cout << list << "\ncapacity= " << list.capacity() << " size = " << list.size() << endl;
    cout << list5 << "\ncapacity= " << list5.capacity() << " size = " << list5.size() << endl;
    cout << list4 << "\ncapacity= " << list4.capacity() << " size = " << list4.size() << endl;
    list4.meld(list, list5);
    cout << endl;
    cout << list << "\ncapacity= " << list.capacity() << " size = " << list.size() << endl;
    cout << list5 << "\ncapacity= " << list5.capacity() << " size = " << list5.size() << endl;
    cout << list4 << "\ncapacity= " << list4.capacity() << " size = " << list4.size() << endl;
    cout << "----------------------meld end--------------------" << endl;

    cout << "----------------------merge start--------------------" << endl;
    circularArrayList<double> list1;
    circularArrayList<double> list2;
    circularArrayList<double> list3;
  
    list1.clear();
    list2.clear();
    list3.clear();
    for (int i = 0; i < 10; i++)
    {
        list1.push_back(2 * i);
    }
    for (int i = 0; i < 20; i++)
    {
        list2.push_back(2 * i + 1);
    }
    cout << list1 << "capacity= " << list1.capacity() << " size = " << list1.size() << endl;
    cout << list2 << "capacity= " << list2.capacity() << " size = " << list2.size() << endl;
    cout << list3 << "capacity= " << list3.capacity() << " size = " << list4.size() << endl;

    list3.merge(list1, list2);

    cout << list1 << "capacity= " << list1.capacity() << " size = " << list1.size() << endl;
    cout << list2 << "capacity= " << list2.capacity() << " size = " << list2.size() << endl;
    cout << list3 << "capacity= " << list3.capacity() << " size = " << list4.size() << endl;
    cout << "----------------------merge end--------------------" << endl;
#if 0

    cout << "----------------------split start--------------------" << endl;
    cout << list1 << "capacity= " << list1.capacity() << " size = " << list1.size() << endl;
    cout << list2 << "capacity= " << list2.capacity() << " size = " << list2.size() << endl;
    cout << list3 << "capacity= " << list3.capacity() << " size = " << list4.size() << endl;
    list3.split(list1, list2);
    cout << list1 << "capacity= " << list1.capacity() << " size = " << list1.size() << endl;
    cout << list2 << "capacity= " << list2.capacity() << " size = " << list2.size() << endl;
    cout << list3 << "capacity= " << list3.capacity() << " size = " << list4.size() << endl;
    cout << "----------------------split end--------------------" << endl;
#endif
    return 0;
}

测试输出

xz@xiaqiu:~/study/algorithm/c++/1/build$ ./test 
----------------------insert start--------------------
list capacity = 10
list size = 0
list capacity = 80
list size = 50
49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 
----------------------insert end--------------------
----------------------拷贝构造 start--------------------
list capacity = 80
list size = 50
49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 
----------------------拷贝构造 end--------------------
----------------------indexOf start--------------------
49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 59 58 57 56 55 54 53 52 51 50 
----------------------indexOf end--------------------
----------------------erase start--------------------
list capacity = 80
list size = 50
49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 
list capacity = 80
list size = 30
49 48 47 46 45 44 43 42 41 40 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 
----------------------erase end--------------------
----------------------reverse start--------------------
49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 59 58 57 56 55 54 53 52 51 50 
50 51 52 53 54 55 56 57 58 59 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 
----------------------reverse end--------------------
----------------------meld start--------------------
49 48 47 46 45 44 43 42 41 40 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 
capacity= 80 size = 30
50 51 52 53 54 55 56 57 58 59 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 
capacity= 80 size = 60

capacity= 10 size = 0

49 48 47 46 45 44 43 42 41 40 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 
capacity= 80 size = 30
50 51 52 53 54 55 56 57 58 59 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 
capacity= 80 size = 60
49 50 48 51 47 52 46 53 45 54 44 55 43 56 42 57 41 58 40 59 19 0 18 1 17 2 16 3 15 4 14 5 13 6 12 7 11 8 10 9 9 10 8 11 7 12 6 13 5 14 4 15 3 16 2 17 1 18 0 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 
capacity= 160 size = 90
----------------------meld end--------------------
----------------------merge start--------------------
capacity > arrayLength || capacity < 0
capacity > arrayLength || capacity < 0
capacity > arrayLength || capacity < 0
0 2 4 6 8 capacity= 10 size = 5
1 3 5 7 9 capacity= 10 size = 5
capacity= 10 size = 90
input capacity <= arrayLength10
0 2 4 6 8 capacity= 10 size = 5
1 3 5 7 9 capacity= 10 size = 5
9 0 0 0 0 0 0 0 0 0 capacity= 10 size = 90
----------------------merge end--------------------
xz@xiaqiu:~/study/algorithm/c++/1/build$