顺序表的循环左移

设将n（n>1）个整数存放到一维数组R中，试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p（0<p<n）个位置，即把R中的数据序列由（x0，x1，…，xn-1）变换为（xp，xp+1，…，xn-1，x0，x1，…，x）。

比如：长度为 8 的顺序表 (1, 2, 3, 4, 5, 6, 7, 8)(1,2,3,4,5,6,7,8)，循环左移 3 位后的结果为 (4, 5, 6, 7, 8, 1, 2, 3)(4,5,6,7,8,1,2,3)。

样例输入

8 3
1 2 3 4 5 6 7 8

样例输出

4 5 6 7 8 1 2 3

算法分析

• 通过偏移量将顺序表分为两部分
• 创建一个临时数组存储偏移量右边的数据结构
• 修改顺序表的排列顺序，让偏移量n以后的数据结构整体循环左移（向右移动）3位；
• 将临时数组内保存的数据结构追加到顺序表之后（左移）

代码如下：

#include <iostream>

using namespace std;

class Vector{
private :
    int size, length;
    int *data;
public:
    Vector(int input_size)
    {   
        size = input_size;
        length = 0;
        data = new int[size];
    }   
    ~Vector()
    {   
        delete [] data;
    }   
    
    bool insert(int loc, int value)
    {   
        if(loc < 0 || loc > length)
        {
            return false;
        }
        if(length >= size)
        {
            return false;
        }
        for(int i=length; i>loc; --i)
        {
            data[i] = data[i-1];
        }
        data[loc] = value;
        length++;
        return true;
    }   
    
    bool remove(int index)
    {   
        if(index < 0 || index >= length)
        {
            return false;
        }
        for(int i=index+1; i<length; i++)
        {
            data[i-1] = data[i];
        }
        length--;
        return true;
    }   
    
    int search(int value)
    {   
       for(int i=0; i<length; i++)
       {
           if(data[i] == value)
           {
               return i;
           }
       }
       return -1;
    }

    void print()
    {
        for(int i=0; i<length; i++)
        {
            if(i>0)
            {
                cout << " ";
            }
            cout << data[i];
        }
        cout << endl;
    }

    void expand()
    {
        int *old_data = data;
        size *= 2;
        data = new int[size];
        for(int i=0; i<length; i++)
        {
            data[i] = old_data[i];
        }
        delete [] old_data;
    }

    bool move_left(int offset)
    {
        if(offset < 0 || offset >= length)
        {
            return false;
        }
        
        //开辟临时空间存储右半部分数据结构
        int* temp_data = new int[offset];
        for(int i=0; i<offset; i++)
        {
            temp_data[i] = data[i];
        }
        
        //将左半部分数据结构整体向右偏移3位
        for(int i=0; i<length-offset; i++)
        {
            data[i] = data[i+offset];
        }

        //将左半边数据结构整追加
        for(int i=length, j=offset; j>0; --i, --j )
        {
            data[i-1]= temp_data[j-1];
        }

        delete [] temp_data;
        return true;
    }
};

int main()
{
    int n,k,value;
    cin >> n;
    cin >> k;
    Vector vec(n);
    for(int i=0; i<n; i++)
    {
        cin >> value;
        vec.insert(i,value);
    }
    vec.move_left(k);
    vec.print();
    return 0;
}   

另一种思路：
减少一个for循环,重新开辟的内存空间较大：

 /*   bool move_left(int offset)
    {
        if(offset < 0 || offset >= length)
        {
            return false;
        }

        int* temp_data = data;
        
        data = new int[size];
        
        for(int i=0; i<length-offset; i++)
        {
            data[i] = temp_data[i+offset];
        }

        for(int i=length, j=offset; j>0; --i, --j )
        {
            data[i-1]= temp_data[j-1];
        }

        delete [] temp_data;
        return true;
    }
*/