数据结构

#ifndef ARRAY_H
#define ARRAY_H
#include
#include 

//默认的容量大小
#define DEFAULT_CAPACITY 10

class Array{
private:
    int *_elems;
    int _capactity;
    int _size;
private:
    //拷贝
    void copyFrom(int const *src, int left, int right)
    {
        _size = right - left + 1;
        for(int i=0;i<_size;i++)
        {
            _elems[i] = src[left+i];
        }
    }
    // 扩容为原来的2倍
    void expand()
    {
        _capactity *= 2;
        int *oldElems = _elems;
        _elems = new int [_capactity];

        for(int i=0;i<_size;i++)
        {
            _elems[i] = oldElems[i];
        }

        delete [] oldElems;
    }
    // 减容为原来的2倍
    void shrink()
    {
        _capactity /= 2;
        int *oldElems = _elems;
        _elems = new int [_capactity];

        for(int i=0;i<_size;i++)
        {
            _elems[i] = oldElems[i];
        }

        delete [] oldElems;
    }

    void exchange(int a,int b)
    {
        int tmp   = _elems[a];
        _elems[a] = _elems[b];
        _elems[b] =       tmp;
    }

    int find(int target, int left, int right ) const
    {
        if(right > _size-1)
            right = _size-1;

        for(int i= left;i<=right; i++)
        {
            if(_elems[i] == target)
                return i;
        }

        return -1;
    }

public:
    Array(int c =DEFAULT_CAPACITY,int s=0,int v=0)
    {
        _capactity = c;
        _size = s;
        _elems = new int [_capactity];
        for(int i=0;i<_size;i++)
            _elems[i] = v;
    }

    Array(int const *A,int size)
    {
        _capactity = size + 1;
        _elems = new int [_capactity];
        copyFrom(A,0,size-1);
    }

    Array(int const *A,int left , int right)
    {
        _capactity = right - left + 1 + 1;
        _elems = new int [_capactity];
        copyFrom(A,left, right);
    }

    Array(const Array &v)
    {
        _capactity = v.size() + 1;
        _elems = new int [_capactity];
        for(int i=0;i
        delete []  _elems;
    }

    int & operator[](int i) const
    {
        return _elems[i];
    }
    friend std::ostream & operator<<(std::ostream& os, const Array &v)
    {
        for(int i=0;i
        return _size;
    }

    bool isEmpty() const
    {
        return _size == 0;
    }

    bool isOrdered() const
    {
        for(int i=1;i<_size;i++)
        {
            if(_elems[i-1]>_elems[i])
                return false;
        }

        return true;
    }

    int find(int e) const
    {
        return find(e,0,_size-1);
    }

    int binarySearch(int e) const
    {
        if(!isOrdered())
            return -1;

        int left =0;
        int right = _size -1 ;

        while(left <= right)
        {
            int mid = (left + right)/2;
            if(_elems[mid] > e)
            {
                right = mid -1;
            }else if(_elems[mid] < e)
            {
                left = mid + 1;
            }else
                return mid;
        }

        return -1;
    }

    int remove(int left,int right)
    {
        if(right > _size-1)
            right = _size-1;

        int delta = right  - left + 1;

        for(int i= right+1;i<_size;i++)
        {
            _elems[i-delta] = _elems[i];
        }

        _size -= delta;

        if(_size<_capactity/2.0)
            shrink();

        return delta;

    }

    int insert(int pos, int e)
    {
        if(pos>_size)
            pos = _size;

        if(_size+1>_capactity)
            expand();

        for (int i=_size-1;i>=pos;i-- ) {
            _elems[i+1] = _elems[i];
        }
        _elems[pos]=e;

        _size++;

        return pos;
    }

    void push_back(int e)
    {
        insert(_size,e);
    }
    int pop_back()
    {
        int last = _elems[_size - 1];
         remove(_size-1,_size-1);
         return last;
    }
    //冒泡排序
    void sort()
    {
        for(int i=0;i<_size-1;i++)
        {
            //判断是否排序
            bool ordered = true;
            for(int j=0;j<_size-1-i;j++)
            {
                if(_elems[j]>_elems[j+1]){
                    exchange(j,j+1);
                    ordered = false;
                }
            }
            if(ordered)
            {
                break;
            }
        }
    }
    //打乱数组中的数据
    void shffle()
    {
        for(int i = _size;i>0;i--)
        {
            exchange(i-1,rand()%i);
        }
    }
};


#endif // ARRAY_H

int main()
{
    Array ts(5,5,2);
    cout<5,4,6,9,0};
    //数组——》Array
    Array ts1(a,5);
    cout<