--------------------------------------------分割线(转载部分)--------------------------------------
-
/*
-
Name: 向量旋转算法集锦
-
Copyright: 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处
-
Author: goal00001111
-
Date: 28-12-08 23:28
-
Description:
-
向量旋转算法：将具有n个元素的向量a向左旋转r个位置。
-
例如 ：将字符串"abcdefghij"旋转成"defghjabc"，其中n=10，r=3。
-
其实就是将 AB 转换成 BA 的过程，这里A ="abc"， B="defghij"。
-
本文总共采用了四种方法来解决向量旋转问题，依次是：
-
方法一：最简单的直接移动向量旋转算法；
-
方法二：简明的的逆置数组旋转算法；
-
方法三：传说中的杂耍旋转算法；
-
方法四：一个类似于欧几里得算法的旋转算法；
-
其中方法一需要一个辅助数组，空间复杂度较高；方法二每个元素都要移动两次，效率相对较低；
-
方法三和方法四都是极牛的算法，空间和时间复杂度都很低。
-
这是牛书《编程珠玑》中的一个例题，在书的网站上有详细的源码，我把它改成了我所熟悉的样子。
-
源码的网站是：
--------------------------------------------分割线----------------------------------------------
「方法1」
利用memcpy函数，需开辟临时空间。先把从a+n-k到a+n-1这k个字符，存到tmp中；然后，把以a开始的地址空间中的字符复制到a+k开始的地址空间中去；最后，把tmp的k个字符放回以a开始的地址空间中去。
|
a
|
...
|
a+n-k-1
|
a+n-k
|
...
|
a+n-1
|
|
void loopRightShiftV2(char a[], int n, int k)
{
char *tmp = (char *)malloc(sizeof(char)*k);
k %= n;
memcpy(tmp, a+n-k, k);
memcpy(a+k, a, n-k);
memcpy(a, tmp, k);
}
|
「方法1版本2」
先看循环右移一个字符的思路：首先，保存最有一个非'\0'字符；然后将字符数组从最后一个非'\0'字符开始，依次后移；最后将已保存的最后一个字符放到第一字符所在位置处。循环右移k个字符，只需将上述过程重复k次即可。
|
void loopRightShift(char a[], int n, int k)
{
int tmp;
int i;
k %= n;
while(k--){
tmp = a[n-1];
for(i = n-1; i >0; i--){
a[i] = a[i-1];
}
a[0] = tmp;
}
}
|
「方法2」
初始状态
|
c1
|
c2
|
...
|
cn-k-1
|
cn-k
|
cn-k+1
|
cn-k+2
|
...
|
cn-1
|
cn
|
逆序一次后 |
|
cn-k
|
cn-k-1
|
...
|
c2
|
c1
|
cn
|
cn-1
|
...
|
cn-k+2
|
cn-k+1
|
再整体逆序，循环右移完成。
|
cn-k+1
|
cn-k+2
|
...
|
cn-1
|
cn
|
c1
|
c2
|
...
|
cn-k-1
|
cn-k
|
补充：来自《编程珠玑》，将数组看成一个向量x=ab，那么循环右移后数组就变成ba。从向量的角度考虑
(a-1b-1)-1=ba
|
/* 不用临时变量交换a[begin]和a[end]两内存单元的内容 */
void stringReverse(char a[], int begin, int end)
{
for(; begin < end; begin++, end--){
a[begin] ^= a[end];
a[end] ^= a[begin];
a[begin] ^= a[end];
}
}
void loopRightShift(char a[], int n, int k)
{
k %= n;
stringReverse(a, 0, n-k-1); /* 先对a[0...n-k-1]这(n-k)个字符逆序 */
stringReverse(a, n-k, n-1); /* 再对a[n-k...n-1]这k个字符逆序 */
stringReverse(a, 0, n-1); /* 最后对整个字符串逆序 */
}
|
|
/*
函数名称：gcd
函数功能：欧几里德算法求最大公约数
输入参数：int m：正整数之一
int n：正整数之二
输出参数：无
返回值：正整数m和n的最大公约数
*/
int gcdLoop(int m, int n)
{
int t;
assert(m > 0 && n >0);
if(m < n){
swapInt(&m, &n);
}
while( n > 0){
t = m % n;
m = n;
n = t;
}
return m;
}
int gcdRecursive(int m, int n)
{
if(m < 0 || n < 0){
printf("Error! not positive integer!\n");
return 0;
}
if(m < n){
swapInt(&m, &n);
}
if(n == 0) {
return m;
}else{
return gcdRecursive(n, m % n);
}
}
/*
函数名称：juggleRotate
函数功能：杂耍(杂技)旋转算法：
1. 将a[0]存储到临时变量t中;
2. 将a[r%n]移动到a[0],将a[2r%n]移动到a[r%n]...a[x*r%n]移动到a[(x-1)*r%d],直到(x*r)%n == 0;
3. a[x*r%n] = t;
如果该过程不能移动所有的元素，那么我们从a[1]开始移动，循环，共重复gcd(n, n)次
说明： 此算法每个元素只需移动一次就可以到达正确位置，理论上效率是最高的，
但由于要做求最大公约数和求余运算等准备工作，所以没有显示出优势。
输入参数：char a[]：需要被旋转的向量
int n：向量的长度
int r：向量左半段长度
输出参数：char a[]：旋转后的向量
返回值：无
*/
void juggleRotate(char a[], int n, int r)
{
int i, j, k;
int t;
int gcdNum = gcdLoop(n, r); //用r和n的最大公约数作为循环次数
for(i = 0; i < gcdNum; i++){//总共需要重复开始移动gcdNum次，才能使得所有的元素都移动到正确位置
j = i;
t = a[j];
while(1){ //依次移动元素，直到 (k*r)%n == 0
k = (j+r) % n;
if(k == i) break;
a[j] = a[k];
j = k;
}
a[j] = t;
}
}
|
|
/*
函数名称：swapArrayp
函数功能：交换两个长度均为len的数组a[left1..left1+len-1) 和 a[left2..left2+len-1)
输入参数：char a[]：需要被处理的数组
int left1：向量块a[left1..left1+len-1)的左界
int left2：向量块a[left2..left2+len-1)的左界
int len： 两个向量块的长度
输出参数：char a[]：交换了部分元素的向量
返回值：无
*/
void swapArray(char a[], int left1, int left2, int len)
{
int t;
while (len > 0)
{
t = a[left1];
a[left1] = a[left2];
a[left2] = t;
left1++;
left2++;
len--;
}
}
/*
函数名称：gcdRotate
函数功能：一个类似于欧几里得辗转相除算法的旋转算法：
就像一个做阻尼振动的弹簧振子一样，按照由两边到中间的顺序，整段的交换向量块，
并且被交换的向量块长度不断缩减，直到lLen == rLen。
由于重复移动的元素较少，所以效率比逆置数组旋转算法要高。
输入参数：char a[]：需要被旋转的向量
int n：向量的长度
int r：向量左半段长度
输出参数：char a[]：旋转后的向量
返回值：无
*/
void gcdRotate(char a[], int n, int r)
{
int lLen, pos, rLen;
lLen = pos = r;
rLen = n - r;
while(lLen != rLen){
if(lLen > rLen){
swapArray(a, pos-lLen, pos, rLen);
lLen -= rLen;
}else{
swapArray(a, pos-lLen, pos+rLen-lLen, lLen);
rLen -= lLen;
}
}
swapArray(a, pos-lLen, pos, lLen);
}
|
阅读(2255) | 评论(0) | 转发(0) |
