2010年计算机联考真题——一维数组循环左移

前记

从七月份决定开始考研，中间由于听报告，回家复习数学和政治而耽误了一些时间。自己准备报考山东大学计算机技术的专硕，幸好是数学是考数学二，专业课也只有一门数据结构，这位我的复习节省了很多时间，不想数学一和统考的计算机基础综合的专业复习那么费劲。现在数据结构的复习完全是参照《王道考研系列——2018年数据结构考研复习指导》在复习。对于数据结构虽然到时候是手写算法，但是毕竟这是编程，对于算法能否正确实现并符合题目要求，只有跑程序才能看见。所以复习的同时，有也想利用好csdn博客来记录自己复习过程，故现在开始把指导书上的所有题与基础算法和数据结构利用博客来记录一下。

题目

设将n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P（0﹤P﹤n）个位置，即将R中的数据由（X0 X1 ……Xn-1）变换为（Xp Xp+1 ……Xn-1 X0 X1 ……Xp-1）要求：

　　（1）给出算法的基本设计思想。

　　（2）根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释。

　　（3）说明你所设计算法的时间复杂度和空间复杂度

思路

对于这个问题：可以把问题转化为把数组的前p个数与后n-p个数进行位置互换。即把后n-p个数整体放到前p个数的前面即可。

代码

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;

//把下标在[left,right]的数进行逆置 
bool Reverse(int* A ,int left , int right , int size)
{
    if(left >= right || right >= size)
        return false;
    int mid = (left+right)/2;
    for(int i = 0 ; i < mid - left ; i++){
        A[i+left] += A[right-i];
        A[right-i] = A[i+left] - A[right-i];
        A[i+left] -= A[right-i];
    }
    return true;
}

//把前ｍ个数与后ｎ个数互换位置 
void Exchange(int* A ,int m, int n ,int size) 
{
    Reverse(A,0,m+n-1,size);        //下标０～ｍ+n-1的数逆置
    Reverse(A,0,n-1,size);          //下标０～n-1的数逆置
    Reverse(A,n,m+n-1,size);        //下标n～ｍ+n-1的数逆置 
}

int main()
{
    int a[7];
    for(int i = 0 ; i < 7 ; i++){
        a[i] = i+1;
    } 

    cout<<"对换前"<<endl;
    for(int i = 0 ; i< 7 ; i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;

    Exchange(a ,3,4,7);
    cout<<"对换后"<<endl;
    for(int i = 0 ; i< 7 ; i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;

    return 0;
}           

复制