經典面試題之手撕字元串函數
- 2019 年 10 月 6 日
- 筆記
經典面試題之手撕字元串函數
最近看到一些面試C/C++的一個問題：手撕字元串函數，包括：
- strcpy
- memcpy
- memmove
- strcat
- strcmp
- strstr
下面一起來手撕。
1.strcpy
功能：把 src 所指向的字元串複製到 dest。
看到這個需求你一想，這還不簡單，就寫出了下面程式碼，可惜啊，你掛了！
char *strcpy(char *dest, const char *src) { if (!dest || !src) return NULL; char *d = dest; while (*src != ' ') { *d++ = *src++; } *d = ' '; return dest; }
考慮一個場景，現在測試程式調用如下：
char src[66] = "lightcity"; strcpy(src + 1, src, strlen(src) + 1);
你跑一下你的程式碼發現運行結果是：lllllllll。失敗吧！什麼原因呢？
這裡有個重要的點：記憶體重疊！
在上述程式碼中：
src+1指向的是i這個位置src指向的是l這個位置
當指針dst賦值為l的時候，前面的i已經被改為l，依次類推，就輸出了lllllllll。
我們分析一下記憶體重疊的位置：
記憶體重疊：當 src<dst<src+n n為字元串的長度，不包含 。
實現如下：
char *strcpy1(char *dest, const char *src) { if (!dest || !src) return NULL; char *d = dest; int size = strlen(src) + 1; if (d > src && d < src + size) { d = d + size - 1; src = src + size - 1; while (size--) { *d-- = *src--; } } else { while (size--) { *d++ = *src++; } } }
2.memcpy與memmove
功能：從存儲區 src 複製 n 個字元到存儲區 dest。
如果寫出的程式碼如下：同strcpy一樣你也失敗了！
void *memcpy(void *dest, const void *src, size_t n) { if (!dest || !src) return NULL; char *d = (char *) dest; const char *s = (const char *) src; size_t i = 0; for (i = 0; i < n; i++) { *d++ = *s++; } return dest; }
優化也是消除記憶體重疊！
我們看一下man手冊中的memcpy函數：
The memcpy() function copies n bytes from memory area src to memory area dest. The memory areas must not overlap. Use memmove(3) if the memory areas do overlap。
翻譯一下就是，memcpy函數從存儲區 src 複製 n 個字元到存儲區 dest。存儲區不能重疊！
如果重疊了，需要使用memmove。
實現如下：
void *memcpy1(void *dest, const void *src, size_t n) { if (!dest || !src) return NULL; char *d = (char *) dest; const char *s = (const char *) src; if (d > s && d < s + n) { d = d + n - 1; s = s + n - 1; while (n--) *d-- = *s--; } else { while (n--) *d++ = *s++; } return dest; }
上述也是memmove函數實現！
3. strcmp
比較兩個字元串，正數就是srt1大，負數就是srt2大，反之相等！
int strcmp(const char* str1,const char* str2) { while(*str1==*str2&&*str1!=' ') { str1++; str2++; } return *str1-*str2; }
4.strcat
將src字元串追加到dest中。
char* strcat(char* dest,const char* src) { char* d = dest; while(*d!=' ') ++d; while(*src!=' ') { *d++=*src++; } *d=' '; return dest; }
5.strstr
在str1中查找str2，並返回str2在str1中的起始位置後的所有字元串。
char* strstr(char *str1, char *str2) { if (str1 == NULL || str2 == NULL) return NULL; char *s = str1; if (*str2 == ' ') { return NULL;//若str2為空，則直接返回空 } while (*s != ' ') {//若不為空，則進行查詢 char *s1 = s; char *s2 = str2; while (*s1 != ' ' && *s2 != ' ' && *s1 == *s2) { s1++, s2++; } if (*s2 == ' ') { return s;//若s2先結束 } if (*s2 != ' ' && *s1 == ' ') { return NULL;//若s1先結束而s2還沒結束，則返回空 } s++; } return NULL; }
6.總結
手撕完畢！歡迎訂閱公眾號，轉發與收藏！
