在C语言中使用qsort()实现多层优先级排序的问题

Let's break down the issues in your current code and fix them step by step to meet the problem's requirements.

Key Issues in Your Current Code #

1. Incorrect Entry Generation: You're adding both 1: and 2: entries for the same letter when their counts differ, which violates the problem's rule (we only keep the entry with the higher count for each letter).
2. Incomplete Sorting Logic: Your compare_letters only sorts by count, ignoring the source priority (1 > 2 > =) and alphabetical order for ties.
3. Memory Allocation Mistakes: Fixed-size malloc calls lead to buffer overflows, and your final string construction doesn't account for the total required length.
4. Broken Deduplication: Your attempt to remove duplicate entries is error-prone (out-of-bounds access) and unnecessary if you generate entries correctly in the first place.

Corrected Code #

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

// Comparison function for qsort implementing multi-level priority
int compare_letters(const void* a, const void* b) {
    const char *sa = *(const char**)a;
    const char *sb = *(const char**)b;

    // Extract count: length of string minus 2 (for "X:")
    int count_a = strlen(sa) - 2;
    int count_b = strlen(sb) - 2;

    // 1. Sort by count descending
    if (count_a != count_b) {
        return count_b - count_a; // Higher count comes first
    }

    // 2. Sort by source priority: '1' > '2' > '='
    int prio_a = (sa[0] == '1') ? 3 : (sa[0] == '2') ? 2 : 1;
    int prio_b = (sb[0] == '1') ? 3 : (sb[0] == '2') ? 2 : 1;
    if (prio_a != prio_b) {
        return prio_b - prio_a; // Higher priority comes first
    }

    // 3. Sort by letter ascending
    return sa[2] - sb[2]; // Lex order for same count and source
}

char* mix(char* s1, char* s2){
    int s1_n[26] = {0}, s2_n[26] = {0};

    // Count lowercase letters in s1
    for (int x = 0; s1[x] != '\0'; x++) {
        if (islower(s1[x])) {
            s1_n[s1[x] - 'a']++;
        }
    }

    // Count lowercase letters in s2
    for (int x = 0; s2[x] != '\0'; x++) {
        if (islower(s2[x])) {
            s2_n[s2[x] - 'a']++;
        }
    }

    // Generate valid entries (one per letter, only if max count > 1)
    char* combined_string[26];
    int size_s = 0;
    for (char ch = 'a'; ch <= 'z'; ch++) {
        int c1 = s1_n[ch - 'a'];
        int c2 = s2_n[ch - 'a'];
        int max_c = (c1 > c2) ? c1 : c2;

        if (max_c <= 1) {
            continue; // Skip letters with max count <=1
        }

        char* entry;
        int entry_len = 2 + max_c + 1; // "X:" + max_c chars + null terminator
        entry = malloc(entry_len);
        if (!entry) {
            // Cleanup on allocation failure
            for (int i = 0; i < size_s; i++) free(combined_string[i]);
            return NULL;
        }

        if (c1 > c2) {
            entry[0] = '1';
            entry[1] = ':';
            memset(entry + 2, ch, max_c);
            entry[2 + max_c] = '\0';
        } else if (c2 > c1) {
            entry[0] = '2';
            entry[1] = ':';
            memset(entry + 2, ch, max_c);
            entry[2 + max_c] = '\0';
        } else {
            entry[0] = '=';
            entry[1] = ':';
            memset(entry + 2, ch, max_c);
            entry[2 + max_c] = '\0';
        }

        combined_string[size_s++] = entry;
    }

    // Sort entries using our custom comparator
    qsort(combined_string, size_s, sizeof(char*), compare_letters);

    // Calculate total length of final string
    int total_len = 0;
    for (int i = 0; i < size_s; i++) {
        total_len += strlen(combined_string[i]);
        if (i != size_s - 1) {
            total_len += 1; // Add '/' separator length
        }
    }

    // Allocate final string
    char* return_string = malloc(total_len + 1);
    if (!return_string) {
        for (int i = 0; i < size_s; i++) free(combined_string[i]);
        return NULL;
    }

    // Build the final string by concatenating entries with '/'
    char* ptr = return_string;
    for (int i = 0; i < size_s; i++) {
        strcpy(ptr, combined_string[i]);
        ptr += strlen(combined_string[i]);
        if (i != size_s - 1) {
            *ptr++ = '/';
        }
    }
    *ptr = '\0';

    // Cleanup temporary entries
    for (int i = 0; i < size_s; i++) {
        free(combined_string[i]);
    }

    return return_string;
}

int main(int argc, char** argv){
    char s1[] = "Are they here";
    char s2[] = "yes, they are here";
    char* result = mix(s1, s2);
    puts(result);
    free(result); // Don't forget to free the allocated memory
    return 0;
}

Key Changes Explained #

1. Entry Generation:

   • For each letter, we only create one entry: the one with the higher count (or = if counts are equal).
   • We use memset to safely fill the repeated letters, avoiding sprintf format issues.
   • Properly calculate the entry length to prevent buffer overflows.

2. Multi-Level Sorting:

   • First, sort by count in descending order (higher counts come first).
   • For ties, sort by source priority: 1 (highest) → 2 → = (lowest). We assign numerical priorities to make comparison easy.
   • For remaining ties (same count and source), sort by the letter in ascending alphabetical order.

3. Memory Management:

   • Calculate the exact total length needed for the final string before allocating, ensuring no overflow.
   • Clean up all temporary allocated memory to avoid leaks.
   • Added error checking for malloc failures.

4. Simplified Logic:

   • Removed the unnecessary s1_rf and s2_rf arrays (we don't need to store filtered characters, just count them).
   • Removed the broken deduplication step since we now generate only one entry per letter.

Testing your sample input will now produce the expected output: 2:eeeee/2:yy/=:hh/=:rr.

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