PTA 数据结构数组循环左移

我就是我 2022-04-03 06:47 211阅读 0赞

7-1 数组循环左移 （20 分）

本题要求实现一个对数组进行循环左移的简单函数：一个数组a中存有n（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向左移m（≥0）个位置，即将a中的数据由（a0a1⋯an−1）变换为（am⋯an−1a0a1⋯am−1）（最前面的m个数循环移至最后面的m个位置）。如果还需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

### 输入格式: ###

输入第1行给出正整数n（≤100）和整数m（≥0）；第2行给出n个整数，其间以空格分隔。

### 输出格式: ###

在一行中输出循环左移m位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

### 输入样例： ###

8 3
    1 2 3 4 5 6 7 8

### 输出样例： ###

4 5 6 7 8 1 2 3

先将左右两个部分内部各自逆置，再逆置整个数组。如此则算法时间复杂度为O(n)，空间复杂度O(1)。

//库函数头文件包含
    #include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    
    //函数状态码定义
    #define TRUE        1
    #define FALSE       0
    #define OK          1
    #define ERROR       0
    #define INFEASIBLE -1
    #define OVERFLOW   -2
    
    typedef int  Status;
    
    //顺序表的存储结构定义
    #define LIST_INIT_SIZE  100
    #define LISTINCREMENT   10
    typedef int ElemType;  //假设线性表中的元素均为整型
    typedef struct{
        ElemType* elem;   //存储空间基地址
        int length;       //表中元素的个数
        int listsize;     //表容量大小
    }SqList;    //顺序表类型定义
    
    Status CreateList(SqList &L,int n)
    {
        L.elem = (ElemType*)malloc(sizeof(ElemType)*(n+1));
        L.length = 0;
        L.listsize = n+1;
        if(!L.elem)
            exit(OVERFLOW);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&L.elem[i]);
            ++L.length;
        }
        return OK;
    }
    void PrintList(SqList L)
    {
        for(int i=0;i<L.length;i++)
        {
            if(!i)
                printf("%d",L.elem[i]);
            else
                printf(" %d",L.elem[i]);
        }
    }
    void Reverse(int *a,int begin,int end)
    {
        int left = begin,right = end;
        while(left < right)
        {
            int t = a[left];
            a[left] = a[right];
            a[right] = t;
            ++left;
            --right;
        }
    }
    void MoveLeft(SqList &L,int m)
    {
        m %= L.length;
        Reverse(L.elem,0,m-1);
        Reverse(L.elem,m,L.length-1);
        Reverse(L.elem,0,L.length-1);
    }
    
    int main()
    {
        SqList L;
        int n,m;
        scanf("%d %d",&n,&m);
        CreateList(L,n);
        //Reverse(L.elem,0,L.length-1);
        MoveLeft(L,m);
        PrintList(L);
        return 0;
    }