字符串循环移位的三种算法

如题:将一个n位字符串进行循环移位k。例如:对于字符串abcdef循环移位k=2,则输出cdefab。

一、算法一思想:

采用一个辅助空间,将要移动到末尾的k位存储到一个k位的辅助空间,先将n-k个字符往字符串前面移动,然后将辅助空间的k个字符复制到原数组后面。在这里可以采用strncpy函数来简化操作,这个函数是用来拷贝指定地址指定字节的字符串。

二、算法二思想:

直接采用一次交换的思想,即从第i+1个字符开始,将其放置到最终目标位置,当循环结束,所有的字符均到目标位置,达到字符串循环的目的。

三、算法三思想:

从第1到第i个字符倒序,第i+1到第n个倒序,最终所有字符再一次倒序,即可完成字符串循环的目的。

实现代码如下(VC6.0通过测试):

#include <stdio.h>

#include <string>

using namespace std;

//申请辅助空间  空间复杂度为O(n)       

void ne(char * str,int i)

{

//将首部i个字符串拷贝到辅助数组

char* temp=new char[i+1];

strncpy(temp,str,i);

temp[i]='\0';

//将第i个字符后面的字符全部前移i个位置

strncpy(str,str+i,strlen(str)-i);

//从辅助空间拷贝i个字符到原字符串尾部

strncpy(str+strlen(str)-i,temp,i);

//释放辅助数组

delete[] temp;

printf("%s\n",str);

}

//字符串循环移位  空间复杂度为O(1)   

void re(char * str,int i)

{

//把每个字符置换到目标位置

for(int j=i;j<strlen(str);j++)

{

swap(str[j],str[j-i]);

}

printf("%s\n",str);

}

//字符串倒序 

void exchange(char *str,int low,int high)

{

int i=low;

int h=high;

//将字符串倒序采用while循环非常不错!

while(i<h)

{

swap(str[i],str[h]);

i++;

h--;

}

}

//三次倒序算法   空间复杂度为O(1)  

void three(char * str,int i)

{

//首部倒序

exchange(str,0,i-1);

//尾部倒序

exchange(str,i,strlen(str)-1);

//整体倒序

exchange(str,0,strlen(str)-1);

printf("%s\n",str);

}

int main()

{

printf("原字符串:abcdef\n");

char name1[]="abcdef"; 

ne(name1,2);

char name[]="abcdef";

re(name,2);

char test[]="abcdef";

three(test,2);

return 0;

}

输出截图:

 

 

源代码下载请点击

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐