替换空格

题目：请实现一个函数，把字符串中的每个空格替换成“%20”，例如输入“welcome to my world!”,则输出“welcome%20to&20my%20world”.

这个例子的应用主要用在网络编程中，如果URL参数中含有一些特殊字符譬如：空格，‘#’，可能导致服务器端无法获得正确的参数，故需要把这些特殊符号转换成以‘%’开头再加此特殊符号ASCII码的两位十六进制表示。空格转换为‘%20’，‘#’转换为‘%23’.

　　此类问题的求解有两种实现方式，一是：在新的数组中实现，比较简单。二是：在原数组中实现不重新申请新的空间，本例就实现这种方式。

从前往后扫描把空格替换为%20的算法一般都需要把空格之后的有效字符向后移动多次（以便腾出空间存放20），从而导致多次的数据移动导致时间复杂度O(n2).例如：

故此类的问题一般采用从后往前添加的方法，防止有效字符的多次移动，更为高效。

思路：先把原数组扫描一遍，得到数组中的空格数和数组的原长度，则添加完%20后数组新的长度=原长度+2*空格数，另设置两个指针p1和p2,p1指向原数组的最后一个位置，p2指向新数组的最后一个位置，然后具体过程如下图所示。

故可以写出如下的代码：

 1 #include<iostream>
 2 using namespace std;
 3 const int Max_Len = 100;//数组最大长度
 4 void Space_Change(char str[Max_Len],int max_len)
 5 {
 6     if (str==nullptr||max_len<=0) return ;
 7     int first_len = 0;　　　　　　　　　　　　　　　　　　//数组原长度
 8     int second_len = 0;　　　　　　　　　　　　　　　　　 //替换完成后的数组长度
 9     int space_len = 0;                               //空格数
10     int i = 0;
11     while (str[i] != ''){　　　　　　　　　　　　　　　//先扫描一次得到空格数和原数组长度
12         if (str[i] == ' ')
13             ++space_len;
14         ++i;
15     }
16     first_len = i + 1;
17     second_len = first_len + 2 * space_len;
18     if (second_len > max_len)　　　　　　　　　　　　　　//如果新数组长度太大，则返回
19         return;
20     int p1 = first_len - 1;　　　　　　　　　　　　　　　 //p1指向原数组最后一个位置
21     int p2 = second_len - 1;　　　　　　　　　　　　　　  //p2指向新数组的最后一个位置
22     while (p1 != p2){
23         if (str[p1] == ' '){　　　　　　　　　　　　　　  //遇到空格替换
24             --p1;
25             str[p2--] = '0';
26             str[p2--] = '2';
27             str[p2--] = '%';
28         }
29         else{                                        //否则直接移动复制
30             str[p2--] = str[p1--];
31         }
32     }
33     for (int i = 0; i < second_len; i++)             //输出替换后的新数组
34     {
35         cout << str[i] << " ";
36     }
37     cout << endl;
38 }
39 int main()
40 {
41     char string[Max_Len] = "welcome to my world!";
42     Space_Change(string, Max_Len);
43     system("pause");
44     return 0;
45 }