_{C++基础教程}
——
作业及参考答案全部汇总文档
^{_节4指针和数组阶段作业}

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

C++基础教程 —— 作业及参考答案全部汇总文档 节4指针和数组阶段作业 最新版本V2.0 王道C++团队 COPYRIGHT ⓒ 2021-2024. 王道版权所有基础题篇数组与指针基础练习题1数组与指针基础练习题2数组与指针基础练习题3数组与指针基础练习题4扩展题篇扩展：数组分区思想扩展：合并两个有序子数组扩展：分离非负数以及正数扩展：荷兰国旗问题扩展：三向分区负数、0以及正数The End

基础题篇

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

数组与指针基础练习题1

_Gn!

以下题目功能，都要求编写函数将数组作为参数传递来实现：

1.编写函数交换数组中两个下标的元素。函数声明如下：void swap(int *arr, int i, int j) 。要求不使用[]运算符，将[]还原成解引用运算符和指针加法来完成。

2.数组元素的逆序。要求使用[]运算符以及纯粹指针操作两种方式来完成。

3.数组元素求和。要求使用"*p++"语法结构来完成数组元素的累加。

4.给定一个int数组以及一个目标值target，请编写函数找到这个目标值的下标，要求该函数没有返回值。（目标元素在数组中唯一，不考虑多次出现目标元素的情况）

5.编写一个函数，检查一个整数数组是否是回文，即正序与倒序相同。例如[1,2,3,2,1]就是回文的。要求使用指针的算术运算，不要使用取下标[]运算符。

6.给定一个非空整数数组src，再给定一个足够长的dest数组。编写一个函数 copy_array，使用 *p++ 复制src数组到dest数组。

注意：这道题目要把代码写得尽量简洁！！

7.给定一个整数数组，将所有奇数移到数组前面，偶数移到数组后面。（扩展题）

参考代码如下：

参考代码：

第一题非常简单，无非就是将"[]"运算符都还原成解引用的形式，参考代码如下：


x
1
// 使用指针操作交换数组中的两个元素
2
void swap(int *arr, int i, int j) {
3
    // 交换 arr[i] 和 arr[j]
4
    int temp = *(arr + i);   // tmp = arr[i]
5
    *(arr + i) = *(arr + j); // arr[i] = arr[j]
6
    *(arr + j) = temp;       // arr[j] = tmp
7
}

第二题也非常简单，是上课讲过的，参考代码如下：


x
1
// 使用指针操作逆序数组中的元素
2
void reverse_by_ptr(int *arr, int n) {
3
    // 定义起始指针指向数组的第一个元素
4
    int *start_ptr = arr;
5
    // 定义结束指针指向数组的最后一个元素
6
    int *end_ptr = arr + n - 1;
7

8
    // 当起始指针小于结束指针时，执行循环
9
    while (start_ptr < end_ptr) {
10
        // 交换两个指针指向的元素
11
        int temp = *start_ptr;
12
        *start_ptr = *end_ptr;
13
        *end_ptr = temp;
14

15
        // 将起始指针后移一个元素，将结束指针前移一个元素
16
        start_ptr++;
17
        end_ptr--;
18
    }
19
}
20

21
// 先用纯粹的C基础代码来实现, 不用指针操作, 只用[]取下标运算
22
// 这个操作无需额外的临时数组, 直接原地交换就可以实现了
23
// 0 <-> len - 1, 1 <-> len - 2.... i <-> len - i - 1
24
void reverse_arr(int arr[], int len){
25
    for (int i = 0; i < len / 2; i++){
26
        int tmp = arr[i];
27
        arr[i] = arr[len - 1 - i];
28
        arr[len - 1 - i] = tmp;
29
    }
30
}

第三题参考代码如下：


x
1
// 遍历求和数组
2
int sum_arr(int arr[], int len) {
3
    int* p = arr;
4
    int sum = 0;
5
    // 每循环一次累加一次元素并且刚好指针p移动一个位置
6
    while (p < arr + len) {
7
        sum += *p++;
8
    }
9
    return sum;
10
}

第四题参考代码：


x
1
// 使用指针操作找到目标值的下标
2
void find_target_index(int *arr, int len, int target, int *result_index) {
3
    // 初始化下标为-1，表示未找到
4
    *result_index = -1;
5

6
    for (int i = 0; i < len; i++) {
7
        if (arr[i] == target) {
8
            // 如果找到目标值，更新结果下标并结束循环
9
            *result_index= i;
10
            break;
11
        }
12
    }
13
    // 如果循环结束还没找到，*resultIndex 仍为-1，表示目标值不在数组中
14
}

第五题参考代码：


x
1
/*
2
 回文数组(palindrome array)即正读和反读一样的数组
3
 整个实现的过程非常类似于数组逆序
4
 用两个指针指向数组开头和末尾
5
 然后两个比较指针指向的元素，若任意元素不相等，就不是回文数组
6
*/
7
bool is_palindrome(int* arr, int len) {
8
    int* start = arr;          // 指向数组首元素
9
    int* end = array + size - 1; // 指向数组尾元素
10

11
    // 首尾指针未相遇，那就继续移动指针比较两个元素的值
12
    while (start < end) {
13
        if (*start != *end) { // 如果两个指针指向的元素不相等，则不是回文数组
14
            return false;
15
        }
16
        start++; 
17
        end--;   
18
    }
19
    return true; // 所有对应元素检查结束，都相等，则是回文数组
20
}

第六题参考代码：


x
1
// len是src源数组的长度
2
void copy_arr(int* src, int* dest, int len) {
3
    // 将源数组中所有元素复制过去，所以指针要移动len次
4
    while (len--) {
5
        *dest++ = *src++;
6
    }
7
}
8

9
int main(void) {
10
    int src[] = { 0, 2, 3, 4, 5 };
11
    int dest[10];
12

13
    copy_arr(src, dest, 5);
14
    return 0;
15
}

第七题参考代码，需要使用双指针法求解：


x
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3
#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))
4
/*
5
* 所有的奇数都要移动到前面，所有的偶数都要移动到后面
6
* 我们采用双指针的思路解决这道题：
7
* 1.定义一个指针start指向数组首元素，它用于寻找数组左边的偶数
8
* 2.定义一个指针end指向数组尾元素，它用于寻找数组右边的奇数
9
* 接下来：
10
* start指针向右移动直到：
11
*   1.碰到一个偶数
12
*   2.或者与end相遇
13
* end指针向左移动直到：
14
*   1.碰到一个奇数
15
*   2.或者与start相遇
16
* 总之，当两个指针都停下来的时候：
17
*   1.start指向一个偶数且end指向一个奇数
18
*   2.start与end相遇
19
* 所以在start与end没相遇的前提下：
20
*   交换两个两个指针指向的元素
21
* 在最终两个指针相遇时，所有的奇数元素一定在前面
22
*
23
*/
24
void separate_odd_even(int arr[], int len) {
25
    int* start = arr;
26
    int* end = arr + len - 1;
27

28
    // 只要不相遇就可能出现交换
29
    while (start < end) {
30
        // 只要没相遇并且没有找到偶数，就向右移动start
31
        while (start < end && (*start % 2 != 0)) {
32
            start++;
33
        }
34
        // 只要没相遇并且没有找到奇数，就向左移动end
35
        while (start < end && (*end % 2 == 0)) {
36
            end--;
37
        }
38

39
        // 如果未相遇说明start指向一个偶数，end指向一个奇数，需要交换
40
        if (start < end) {
41
            int tmp = *start;
42
            *start = *end;
43
            *end = tmp;
44

45
            // 交换元素后，指针继续移动
46
            start++;
47
            end--;
48
        }
49
    }
50
}
51

52
int main(void) {
53
    int arr[] = { 1,23,34,32,4,32,4,23,12,33,4,89,324,821,213,12,3,12,312,313,123,12 };
54
    separate_odd_even(arr, ARR_LEN(arr));
55

56
    return 0;
57
}

以上。

数组与指针基础练习题2

_Gn!

第一题：

查找数组的最大值和最小值，但要将最大值作为返回值返回，最小值则依靠传入的指针完成赋值。

要求不能使用"[]"运算符。

函数的声明如下：


xxxxxxxxxx
1
1
int max_min(int *arr, int len, int *pmin);

第二题：

求平均值，给定一个double数组，求平均值，并且返回。

要求使用while循环遍历数组，然后配合"*p++"的语法实现。

函数的声明如下：


xxxxxxxxxx
1
1
double get_ave(double *arr, int len);

参考代码如下：

参考代码：

第一题和课堂上讲的题目实现非常类似，参考代码如下：


x
1
int max_min(int *arr, int len, int *pmin) {
2
    int max = *arr; // 假设第一个元素是最大的
3
    *pmin = *arr; // 同样假设第一个元素是最小的
4
    int *p = arr + 1; // 指向数组的第二个元素
5

6
    while (p < arr + len) {
7
        if (*p > max) {
8
            max = *p;
9
        }
10
        if (*p < *pmin) {
11
            *pmin = *p;
12
        }
13
        p++; // 移动到下一个元素
14
    }
15
    return max;
16
}

第二题参考代码：


x
1
double get_ave(double *arr, int len) {
2
    double sum = 0.0;
3
    double *p = arr;
4

5
    while (p < arr + len) {
6
        sum += *p++; // 取出当前指针指向的值，然后将指针向后移动
7
    }
8

9
    return sum / len; 
10
}

以上。

数组与指针基础练习题3

_Gn!

编写函数，查找一个int数组中的最大元素和第二大元素，并将它们分别存放在由 largest 和 second_largest 指向的变量中。

按照下面的函数声明来实现这个函数。


xxxxxxxxxx
1
1
void find_two_largest(int arr[], int n, int* largest, int* second_largest);

注意：为了简化实现，数组不存在重复元素，请不要考虑存在重复元素的情况。

参考代码如下：

参考代码：


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

4
// 前提：arr数组不存在重复元素
5
void find_two_largest(int arr[], int n, int *largest, int *second_largest) {
6
    // 将数组的前两个元素设置为最大值和第二最大值
7
    *largest = arr[0] > arr[1] ? arr[0] : arr[1];
8
    *second_largest = arr[0] < arr[1] ? arr[0] : arr[1];
9

10
    for (int i = 2; i < n; i++) {   // 从第三个元素开始遍历
11
        if (arr[i] > *largest) {
12
            // 如果当前元素大于最大值，则更新最大值，并将原最大值赋给第二大值
13
            *second_largest = *largest;
14
            *largest = arr[i];
15
        }
16
        else if (arr[i] > *second_largest) {
17
            // 如果当前元素大于第二大值但小于最大值，则更新第二大值
18
            *second_largest = arr[i];
19
        }
20
    }
21
}
22

23
int main(void) {
24
    int largest, second_largest;
25
    int arr[] = { 9, 5, 2, 7, 1, 3, 4, 6, 8, 0 };
26
    find_two_largest(arr, 10, &largest, &second_largest);
27
    printf("largest = %d, second_largest = %d\n", largest, second_largest);
28

29
    return 0;
30
}

以上。

数组与指针基础练习题4

_Gn!

基于以下函数声明，实现函数：


xxxxxxxxxx
1
1
void split_time(long total_sec, int* hour, int* minute, int* second);

形参中的 total_sec 表示从凌晨00:00:00开始，到现在时间的秒数。

请将 total_sec 转化以时(0-23)、分(0-59)、秒(0-59)表示的时间，并存放到函数外部由指针 hour, minute, second 指向的变量中。

并在函数调用的位置，打印出当前的时间。

测试用例：

total_sec = 0，表示时间 00:00:00

total_sec = 9527，表示时间 02:38:47

total_sec = 3001，表示时间 00:50:01

参考代码如下：


x
1
void split_time(long total_sec, int *hour, int *minute, int *second) {
2
    // 计算秒数
3
    *second = total_sec % 60;
4
    // 计算分钟数
5
    *minute = (total_sec / 60) % 60;
6
    // 计算小时数
7
    *hour = (total_sec / 60 / 60) % 24;
8
}
9

10
int main() {
11
    long total_sec = 3001;  
12
    int hour, minute, second;
13

14
    split_time(total_sec, &hour, &minute, &second); 
15

16
    // 打印当前时间，%02d意味着如果整数小于2位，则在前面补0
17
    printf("当前时间为：%02d:%02d:%02d\n", hour, minute, second);
18

19
    return 0;
20
}

以上。

扩展题篇

_Gn!
以下题目都属于扩展题。

扩展：数组分区思想

_Gn!

数组分区（Partitioning）是一种将数组元素重新排列的操作，使得符合某种条件的元素位于一侧，而不符合条件的元素位于另一侧。

数组分区在很多算法的实现当中，都是非常重要和关键的步骤，最典型的例子就是快速排序算法的实现。

除此之外，数组分区的应用还包括：

将整数数组分为奇数和偶数两部分，比如移动奇数到数组前部，偶数到后部。
分离负数和正数，将所有负数移至数组的一端，正数移到另一端。
字符串中删除某个字符。
荷兰国旗问题。
...

这里我们就以int数组实现奇偶分区来探讨一下数组分区的思想以及实现。

题目：
给定一个整数数组，将所有奇数移到数组前面，偶数移到数组后面。

首先，实现数组的分区操作，最容易想到且容易实现的应该是——利用临时数组实现分区。


x
1
/*
2
    数组分区一个最简单粗暴,容易理解的实现是:
3
    利用临时数组来进行分区:
4
    1.分配一个临时数组,长度和原数组是一样的(动态内存分配)
5
    2.遍历原数组, 将原数组中的所有奇数放入临时数组的前面
6
    3.再遍历一次原数组, 将原数组中的所有偶数放入临时数组的后面
7
    4.遍历临时数组, 将临时数组的元素全部覆盖到原数组
8

9
    缺点:
10
    1.需要额外的内存空间占用
11
    2.需要多次遍历数组,显然效率也比较差
12

13
    优点:
14
    1.简单直接,易于理解
15
    2.是稳定的(算法执行后,不会改变原始数据集元素的相对位置)
16
*/
17
void separate_odd_even(int arr[], int len) {
18
    int tmp[N];
19
    int tmp_idx = 0;    // 临时数组的下标,从0开始,每将一个元素放入临时数组,下标就加1
20
    // 遍历原数组,将奇数放入临时数组前面
21
    for (int i = 0; i < len; i++) {
22
        if (arr[i] % 2 != 0) {
23
            tmp[tmp_idx++] = arr[i];
24
        }
25
    }
26

27
    // 遍历原数组,将偶数放入临时数组后面
28
    for (int i = 0; i < len; i++) {
29
        if (arr[i] % 2 == 0) {
30
            tmp[tmp_idx++] = arr[i];
31
        }
32
    }
33

34
    // 将临时数组的元素全部复制回原数组
35
    for (int i = 0; i < len; i++) {
36
        arr[i] = tmp[i];
37
    }
38
}

从不使用额外空间和性能优化的角度出发，我们还有一种非常优秀的实现方式——双指针法。

所谓双指针法就是利用两个指针（数组可以基于双索引），来实现某些操作。双指针法在求解线性数据结构（数组/字符串/链表）的相关算法问题时，特别常用。

比如：

数组的分区操作。数组快速排序，数组逆序、二分查找、回文检查等都可以基于双指针法实现。
链表操作中的快慢指针法。可以用于求链表的中间结点，以及检查单链表是否有环等。
字符串操作中的删除某个字符，也可以基于双指针实现。

下面我们将采用两种双指针法来实现数组奇偶分区。

方式一：双指针夹逼交换元素法

参考代码如下：


x
1
/*
2
    双指针法实现分区的思路一: 双指针夹逼交换元素法
3
    创建两个指针: 左指针指向数组首元素, 右指针指向数组尾元素
4
    左指针的目的是找到一个偶数,将它交换到数组末尾
5
    右指针的目的是找到一个奇数,将它交换到数组开头
6

7
    优点:不占用额外内存空间,而且只需要遍历数组一次,性能较好
8
    缺点:不稳定,算法实现相对复杂
9
*/
10
void separate_odd_even2(int arr[], int len) {
11
    int *left = arr;
12
    int *right = arr + len - 1;
13

14
    // 左右指针不相遇那就继续往中间移动
15
    while (left < right) {
16
        // 左指针向右移动,直到找到一个偶数
17
        // 细节: 在找的过程中, 左指针仍然不能越过右指针
18
        while (left < right && (*left % 2 != 0)) {
19
            left++;
20
        }
21
        // 右指针向左移动,直到找到一个奇数
22
        while (left < right && (*right % 2 == 0)) {
23
            right--;
24
        }
25

26
        // 代码运行到这里,说明左右指针都找到了目标元素,那就交换
27
        if (left < right){
28
            int tmp = *left;
29
            *left = *right;
30
            *right = tmp;
31

32
            left++;
33
            right--;
34
        }
35
    }
36
}

方式二：双索引单向分区法

参考代码如下：


x
1
/*
2
    双指针单向分区交换元素法
3
    由于数组本身就存在索引,所以双指针法的实现,并不一定就要创建指针
4
    可以用索引模拟指针来实现双指针法
5

6
    用索引还是用指针,从性能上来说,区别微乎其微,更多的是代码风格上的区别
7
    双索引单向分区交换元素法的思路:
8
    1.首先利用一个索引i来遍历整个数组,从0开始
9
    2.再利用一个索引idx来指示下一个奇数应该放置的位置,从0开始
10
    3.一旦i索引找到了一个奇数,那就把它交换到idx位置,这样就实现了把所有的奇数放到前面
11
        当然这个交换的过程中,需要判断i和idx位置不同,位置不同才交换,否则没有交换的必要
12
        (细节)当交换元素了或者两个索引指向同一个奇数时,都要向后移动idx索引的位置
13
    4.当i索引遍历完整个数组时,奇数就都放置在了前面,偶数就都放在了后面
14

15
    优点:不占用额外内存空间,而且只需要遍历数组一次,性能较好
16
        奇数部分是稳定的
17
    缺点:算法实现相对复杂,偶数部分不稳定
18

19
    对于交换元素实现的算法,它的稳定与不稳定,可以考虑以下原则:
20
    如果交换元素是连续的,相邻的元素交换,那么稳定性就可以保证,元素的相对位置就不会改变
21
    如果交换元素是不连续的,是跨越长距离的交换,那么稳定性就难以保证了,可以认为是不稳定的
22
    这个结论对后续学习比较排序算法是非常关键的
23
*/
24
void separate_odd_even3(int arr[], int len) {
25
    int idx = 0;    // 标记下一个奇数放置的位置
26
    for (int i = 0; i < len; i++){
27
        if (arr[i] %2 != 0) {
28
            if (i != idx) {
29
                // 交换i和idx索引位置的元素
30
                int tmp = arr[i];
31
                arr[i] = arr[idx];
32
                arr[idx] = tmp;
33
            }
34
            idx++;
35
        }
36
    }
37
}

以上。

扩展：合并两个有序子数组

_Gn!

给定两个有序的整数子数组，然后将它们合并到一个足够长的新数组中，合并后的结果数组也应当是有序的。

比如：
数组1：[1, 3, 5, 6, 7]
数组2：[2, 3, 4, 8]
合并后的结果数组3：[1, 2, 3, 3, 4, 5, 6, 7, 8]

提示：整个合并的过程类似"穿针引线"，利用两个索引逐一比较两个数组的元素大小，然后把较小元素放入数组3中。"穿针引线"结束，最终：

一定会有一个数组元素被全部被赋值到数组3当中了
另一个数组元素一定还有剩余

那就把剩余数组的元素全部复制到数组3的后面即可。

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

参考代码：


x
1
#include <stdio.h>
2

3
#define N1 5  // 定义第一个数组的长度
4
#define N2 4  // 定义第二个数组的长度
5

6
// 合并两个有序数组的函数
7
void merge(const int arr1[], const int arr2[], int arr3[]) {
8
    // i是数组1的索引下标,j是数组2的,k是数组3的
9
    int i = 0, j = 0, k = 0;
10

11
    // 只要两个数组同时还有元素，那就比较对应位置元素，将较小元素放入数组3中
12
    while (i < N1 && j < N2) {
13
        /*
14
         这里使用<运算符意味着如果数组1和数组2中元素若一致
15
             则优先把数组2中的元素放入数组3
16
         这里如果使用<=运算符则意味着如果数组1和数组2中元素若一致
17
             优先把数组1中的元素放入数组3中
18
         这两种实现在这里是没有区别的，因为元素来自于两个独立的数组
19
         没有稳定性的概念，相同元素是数组1优先还是数组2优先没有区别
20
     */
21
        if (arr1[i] < arr2[j]) {    
22
            arr3[k++] = arr1[i++];
23
        }
24
        else {
25
            arr3[k++] = arr2[j++];
26
        }
27
    }
28

29
    // 如果第一个数组还有剩余，继续添加
30
    while (i < N1) {
31
        arr3[k++] = arr1[i++];
32
    }
33

34
    // 如果第二个数组还有剩余，继续添加
35
    while (j < N2) {
36
        arr3[k++] = arr2[j++];
37
    }
38
}
39

40
int main(void) {
41
    int arr1[N1] = { 1, 3, 5, 6, 7 };
42
    int arr2[N2] = { 2, 3, 4, 8 };
43

44
    // 用于存储结果的数组
45
    int arr3[N1 + N2];  
46
    merge(arr1, arr2, arr3);  // 调用合并函数
47

48
    // 打印合并后的数组
49
    for (int i = 0; i < N1 + N2; i++) {
50
        printf("%d ", arr3[i]);
51
    }
52

53
    return 0;
54
}

以上。

扩展：分离非负数以及正数

_Gn!

给定一个整数数组，请将所有非正数(包含负数和0)全部移到数组开头，正数则全部移到数组末尾，要求原地完成，不使用额外内存空间。

比如：
数组[1, -2, 3, 0, -9, 0, 10, 3]
最终分组完成后的效果应该是[非正数（包含0）, 正数]（稳定性不做要求）

提示：仍然可以基于双指针单向分区或夹逼法求解。

参考代码如下：

参考代码：

解法一：双索引单向分区法


x
1
// 函数用于将所有非正数移到数组的开头，所有正数移到数组的末尾
2
void separate_arr(int arr[], int size) {
3
    int idx = 0;  // 索引idx用于标记下一个非正数应该放置的位置
4
    for (int i = 0; i < size; i++) {
5
        // 如果当前元素是非正数（包括 0）
6
        if (arr[i] <= 0) {
7
            if (i != idx) {  // i和idx索引不是同一个位置时才交换元素
8
                int tmp = arr[i];
9
                arr[i] = arr[idx];
10
                arr[idx] = tmp;
11
            }
12
            // idx位置加1，标记下一个位置为新的非正数应该放置的位置
13
            idx++;
14
        }
15
    }
16
}

解法二：双索引双向夹逼交换元素法


x
1
// 左索引寻找正数，右索引寻找非正数，然后交换元素实现分区操作
2
void separate_arr2(int arr[], int size) {
3
    int left = 0;
4
    int right = size - 1;
5

6
    while (left < right) {
7
        while (left < right && arr[left] <= 0) {
8
            left++;  // 移动左索引，直到找到正数
9
        }
10
        while (left < right && arr[right] > 0) {
11
            right--;  // 移动右索引，直到找到非正数
12
        }
13
        if (left < right) {
14
            int tmp = arr[left];
15
            arr[left] = arr[right];
16
            arr[right] = tmp;
17
        }
18
    }
19
}

以上。

扩展：荷兰国旗问题

_Gn!
荷兰国旗问题（也称为三色排序问题）是一个计算机科学中的经典问题，常用于讨论快速排序算法的三向分区(three-way-partitioning)策略。
这个问题来源于荷兰国旗的三种颜色：红色、白色和蓝色，目标是将含有三种颜色的条带（通常用0, 1, 2来代表三种颜色）重新排序，使得同一颜色的条带聚集在一起，并且顺序是红、白、蓝（或0、1、2）。
现在给定一个整型数组，其中包含不确定数量的三个元素0、1、2，请将该整数数组分区为三个部分：0在前面，1在中间，2在最后面。
举例：
整型数组为：[0, 1, 2, 2, 1, 0, 0, 2, 1, 1, 0, 2]
分区后的结果是：[0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2]
由于进行的是三向分区，那么单纯的双指针法就无法实现了，这时要使用"三指针法"。其算法的思路是：
创建一个"左索引left"指向数组左边界(首元素)，创建一个"右索引right"指向数组的右边界(尾元素)，创建一个"中间索引mid"开始时也指向数组首元素
利用中间索引mid来遍历整个数组。
左索引left的作用是：标记下一个0元素应该放置的位置（小于基准值的元素应放置的位置）
中间索引mid的作用是：标记下一个1元素应该放置的位置（等于基准的元素应放置的位置）
右索引right的作用是：标记下一个2元素应该放置的位置（大于基准的元素应放置的位置）
核心操作思路是：
遍历数组，条件是mid <= high，在这个过程中：
如果 mid 位置的元素是0，则需要将mid位置和left位置的元素交换，然后 left 和 mid索引都加1。这里为什么两个索引都需要加1呢？请看下图：
如果 mid位置的元素是1，那么不需要任何交换，只需要mid索引加1即可。这个很好理解，不解释了。
如果mid位置的元素是2，则需要将mid位置和right位置的元素交换，然后 right 索引需要减1。这里的问题是：为什么mid索引就不需要加1了呢？仍然请看下图：
遍历结束时，数组的三个分区就分区完成了。
参考代码实现如下：
参考代码如下：
x
1
#define SWAP(arr, i, j) { \
2
 int temp = arr[i]; \
3
 arr[i] = arr[j]; \
4
 arr[j] = temp; \
5
}
6

7
void three_partition(int arr[], int size) {
8
    int left = 0, mid = 0, right = size - 1;
9
    while (mid <= right) {
10
        switch (arr[mid]) {
11
            case 0:
12
                if (mid != left) {
13
                    SWAP(arr, mid, left);
14
               }
15
                mid++;
16
                left++;
17
                break;
18
            case 1:
19
                mid++;
20
                break;
21
            case 2:
22
                SWAP(arr, mid, right);
23
                right--;
24
                break;
25
       }
26
   }
27
}
以上。

扩展：三向分区负数、0以及正数

_Gn!

如果你已经搞清楚了荷兰国旗问题，那么这个问题就比较简单了。

比如：
数组[1, -2, 3, 0, -9, 0, 10, 3]
最终分组完成后的效果应该是[负数, 0, 0, 正数]（稳定性不做要求）

思路是：仍然是三个索引：

left索引标记下一个负数放置的位置
mid索引用于遍历数组，并且标记0元素放置的位置
right索引用标记下一个正数放置的位置

核心操作逻辑是：

当mid索引发现一个负数时，交换left和mid索引位置的元素，并后移1位mid和left索引（原理是一样的）
当mid索引发现一个0时，不需要交换元素，仅需要mid索引后移1位
当mid索引发现一个正数时，交换right和mid索引位置的元素，仅后移1位right索引，mid索引不动。

当mid索引遍历完整个数组，这个三向分区操作就完成了。

参考代码实现如下：

参考代码如下：


x
1
void three_way_partition(int arr[], int size) {
2
    int left = 0, mid = 0, right = size - 1;
3

4
    while (mid <= right) {
5
        if (arr[mid] < 0) {
6
            // 交换arr[low]和arr[mid]，并移动low和mid索引
7
            if (mid != left) {
8
                SWAP(arr, mid, left);
9
            }
10
            left++;
11
            mid++;
12
        }
13
        else if (arr[mid] == 0) {
14
            // 如果是0，只移动mid索引
15
            mid++;
16
        }
17
        else {
18
            // 交换arr[mid]和arr[high]，并移动high索引
19
            SWAP(arr, mid, right);
20
            right--;
21
        }
22
    }
23
}

以上。

C++基础教程——作业及参考答案全部汇总文档节4指针和数组阶段作业最新版本V2.0王道C++团队COPYRIGHT ⓒ 2021-2024. 王道版权所有

基础题篇

数组与指针基础练习题1

参考代码：

数组与指针基础练习题2

参考代码：

数组与指针基础练习题3

参考代码：

数组与指针基础练习题4

参考代码如下：

扩展题篇

扩展：数组分区思想

扩展：合并两个有序子数组

参考代码：

扩展：分离非负数以及正数

参考代码：

扩展：荷兰国旗问题

参考代码如下：

扩展：三向分区负数、0以及正数

参考代码如下：

The End

_{C++基础教程}
——
作业及参考答案全部汇总文档
^{_节4指针和数组阶段作业}

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