字符串的空格替换

题目：请实现一个函数，把字符串中的每个空格替换成"%20"，例如输入："We are happy.",则输出："We%20are%20happy."。

这道题的思路很简单，就是在字符串中找到空格。然后将空格转换为：'%'，'2'和'0'这个三个字符。当然，直接替换会由于这三个字符所占的空间大于空格所占的空间而使后面的内存被覆盖。所以我们替换完成后的字符串长度与原字符串的长度必然是不一致的。此处我们就有两种做法：

1.我们在原字符串上进行替换；

2.我们新建一个字符数组用来存放替换后的字符串。

我们来试试这两种做法：

1.直接在原字符串上进行替换：

//题目：请实现一个函数，把字符串中的每个空格替换成"%20"，例如输入："We are happy.",
//则输出："We%20are%20happy."。

//如果是在原数组上进行替换：
//一个一个寻找，找到空格在替换为"%20"：
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
int my_strlen(char *a)    //这次是为了解决确定的字符串，所以这个模拟函数未考虑特殊情况
{
	int len = 0;
	assert(a != NULL);
	while (*a++)
	{
		len++;
	}
	return len;
}
void exch_space(char *a,int b)
{
	assert(a != NULL);
	int i = 0;
	while (*(a+i))  //循环：遍历一遍字符串，碰到了空格则进行特殊处理
	{
		int c = b;  //此时c就是原字符串的长度
		if (' ' == *(a+i))  //判断是否出现了空格，是则进行处理
		{
			while (c-i)   //将空格后面的字符移位，防止它们被替换后的内容覆盖
			{
				*(a+c+2) = *(a+c);
				c--;
			}
			*(a + i) = '%';     //空格替换，并且记录下此时字符串的长度
			*(a + i + 1) = '2';
			*(a + i + 2) = '0';
			b = b + 2;
		}
		i++;
	}
	return;
}
int main()
{
	char a[30] = "We are happy."; //原字符串
	int len = my_strlen(a); //得到字符串的实际长度
	exch_space(a,len);
	printf("%s\n", a);  //打印结果
	return 0;
}

我们来运行一下程序，看看结果怎么样？

结果正确。

2.新建一个字符数组用来存放替换后的字符串：

//这个代码和上面的代码大同小异，不做过多注释

//题目：请实现一个函数，把字符串中的每个空格替换成"%20"，例如输入："We are happy.",
//则输出："We%20are%20happy."。

//如果是新建一个数组来存放新内容的话：
//一个一个找到" "并且替换为"%20"。
#include <stdio.h>
#include <assert.h>
char *strex_space(char *dest,char *b, char c)
{
	assert(dest != NULL);
	char *tmp = b;
	while (*dest)   //当目标字符串结束，则循环结束。
	{
		if (c == *dest)   //找到空格，进行替换。
		{
			*b++ = '%';
			*b++ = '2';
			*b++ = '0';
			dest++;
			continue;       //空格替换完成后直接开始下一次循环。
		}
		*b++ = *dest++;     //不需要转换则直接拷贝。
	}
	return tmp;
}
int main()
{
	char a[] = "We are happy.";
	char b[25] = { 0 };        //创建一个拥有足够空间的char型数组。
	char c = ' ';
	char *str = strex_space(a,b,c);  //调用空格替换函数。
	printf("%s\n", a);
	printf("%s\n", b);
	printf("%s\n", str);
	return 0;
}

运行一下：

结果正确。

以上两个代码用的都是同一个思路：我们遍历整个字符串，遇到空格则开始处理。将空格后面的字符统统向后挪动，然后在进行空格替换。替换完成后继续向后遍历，重复上面的步骤，直到字符串结束。但是这种替换思路每次遇到空格都要将后面所有的字符挪动，实际的工作量非常大，我们有没有一些更简单的思路来进行空替换呢？

我们先开仔细分析一下这种遍历替换的复杂的替换方式：

仔细观察一下上面的示意图，我们发现如果将这个字符串从后面开始向前进行遍历替换就可以直接替换。这样就不必考虑后面的字符串被前面的内容覆盖这个问题了。但是我们从后面开始放的话，就必须要知道替换后字符串最后一个元素的位置。很简单，我们先遍历一遍原字符串，求出它的里面有几个空格字符。每个空格字符替换后都会使原字符串扩大两个字节长度，我们在知道原字符串的长度就可以求出替换完成字符串的长度了。我们就得到了起始存放位置，从它开始将原字符串以由后向前的顺序存放，遇到空格字符，则依次存入字符'0','2'和'%'。

我们画图来表示这一思路：

我们根据这一思路写出代码：

//上面的方法我们需要每次遇到空格都要将后面的元素向后挪两位，这样效率十分低。
//我们来看看另一种思路：                        fadsf dsf afa\0
//遍历一次，得到空格个数，求出替换后的空间大小：fadsf%20dsf%20afa\0
//从后面向前面覆盖，这样就不用进行多余的操作了。

//下面是我自己根据这一思想实现的代码：

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

void strex_space(char *str, int c)
{
	assert(str != NULL);
	int strlen = 1; //要替换数组的实际长度，考虑到即使第一个元素就是'\0',它可以算长度为1。
	int newstrlen = 0;//替换后数组的实际长度。
	int count = 0;  //空格的个数，count是一个计数器。
	char *tmp = str;  //记下数组的地址。
	
	while (*str)  //由这个循环求出空格的个数。
	{                //注意：这个循环会导致str指针指向的变化，后面要将str指针还原。
		if (' ' == *str)
		{
			count++;
		}
		str++;
		strlen++;
	}

	str = tmp;     //str指针还原，求出替换后数组的实际长度。
	newstrlen = strlen + count * 2;
	
	if (newstrlen > c)   //如果替换后数组的实际长度已经大于数组容量，则无法完成目标。
	{
		return;
	}
	while (newstrlen > strlen)   //完成替换的循环，循环结束，替换完成。
	{
		if (' ' == *(str+strlen-1))  //找到空格时，进行空格替换。
		{
			*(str+newstrlen-1) = '0';
			*(str+newstrlen-1-1) = '2';
			*(str+newstrlen-1-2) = '%';
			newstrlen -= 3;
			strlen-=1;
			continue;
		}
		*(str+newstrlen-1) = *(str+strlen-1);  //不需要替换的元素直接覆盖。
		newstrlen--;
		strlen--;
	}
	return;
}

int main()
{
	char a[30] = "We are happy.";
	int size = sizeof(a) / sizeof(a[0]);        //得到a数组的长度（最大容量）。
	strex_space(a,size);  //调用空格替换函数。
	printf("%s\n", a);
	return 0;
}

运行一下：

结果正确。

参考文献：《剑指offer》