首页 > 代码库 > 杂题之循环移动字符串
杂题之循环移动字符串
1.问题:一个m个字符的字符串,‘循环’ 向左或向右移动n(n <= m)位,求移动后的字符串。例如abcdefg 左循环移动3位 -> defgabc, 又循环移动三位 -> efgabcd.
2.实现方法很多,最直接但是效率很低的方法是挨个移动字符元素,类似移动数组。这里介绍一个技巧来实现, 以循环左移n位为例:
1).首先翻转前n位,此时你可以伸出右手,手心对着你自己,假设此时从无名指到大拇指标号为1,2,3,4,5;然后翻转你的右手,让手心对外,则此时为5,4,3,2,1。翻转前n位字符串的过程与此类似。
那么程序中这个过程如何实现呢,很简单,就是第一位和最后以为对换,第二位和倒数第二位对换,依次类推,实现代码如下:
static void swap(char &a, char &b) { a = a ^ b; b = a ^ b; a = a ^ b; } static void move(char *str, int head, int tail) { if (str == NULL || strlen(str) < 2) { return; } for (; head < tail; head++, tail--) { swap(*(str + head), *(str + tail)); } }
2).将n+1到m位翻转,过程与上边类似。当然这两个翻转执行顺序没有先后的区别。
3).将字符串整体翻转后,便得到循环左移后的字符串。
循环右移的过程于此类似。
3.下面贴出可以选择循环左移和右移的代码(move.c),读者可以参考这理解:
#include <stdio.h> #include <stdlib.h> #include <string.h> static void swap(char &a, char &b) { a = a ^ b; b = a ^ b; a = a ^ b; } static void move(char *str, int head, int tail) { if (str == NULL || strlen(str) < 2) { return; } for (; head < tail; head++, tail--) { swap(*(str + head), *(str + tail)); } } int main(int argc, char *argv[]) { char str[100] = { 0 }; int movenum; char direc; while(1) { printf("Enter a string And move direction(L or R) And a move num\n"); if (scanf("%s %c %d", str, &direc, &movenum) == 3) { if (movenum < 0 || movenum > strlen(str)) { printf("error\n"); continue; } printf("Before Move: %s \n", str); if (‘R‘ == direc) { //the sequence of two move op can be changed move(str, strlen(str) - movenum, strlen(str) - 1); move(str, 0, strlen(str) - movenum - 1); } else if (‘L‘ == direc) { //the sequence of two move op can be changed move(str, 0, movenum - 1); move(str, movenum, strlen(str) - 1); } else { continue; } move(str, 0, strlen(str) - 1); printf("After Move: %s \n", str); } else { break; } } return 0; }
编译命令: g++ -g -o move move.c;,运行: ./move
部分运行结果:
当让只是简单的示例程序,如果代码出错,欢迎指正, 同时若有更好的方法,希望不吝赐教。
杂题之循环移动字符串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。