字元串反轉

以下内容轉自http://k-eckel.cnblogs.com/articles/195931.html

解法一：第一次看到這題目，想到最簡單、最直覺的解法就是：周遊字元串，将第一個字元和最後一個交換，第二個和倒數第二個交換，依次循環，即可，于是有了第一個解法：

char* strrev1(const char* str)

{

  int len = strlen(str);

  char* tmp = new char[len + 1];

  strcpy(tmp,str);

  for (int i = 0; i < len/2; ++i)

  {

    char c = tmp[i];

    tmp[i] = tmp[len-i-1];

    tmp[len-i-1] = c;

  }

  return tmp;

}

這裡是通過數組的下标方式通路字元串的字元，實際上用指針直接操作即可。解法二正是基于此，實作代碼為：

char* strrev2(const char* str)

  char* tmp = new char[strlen(str) + 1];

  strcpy(tmp,str);    

  char* ret = tmp;    

  char* p = tmp + strlen(str) - 1;    

  while (p > tmp)    

  {    

    char t = *tmp;    

    *tmp = *p;    

    *p = t;    

    --p;    

    ++tmp;    

  }    

  return ret;    

顯然上面的兩個解法中沒有考慮時間和空間的優化，一個典型的優化政策就是兩個字元交換的算法優化，我們可以完全不使用任何外部變量即完成兩個字元（或者整數）的交換，這也是一個很經典的面試題目。特别是一些嵌入式硬體相關程式設計中經常要考慮寄存器的使用，是以經常有不使用任何第三個寄存器即完成兩個寄存器資料的交換的題目。一般有兩個解法，對應這裡的解法三和解法四。

解法三的實作代碼為：

char* strrev3(const char* str)

{    

  char* tmp = new char[strlen(str) + 1];    

    *p ^= *tmp;    

    *tmp ^= *p;            

    *p ^= *tmp;

  return ret;

解法四的實作代碼為：

char* strrev4(const char* str)

  char* ret = tmp;

    *p = *p + *tmp;    

    *tmp = *p - *tmp;    

    *p = *p - *tmp;    

實際上我們還可以通過遞歸的思想來解決這個問題，思想很簡單：每次交換首尾兩個字元，中間部分則又變為和原來字元串同樣的問題，是以可以通過遞歸的思想來解決這個問題，對應解法五的實作代碼為：

char* strrev5(char* str,int len)

  if (len <= 1)    

    return str;    

  char t = *str;    

  *str = *(str + len -1);    

  *(str + len -1) = t;    

  return (strrev5(str + 1,len - 2) - 1);

以下給出一個測試程式：

void P(char *a)

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

int main(int argc,char* argv[])

  char* str = "hello";    

  P(str);    

  char* str2 = strrev1(str);    

  P(str2);    

  char* str3 = strrev2(str2);    

  P(str3);    

  char* str4 = strrev3(str3);    

  P(str4);    

  char* str5 = strrev4(str4);    

  P(str5);    

  char* str6 = strrev5(str5,strlen(str5));    

  P(str6);    

  return 0;

 你就可以看到字元串"hello"和"olleh"交替輸出了。

  說明：1）這裡解法中沒有認真考慮輸入字元串的合法性和特殊長度（如NULL、一個字元等）字元串的處理；2）前4個算法不改變輸入字元串的值，解法五修改了輸入字元串。

方法四中利用異或來實作兩個數的交換，這種方法是第一次見到，原理如下

以下内容摘自：http://galaas.blogbus.com/logs/41767402.html

異或是一種基于二進制的位運算，用符号XOR表示，其運算法則是對運算符兩側數的每一個二進制位，同值取0，異值取1。它與布爾運算的差別在于，當運算符兩側均為1時，布爾運算的結果為1，異或運算的結果為0。

異或運算最常見于多項式除法，不過它最重要的性質還是自反性：A XOR B XOR B = A，即對給定的數A，用同樣的運算因子（B）作兩次異或運算後仍得到A本身。這是一個神奇的性質，利用這個性質，可以獲得許多有趣的應用。

例如，所有的程式教科書都會向初學者指出，要交換兩個變量的值，必須要引入一個中間變量。但如果使用異或，就可以節約一個變量的存儲空間：

設有A,B兩個變量，存儲的值分别為a，b，則以下三行表達式将互換他們的值

表達式 （值）

A=A XOR B (a XOR b)

B=B XOR A (b XOR a XOR b = a)

A=A XOR B (a XOR b XOR a = b)

類似地，該運算還可以應用在加密，資料傳輸，校驗等等許多領域。