计算出现次数并与 C 中的给定数组关联

Question

我遇到了问题，无法更正我的代码，以便它按我想要的方式工作。

本例中给出了三个数组:

char arr[MAX_ELEMENTS][MAX_LENGTH] = {"ABS","ABS","ABS","ACT","ACT","PPB","PPB","QQQ","QQQ"};
char race[MAX_ELEMENTS][MAX_LENGTH] = {"PARI", "PARI", "LOND", "PARI", "PARI", "CYKA", "LOND", "CYKA", "PARI"};
int freq[MAX_ELEMENTS];

我希望创建一个函数，可以计算 arr[] 中字符串元素的出现次数，并将它们存储在 freq[] 中。除此之外，我还想知道在哪个 race[] 中，给定的 arr[] 出现次数最多。

为了演示这一点，这里是我希望在函数工作时收到的输出的示例:

In Race [PARI] the highest occurence was [ABS] with 3 occurences!
In Race [LOND] the highest occurence was [ACT] with 1 occurences!
.....

目前，我可以计算 freq[] 中 arr[] 的出现次数，但无法将它们与各自的 race[] 关联起来 并给出输出..

for(i=0; i<size; i++)
{
    count = 1;
    for(j=i+1; j<size; j++)
    {
        /* If duplicate element is found */
        if(strcmp(arr[i], arr[j])==0)
        {
            count++;

            /* Make sure not to count frequency of same element again */
            freq[j] = 0;
        }
    }

    /* If frequency of current element is not counted */
    if(freq[i] != 0)
    {
        freq[i] = count;
    }
}

目前给我:

ABS occurs 3 times.
ACT occurs 2 times.
etc. etc...

但我不知道如何将它们与 race[] 关联起来，并且仅在给定的比赛中对它们进行计数。

Answer 1

您可能必须在此处使用 struct 来格式化数据。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define true 1
#define len 100
#define elms 10
struct NODE;
#define  Node struct NODE
struct NODE {
    unsigned long int val;
    int count;
    char name[len];
    Node *left;
    Node *right;
};

Node * makeNode(char * str, unsigned long int val){
    Node * tmp = (Node *)malloc(sizeof(Node));
    strcpy(tmp->name, str);
    tmp->val = val;
    tmp->left = NULL;
    tmp->right = NULL;
    tmp->count = 1;
    return tmp;
}

unsigned long int getHash(char * name){
    int prime = 19;
    int i = 0;
    unsigned long int val = 0;
    while(name[i]!='\0'){
        val += (name[i] * pow(prime, i) );
        ++i;
    }
    return val;
}
void insert(Node * root, char * name){
    Node * newnode;
    int val = getHash(name);
    Node * tmp = root;
    while(tmp != NULL) {
        if ( tmp->val == val){
            tmp->count += 1;
            break;
        }
        if (val > tmp->val){
            if( tmp->right != NULL)
                tmp = tmp->right;
            else{
                tmp->right = makeNode(name, val);
                break;
            }
        }else {
            if( tmp->left != NULL)
                tmp = tmp->left;
            else{
                tmp -> left = makeNode(name, val);
                break;
            }
        }

    }
}

Node * find(Node * root, char * name){
    int val = getHash(name);
    Node * tmp = root;
    while(tmp != NULL){
        if(tmp -> val == val){
            return tmp;
        }else if (val > tmp->val){
            tmp = tmp->right;
        }else{
            tmp = tmp->left;
        }
    }
    return NULL;
}

struct Race {
    char name[len];
    char elements[elms][len];
};

char arr[elms][len] = {"ABS","ABS","ABS","ACT","ACT","PPB","PPB","QQQ","QQQ"};
char race[elms][len] = {"PARI", "PARI", "LOND", "PARI", "PARI", "CYKA", "LOND", "CYKA", "PARI"};
int freq[elms];

void copyArray(char dest[elms][len], char src[elms][len] ){
    int i = 0;
    while(strlen(src[i]) > 0){
        strcpy(dest[i],src[i]);
        ++i;
    }
}

int main(){
    Node * root = makeNode("root", 0);
    int i = 0;
    while(strlen(arr[i]) > 0){
        insert(root,arr[i]);
        ++i;
    }
    i = 0;
    while(strlen(arr[i]) > 0){
        Node * r = find(root,arr[i]);
        printf("found %s, count = %ld\n", r->name, r->count);
        ++i;
    }
    // make representation of race
    struct Race r1, r2;
    strcpy(r1.name, "PARI");
    {
     char  tmp[elms][len] =  { "ABS", "PPB", "QQQ" };
     copyArray(r1.elements, tmp);
    }
    strcpy(r2.name, "LOND");
    {
     char  tmp[elms][len] =  { "ACT" };
     copyArray(r2.elements, tmp);
    }
    struct Race races[2] = {r1, r2};
    i = 0;
    while(i < 2){
        struct Race * current = &races[i];
        printf("for %s", current->name);
        Node * max = NULL;
        int m = -1;
        int j = 0;
        while(strlen(current->elements[j]) > 0){
            Node * tmp = find(root, current->elements[j]);
            if( tmp != NULL && tmp->count > m) { 
                max = tmp;
                m = tmp->count;
            }
            ++j;
        }
        if (max != NULL){
            printf(" max is %s : %d\n", max->name, max->count);
        }else{
            printf(" max is None\n");
        }
    ++i;
    }


   return 0;
}

基本上，您必须格式化数据，并指定它们之间的链接。这里我使用了二叉树和Rabin karp hashing技术来有效地存储数据。

二叉树是解决计数问题的最佳方法，因为搜索操作相当便宜。而Rabin Karp哈希技术将避免每次都进行字符串比较。

我创建了一个名为 Race 的结构来存储该比赛的所有相关元素。所以算法将是。

let arr be array of elements
let races be array of races
for each race in races
    define related element

#find occurrence now
#Binary tree will increment count if element already exist.
let binary_tree be a Binary Tree
for each element in arr
    add element to binary_tree

# now we have all the elements with it's count
# let's iterate through races now
for each race in races
    m = null
    for element in race.elements
        node = find_element_in_binary_tree(element)
        if node is not null
           m = max(m, node)
    if m is not null then
       print m
    else
       print not found