学步园

Task:

编写一个程序，将某文件名，如F:/testsue/input.txt，更改为F:/testuse/input_cutted.txt

这是我在编写一个分词程序时候遇到的问题。初看起来，该问题非常之简单，首先想到的是使用string.h中的几个库函数来实现，可能你会编码如下(不使用临时数组)：

/*START：更改文件名，添加_cutted标志*/<br /> void*<br /> ChangeFileName(char path[])<br /> {<br /> char tmp[]="_cutted";<br /> register char *p,*q;<br /> int len;</p> <p> p=path+strlen(path)-1; //指向path的最尾字符<br /> len=strlen(tmp); //要添加的后缀的长度<br /> q=p+len; //q指向新文件名的末尾<br /> *(q+1)='/0';</p> <p> while(*(p+1)!='.') //腾出添加后缀所需要的空间<br /> *q--=*p--;<br /> p=tmp+len-1;<br /> while(p+1!=tmp) //添加_cutted<br /> *q--=*p--;<br /> }<br /> /*END*/<br />

先看下strlen的实现（参考自P. J. Plauger 《C标准库》）：

/*START：求字符串的长度*/<br /> size_t<br /> strlen(const char * s)<br /> {<br /> const char *sc;</p> <p> for(sc=s;*sc!='/0';++sc)<br /> ;</p> <p> return (sc-s);<br /> }<br /> /*END*/<br />

可以看出strlen是通过对字符串进行遍历来计算长度的；在以上算法中，strlen使用了两次，因此程序分别对tmp数组和原path数组进行了一次遍历；此后程序又使用while_1从后向前对path进行遍历并在此过程中进行赋值操作；在while_1结束后，程序继续使用while_2同时对path和tmp进行遍历。在这两次while遍历中，对tmp的遍历是完全遍历的而对path的遍历至少进行了一半；连同之前两次strlen所进行的遍历，程序一共对path进行了1.5次遍历，对tmp进行了2遍历；

如果该字符串有很长，虽然时间复杂度仍然是O(n)，但其效率不是可被接受的。如果可以在前两次strlen的同时做点什么，使后来对path和tmp进行的while遍历不发生或少发生，那么效率无疑将得到大步提升。请看以下代码：

/*START：更改文件名，添加_cutted标志*/<br /> char*<br /> ChangeFileName (char path[])<br /> {<br /> char tmp[]="_cutted";<br /> register char *p,*q;<br /> register char *std;</p> <p> for(std=path;*std!='.';++std) //std指向原路径中的.号<br /> ;<br /> p=std;<br /> while(*p++!='/0') //p指向path末尾后一位<br /> ;<br /> q=p+7;</p> <p> while(p>=std) //复制后缀名<br /> *q--=*p--;<br /> for(p=tmp;std<=q;std++,p++) //复制_cutted<br /> *std=*p;</p> <p> return path;<br /> }<br /> /*END*/<br />

在该代码中，手工实现了strlen等的功能；总的看来，程序对path只进行了1次遍历，对tmp只进行了1次遍历；比较第一个算法，该算法的效率无疑更好。

库函数的存在是为了封装某些操作使程序员不必拘泥于细节的实现。但在使用库函数时，应适当了解库函数的实现，正确的使用库函数，否则，轻则影响程序的效率，重则将导致程序崩溃。

/*START：copy s2 to s1*/<br /> char*<br /> strcpy(char *s1,const char *s2)<br /> {<br /> const char *su;<br /> char *sc;</p> <p> for(sc=s1,su=s2;(*sc++=*su++)!='/0';)<br /> ;</p> <p> return s1;<br /> }<br /> /*END*/<br />

可以看出，在strcpy中并没有NULL检查，并没有数组空间检查；因此如果错误的使用，将造成难以预料的结果。

在string.h中，很多库函数都通过遍历字符串来实现。如上面的strlen，strcpy。又如strcat

/*START：copy s2 to the end of s1*/<br /> char*<br /> strcat(char *s1,const char *s2)<br /> {<br /> char *s;</p> <p> for(s=s1;*s!='/0';++s)<br /> ;<br /> for(;(*s=*s2)!='/0';++s,++s2) //PERFECT<br /> ;<br /> }<br /> /*END*/<br />

因此，当我们使用string.h中的库函数时，我们应该考虑下，是否有使用的必要，使用库函数是否会导致多次遍历同一字符串从而导致效率的低下？是否有更好的办法来实现这些目的？

有些库函数只有知道了其实现，才能更好的理解其用法。例如下面的memset

/*START；memset*/<br /> void*<br /> memset(void *des,int ch,size_t n)<br /> {<br /> unsigned char *s=des;<br /> const unsigned char c=ch; //设置为unsigned，是因为可能会传来>127的数字</p> <p> while(n-->0)<br /> *s++=c;</p> <p> return des;<br /> }<br /> /*END*/<br />   

memset内部使用1个字节的char，因此在使用memset时，应根据其类型来选择不同的调用方式

例如，int buff[10];调用方式是memset(buff,0,sizeof(buff)); 而不能是memset(buff,’0’,10)；

又如：char buff[10];调用方式是memset(buff,'0',sizeof(buff)); 而不能是memset(buff,0,10)；

特别要注意的是，若声明int buff[]，则memset的使用目的只会是设置该数组的所有单元均为0，不可能将buff中所有单元设为其他数……（因为在memset中，使用了8位的char，因此，若想设置buff的每一个单元为1，则实际结果是，buff[]每一个单元的int的4个字节，每个字节均为1，因此该int数据实际上是1 00000001 00000001 00000001(32位机)，即是16843009）

另要注意，对char的使用一定要传字符，如’1’是将char[]的每个单元初始化为1而1，则无法；

又如，strncat，我的实现为：

/*START：strncat*/<br /> char*<br /> strncat(char *s1,const char *s2,size_t n)<br /> {<br /> char *sc;</p> <p> for(sc=s1;*sc!='/0';++sc)<br /> ;<br /> while(0<n&&(*sc++=*s2++)!='/0') //MARK<br /> ;<br /> *sc='/0';</p> <p> return s1;<br /> }<br /> /*END*/<br />  

我觉得MARK处用得相当好，相当有创意，原来都不知道。就像上面的strcat中的for(;(*s=*s2)!='/0';++s,++s2)并不会影响性能，且括起来相当简洁，我认为相当不错。（用优先级规则怎么分析？）

如下面的strncpy：

/*START：strncpy*/<br /> char*<br /> strncpy(char *des,const char *src,size_t n)<br /> {<br /> char *s;</p> <p> while(*src!='/0'&&0<n--) //MARK<br /> *s++=*src++;<br /> while(0<n--)<br /> *s++='/0';<br /> return des;<br /> }<br /> /*END*/<br />  

strncpy将char *src中之多n个元素复制至des中，如果src中元素个数少于n，则des中相应的部分应全填充为’/0’

两点注意：

首先，如果这样写代码，那么在MARK处必须写成while(*src!='/0'&&0<n--)而不能是while(0<n--&&*src!=’/0’)。也就是说，while中的判断顺序不能反。形如while(*src!='/0'&&0<n--)时候，当src中字符数少于n时，while会在n>0之前遇到’/0’，此时进行while判断时，*src!=’/0’必为假，因此while会直接break而不会进行0<n—的判断，也就是说，n不会变化。这样就能保证在第二个while中能复制足够的’/0’；而如果使用while(0<n--&&*src!=’/0’)时，当判断出*src==’/0’时，n已经--，这样在while break时，n值比实际的值小1。在某些实现中，这可能造成相当严重的后果；

第二，在使用strncpy时，程序员同样应该保证des中有足够多的空间存放来自src的n个字符。即使src中实际上并没有n个字符要复制。当src中实际上没有n个字符要复制时，des同样会被“复制进”n个字符，同样会覆盖des后的其他数据。虽然如果仅仅复制src中有的数据不会出现这样的情况。

strcspn：用于返回char *s1中从起始位置起，不包含char *s2中任意字符的字符段的最后一个字符的位置（索引）；即是，s1