C语言实现O(n)复杂度归并两个升序数组到第三数组的编译错误求助

现存代码的核心编译与逻辑错误 #

• 函数结构语法非法：代码将malloc语句写在函数签名与函数体大括号之间，完全不符合C语言语法规范，会直接触发编译失败。
• 形参非法覆写：形参a、b是主函数传入的已初始化的升序数组指针，原代码对其执行malloc赋值，既会因为形参是输入数组的引用导致逻辑完全错位，也会因为const修饰的指针不可修改触发编译错误。
• 内存计算与赋值非法：
  • 原代码开头定义了全局栈数组int c[LEN1+LEN2]，数组名是地址常量，无法被直接赋值malloc的返回值
  • malloc的内存大小计算存在运算符优先级问题：sizeof(int)*alen+blen实际是(sizeof(int)*alen) + blen，远小于需要的总长度，会造成内存越界
• 函数缺少返回值：声明的函数返回值类型是int*，但函数执行完合并逻辑后没有返回结果数组的指针，主函数接收到的是随机野指针。
• 缺少依赖头文件：使用malloc、free函数需要引入stdlib.h，否则会触发隐式函数声明的编译警告/错误。

可运行的正确实现 #

#include <stdio.h>
#include <stdlib.h>  // 引入malloc/free所需头文件

#define LEN1    4
#define LEN2    5

// 函数声明和给定的主函数保持一致
int *merge(const int a[], int alen, const int b[], int blen); 

int *merge(const int a[], int alen, const int b[], int blen)
{
    int i = 0, j = 0, k = 0;
    // 按两个数组的总长度分配堆内存，注意括号保证长度计算正确
    int *c = malloc(sizeof(int) * (alen + blen));
    if (c == NULL) {  // 内存分配健壮性判断
        return NULL;
    }

    // 双指针遍历两个输入数组，完成有序合并
    while (i < alen && j < blen) {
        if (a[i] < b[j]) {
            c[k++] = a[i++];
        } else {
            c[k++] = b[j++];
        }
    }
    // 处理其中一个数组遍历完成后，另一个数组的剩余元素
    while (i < alen) {
        c[k++] = a[i++];
    }
    while (j < blen) {
        c[k++] = b[j++];
    }

    return c;  // 返回分配好的结果数组指针，匹配函数签名
}

int main() {
    int a[LEN1] = { 1, 2, 3, 8 };
    int b[LEN2] = { -1, 2, 4, 7, 11 };
    int *m;   
    int *mp;  

    m = merge(a, LEN1, b, LEN2);
    mp = m;
    for (int i = 0; i < LEN1 + LEN2; i++)
        printf("/%d", *mp++);
    free(m);
    printf("\n");
    return 0;
}

实现说明 #

• 归并过程仅通过三个单向移动的指针完成遍历，无回溯操作，时间复杂度为O(n)，n为两个输入数组的长度和。
• 结果数组通过堆内存分配，和主函数中的free(m)逻辑匹配，无内存泄漏。
• 合并后的数组严格保持升序，符合需求。

内容的提问来源于stack exchange，提问作者eOmega