_{C++基础教程}
——
作业及参考答案全部汇总文档
^{_节5字符串阶段作业}

最新版本V2.0
王道C++团队
COPYRIGHT ⓒ 2021-2024. 王道版权所有

基础题篇

_Gn!

下面都是一些基础的语法、概念编程练习题。

手动实现字符串处理库函数

_Gn!

依照C语言的字符串标准库函数，手动实现以下函数：

x
1
size_t my_strlen(const char *str);
2
char *my_strcpy(char *dest, const char *src);
3
char *my_strncpy(char *dest, const char *src, size_t n);
4
char *my_strcat(char *dest, const char *src);
5
char *my_strncat(char *dest, const char *src, size_t n);
6
int my_strcmp(const char *str1, const char *str2);

函数的实现要模拟标准库函数中对应函数的行为，不要依据自己的理解来实现这些函数。

参考代码如下：

参考代码：

第一题参考代码如下：

xxxxxxxxxx
1
size_t my_strlen(const char* s) {
2
    // 用一个指针记录数组首元素
3
    const char* p = s;
4
    // 惯用法: 遍历直到字符串的末尾，
5
    while (*s) {
6
        s++;
7
    }   // 循环结束时，s指针指向了空字符，p指针指向数组首元素
8

9
    // 相当于空字符的下标减去首元素下标，结果就是字符串的长度
10
    return s - p;
11
}

第二题参考代码如下：

x
1
char *my_strcpy(char *dest, const char *src) {
2
    char *tmp = dest;   // dest数组的首元素指针要作为返回值,所以要临时保存一下
3
    while (*dest++ = *src++)
4
        ;
5
    return tmp;
6
}

第三题参考代码如下：

x
1
char *my_strncpy(char *dest, const char *src, size_t n) {
2
    char *tmp = dest;
3
    while (n > 0 && (*dest = *src)) { 
4
        dest++;
5
        src++;
6
        n--;
7
    }// while循环结束时，src指针指向指向空字符，dest指针也指向空字符
8
    while (n > 0) {
9
        *dest++ = '\0';
10
        n--;
11
    }
12
    return tmp;
13
}

第四题参考代码：

x
1
char* my_strcat(char* dest, const char* src) {
2
    char* temp = dest;
3
    // 找到dest的末尾，也就是让dest指针指向空字符
4
    while (*dest) {
5
        dest++;
6
    }
7
    while ((*dest++ = *src++))
8
        ;
9
    return temp;  // 返回dest的起始地址
10
}

第五题参考代码：

x
1
char* my_strncat(char* dest, const char* src, int n) {
2
    char* temp = dest;
3
    while (*dest) {
4
        dest++;
5
    }
6
    // 拷贝最多n个字符从src到dest的末尾
7
    while (n-- && (*src)) {
8
        *dest++ = *src++;
9
    }
10
    // 确保dest以空字符结尾,所以一定会将dest末尾置为空字符
11
    *dest = '\0';
12
    return temp;  // 返回dest的起始地址
13
}

第六题参考代码：

x
1
int my_strcmp(const char* s1, const char* s2) {
2
    while (*s1 && (*s1 == *s2)) {
3
        // 移动两个指针，比较下一对字符
4
        s1++;
5
        s2++;
6
    }
7
    /*
8
    * while循环结束的条件是：
9
    * 1.s1指针指向了空字符
10
    * 2.或者s2指针指向了空字符
11
    * 3.或者s1和s2指针指向的字符不一致
12
    * 不管是哪一种情况，返回它们的编码值差就是结果
13
    */
14
    return *s1 - *s2;
15
}

以上。

统计字符串中的数字和字母数量

_Gn!

给定一个字符串，要求它可能包含数字和字母。

请编写函数，统计该字符串中每个字符出现的次数，统计过程中忽略大小写的差异，并打印最终每个字符出现的次数。

提示：

用一个int数组存储字符出现的次数，可以用一个128长度的数组，这样数组下标位置的元素就是该编码值字符出现的次数，缺点是浪费空间，但你可以先写一个这样的实现。

（扩展）做完后，你可以思考一下：

实际上只会有36个字符(10个数字和26个不区分大小写的字母)，所以int数组的长度实际上只需要36就可以了。

那么怎么把数组的长度缩短到36呢？

参考代码如下：

参考代码：

基础版本以及优化版本的实现，参考代码如下：

xxxxxxxxxx
1
#include <stdio.h>
2
#define MAX_CHARS 128  // ASCII 编码表的大小
3
#define TOTAL_ALNUM 36  // 字母和数字一共36个
4

5
// 用128长度的数组,此时字符的编码值就是元素的下标,该下标位置的元素值就是该字符出现的次数
6
void count_characters(const char *str) {
7
    int count[MAX_CHARS] = { 0 };  // 初始化计数数组
8

9
    // 遍历字符串并统计每个字符出现的次数
10
    while (*str) {
11
        char ch = tolower(*str);  // 将字符转换为小写以忽略大小写差异
12
        if (isalnum(ch)) {  // 检查是否为字母或数字
13
            count[ch]++;
14
        }
15
        str++;
16
    }
17

18
    // 打印统计结果
19
    for (int i = 0; i < MAX_CHARS; i++) {
20
        if (count[i] > 0) {  // 只打印出现过的字符
21
            printf("'%c' 出现了 %d 次\n", i, count[i]);
22
        }
23
    }
24
}
25

26
/*
27
    实际上数组的长度只需要36个就够了
28
    因为有26个字母 + 10个数字
29
    但要计算一下编码值和数组下标的转换关系
30
    假如数组前10个元素存储的是数字，后26个元素存储的是字母，那么：
31
    字符是数字: 下标是编码值 - '0'
32
    字符是字母: 下标是编码值 - 'a' + 10(要把字母先都转换成小写,加10的原因是前面十个字符都是数字,字母的下标从10开始)
33
*/
34
// 计算字符对应的数组索引
35
int char_to_index(char ch) {
36
    if (isdigit(ch)) {
37
        return ch - '0';  // 数字字符的索引从0开始
38
    }
39
    // 不是数字一定是字母
40
    ch = tolower(ch); // 转换为小写字母
41
    return ch - 'a' + 10;  // 字母的索引从10开始 (0-9已经被数字占用)
42
}
43

44
void count_characters2(const char *str) {
45
    int count[TOTAL_ALNUM] = { 0 };  // 初始化计数数组
46

47
    // 遍历字符串并统计每个字符出现的次数
48
    while (*str) {
49
        char ch = *str;
50
        if (isalnum(ch)) {  // 检查是否为字母或数字
51
            // 转换编码值为下标
52
            int idx = char_to_index(ch);
53
            count[idx]++;
54
        }
55
        str++;
56
    }
57

58
    // 打印统计结果
59
    for (int i = 0; i < TOTAL_ALNUM; i++) {
60
        if (count[i] > 0) {  // 只打印出现过的字符
61
            if (i < 10) {  // 数字
62
                printf("'%c' 出现了 %d 次\n", '0' + i, count[i]);
63
            }
64
            else {  // 字母
65
                printf("'%c' 出现了 %d 次\n", 'a' + i - 10, count[i]);
66
            }
67
        }
68
    }
69
}
70

71

72
int main(void) {
73
    const char *str = "aaa111bbb222ccc";
74
    count_characters(str);
75
    printf("-----------------------\n");
76
    count_characters2(str);
77
    return 0;
78
}

以上。

统计字符串当中的单词数量

_Gn!

编写一个函数，计算一个字符串中单词的数量。这里，单词被定义为由空格分隔的字符序列。

例如，对于字符串"hello world! word Excel space blank"

就应该输出有6个单词

注意：空格可能连续出现。

思路参考:

1.整个过程就是跳过前面的所有空白字符，先找到一个非空字符，然后再跳过所有非空字符找到一个空白字符，于是确定找到一个单词。

2.第二种思路: 遍历整个字符串，如果字符是非空格制表符，那么就是单词的一部分，继续遍历直到碰到空字符或者空格制表符，意味着单词结束，计数器加1

两种思路皆可。

参考代码如下：

参考代码：

两种思路的参考代码如下：

x
1
#include <stdio.h>
2
#include <ctype.h>
3

4
// 第一种思路
5
int count_words(const char* str) {
6
    int count = 0; // 初始化单词计数为0
7

8
    // 从头开始遍历字符串
9
    while (*str) {
10
        // 在遍历的过程中如果碰到空格,始终跳过它
11
        // 由于空格可能有多个连续出现,所以这里要嵌套循环遍历字符串.
12
        while (*str && isspace(*str)) {
13
            str++;
14
        }
15

16
        // 代码运行到这里,遍历到的字符肯定不是空字符也不是空格,于是找到一个单词
17
        if (*str) {
18
            count++; // 找到一个单词，计数器加1
19
            // 继续遍历字符串，直到我们再次遇到空格或字符串结束
20
            while (*str && !isspace(*str)) {
21
                str++;
22
            }
23
        }
24
    }
25

26
    return count; // 遍历结束，返回单词总数
27
}
28

29
// 第二种思路
30
int count_words2(char *str) {
31
    int count = 0;
32
    // 遍历字符串直到遇到字符串的结束符
33
    for (int i = 0; str[i]; i++) {
34
        // 遇到一个非空格或制表符,意味着它是单词中的某个字符
35
        if (!isblank(str[i])) {
36
            // 如果发现下一个字符是空字符或者空格制表符,那么说明一个单词结束了
37
            if (isblank(str[i + 1]) || str[i + 1] == '\0') {
38
                count++;    // 因此计数器加1
39
            }
40
        }
41
    }
42
    return count;
43
}
44

45
int main(void) {
46
    char str[] = "hello world!  word  Excel space blank";
47
    int count = count_words(str);
48
    return 0;
49
}

以上。

检查字符串中的小括号是否匹配

_Gn!

编写一个函数，检查给定的字符串中的圆括号()是否正确匹配。注意只考虑小括号，字符串中没有其它括号。

如字符串：((Hello) (World))

函数会返回一个布尔值，表示匹配成功或失败

注意：只考虑英文小括号()，不需要考虑其它括号，更不需要考虑中文符号。

参考代码如下：

参考代码如下：

只考虑小括号的匹配，所以整个实现是比较简单的：

x
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3
#include <stdbool.h>
4

5
// 函数用于检查字符串中的圆括号是否正确匹配
6
bool check_parentheses(const char* str) {
7
    int count = 0;
8
    // 遍历整个字符串到空字符
9
    while (*str) {
10
        // 先找到左括号
11
        if (*str == '(') {
12
            // 统计左括号个数，遇到右括号就--
13
            count++;
14
        }
15
        else if (*str == ')') {
16
            if (count == 0) {
17
                // 一开始就碰到右括号 匹配失败
18
                return 0;
19
            }
20
            count--;
21
        }
22
        str++;
23
    }
24
    return count == 0; // 检查是否所有左括号都被匹配了
25
}
26

27
int main(void) {
28
    const char* str = "((Hello) (World))";
29
    if (check_parentheses(str)) {
30
        printf("匹配成功！\n");
31
    }
32
    else {
33
        printf("匹配失败！\n");
34
    }
35
    return 0;
36
}

以上。

扩展题篇

_Gn!

以下题目都属于扩展题。

扩展：字符串替换/删除/分组操作

_Gn!

第一题：

将字符串中的空格替换成 %020 (假定原字符数组能够存放替换后的字符串)。

xxxxxxxxxx
3
1
void substitute_space(char* str);
2
输入: "hello world how "
3
输出: "hello%020world%020how%020"

注意：只考虑字符串中存在空格字符，不考虑制表、换行等其它空白字符。

第二题：

删除字符串中指定的字符。

xxxxxxxxxx
3
1
void delete_character(char* str, char c);
2
输入: "abcdaefaghiagkl", 'a'
3
输出: "bcdefghigkl"

参考代码如下：

参考代码如下：

第一题，字符串替换操作，参考代码如下：

x
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3
#include <string.h>
4

5
#define MAX_STR_LEN 100
6

7
/*
8
    思路一：使用临时数组替换空格
9
    初始化一个足够长度的临时数组
10
    然后遍历原数组，将非空格字符正常复制，但在复制空格时将空格替换成%020
11
    最后将临时数组字符串复制回原始字符字符数组中
12
*/
13
void substitute_space(char *str) {
14
    char tmp[MAX_STR_LEN + 1];
15
    char *s = str;
16
    int i = 0;  // 临时数组的下标，用于定位复制操作的位置
17
    while (*s) {
18
        if (*s == ' ') {
19
            // 当前字符是空格就复制%020并使得i索引后移4位
20
            tmp[i] = '%';
21
            tmp[i + 1] = '0';
22
            tmp[i + 2] = '2';
23
            tmp[i + 3] = '0';
24
            i += 4;
25
        }
26
        else {
27
            tmp[i++] = *s;
28
        }
29
        s++;
30
    }
31
    tmp[i] = '\0';  // 不要忘记加空字符
32

33
    strcpy(str, tmp);
34
}
35

36
/*
37
    思路二：原地替换字符，不占用额外内存空间
38
    替换过程字符串肯定会变长, 为了更好实现避免覆盖掉未操作的字符, 最好倒着遍历字符串
39
    遍历的过程中,将字符向后移动
40

41
    于是就有一个重要的问题, 字符向后移动几个位置呢?
42
    首先我们要统计一下空格的数量count, 很明显空格数量越多，向后移动的位置越多
43
    那么：
44
    count代表当前剩余未处理的空格的数量
45
    非空格字符需要向后移动： count * 3
46
    空格字符替换成:
47
    '%' 字符的位置是当前空格的原始位置。
48
    前面的'0' 字符的位置是 '%' 字符位置加1。
49
    '2' 字符的位置是 '0' 字符位置加1。
50
    后面的'0' 字符的位置是 '2' 字符位置加1。
51
*/
52
void substitute_space2(char *str) {
53
    int count = 0;  // 空格字符的数量
54
    char *p = str;
55
    while (*p) {
56
        if (*p == ' ') {
57
            count++;
58
        }
59
        p++;
60
    }   // while循环结束时,p指向空字符的下一个字符
61
    p--;    // p指针回退一个位置
62

63
    // 倒着遍历字符串, 此时count代表未处理空格字符的数量
64
    while (p >= str) {
65
        char c = *p;
66
        if (c == ' ') {
67
            *(p + 3 * count) = '0';
68
            *(p + 3 * count - 1) = '2';
69
            *(p + 3 * count - 2) = '0';
70
            *(p + 3 * count - 3) = '%';
71
            count--;
72
        }
73
        else {
74
            *(p + 3 * count) = c;
75
        }
76
        p--;
77
    }
78
}
79

80
int main(void) {
81
    char str[100] = "hello world how "; // str数组必须要足够长
82
    substitute_space(str);
83
    puts(str);
84
    return 0;
85
}

第二题：字符串删除，可以基于字符串分组来实现，参考代码如下：

x
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3
#include <string.h>
4

5
#define MAX_STR_LEN 100
6

7
/*
8
 思路一: 临时数组法
9
 遍历原字符串, 遇到需要删除的字符, 就不复制到临时数组
10
 其余字符正常复制到临时数组
11
 最后将临时数组复制回原字符串数组
12
*/
13
void delete_character(char *str, char c) {
14
    char tmp[MAX_STR_LEN + 1];
15

16
    char *s = str;
17
    int i = 0; // 用于在临时数组中定位
18
    while (*s) {
19
        if (*s != c) { 
20
            // 如果当前字符不是要删除的字符, 将它添加到临时数组中
21
            tmp[i++] = *s;
22
        }
23
        s++;
24
    }
25
    // 不要忘记加空字符
26
    tmp[i] = '\0';
27

28
    strcpy(str, tmp); // 将临时数组的内容复制回原字符串
29
}
30

31
/*
32
 思路二: 原地删除字符串, 仍然使用双指针法, 仍然是一个单向分区的思想
33
 p指针用于遍历字符串
34
 pstore指针用于指示那些不被删除的元素该放置的位置
35
 一开始两个指针都指向首字符
36
 只要p找到一个非删除字符,那么就把它直接覆盖到pstore指针位置, pstore后移一位
37
 直到遍历完整个字符串, 所有的非删除字符都被移到了前面, 所有的待删除字符都移到了后面, 这就完成了分区
38
 此时p指针指向空字符的下一个字符
39
 pstore指针则指向第一个待删除目标字符, 于是只要把pstore指针位置的元素设置为空字符就完成了字符串删除
40
*/
41
void delete_character2(char *str, char c) {
42
    char *pstore = str; // 下一个不等于c的元素应该置于的位置
43
    char *p = str;
44

45
    while (*p) {
46
        if (*p != c) {
47
            char tmp = *pstore;
48
            *pstore = *p;
49
            *p = tmp;
50
            pstore++;
51
        }
52
        p++;
53
    }
54
    *pstore = '\0';   // 不要忘记最后要添加空字符
55
}
56
int main(void) {
57
    char str[] = "abcdaefaghiagkl";
58
    delete_character2(str, 'a');
59
    return 0;
60
}

以上。

扩展：字符串字符分组

_Gn!

请编写函数，将字符串中的字母和数字分开，使得字符串中前一部分是数字，后一部分是字母。

xxxxxxxxxx
3
1
void seperate(char* str);
2
输入: "h1ell2o3"
3
结果: "123hello"或者任意数字在前，字母在后的字符串

注意：要求字符串只包含字母和数字，字符串的长度不超过100，且分组要最终在原数组上完成。

提供几个参考的实现思路：

1.临时数组法。用两个临时数组一个装数字，一个装字母，然后再将数据合并回原数组。

2.双指针夹逼交换法。两个指针向中间逼近，一个找字母一个找数字，找到后交换，直到两个指针相遇。

3.双指针单向分区交换法。

一个指针p用于遍历字符串，另一个指针p_num从头开始向后移动，用于标记下一个数字应该插入的位置。

p指针每发现一个数字，就把它交换到p_num位置，然后p_num指针后移。

直到遍历完字符串，所有的数字都会被交换到前面，所有字母都会被交换到后面。

最后，上面提到的双指针法，既可以用真正意义上的指针，也可以直接用索引。两者没有本质上的区别，更多是代码风格上的区别。

基于上述思想，参考代码如下：

参考代码：

x
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3

4
#define MAX_STR_LEN 100
5

6
/*
7
    方式一：利用临时数组实现分组
8
    这种方式能保证字符相对位置不变
9
    但缺点是占用额外内存空间，且效率不高
10
*/
11
void separate(char *str) {
12
    // 两个临时数组一个装字母一个装数字
13
    // 虽然一个临时数组也可以实现，但会比较麻烦，建议用双临时数组
14
    char digits[MAX_STR_LEN + 1];
15
    char alphas[MAX_STR_LEN + 1];
16
    char *s = str;
17
    int i = 0, j = 0;
18
    while (*s) {
19
        if (isdigit(*s)) {
20
            digits[i++] = *s;
21
        }
22
        else if (isalpha(*s)) {
23
            alphas[j++] = *s;
24
        }
25
        s++;
26
    }
27
    // 在后面添加空字符
28
    digits[i] = '\0';
29
    alphas[j] = '\0';
30

31
    strcpy(str, digits);
32
    strcat(str, alphas);
33
}
34
/*
35
    方式二：双指针法夹逼交换法
36
    使用两个指针left和right
37
    left指针从字符串开头向后遍历寻找字母，right指针从字符串末尾向前遍历寻找数字。
38
    当left找到一个字母且right找到一个数字时，交换它们的位置
39
    重复这个过程直到left和right指针相遇。
40
*/
41
void separate2(char *str) {
42
    char *left = str; // 从字符串开始处向后寻找字母
43
    char *right = str + strlen(str) - 1; // 从字符串结束处向前寻找数字
44

45
    while (left < right) {
46
        // 向后寻找直到找到一个字母
47
        while (left < right && !isalpha(*left)) {
48
            left++;
49
        }
50
        // 向前寻找直到找到一个数字
51
        while (left < right && !isdigit(*right)) {
52
            right--;
53
        }
54
        // 交换数字和字母
55
        if (left < right) {
56
            char temp = *left;
57
            *left = *right;
58
            *right = temp;
59
            /*      left++;
60
            right--;*/
61
        }
62
    }
63
}
64

65

66
/*
67
    方式三：双指针单向分区交换法
68
    思路：
69
    先初始化一个临时指针 p 指向首字符，用于遍历字符串
70
    再初始化另一个临时指针 p_num 指向首字符，该指针用于指示一个数字字符应该放置的位置（因为数字要放到前面）
71
    在遍历字符串的过程中，一旦 p指针 指向一个数字字符，那么就交换两个指针位置的元素，然后将p_num向后移
72
    这样直到遍历完整个字符串，所有的数字就都会被交换到前面
73

74
    这里提到的分区思想是：
75
    一个指针用于遍历，另一个指针标记插入位置
76
    这种做法是数组分区分组更常见的思想策略
77
*/
78
void separate3(char *str) {
79
    char *p = str; // p指针用于遍历字符串
80
    char *p_num = str; // p_num 指向下一个数字应该放置的位置
81

82
    // 利用p指针遍历字符串直到结束
83
    while (*p) {
84
        // 如果当前字符是数字
85
        if (isdigit(*p)) {
86
            // 只有当 p 和 p_num 指向不同位置时才需要交换
87
            if (p != p_num) {
88
                // 交换 *p 和 *p_num 指向的值
89
                char temp = *p_num;
90
                *p_num = *p;
91
                *p = temp;
92
            }
93
            p_num++; // 移动 p_num 到下一个位置
94
        }
95
        p++; // 移动p继续遍历字符串
96
    }
97
}
98

99
/*
100
    数组本身是有索引的，可以利用索引来模拟指针，这样也可以实现"双指针"
101
    两种方式在性能的差异上微乎其微
102
    更多的是代码风格上的区别
103
*/
104
void separate4(char *str) {
105
    int i = 0; // i 用于遍历字符串中的每个字符
106
    int j = 0; // j 指向下一个数字应该放置的位置
107
    // 遍历字符串直到结束
108
    while (str[i]) {
109
        // 如果当前字符是数字
110
        if (isdigit(str[i])) {
111
            // 如果 i 不等于 j，则需要交换字符
112
            if (i != j) {
113
                // 交换 `str[i]` 和 `str[j]`
114
                char temp = str[j];
115
                str[j] = str[i];
116
                str[i] = temp;
117
            }
118
            j++; // j索引++，模拟指针向后移动
119
        }
120
        i++; // i索引++，模拟指针向后移动，继续遍历字符串
121
    }
122
}
123

124
int main(void) {
125
    char str[] = "h1ell2o3";
126
    separate2(str);
127

128
    return 0;
129
}

以上。

The End