字元串逆序（一）

一、普通的字元串逆序

例如，給定一個字元串 s，将 s 中的字元順序颠倒過來，如 s = “abcd”，逆序後變成 “dcba”。可以采用多種方法對字元串進行逆序，以下将對其中的一些方法進行分析。

（1）直接配置設定一個與原字元串等長的字元數組，然後反向拷貝即可。

具體實作如下：

#include <iostream>

char *Reverse(char *s)
{
    char *q = s;
    while (*q)
        ++q;
    q--; // q指向字元串s的倒數第二個字元(即空字元前的那個字元)

    char *p = new char[sizeof(char)*(q - s + )]; // 包含空字元
    char *r = p; // r指向逆序後字元串的首部

    while (q >= s)
        *p++ = *q--;
    *p = '\0';

    return r;
}

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

    char str[] = "I am a student";
    char *s = Reverse(str);

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

    return ;
}
           

注意點：

<1> new char[10]; 配置設定一塊連續的記憶體，即一個數組，裡面有10個元素。

<2> new char(10); 配置設定一塊記憶體，有一個元素，該元素被初始化為10。

（2）原地逆序

原地逆序不允許額外配置設定空間，就是将字元串兩邊的字元逐個交換。例如，給定字元串 “abcd”，逆序的過程分别是交換字元a和d，交換字元b和c。如果最中間有兩個字元（即需要反轉的字元串長度為偶數），那就交換；如果最中間有一個字元（即需要反轉的字元串長度為奇數），那就不需要碰它。還有就是最後一個用來辨別字元串結尾的0x00字元不用動它。

實作方式有以下幾種：

1）設定兩個指針，分别指向字元串的頭部和尾部，然後交換兩個指針所指的字元，并向中間移動指針直到交叉。

具體實作如下：

#include <iostream>

char *Reverse(char *s) // 該函數應有傳回值，或者建議使用引用型形參。
{
    char *p = s;
    char *q = s;

    while (*q)
        ++q;
    q--;
    while (q > p)
    {
        char temp = *q;
        *q-- = *p;
        *p++ = temp;
    }

    return s;
}

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

    char str[] = "I am a student";
    char *s = Reverse(str);

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

    return ;
}
           

2）遞歸：思想很簡單，每次交換首尾兩個字元，中間部分則又變為和原來字元串同樣的問題，是以可以通過遞歸的思想來解決這個問題；需要給定逆序的空間，調用方法Reverse( s, 0, strlen(s) - 1 )，對字元串 s 在區間 left 和 right 之間進行逆序。

具體實作如下：

#include <iostream>

char *Reverse(char *s, int left, int right)
{
    if (left >= right)
        return s;

    char temp = s[left];
    s[left] = s[right];
    s[right] = temp;

    return Reverse(s, left + , right - ); // 此處一定要帶上return。
}

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

    char str[] = "I am a student";
    char *s = Reverse(str, , (int)strlen(str)-); // 使用的是下标，不是長度，是以需要strlen(str)-1。

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

    return ;
}
           

注意：

該遞歸方法的缺陷：不能直接反轉常量字元串，需要轉換，而且需要額外配置設定空間，已經不滿足原地逆序的要求。參考如下：

// 如果想用遞歸方法，反轉字元串常量，需要做如下修改。
int main(int argc, const char * argv[]) {

    const char *str1 = "I am a student";
    int len = (int)strlen(str1); // 不包含空字元

    char str[len+];
    for (int j = ; j <= len; j++) { // 連同空字元一起拷貝過來
        str[j] = str1[j];
    }

    char *s = Reverse(str, , (int)strlen(str)-);

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

    return ;
}
           

3）非遞歸，同樣指定逆序區間，和方法 1）沒有本質差別，一個使用指針，一個使用下标。

具體實作如下：

#include <iostream>

char *Reverse(char *s, int left, int right)
{
    while (left < right)
    {
        char temp = s[left];
        s[left++] = s[right];
        s[right--] = temp;
    }

    return s;
}

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

    char str[] = "I am a student";
    char *s = Reverse(str, , (int)strlen(str) - );

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

    return ;
}
           

（3）不允許使用臨時變量的原地逆序

原地逆序雖然沒有額外配置設定空間，但還是使用了臨時變量，占用了額外的空間。如果不允許使用額外空間，主要有以下幾種實作方法。

1）利用異或操作，實作兩個變量的交換（按位異或）

#include <iostream>

char *Reverse(char *s)
{
    char *r = s;
    char *q = s;
    while (*q)
        ++q;
    q--; // q指向字元串s的倒數第二個字元(即空字元前的那個字元)

    while (q > r)
    {
        *q = *q ^ *r;
        *r = *q ^ *r;
        *q = *q ^ *r;
        q--;
        r++;
    }

    return s;
}

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

    char str[] = "I am a student";
    char *s = Reverse(str);

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

    return ;
}
           

2）利用加減法，實作兩個變量的交換

#include <iostream>

char *Reverse(char *s)
{
    char *r = s;
    char *q = s;
    while (*q)
        ++q;
    q--; // q指向字元串s的倒數第二個字元(即空字元前的那個字元)

    while (q > r)
    {
        *q = *q + *r;
        *r = *q - *r;
        *q = *q - *r;
        q--;
        r++;
    }

    return s;
}

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

    char str[] = "I am a student";
    char *s = Reverse(str);

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

    return ;
}
           

3）使用字元串的結束字元 ‘\0’ 所在的位置作為交換空間，但這個有局限，隻适合以 ‘\0’ 結尾的字元串，對于不支援這種字元串格式的語言，就不能使用了。

#include <iostream>

char *Reverse(char *s)
{
    char *r = s;
    char *q = s;
    while (*q)
        ++q;

    char *p = q - ;

    while (p > r)
    {
        *q = *p;
        *p-- = *r;
        *r++ = *q;
    }
    *q = '\0';

    return s;
}

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

    char str[] = "I am a student";
    char *s = Reverse(str);

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

    return ;
}
           

小記：

交換2個數，常用的方法：

<1> 第一種方法，大家會借助第三個變量來實作：

如：tmp=A;A=B;B=tmp;

這種方法需要借助第三變量來實作；

<2> 第二種方法是利用加減法實作兩個變量的交換，

如：A=A+B;B=A-B;A=A-B;

但是 如果 A+B 超出 A的範圍，就會出錯！極為不推薦 此方法

<3> 第三種方法是得用位異或運算來實作，也是效率最高的一種，在大量資料交換的時候，效率明顯優于前兩種方法，

如：A=A^B;B=A^B;A=A^B;

原理：利用一個數異或本身等于０和異或運算符合交換率。

異或運算的性質：

1.任意一個變量X與其自身進行異或運算，結果為0，即X^X=0

2.任意一個變量X與0進行異或運算，結果不變，即X^0=X

3.異或運算具有可結合性，即a^b^c=（a^b）^c=a^（b^c）

4.異或運算具有可交換性，即a^b=b^a

分析：

第一步： a = a ^ b;

完成後 a變量的結果為a ^ b

第二步： b = a ^ b;

此時指派号右邊的a儲存的是a ^ b的值，那麼将指派号右邊的a用a ^ b替換，

得到（a ^ b） ^ b=a ^ (b ^ b)=a ^0=a,

即經過第二步運算後b中的值為a，即b=a，将a換到了b裡

第三步： a = a ^ b;

此時指派号右邊的a儲存的仍然是a ^ b的值，不變，而指派号右邊的b已經是a 了，

将指派号右邊的a,b分别進行替換，

即此時指派号右邊a ^ b=（a ^ b）^ a=a ^ b^ a=a ^ a^ b=0^ b=b, 該值指派給a,即a=b

即經過第三步運算後a中的值為b，即a=b,将b換到了a裡

這樣經過如上的三步驟，完成了交換兩個變量a,b而無需借助第3個臨時變量過程。