数据结构之字符串函数

常用的字符串函数看似非常简单,但真正在实践过程中,会出现很多坑。关于这些函数的实现,网上代码一大堆错误,能全部作对的少之又少,现在终于理解了为什么面试官最喜欢问这几个函数了。

strcpy

strcpy函数要注意目的地址和原地址可能是重叠的,要分别做处理。下面是源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
char *my_strcpy(char *dst, const char *src) {
assert(dst != NULL);
assert(src != NULL);
unsigned int len = strlen(src)+1;
char *ret = dst;
if (dst <= src || (dst >= src + len)) {
while (len--) {
*dst++ = *src++;
}
} else {
dst = dst+len-1;
src = src+len-1;
while (len--) {
*dst-- = *src--;
}
}
return ret;
}


strlen

strlen实现比较简单,没有什么好说的,下面是标准库的实现,非常简洁。

1
2
3
4
5
unsigned int my_strlen(const char *str) {
const char *eos = str;
while(*eos++);
return (eos - str - 1);
}


strcat

对于此实现,网上有很多标准库的实现,但是对于str[10]=”abc”,strcat(str+1, str)这种情况下,网上的代码基本上都不会输出正确的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
char *my_strcat(char *dst, const char *src) {
assert(dst != NULL);
assert(src != NULL);
char *pstr = dst;
while (*pstr) pstr++;
// strcat(str+1, str)
unsigned int len = strlen(src);
while (len--) *pstr++ = *src++;
*pstr = '\0';
return dst;
}


strcmp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int my_strcmp(const char *src, const char *dst) {
assert(dst != NULL);
assert(src != NULL);
int ret = 0;
while (!(ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst) {
src++;
dst++;
}
if (ret < 0)
ret = -1;
else if(ret > 0)
ret = 1;
return ret;
}

strncmp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int my_strncmp(const char *src, const char *dst, unsigned int n) {
assert(dst != NULL);
assert(src != NULL);
int ret = 0;
while (n-- && !(ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst) {
src++;
dst++;
}
if (ret < 0)
ret = -1;
else if(ret > 0)
ret = 1;
return ret;
}

string类

第一种实现方式:拷贝构造和拷贝赋值的时候需要重新开辟空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#ifndef STRING_H
#define STRING_H
#include <iostream>
#include <string.h>
using namespace std;
class String {
public:
String(const char *cstr = 0);
String(const String &str);
String& operator = (const String &str);
~String();
char *c_str() const { return m_data; }
String operator + (const String &str);
String& operator += (const String &str);
bool operator == (const String &str) const;
friend ostream& operator << (ostream &, const String &);
friend istream& operator >> (istream &, String &);
private:
char *m_data;
};
inline
String::String(const char *cstr) {
if (cstr) {
m_data = new char[strlen(cstr) + 1];
strcpy(m_data, cstr);
} else {
m_data = new char[1];
*m_data = '\0';
}
}
inline
String::~String() {
delete[] m_data;
}
inline
String::String(const String &str) {
m_data = new char[strlen(str.m_data) + 1];
strcpy(m_data, str.m_data);
}
inline
String& String::operator = (const String &str) {
if (this == &str) {
return *this;
}
delete[] m_data;
m_data = new char[strlen(str.m_data) + 1];
strcpy(m_data, str.m_data);
return *this;
}
String String::operator + (const String &str) {
String tmp;
tmp.m_data = new char[strlen(this->m_data) + strlen(str.m_data) + 1];
strcpy(tmp.m_data, this->m_data);
strcat(tmp.m_data, str.m_data);
return tmp;
}
String& String::operator += (const String &str) {
String tmp = *this + str;
delete[] this->m_data;
this->m_data = new char[strlen(tmp.m_data) + 1];
strcpy(this->m_data, tmp.m_data);
return *this;
}
bool String::operator == (const String &str) const {
return strcmp(this->m_data, str.m_data) == 0;
}
ostream& operator << (ostream &os, const String &s) {
os << s.m_data;
return os;
}
istream& operator >> (istream &in, String &s) {
delete[] s.m_data;
s.m_data = new char[1024];
in >> s.m_data;
return in;
}
#endif

第二个版本:拷贝构造和拷贝赋值的时候通过交换指针,不要开辟额外的空间,采用值传递的方式,更加简洁的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#ifndef STRING_H
#define STRING_H
#include <iostream>
#include <string.h>
#include <algorithm>
#include <string>
using namespace std;
class String {
public:
String(const char *cstr = 0);
String(const String &str);
String& operator = (String str);
~String();
char *c_str() const { return m_data; }
String operator + (const String &str);
String& operator += (const String &str);
bool operator == (const String &str) const;
friend ostream& operator << (ostream &, const String &);
friend istream& operator >> (istream &, String &);
private:
char *m_data;
};
inline
String::String(const char *cstr) {
if (cstr) {
m_data = new char[strlen(cstr) + 1];
strcpy(m_data, cstr);
} else {
m_data = new char[1];
*m_data = '\0';
}
}
inline
String::~String() {
if (m_data) {
delete[] m_data;
}
}
inline
String::String(const String &str) : m_data(NULL) {
String tmp(str.m_data);
swap(m_data, tmp.m_data);
}
inline
String& String::operator = (String str) {
swap(m_data, str.m_data);
return *this;
}
String String::operator + (const String &str) {
String tmp;
tmp.m_data = new char[strlen(this->m_data) + strlen(str.m_data) + 1];
strcpy(tmp.m_data, this->m_data);
strcat(tmp.m_data, str.m_data);
return tmp;
}
String& String::operator += (const String &str) {
String tmp(*this + str);
swap(m_data, tmp.m_data);
return *this;
}
bool String::operator == (const String &str) const {
return strcmp(this->m_data, str.m_data) == 0;
}
ostream& operator << (ostream &os, const String &s) {
os << s.m_data;
return os;
}
istream& operator >> (istream &in, String &s) {
delete[] s.m_data;
s.m_data = new char[1024];
in >> s.m_data;
return in;
}
#endif

第三个版本:拷贝构造和拷贝赋值的时候只对其引用计数操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#ifndef STRING_H
#define STRING_H
#include <iostream>
#include <string.h>
#include <algorithm>
#include <string>
using namespace std;
class String {
public:
String(const char *cstr = 0);
String(const String &str);
String& operator = (const String &str);
~String();
char *c_str() const { return m_data; }
String operator + (const String &str);
String& operator += (const String &str);
bool operator == (const String &str) const;
friend ostream& operator << (ostream &, const String &);
friend istream& operator >> (istream &, String &);
private:
char *m_data;
int *m_count;
};
inline
String::String(const char *cstr) : m_count(new int(1)){
if (cstr) {
m_data = new char[strlen(cstr) + 1];
strcpy(m_data, cstr);
} else {
m_data = new char[1];
*m_data = '\0';
}
}
inline
String::~String() {
if (--(*m_count) == 0) {
delete[] m_data;
}
}
inline
String::String(const String &str) : m_count(str.m_count) {
m_data = str.m_data;
++(*m_count);
}
inline
String& String::operator = (const String &str) {
if (--(*m_count) == 0) {
delete[] m_data;
}
m_data = str.m_data;
m_count = str.m_count;
++(*m_count);
return *this;
}
String String::operator + (const String &str) {
String tmp;
tmp.m_data = new char[strlen(this->m_data) + strlen(str.m_data) + 1];
strcpy(tmp.m_data, this->m_data);
strcat(tmp.m_data, str.m_data);
return tmp;
}
String& String::operator += (const String &str) {
String tmp(*this + str);
swap(m_data, tmp.m_data);
return *this;
}
bool String::operator == (const String &str) const {
return strcmp(this->m_data, str.m_data) == 0;
}
ostream& operator << (ostream &os, const String &s) {
os << s.m_data;
return os;
}
istream& operator >> (istream &in, String &s) {
delete[] s.m_data;
s.m_data = new char[1024];
in >> s.m_data;
return in;
}
#endif

参考文献
strcpy函数的实现
C语言中的strlen实现方法
https://blog.csdn.net/wenqian1991/article/details/38981819