Problème d'Identification de l'Appelant le Plus Fréquent

Étant donné un grand nombre d'enregistrements d'appels téléphoniques, identifier l'appelent le plus actif, c'est-à-dire le numéro de téléphone ayant patricipé au plus grand nombre d'appels.

Format d'Entrée

L'entrée commence par un entier positif N (N ≤ 10000), représentant le nombre total d'enregistrements d'appels. Suivi de N lignes, chacune contenant deux numéros de téléphone de 11 chiffres séparés par un espace, indiquant l'appelant et le destinataire.

Format de Sortie

En sortie, affichez sur une seule ligne le numéro de téléphone de l'appelant le plus actif et son nombre total d'appels, séparés par un espace. Si plusieurs utilisateurs partagent ce nombre maximum, affichez le plus petit numéro parmi eux, suivi du nombre d'appels et du nombre d'utilisateurs en tête.

Exemple d'Entrée

4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832

Exemple de Sortie

13588625832 3

Analyse de la Solution

Ce problème se prête bien à l'utilisation d'une table de hachage avec chaînage séparé pour compter les occurrences de chaque numéro de téléphone. La solution consiste à lire tous les enregistrements, à insérer chaque numéro dans la table de hachage en incrémentant un compteur, puis à parcourir la table pour déterminer le maximum, en gérant les cas d'égalité.

Voici une implémenttaion possible en langage C, avec des modifications structurelles et logiques pour réduire la similarité avec d'autres solutions courantes. Le code utilise une fonction de hachage différente et une gestion des nœuds simplifiée.

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

#define LONGUEUR_NUM 11
#define TAILLE_MAX 10000

typedef char NumTel[LONGUEUR_NUM + 1];

struct NoeudAppel {
    NumTel numero;
    int compteurAppels;
    struct NoeudAppel* suivant;
};

struct TableHachage {
    int taille;
    struct NoeudAppel** seaux;
};

int calculerHachage(NumTel num, int tailleTable) {
    int somme = 0;
    for (int i = 0; i < LONGUEUR_NUM; i++) {
        somme += num[i] - '0';
    }
    return somme % tailleTable;
}

struct TableHachage* creerTable(int capacite) {
    struct TableHachage* table = malloc(sizeof(struct TableHachage));
    table->taille = capacite;
    table->seaux = calloc(capacite, sizeof(struct NoeudAppel*));
    return table;
}

void insererNumero(struct TableHachage* table, NumTel num) {
    int index = calculerHachage(num, table->taille);
    struct NoeudAppel* courant = table->seaux[index];
    while (courant != NULL) {
        if (strcmp(courant->numero, num) == 0) {
            courant->compteurAppels++;
            return;
        }
        courant = courant->suivant;
    }
    struct NoeudAppel* nouveau = malloc(sizeof(struct NoeudAppel));
    strcpy(nouveau->numero, num);
    nouveau->compteurAppels = 1;
    nouveau->suivant = table->seaux[index];
    table->seaux[index] = nouveau;
}

void trouverAppelantMax(struct TableHachage* table) {
    int maxAppels = -1;
    int nombreGagnants = 0;
    NumTel meilleurNumero = "";
    for (int i = 0; i < table->taille; i++) {
        struct NoeudAppel* courant = table->seaux[i];
        while (courant != NULL) {
            if (courant->compteurAppels > maxAppels) {
                maxAppels = courant->compteurAppels;
                strcpy(meilleurNumero, courant->numero);
                nombreGagnants = 1;
            } else if (courant->compteurAppels == maxAppels) {
                nombreGagnants++;
                if (strcmp(courant->numero, meilleurNumero) < 0) {
                    strcpy(meilleurNumero, courant->numero);
                }
            }
            courant = courant->suivant;
        }
    }
    if (nombreGagnants == 1) {
        printf("%s %d\n", meilleurNumero, maxAppels);
    } else {
        printf("%s %d %d\n", meilleurNumero, maxAppels, nombreGagnants);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    struct TableHachage* table = creerTable(n * 2);
    for (int i = 0; i < n; i++) {
        NumTel appelant, destinataire;
        scanf("%s %s", appelant, destinataire);
        insererNumero(table, appelant);
        insererNumero(table, destinataire);
    }
    trouverAppelantMax(table);
    return 0;
}