异常教程

C 练习实例76（千字长文）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战(已更新的所有项目都能学习) / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

  • 新开坑项目:《Spring AI 项目实战》 正在持续爆肝中，基于 Spring AI + Spring Boot 3.x + JDK 21...， 点击查看 ;
  • 《从零手撸：仿小红书（微服务架构）》 已完结，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;演示链接： http://116.62.199.48:7070 ;
  • 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

前言：走进 C 练习实例76 的核心逻辑

在 C 语言的学习旅程中，练习实例不仅是检验知识的试金石，更是深化理解的阶梯。"C 练习实例76" 是一个经典的算法实践课题，它聚焦于数组合并与排序的综合应用。本文将通过分步解析、代码示例以及常见误区的剖析，带领读者逐步掌握这一实例的核心逻辑，同时帮助编程初学者和中级开发者建立系统化的算法思维。

问题背景与目标：理解实例76的挑战

问题描述

假设你有两个已排序的整数数组 arrayA 和 arrayB，它们的长度分别为 sizeA 和 sizeB。你的任务是编写一个 C 程序，将这两个数组合并为一个新的有序数组 mergedArray，且不允许使用额外的排序算法（如快速排序或冒泡排序）。

核心挑战

  • 有序合并：如何在不打乱原有顺序的前提下，高效地将两个有序数组合并为一个新数组？
  • 空间管理：由于 C 语言的静态内存特性，需预先分配足够内存空间存储合并后的数组。
  • 边界条件：如何处理其中一个数组元素全部合并完成后的剩余元素？

算法思路分析：从比喻到逻辑的转化

比喻理解：快递分拣站的合并流程

想象两个快递分拣站，每个站的包裹按重量从小到大排列。你的任务是将这两个站点的包裹合并到一个新站点，并保持重量的升序排列。这与实例76的核心逻辑高度相似：

  • 双指针策略：使用两个“快递员”分别指向两个数组的当前元素。
  • 逐项对比：每次比较两个“快递员”所在位置的包裹重量，将较轻的包裹放入新站点。
  • 指针移动：取出包裹后，对应的快递员向前移动一位。

算法步骤分解

  1. 初始化指针：定义三个指针 i（指向 arrayA）、j（指向 arrayB）、k（指向 mergedArray）。
  2. 循环对比：当 i < sizeA 且 j < sizeB 时，比较 arrayA[i] 和 arrayB[j] 的值。
  3. 较小值入列：将较小的值存入 mergedArray[k]，并移动对应的指针（i 或 j）和 k。
  4. 处理剩余元素：当其中一个数组遍历完毕后，将另一个数组的剩余元素直接拷贝到 mergedArray。

代码实现：从逻辑到 C 语言的落地

完整代码示例

#include <stdio.h>  
#include <stdlib.h>  

void merge_arrays(int *arrayA, int sizeA, int *arrayB, int sizeB, int *mergedArray) {  
    int i = 0, j = 0, k = 0;  

    // 双指针循环对比  
    while (i < sizeA && j < sizeB) {  
        if (arrayA[i] < arrayB[j]) {  
            mergedArray[k++] = arrayA[i++];  
        } else {  
            mergedArray[k++] = arrayB[j++];  
        }  
    }  

    // 处理剩余元素  
    while (i < sizeA) {  
        mergedArray[k++] = arrayA[i++];  
    }  
    while (j < sizeB) {  
        mergedArray[k++] = arrayB[j++];  
    }  
}  

int main() {  
    int arrayA[] = {1, 3, 5, 7};  
    int sizeA = sizeof(arrayA) / sizeof(arrayA[0]);  
    int arrayB[] = {2, 4, 6, 8, 10};  
    int sizeB = sizeof(arrayB) / sizeof(arrayB[0]);  

    int mergedSize = sizeA + sizeB;  
    int *mergedArray = (int *)malloc(mergedSize * sizeof(int));  

    merge_arrays(arrayA, sizeA, arrayB, sizeB, mergedArray);  

    printf("Merged Array: ");  
    for (int i = 0; i < mergedSize; i++) {  
        printf("%d ", mergedArray[i]);  
    }  
    free(mergedArray);  
    return 0;  
}

代码解析

  1. 函数设计：merge_arrays 函数接收两个输入数组及其长度，以及预分配的 mergedArray。
  2. 双指针移动：通过 i++ 和 j++ 实现指针的同步或异步移动，确保时间复杂度为 O(n + m)。
  3. 内存管理：在 main 函数中动态分配内存，避免静态数组的大小限制，合并完成后释放内存。

知识点拓展：深入理解关键概念

指针与内存管理

在 C 语言中，指针是访问内存地址的“钥匙”。例如，mergedArray[k++] = arrayA[i++]; 这一行代码：

  • arrayA[i] 通过指针 i 访问 arrayA 的当前元素。
  • k++ 通过后缀自增操作，使指针 k 每次递增后指向下一个内存位置。

比喻：想象指针是快递员手中的扫描枪，每次扫描后自动跳转到下一个包裹的位置。

时间与空间复杂度分析

  • 时间复杂度：合并过程需遍历所有元素一次，因此为 O(n + m)，其中 n 和 m 是两个数组的长度。
  • 空间复杂度：合并后的数组需要额外的 O(n + m) 空间，但这是题目的必要条件。

常见错误与调试技巧

错误场景1：指针越界

错误示例：

while (i <= sizeA && j <= sizeB) { ... }

问题：数组索引从 0 开始，i < sizeA 才是正确的终止条件。若使用 <=，可能导致访问无效内存。

错误场景2：未处理剩余元素

错误示例：

// 缺少对剩余元素的拷贝  
while (i < sizeA && j < sizeB) { ... }

修复：必须通过两个额外的循环，将未遍历完的数组元素拷贝到 mergedArray。

优化与进阶思考

优化点：减少内存分配次数

若多次合并操作，可以复用已分配的 mergedArray，避免频繁调用 malloc 和 free。

进阶挑战

  1. 逆序合并：将合并后的数组按降序排列。
  2. 原地合并：尝试在不使用额外数组的情况下，直接修改其中一个数组的结构完成合并。

结论：从实例76到算法思维的提升

通过“C 练习实例76”的实践，我们不仅掌握了数组合并的算法逻辑，更深刻理解了指针操作、循环控制以及内存管理在 C 语言中的重要性。这个实例如同一面镜子，映射出编程思维的核心：将抽象问题转化为可执行的逻辑步骤，并通过代码实现细节的打磨，最终达成目标。

无论是初学者还是中级开发者，都可以通过类似实例不断精进自己的技能。建议读者尝试修改输入数组的值或调整合并条件，进一步巩固对算法的理解。编程的真谛，往往就在这样的实践与反思中逐步显现。

最新发布

查看更多文章