现在的位置: 首页 > 综合 > 正文

字符串的逆序之旅

2012年02月01日 ⁄ 综合 ⁄ 共 1399字 ⁄ 字号 评论关闭

这两天在看《编程珠玑》,第一章就收获非常的多,真的挺后悔现在才看着本书,第二章有个将字符串逆序的例子,就是比如“this is a string”变成“string a is this”,那么今天就总结一下这个逆序字符串的小专题。

       首先假设有人问你:如何将“this is a string”完全逆序,也就是gnirts a si siht

       方案一:申请一个同样大小的空间,直接逆序将字符串保存一遍。                                                                            


 

       这是我们最容易想到的一种方法,我们只需要找到字符串尾指针就好了,下面就是一段简单的代码:

        

        这个代码的关键是找准字符串尾的位置,(每一个字符串以‘\0’结尾)

   

        那么,现在我们的问题增加了,再开一个n,空间太大了,我们必须减少空间。。。

        方案二:其实仔细观察就会发现,逆序其实就是不断的首尾交换,比如abcde首先是a和e进行交换,接着是b和d交换,这样以此类推n/2次交换就可以完成任务了,这个的远离其实就是我们早就会的轴对称。


 

      

        写这个方法的时候,我曾经犯的错误就是把right-- 写成了right++,结果悲剧的段错误就出现了,希望大家不要有这样低级的失误。

    

        现在问题又的苛刻了,干脆不允许我们用临时变量了,该如何使字符串逆序,这个时候

        方案三:有没有想起以前有一个经典的问题就是,如何不经过临时变量如何交换两个整数,那就是经典的;


 

        a = a + b;

        b = a - b;  //此时 b = a

        a = a - b ; //此时 a = b         

        其实我们还可以使用一个渐渐被我们遗忘的操作符,那就是异或^,补一点小知识,两个数异或,比如1101和1001,相同位为0,不同位为1,则结果为0100,所以任何数和0异或的结果都是其本身,一个数和自身异或的结果就是0.

        于是上面的代码其实也可以这样来写

       a = a ^ b;

       b = a ^ b;

       a = a ^ b;            哈哈,是不是感觉非常的棒。

      有了这个思路的话,接下来实现无临时变量的交换就变得非常的简单了        

       

        还是那句话,注意符号。。。

 


 

       最后回归话题了,我们不是要完全的逆序,而是要求每一个单词的逆序,比如 “string a is this”,说真的第一次看这个问题就是一下子头很乱,无从下手,《编程珠玑》中的提示就是逆序的逆序,一下子就有了灵感,我们把这个字符串抽象成ABCD,我们用A~表示其逆序,这样(A~B~C~D~)~就是DBAC了。通俗的描述就是先对每一个单词求逆序,得到 siht si a gnirts,然后对整个字符串逆序,也就得到了string a is this

      

     

      好了,大功告成了,这样我们一步步的归纳了一下字符串逆序的种种~希望对大家有所帮助。

     

   本文源代码:https://github.com/octobershiner/Algorithm/tree/master/Reverse

 

 


 

抱歉!评论已关闭.