C语言字符串的循环右移

那天参加某公司（应公司要求不可透露名称）的招聘笔试，题目是：给出一个字符串及所要移动的位数steps，编写一个函数实现字符串的循环右移，题目中给出了函数的定义，当时的感觉是自己做的挺不错的，但是实际上机之后才发现自己还是没有把数组的边界和字符数组指针相关的内容弄清楚，也可能是因为当时时间仓促吧，最终实现代码如下，欢迎各位高手提出意见……

 

#include <stdio.h>
#include <stdlib.h>
void loopMove(char *pStr,int steps)
{
	int length=0,i=0;
	char *sub=pStr,*str;

	while (*pStr!='\0')
	{
		length++;
		pStr++;
	}
	pStr--;
	if (steps>length)
		steps=steps-length;
	str=(char *)malloc(steps);

	for (i=0;i<steps;i++)
		str[i]=sub[length-steps+i];
	
	for (i=0;i<length-steps;i++)
		sub[length-i-1]=sub[length-steps-i-1];

	for (i=0;i<steps;i++)
		sub[i]=str[i];

}

int main()
{
	char a[]="abcdef";
	loopMove(a,7);
	printf("%s\n",a);

	return 0;
}

  

 关于这段程序的时间复杂度和空间复杂度，由于没有循环的嵌套，所以时间复杂度应该为O(n)，对于空间复杂度，由于引进了str用于临时存储要移出去的字符，所以空间复杂度应该为steps（steps<length）或者steps-length（steps>length），最大不超过要移位的字符串的长度……

评论

1 楼 tanss 2011-12-12  

if (steps>length)  
        steps=steps-length; 
我觉得应该改为：
if (steps>length)  
        steps=steps%length;