c - 在 C 中通过排序添加优先级 | qsort()

Question

我正在尝试解决这个代码大战 kata

这就是它的要点

Given two strings s1 and s2, we want to visualize how different the two strings are. We will only take into account the lowercase letters (a to z). First let us count the frequency of each lowercase letters in s1 and s2.

s1 = "A aaaa bb c"

s2 = "& aaa bbb c d"

s1 has 4 'a', 2 'b', 1 'c'

s2 has 3 'a', 3 'b', 1 'c', 1 'd'

So the maximum for 'a' in s1 and s2 is 4 from s1; the maximum for 'b' is 3 from s2. In the following we will not consider letters when the maximum of their occurrences is less than or equal to 1.

<小时/>

s1 = "my&friend&Paul has heavy hats! &"
s2 = "my friend John has many many friends &"
mix(s1, s2) --> "2:nnnnn/1:aaaa/1:hhh/2:mmm/2:yyy/2:dd/2:ff/2:ii/2:rr/=:ee/=:ss"

<小时/>

这是我到目前为止所想到的

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

int compare_letters(const void* a, const void* b){
    const char **ia = (const char **) a;
    const char **ib = (const char **) b;

    const char *sa = *ia;
    const char *sb = *ib;

    return (sa[2] < sb[2]) - (sa[2] > sb[2]);
}

char* mix(char* s1, char* s2){
    int i, j;
    char s1_rf[strlen(s1)];
    char s2_rf[strlen(s2)];
    int s1_n[26] = {0}, s2_n[26] = {0};

    i = 0;
    for(int x = 0; x < strlen(s1); x++){
        if('a' <= s1[x] && s1[x] <= 'z'){
            s1_rf[i] = s1[x];
            s1_n[s1_rf[i] - 'a']++;
            i++;
        }
    }

    i = 0;
    for(int x = 0; x < strlen(s2); x++){
        if('a' <= s2[x] && s2[x] <= 'z'){
            s2_rf[i] = s2[x];
            s2_n[s2_rf[i] - 'a']++;
            i++;
        }
    }

    char* combined_string[26];

    int size_s = 0;
    for(char ch = 'a'; ch <= 'z'; ch++) {
        if(s1_n[ch - 'a'] != s2_n[ch - 'a']) {
            if (s1_n[ch - 'a'] > 1) {
                combined_string[size_s] = malloc(sizeof("3D4"));
                sprintf(combined_string[size_s], "1:%d%c", s1_n[ch - 'a'], ch);
                size_s++;
            }

            if (s2_n[ch - 'a'] > 1) {
                combined_string[size_s] = malloc(sizeof("3D4"));
                sprintf(combined_string[size_s], "2:%d%c", s2_n[ch - 'a'], ch);
                size_s++;
            }
        }
        else {
            if (s2_n[ch - 'a'] > 1) {
                combined_string[size_s] = malloc(sizeof("3D4"));
                sprintf(combined_string[size_s], "=:%d%c", s2_n[ch - 'a'], ch);
                size_s++;
            }

        }
    }

    qsort(combined_string, (size_t) size_s, sizeof(combined_string[0]), compare_letters);

    char *final_string[size_s];

    j = 0;
    for(int x = 0; x < size_s; x++){
        final_string[j] = malloc(sizeof(combined_string[x]));

        if(combined_string[x][3] == combined_string[x - 1][3]){
        }
        else{
            final_string[j] = combined_string[x];
            j++;
        }
    }

    char *return_string = malloc(sizeof("2:5D"));

    int k = 0;
    for(int x = 0; x < j; x++){
        return_string[k] = final_string[x][0];
        k++;
        return_string[k] = final_string[x][1];
        k++;
        for(int y = 0; y < (final_string[x][2] - '0'); y++){
            return_string[k] = final_string[x][3];
            k++;

        }
        return_string[k] = '/';
        k++;
    }

    char *final_sting = malloc(sizeof(return_string));

    strncpy(final_sting, return_string, (size_t) (k - 1));

    puts(final_sting);

}


int main(int argc, char** argv){
    char s1[] = "Are they here";
    char s2[] = "yes, they are here";

    mix(s1, s2);
}

<小时/>

控制台输出

2:eeeee/=:hh/=:rr/2:yy

<小时/>

预期输出

2:eeeee/2:yy/=:hh/=:rr

如您所见，我的(字母)计数排序方式没有考虑字符串数字。

所以我想知道是否有一种方法可以使用现有的 qsort() 调用或添加另一个可以添加另一层优先级的函数，首先是我的字母计数，如果有两个或更多相等的计数，则它' d 按照字符串编号排序，如果还有未排序，最后按字母顺序排序。

Answer 1

我已经使用链接列表和插入所需的排序标准(出现次数、句子编号、字母顺序)找到了解决您问题的方法。虽然效率不是很高，但看起来效果还不错。抱歉，我没有遵循您的解决方案的步骤，也没有真正回答您有关 qsort 的问题，但也许您可以使用下面的代码。 (您应该使用标志 -std=c11 来编译它。)

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

typedef struct list
{
    int sentence;
    int repeats;
    char character;
    struct list * next;
} * List;

List insertSorted(List l, int s, int n, char c)
{
    List currentNode = l;
    List previousNode = NULL;
    while(currentNode && (currentNode->repeats > n || (currentNode->repeats == n && currentNode->sentence <= s)))
    {
        previousNode = currentNode;
        currentNode = currentNode->next;
    }
    List newNode = (List) malloc(sizeof(struct list));
    newNode->sentence = s;
    newNode->repeats = n;
    newNode->character = c;
    newNode->next = currentNode;
    if(previousNode) previousNode->next = newNode;
    if(!l || l->repeats < n || (l->repeats == n && l->sentence > s)) l = newNode;
    return l;
}

char * mix(char * s1, char * s2)
{
    char alphasInS1[26];
    char alphasInS2[26];

    for(int i = 0; i < 26; ++i) alphasInS1[i] = alphasInS2[i] = 0;

    int n = 0;
    while(s1[n])
    {
        char c = s1[n];
        if(isalpha(c))
        {
            if(isupper(c)) c = (char) tolower(c);       
            int alphaIndex = ((int) c) - 97;
            ++(alphasInS1[alphaIndex]);
        }
        ++n;
    }

    n = 0;
    while(s2[n])
    {
        char c = s2[n];
        if(isalpha(c))
        {
            if(isupper(c)) c = (char) tolower(c);       
            int alphaIndex = ((int) c) - 97;
            ++(alphasInS2[alphaIndex]);
        }
        ++n;
    }

    int resultSize = 0;
    List alphaList = NULL;

    for(int i = 0; i < 26; ++i)
    {
        if(alphasInS1[i] > 1 || alphasInS2[i] > 1)
        {
            if(alphasInS1[i] > alphasInS2[i])
            {
                resultSize += alphasInS1[i] + 3;
                alphaList = insertSorted(alphaList, 1, alphasInS1[i], (char) (97 + i));
            }
            else if(alphasInS1[i] < alphasInS2[i])
            {
                resultSize += alphasInS2[i] + 3;
                alphaList = insertSorted(alphaList, 2, alphasInS2[i], (char) (97 + i));
            }
            else if (alphasInS1[i] == alphasInS2[i])
            {
                resultSize += alphasInS1[i] + 3;
                alphaList = insertSorted(alphaList, 3, alphasInS1[i], (char) (97 + i));
            }
        }
    }

    if(!alphaList) return (char *) NULL;

    char * result = (char *) malloc(sizeof(char) * (long unsigned) resultSize);

    n = 0;
    do
    {
        result[n++] = alphaList->sentence == 1 ? '1' : alphaList->sentence == 2 ? '2' : '=';
        result[n++] = ':';
        for(int i = 0; i < alphaList->repeats; ++i) result[n++] = alphaList->character;
        result[n++] = '/';
    }
    while((alphaList = alphaList->next));

    result[n - 1] = '\0';

    return result;
}

int main()
{
    char s1[128], s2[128];

    strcpy(s1, "Are they here");
    strcpy(s2, "yes, they are here");

    fprintf(stdout, "%s\n", mix(s1, s2));

    return 0;
}

输出

2:eeeee/2:yy/=:hh/=:rr