实现一些字符串操作标准库函数与解决一些字符串笔试问题

1、实现字符串操作标准库函数

1、strcpy 的实现

  1. char *strcpy(char *dest, const char *src)
  2. {
  3.     assert((src != NULL) && (dest != NULL));
  4.     size_t i;
  5.     for (i = 0; src[i] != '\0'; i++)
  6.         dest[i] = src[i];
  7.     dest[i] = '\0';
  8.     return dest;
  9. }

2、strncpy 的实现

  1. char *strncpy(char *dest, const char *src, size_t n)
  2. {
  3.     assert((src != NULL) && (dest != NULL));
  4.     size_t i;
  5.     for (i = 0; i < n && src[i] != '\0'; i++)
  6.         dest[i] = src[i];
  7.     for (; i < n; i++)
  8.         dest[i] = '\0';
  9.     return dest;
  10. }

3、memmove 的实现

  1. /* 借助于一个临时缓冲区temp ,即使src 和dest 所指的内存区间有重叠也能正确拷贝。*/
  2. void *memmove(void *dest, const void *src, size_t n)
  3. {
  4.     assert((src != NULL) && (dest != NULL));
  5.     char* temp = (char*)malloc(sizeof(char)*n);
  6.     size_t i;
  7.     char *d = (char*)dest;
  8.     const char *s = (const char*)src;
  10.     for (i = 0; i < n; i++)
  11.         temp[i] = s[i];
  12.     for (i = 0; i < n; i++)
  13.         d[i] = temp[i];
  15.     free(temp);
  17.     return dest;
  18. }

不用临时空间的memmove实现：

  1. //src可以不保留
  2. void *memmove(void *dst, const void *src, size_t count)
  3. {
  4.     byte *pbTo = (byte *)dst;
  5.     byte *pbFrom = (byte *)src;
  6.     assert(dst != NULL && src != NULL);//不能存在空指针
  7.     if (dst <= src || pbTo >= pbFrom + count)//
  8.     {
  9.         while (count-- > 0)
  10.         {
  11.             *pbTo++ = *pbFrom++; //按递增拷贝
  12.         }
  13.     }
  14.     else  //
  15.     {
  16.         pbTo = pbTo + count - 1; //overlap的情况，从高位地址向低位拷贝
  17.         pbFrom = pbFrom + count - 1;
  18.         while (count-- > 0)
  19.         {
  20.             *pbTo-- = *pbFrom--; //按递减拷贝
  21.         }
  22.     }
  23.     return dst;
  24. }

4、memcpy 的实现

  1. /* 在32位的x86平台上,每次拷贝1个字节需要一条指令,每次拷贝4个字节也只需要一条指
  2.  * 令,memcpy函数的实现尽可能4个字节4个字节地拷贝 */
  3. void *memcpy(void *dest, const void *src, size_t n)
  4. {
  5.     assert((src != NULL) && (dest != NULL));
  6.     char *d = dest;
  7.     const char *s = src;
  8.     int *di;
  9.     const int *si;
  10.     int r = n % 4;
  11.     while (r--)
  12.         *d++ = *s++;
  13.     di = (int *)d;
  14.     si = (const int *)s;
  15.     n /= 4;
  16.     while (n--)
  17.         *di++ = *si++;
  18.     return dest;
  19. }

5、strlen 的实现

  1. size_t strlen(const char *p)
  2. {
  3.     assert(p !=  NULL);
  4.     size_t size = 0;
  5.     while (*p++ != '\0')
  6.         ++size;
  7.     return size;
  8. }

6、strncat 的实现

  1. char *strncat(char *dest, const char *src, size_t n)
  2. {
  3.     size_t dest_len = strlen(dest);
  4.     size_t i;
  6.     for (i = 0 ; i < n && src[i] != '\0' ; i++)
  7.         dest[dest_len + i] = src[i];
  8.     dest[dest_len + i] = '\0';
  10.     return dest;
  11. }

7、memset 的实现

  1. void *memset(void *buffer, int c, int count)
  2. {
  3.     char *buffer_p = (char *)buffer;
  4.     assert(buffer != NULL);
  5.     while(count-- > 0)
  6.         *buffer_p++ = (char)c;
  7.     return buffer;
  8. }

2、解决字符串问题

1、将单词之间出现一个或多个连续的空白字符都压缩为1个

  1. //编一个函数，输入一个字符串，要求做一个新字符串，把其中所有的一个或多个连续的空白字符都压缩为一个空格。这里所说的空白包括空格、'\t'、'\n'、'\r'。
  2. char *shrink_space(char *dest, const char *src, size_t n)
  3. {
  4.     assert((src != NULL) && (dest != NULL));
  5.     size_t i, j;
  7.     dest[0] = src[0];
  9.     for (i = 1, j = 1; src[i] != '\0'; i++, j++)
  10.     {
  11.         if (src[i] == '\t' || src[i] == '\n'
  12.                 || src[i] == '\r' || src[i] == ' ')
  14.             if (src[i - 1] != '\t' && src[i - 1] != '\n'
  15.                     && src[i - 1] != '\r' && src[i - 1] != ' ')
  17.                 dest[j] = ' ';
  18.             else
  19.                 j--;
  20.         else
  21.             dest[j] = src[i];
  22.     }
  23.     dest[j] = '\0';
  25.     return dest;
  26. }

2、解析URL 中的路径和查询字符串。? 号后面是查询字符串，由 “key=value”形式的键值对组成，以&隔开

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<stdlib.h>
  5. #define N 10
  6. typedef struct
  7. {
  8.     char *tokens[N];
  9.     int count;
  10. } unit_t;
  12. void find_url_token(char str[], const char tok[], unit_t *ptr)
  13. {
  14.     int i;
  15.     char *token = NULL;
  16.     char *saveptr = NULL;
  18.     ptr->count = 0;
  19.     const char *needle = "://";
  21.     if (strstr(str, needle))
  22.     {
  23.         for (i = 0; ; str = NULL, i++)
  24.         {
  25.             token = strtok_r(str, tok, &saveptr);
  26.             if (token == NULL)
  27.                 break;
  28.             else
  29.             {
  30.                 ptr->tokens[i] = token;
  31.                 ptr->count++;
  32.             }
  33.         }
  34.     }
  35. }
  37. int main(void)
  38. {
  39.     /* 不能定义为char *url = "..."; 因为此时是定义一个指向字符串字面值(位于.rodata段)的指针,而
  40.        调用strtok_r函数会修改这个字符串,运行时会产生段错误 */
  41.     char url[] = "http://www.google.cn/search?complete=1&hl=zh-CN&ie=GB2312&q=linux&meta=";
  42.     /* 给url初始化用的这个字符串并没有分配在.rodata段,而是直接写在指令里了,
  43.      * 运行程序时通过movl 指令把字符串写到栈上,这就是url的存储空间*/
  44.     unit_t *ptr = malloc(sizeof(unit_t));
  45.     find_url_token(url, "?&", ptr);
  46.     int i;
  47.     for (i = 0; i < ptr->count; i++)
  48.         printf("%s\n", ptr->tokens[i]);
  49.     free(ptr);
  50.     return 0;
  51. }

3、去除\r\n，去除左右空白字符

  1. void str_trim_crlf(char *str)
  2. {
  3.     char *p = &str[strlen(str) - 1];
  4.     while (*p == '\r' || *p == '\n')
  5.         *p-- = '\0';
  6. }
  7. void AllTrim( char *str )
  8. {
  9.     char *head, *tail;
  11.     if ( str == NULL )
  12.         return;
  14.     for( head = str; *head == ' ' || *head == '\t'; head ++ );
  16.     for( tail = str + strlen(str) - 1; (*tail == ' ' || *tail == '\t' ) && tail >= head; tail -- );
  18.     while( head <= tail )
  19.         *str ++ = *head ++;
  21.     *str = 0;
  22. }

4、判断字符串是否为回文

  1. // 判断字符串是否为回文
  2. bool isSysmmetry(const char *src)
  3. {
  4.     assert(src != NULL);
  5.     int len = strlen(src);
  6.     assert(len != 0);
  7.     const char *tmp = src + len - 1;
  9.     int i;
  10.     for (i = 0; i < len / 2; i++)
  11.     {
  12.         if (*src++ != *tmp--)
  13.             break;
  14.     }
  16.     if (i == len / 2)
  17.         return true;
  18.     else
  19.         return false;
  21. }

5、google笔试：编码实现求给定字符串（全为小写英文字母）的最小后继，如 “abc” 的最小后继为“abd”, “dhz” 的最小后继为“di”

  1. int MinNextStr(const char *src, char *&minnext)
  2. {
  3.     int srclen = strlen(src);
  4.     minnext = (char *)malloc((srclen + 1) * sizeof(char));
  5.     if (minnext == NULL)
  6.         return -1;
  7.     strcpy(minnext, src);
  9.     int i = srclen - 1;
  10.     while (i >= 0)
  11.     {
  12.         minnext[i]++;
  13.         if (minnext[i] <= 'z')
  14.             break;
  15.         i--;
  16.     }
  18.     if (i < 0)
  19.         return 0;
  20.     else
  21.     {
  22.         minnext[++i] = '\0';
  23.         return 1;
  25.     }
  26. }

如果把给定字符串全为小写英文字母改为大小写英文字母，则只要把 第 13 行改为：if (minnext[i] <= 'z' && minnext[i] >= 'a' || minnext[i] <= 'Z');

6、中兴：编码实现字符串右移n位，如“diopheg” 右移2位为“egdioph”。

  1. bool RightMoveStr(char *src, int n)
  2. {
  3.     int len = strlen(src);
  4.     int mov = n % len;
  5.     char *rstr = (char *)malloc((mov + 1) * sizeof(char));
  6.     if (rstr == NULL)
  7.         return false;
  9.     int i = 0;
  10.     while (i < mov)
  11.     {
  12.         rstr[i] = src[len - mov + i];
  13.         i++;
  14.     }
  15.     rstr[i] = '\0';
  17.     i = len - mov - 1;
  18.     while (i >= 0)
  19.     {
  20.         src[i + mov] = src[i];
  21.         i--;
  22.     }
  24.     i = 0;
  25.     while (i < mov)
  26.     {
  27.         src[i] = rstr[i];
  28.         i++;
  29.     }
  31.     free(rstr);
  32.     return true;
  33. }
  35. bool RightMove(char *src, char *&ssrc, int n)
  36. {
  37.     int len = strlen(src);
  38.     ssrc = (char *)malloc(sizeof(char) * (len + 1));
  39.     if (ssrc == NULL)
  40.         return false;
  42.     n = n % len;
  43.     char *tmp = src + len - n;
  45.     strcpy(ssrc, tmp);
  46.     strncat(ssrc, src, len - n);
  48.     return true;
  50. }

更巧妙的方法：

  1. void reverse(char* str, int left, int right)
  2. {
  3.     char tmp;
  4.     while (left < right)
  5.     {
  6.         tmp = str[left];
  7.         str[left++] = str[right];
  8.         str[right--] = tmp;
  10.     }
  11. }
  13. void rightmove(char* str, int k)
  14. {
  15.     n = strlen(str);
  16.     k = k % n;
  17.     reverse(str, 0, n-k-1);
  18.     reverse(str, n-k, n-1);
  19.     reverse(str, 0, n-1);
  20. }

7、新邮通：字符串反转：给定字符串“we;tonight;you;”，编码实现输出”ew;thginot;uoy;“

  1. void ReverseStr(char *src)
  2. {
  3.     int len = strlen(src);
  4.     int i = 0;
  5.     int first = 0;
  6.     int end = 0;
  7.     while (i < len)
  8.     {
  9.         if (src[i] == ';')
  10.         {
  11.             end = i - 1;
  12.             while (first < end)
  13.             {
  14.                 char tmp = src[first];
  15.                 src[first] = src[end];
  16.                 src[end] = tmp;
  17.                 first++;
  18.                 end--;
  19.             }
  20.             first = i + 1;
  22.         }
  23.         i++;
  24.     }
  25. }

如果给定字符串末尾没有’;’，只需要修改 9，10，11 行

  1. if (src[i] == ';' || i == len - 1)
  2. {
  3.     if (src[i] == ';')
  4.         end = i - 1;
  5.     else
  6.         end = i;
  7.     while...
  8. }

8、不使用局部变量实现strlen、两数交换

  1. #define swap(a,b) \
  2. { assert(sizeof(a)==sizeof(b)); char tempBuf[sizeof(a)]; memcpy(tempBuf,&a,sizeof(a)); memcpy(&a,&b,sizeof(b)); memcpy(&b,tempBuf,sizeof(b)); }
  4. #define swap(a, b) \
  5.     do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)
  6. // typeof 是gcc支持，iso c支持__typeof__
  9. int mstrlen(char *p)
  10. {
  11.     return ToEnd(p)-p;
  12. }
  13. char * ToEnd(char * p)
  14. {
  15.     while(*p != '\0')
  16.         p++;
  17.     return p;
  18. }