已排序字符串矩阵归并为全局有序数组的C语言代码问题排查

Hey there! Let's break down what's wrong with your current code and fix it to properly merge all the sorted rows into a single globally sorted array.

🔍 What's Wrong with the Current Code? #

Your function has three critical issues that prevent it from working correctly:

• Variable Name Collision: You named your column count parameter co, but also have a counter variable c inside the function. When you print with i < (r*c), you're using the counter c (which holds the number of elements added so far) instead of the column count co, leading to out-of-bounds array access.
• Incorrect Merging Logic: Right now, you're only merging adjacent pairs of rows (row i and row i+1) and appending the result to c1 each time. This doesn't produce a single sorted array—instead, it just concatenates multiple merged pairs, which is totally wrong when you have more than 2 rows.
• Memory Allocation Bug: When you allocate space for each string with malloc(strlen(mat[i][a])*sizeof(char)), you forget to account for the null terminator \0 at the end of every C string. This will cause strcpy to write past the allocated memory, leading to undefined behavior.

✅ Fixed Implementation (Iterative Merging) #

Here's a corrected version that uses iterative merging: first merge the first two rows into a temporary sorted array, then merge that result with the third row, and so on until all rows are merged into one global sorted array.

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

// Helper function to merge two sorted string arrays into one sorted array
char** mergeTwoSortedArrays(char** arr1, int len1, char** arr2, int len2, int* outLen) {
    *outLen = len1 + len2;
    char** merged = malloc(*outLen * sizeof(char*));
    if (!merged) return NULL;

    int i = 0, j = 0, k = 0;
    while (i < len1 && j < len2) {
        int cmp = strcmp(arr1[i], arr2[j]);
        if (cmp <= 0) {
            // Allocate space including null terminator
            merged[k] = malloc(strlen(arr1[i]) + 1);
            strcpy(merged[k], arr1[i]);
            i++;
        } else {
            merged[k] = malloc(strlen(arr2[j]) + 1);
            strcpy(merged[k], arr2[j]);
            j++;
        }
        k++;
    }

    // Copy remaining elements from arr1
    while (i < len1) {
        merged[k] = malloc(strlen(arr1[i]) + 1);
        strcpy(merged[k], arr1[i]);
        i++;
        k++;
    }

    // Copy remaining elements from arr2
    while (j < len2) {
        merged[k] = malloc(strlen(arr2[j]) + 1);
        strcpy(merged[k], arr2[j]);
        j++;
        k++;
    }

    return merged;
}

void orderMat(char ***mat, int r, int co) {
    if (r == 0 || co == 0) return;

    // Start with the first row as the initial merged array
    int currentLen = co;
    char** currentMerged = malloc(currentLen * sizeof(char*));
    if (!currentMerged) return;
    for (int i = 0; i < co; i++) {
        currentMerged[i] = malloc(strlen(mat[0][i]) + 1);
        strcpy(currentMerged[i], mat[0][i]);
    }

    // Merge with each subsequent row one by one
    for (int row = 1; row < r; row++) {
        int newLen;
        char** temp = mergeTwoSortedArrays(currentMerged, currentLen, mat[row], co, &newLen);
        // Free the previous merged array to avoid memory leaks
        for (int i = 0; i < currentLen; i++) {
            free(currentMerged[i]);
        }
        free(currentMerged);
        currentMerged = temp;
        currentLen = newLen;
    }

    // Print the final sorted array
    printf("Mat ordered:\n");
    for (int i = 0; i < currentLen; i++) {
        printf("%s ", currentMerged[i]);
        free(currentMerged[i]); // Free each string after printing
    }
    printf("\n");
    free(currentMerged); // Free the array itself
}

// Example test case
int main() {
    // Create the input matrix: row 0 = {"fbc", "zfb"}, row 1 = {"abc", "tuv"}
    char*** mat = malloc(2 * sizeof(char**));
    mat[0] = malloc(2 * sizeof(char*));
    mat[0][0] = strdup("fbc");
    mat[0][1] = strdup("zfb");
    mat[1] = malloc(2 * sizeof(char*));
    mat[1][0] = strdup("abc");
    mat[1][1] = strdup("tuv");

    orderMat(mat, 2, 2);

    // Clean up input matrix
    for (int i = 0; i < 2; i++) {
        free(mat[i][0]);
        free(mat[i][1]);
        free(mat[i]);
    }
    free(mat);

    return 0;
}

📝 How It Works #

1. Helper Function mergeTwoSortedArrays: This takes two sorted string arrays, merges them into a single sorted array using the standard two-pointer technique (just like merging two sorted lists), and returns the merged array along with its length. It also fixes the memory allocation bug by adding 1 for the null terminator.
2. Iterative Merging: We start with the first row as our initial sorted array. Then, we merge this array with each subsequent row one by one, updating our merged array each time. This ensures that after each step, we have a single sorted array containing all rows processed so far.
3. Memory Management: We carefully free all allocated memory to avoid leaks—this includes freeing each string in the merged array and the array itself after printing.

🚀 Bonus: More Efficient Multiplex Merge (Using a Min-Heap) #

If you have a large number of rows (r is big), the iterative approach has a time complexity of O(rcr) = O(r²c). A more efficient approach uses a min-heap (priority queue) to track the smallest current element from each row, leading to O(rclog r) time complexity. Here's a quick outline:

• Each heap element stores the string, its row index, and its column index in that row.
• Initialize the heap with the first element of each row.
• Extract the smallest element from the heap, add it to the result, and if there's a next element in that row, push it into the heap.
• Repeat until the heap is empty.

This is better for large r, but the iterative approach is simpler to understand for small to medium r.

内容的提问来源于stack exchange，提问作者Big-D