数组循环移位五种方法的实现

#include <stdio.h>
#include <stdlib.h>

void swap(char *a, char *b)
{
    char t = *a;
    *a = *b;
    *b = t;
}

void print(char *a, int n)
{
    int i;
    
    for (i = 0; i < n; i++)
    {
        printf("%c", a[i]);
    }
    printf("\n");
}

void rotation10(char *a, int n, int k)
{
    char *t = (char*)malloc(sizeof(char) * k);

    int i;
    for (i = 0; i < k; i++)
    {
        t[i] = a[i];
    }
    for (i = k; i < n; i++)
    {
        a[i - k] = a[i];
    }
    for (i = n - k; i < n; i++)
    {
        a[i] = t[i - n + k];
    }
    free(t);
}

void rotation11(char *a, int n, int k)
{
    char t;
    int i, j;

    for (i = 0; i < k; i++)
    {
        t = a[0];
        for (j = 1; j < n; j++)
        {
            a[j - 1] = a[j];    
        }
        a[n - 1] = t;
    }
}

#define ALLOC(s) ((s*)malloc(sizeof(s)))

void rotation2(char *a, int n, int k)
{
    struct node { char c; struct node *next; };
    struct node *head1, *head2, *p;
    int i;

    head1 = p = ALLOC(struct node);
    for (i = 0; i < k - 1; i++)
    {
        p->c = a[i];
        p->next = ALLOC(struct node);
        p = p->next;
    }
    p->c = a[i];
    p->next = NULL;
    
    head2 = p = ALLOC(struct node);
    for (i = k; i < n - 1; i++)
    {
        p->c = a[i];
        p->next = ALLOC(struct node);
        p = p->next;
    }
    p->c = a[i];
    p->next = head1;

    for (i = 0, p = head2; p; i++)
    {
        a[i] = p->c;
        p = p->next;
    }

    for (p = head2; head2; p = head2)
    {
        head2 = p->next;
        free(p);
    }    
}

static void _grp_swap(char *a, int s1, int s2, int m)
{
    for (; m ; m--)
    {
        swap(&a[s1], &a[s2]);
        s1++;
        s2++;
    }
}

// rotate [s1..e1] with [s2..e2], s2 = e1 + 1

static void _rotation30(char *a, int s1, int e1, int s2, int e2)
{
    int left = e1 - s1 + 1, right = e2 - s2 + 1;

    if (left <= 0 || right <= 0)
    {
        return;
    }
    
    if (left < right)
    {
        _grp_swap(a, s1, e2 - left + 1, left);
        _rotation30(a, s1, e1, s2, e2 - left);
    }
    else
    {
        _grp_swap(a, s1, s2, right);
        _rotation30(a, s1 + right, e1, s2, e2);
    }

}

void rotation30(char *a, int n, int k)
{
    _rotation30(a, 0, k-1, k, n-1);        
}

void rotation31(char *a, int n, int k)
{
    int s1 = 0, e1 = k-1, s2 = k, e2 = n-1;
    int left = e1 - s1 + 1, right = e2 - s2 + 1;
    
    while (left >0 && right > 0)
    {
        if (left < right)
        {
            _grp_swap(a, s1, e2 - left + 1, left);
            e2 = e2 - left;
        }
        else
        {
            _grp_swap(a, s1, s2, right);
            s1 = s1 + right;
        }
        left = e1 - s1 + 1;
        right = e2 - s2 + 1;    
    }
}

static int gcd(int x, int y)
{
    return y ? (x > y ? gcd(y, x - y) : gcd(x, y - x) ): x;
}

void rotation4(char *a, int n, int k)
{
    int g = gcd(n, k);
    int i;

    for (i = 0; i < g; i++)
    {
        char t = a[i];
        int j = i, p;
        for (;;)
        {
            p = (j + k) % n;
            if (p == i)
                break;
            a[j] = a[p];
            j = p;
        }    
        a[j] = t;
    }
}

static void _reverse(char *a, int s, int e)
{
    for (; s < e; s++,e--)
    {
        swap(&a[s], &a[e]);
    }
}

void rotation5(char *a, int n, int k)
{
    _reverse(a, 0, k - 1);
    _reverse(a, k, n - 1);
    _reverse(a, 0, n - 1);    
}

int main()
{
    char a[] = {'a','b','c','d','e',
         'f','g','h','i','j',
         'k','l','m','n','o',
         'p','q','r','s','t',
         'u','v','w','x','y',
         'z'};

    // rotation10(a, sizeof(a), 3);

    // rotation11(a, sizeof(a), 4);

    // rotation2(a, sizeof(a), 2);

    // rotation30(a, sizeof(a), 2);

    // rotation31(a, sizeof(a), 2);

    rotation4(a, sizeof(a), 2);
    // rotation5(a, sizeof(a), 2);


    print(a, sizeof(a));
    return 0;
}