首页 > 代码库 > 数据结构——算法设计(12页)方案三

数据结构——算法设计(12页)方案三

方案三的思路尽可能减少元素的重复挪动,设法实现元素移动一次性地“最终定位”;同时在空间效率方面,避免大段复制数据元素序列,降低缓存元素所需的辅助空间使用量。

代码如下:

#include<stdio.h>int gcd(int a , int b)  {    if(a%b!=0)        gcd(b,a%b) ;    else        return b ;}void leftshift3(int *a , int n , int p) {    int i , j , k , m , d ;    int temp ;    int g = gcd(p,n) ;   // printf("%d\n",g) ;    int M = n / g ;    for(i = 0 ; i < g ; i++)    {        temp = a[i] ;        for(j = i , m = 1 ; m < M ; m++)    {            k = (m*p+i)%n ;            a[j]=a[k] ;            j = k ;        }        a[j] = temp ;       // printf("%d\n",j) ;    }}int main()  {    int a[] = {1,2,3,4,5,6,7,8} ;    leftshift3(a,8,3);    for(int i = 0 ; i < 8 ; i++)        printf("%d ",a[i]) ;    printf("\n") ;    return 0 ;}