题目:实现一个函数,要求吧字符串中的所有空格替换成“%20”。例如“hello world " ——> ”hello%20world%20"
实际背景:在网络编程中,如果URL参数中含有特殊的字符,如空格、'#'等,导致服务器端无法识别时,就把这些特殊的字符转换成可以识别的字符。规则:%加上十六进制的ascii码,例如‘#’的ascii码是0x23(16进制),就替换成%23,看下图地址栏中,输入“hello#hao"
分析:
注意:在c语言中存字符串最后一位是认为”\0“的,例如a[] = "12",那么a的长度为3,a[0]='1',a[1]='2',a[2]='\0',‘\0’是空字符,其ascii码为0如下图。相比之下:b[] = {'1', '2'}长度则为2.
思路一:可以再造一个数组,遇到空格就替换成”%20“这样就造成了空间的浪费,可以实现但不是最佳
思路二:
- 从前往后:在原基础上进行替换(当然前提是空间足够),如果从前往后遇到空格就替换,必然会对原来的字符造成覆盖,不可以实现。
- 从后往前:如果倒着遇到空格就往后移动同时替换,那么如果全部是空格,那势必造成时间复杂度为O(n2)的开销。可以实现,但不是最佳
思路三:因为把空格替换为”%20“,每次替换多2个字符,因此可以统计出字符串中空格的总个数,然后新数组大小为 “原数组大小 + 2*空格数 ”。从后往前处理:遇到非空格,直接搬到后面,遇到空格替换为”%20“. 直到待插入位置指针和原数组为指针重合位置。图示如下:
参考代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXLEN 100 void ReplaceBlack(char *p) { if (p != NULL) { int i, end, pos ,size_black = 0; size_t lenold = strlen(p), lennew; for (i=0; i != lenold; i++) { if (p[i] == ' ') size_black++; } lennew = lenold + 2 * size_black; if(lennew > MAXLEN) return; pos = lennew-1; end = lenold-1; while(pos != end) { if (p[end] != ' ') p[pos--] = p[end--]; else { p[pos--] = '0'; p[pos--] = '2'; p[pos--] = '%'; end--; } }//while } } int main() { char *a = (char*)malloc(sizeof(char) * MAXLEN); if(NULL != a) { strcpy(a, "hell world "); ReplaceBlack(a); printf("%s\n", a); free(a); } return 0; }
运行结果:
这样实现的时间复杂度为O(n),又不浪费多余的空间。
举一反三:
有两个排好序(升序)的两个数组A1,A2,如何高效的把A2的元素复制到A1的后边(假设A1后边有足够的空间)
思路相同
- 先看看两个数组总共的空间大小,知道了需要数组A1的总共的元素个数
- A1和A2同时从后往前处理,比较大的放在A1新的最后位置
- 重复处理,直到A2中没有元素了,这是复制完了
参考代码
#include <stdio.h> #include <string.h> int ReplaceBlack(int *a, int *b, int lena, int lenb, int length) { int i, token = 0; int total = lena + lenb; if (a != NULL && b != NULL && (total <= length)) { lena--; lenb--; i = total - 1; while(lena != -1 && lenb != -1) { if(a[lena] >= b[lenb]) a[i--] = a[lena--]; else a[i--] = b[lenb--]; } while(lenb != -1) a[i--] = b[lenb--]; token = 1; } return token; } int main() { int length = 100; int i, a[100] = {1, 2, 3, 5}, b[] = {0, 4, 7}; int lena = 4, lenb = 3; if(0 != ReplaceBlack(a, b, lena , lenb, length)) for(i = 0; i< lena+lenb; i++) printf("%d\n", a[i]); return 0; }
注意几个技术细节问题
1.strlen与sizeof的区别与联系
- 两者返回类型都是size_t
- strlen是字符串函数,sizeof是运算符
- sizeof可以把类型当做参数,例如sizeof(int),strlen()对象只能是指向字符串类型的指针
- 数组做sizeof参数不退化,传递给strlen()就退化为指针了。例如char a[] = "12" sizeof(a) = 3*1 = 3,此时a指数组; strlen(a) = 3,此时a指指针
数组作为参数传递给函数时,传递的是指针不是数组。例如fuc(char *a),在函数中计算sizeof(a) 是指针的大小4(32位系统)或8(64位系 统)
程序演示
#include <stdio.h> #include <string.h> void fuc1(char *p) { printf("fuction:%s\n", p); printf("fuction:sizeof:%lu,strlen:%lu\n", sizeof(p), strlen(p)); } int main() { char d[] = "hello"; printf("main:%s\n", d); printf("main:sizeof:%lu,strlen:%lu\n", sizeof(d), strlen(d)); fuc1(d); return 0; }
结果
- sizeof在编译时就决定了,而strlen()函数在计算时才得出
2. 动态数组和静态数组的区别
声明
动态数组如:char *a = (char *)malloc(sizeof(char) * 100); 由程序员自己分配空间
静态数组如:char a[100];由操作系统非配空间
初始化
在声明中静态数组是可以的,如:char a[100]=”hello",但是动态的不可以。
主要涉及到molloc()\free()的理解和堆栈,下边地址介绍的相当详细:
浅谈C中的malloc和free:http://www.bccn.net/Article/kfyy/cyy/jszl/200608/4238.html
堆栈(百度百科):http://baike.baidu.com/view/93201.htm
本文转自jihite博客园博客,原文链接:http://www.cnblogs.com/kaituorensheng/archive/2013/04/21/3034653.html,如需转载请自行联系原作者