在 C 中旋转字符串

Question

我正在尝试向左和向右移动字符串，给定要移动字符串的位置数。

这是我到目前为止写的，但它不起作用。

void Shift(char* string, shift)
{
int length = strlen(string)-1;
int i;
char *buff;
buff = malloc((sizeof(char) *shift) + 1);
strncpy(buff, string, shift);
buff[shift] = '/0';
while (string[i + shift] != '/0')
string[i++] = string[i + shift];
strcat(string, buff);
}

我该如何解决这个问题？ 这应该是示例： 移位 = 1

你好 ->奥赫尔

Answer 1

我的解决方案使用 O(1( 存储将字符串轮换到位：

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
void rotleftmem(void *p, size_t len, size_t lshift)
{
unsigned char *d;
size_t start;
size_t dx, sx;
size_t todo;
unsigned char x;
if (!len)
return;
lshift %= len;
if (!lshift)
return;
d = p;
todo = len;
for (start = 0; todo; start++) {
x = d[start];
dx = start;
while (1) {
todo--;
sx = dx + lshift;
if (sx >= len || sx < dx /*overflow*/)
sx -= len;
if (sx == start) {
d[dx] = x;
break;
}
d[dx] = d[sx];
dx = sx;
}
}
}
void *rotatemem(void *p, size_t len, ssize_t rshift)
{
if (len) {
size_t lshift = rshift < 0 ? -rshift : len - rshift % len;
rotleftmem(p, len, lshift);
}
return p;
}
char *rotatestr(char *s, ssize_t rshift)
{
return rotatemem(s, strlen(s), rshift);
}
int main(int argc, char *argv[])
{
ssize_t rshift;
char *s;
if (argc != 3) {
fprintf(stderr,
"usage: %s N STRn"
"Rotate STR right by N or left by -Nn",
argv[0]);
return 2;
}
rshift = strtol(argv[1], NULL, 10);
s = argv[2];
printf("%sn", rotatestr(s, rshift));
return 0;
}

代码的内脏在函数rotleftmem，它旋转由指定的无符号"左移"值留下的指定长度的内存块。rotatemem是围绕rotleftmem的包装器，向任一方向旋转;负移位值左旋，正移位值右旋;带符号移位值将转换为正的"左移"值。rotatestr是围绕rotatemem的包装器，它接受指向以 null 结尾的字符串的指针，而不是指向 void 加上长度的指针。rotatestr和rotatemem都返回原始指针。

对于rotleftmem，如果块长度(len(不为零，则"左移"值(lshift(是模len的约解。如果len或 (缩减的(lshift值中的任何一个为 0，则该函数不执行任何操作。否则，外循环将迭代GCD(len, lshift)次(其中GCD(a, b)是a和b的最大公约数(。对于外循环的每次迭代，内循环将迭代len / GCD(len, lshift)次，因此内循环的迭代总数为len。时间复杂度为 O(n(，其中 n 是块的长度。

Answer 2

我的解决方案是基于模的，使用负数向左移动，使用正数向右移动。

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
void shift(char* string, int shift)
{
char *tmp = strdup(string);
int len = strlen(string);
if (shift < 0)
shift = len + (shift % len);
for (int i = 0; string[i] != 0; i++) {
int new_idx = (i + shift) % len;
tmp[new_idx] = string[i];
}
memcpy(string, tmp, len);
free(tmp);
}
int main(void) {
char test[] = "coucou";
shift(test, -9);
printf("%sn", test);
return 0;
}

诀窍是计算每个字符将在目标字符串中结束的位置。通过使用总大小的模，您可以确保它保持在边界之间，从而添加偏移量，然后确保它保持在边界内，从而给出正确的索引。

对于左移，我只是将左移偏移量转换为右移位偏移量，并重复使用右移位代码。

Answer 3

您可以使用 XOR 按位运算符来交换字符并循环以反转它们。

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

void reverse(char *a, int n) {
for (int i=0, j=n-1; i < j; i++, j--) {
a[i] = a[i] ^ a[j];
a[j] = a[j] ^ a[i];
a[i] = a[i] ^ a[j];
}
}

int main(int argc, char const *argv[]) {
int k = 1; // shift count
int n = 5;
char a[] = "HELLO";
reverse(&a[n-k], k); // reverse end of array
reverse(a, n-k);     // reverse beginning of array
reverse(a, n);       // reverse entire array
// print output
for (int i=0; i < n; i++) {
printf("%cn", a[i]);
}
return 0;

}