Chinaunix首页 | 论坛 | 博客
  • 博客访问: 483830
  • 博文数量: 285
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 629
  • 用 户 组: 普通用户
  • 注册时间: 2013-10-14 17:53
个人简介

相信自己,快乐每一天

文章分类

全部博文(285)

分类: 架构设计与优化

2013-11-01 15:03:05

原文地址:字符串之旋转 作者:scq2099yt

一、原理
        把字符串前面的若干字符移动到字符串的尾部,比如:把字符串"abcdef"前2位字符移动到后面得到字符串为“cdefab”。
        可以把字符串看成两段,分别即为XY,左旋转相当于把字符串XY变成YX。先从数学的角度来分析一下翻转操作吧:
        把X翻转后记为XT,则(XT)T=X,首先对X和Y分别进行翻转操作得到XTYT,再对XTYT进行翻转操作得到XY,即(XTYT)T=(YT)T(XT)T=YX,至此翻转完成。

二、实现
        根据前面原理,可以将字符串分为两段,第一段为前m个字符,其余字符分到第二段,定义一个翻转函数,然后分三步走,即先翻转第一段,再翻转第二段,最后将翻转后的两段合在一起翻转一次即可。这样时间复杂度为O(n)。
        #include  

        char* rotate(char *array,     // 待旋转字符串
                        int begin,          // 旋转起点
                        int end)            // 旋转终点
        {  
            while ((NULL != array) && (begin < end)) 
            {  
                char temp = array[begin];  
                array[begin] = array[end];  
                array[end] = temp;  
                begin++;  
                end--;  
            }  

            return array;
        }  
      
        char* LeftRotate(char *array, int number) 
        {  
            if (NULL == array)
            {
                return NULL;
            }

            char *temp = array;
            int len = 0;
            while (*temp++)
            {
                ++len;
            }

            // XT  
            rotate(array, 0, number-1);  
            // YT  
            rotate(array, number, len-1);  
            // (XTYT)T  
            rotate(array, 0, len-1); 

            return array;
        }      

        int main()
        {
            char array[] = "abcdef";
            int number = 2;  
            printf("str=%s-->LeftRotate=%s\n", array, LeftRotate(array, number));

            return 0;
        }







阅读(888) | 评论(0) | 转发(0) |
0

上一篇:字符串之子串

下一篇:字符串之包含

给主人留下些什么吧!~~