在 C 中通过排序添加优先级层 |排序()

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() 调用或添加另一个可以添加另一层优先级的函数，首先是我的字母计数，如果有两个或更多个相等的计数，它会根据字符串编号排序，如果还有一些未排序，最后按字母顺序排序。

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] = '[=10=]';

    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

在 C 中通过排序添加优先级层 |排序()

Adding layers of priority with sorting in C | qsort()

c

sorting

string

qsort