Le caractère qui apparaît le plus souvent dans la liste chaînée

Nous recevons une liste de caractères chaînés, et notre tâche est d'imprimer le caractère qui apparaît le plus fréquemment dans la liste chaînée. Si plusieurs caractères apparaissent le même nombre de fois, la dernière occurrence du caractère est imprimée.

Une liste chaînée unique est une structure de données linéaire composée de nœuds. Chaque nœud contient des données et un pointeur vers le nœud suivant, qui contient l'adresse mémoire du nœud suivant car la mémoire allouée à chaque nœud n'est pas contiguë.

Exemple

Supposons que nous ayons reçu une liste de liens de personnages

Exemple 1

Entrée : LL = a -> b -> c -> c -> c

Sortie : le caractère le plus courant est c.

Explication : Dans la liste chaînée donnée LL, a apparaît une fois, b apparaît une fois et c apparaît 3 fois. Par conséquent, la sortie est c.

Exemple 2

Entrez :

LL = x -> x -> y -> y -> z -> z

Sortie : le plus grand caractère présent est z.

Explication : Dans la liste chaînée donnée LL, x apparaît 2 fois, y apparaît 2 fois et z apparaît 2 fois. Toutes les occurrences sont identiques car z apparaît en dernier, donc la sortie est z.

Ici, nous discuterons de deux méthodes. Jetons un coup d'œil aux parties ci-dessous -

Méthode 1 : Calculer la fréquence de manière itérative

L'idée de cette méthode est que nous allons parcourir la liste chaînée et calculer la fréquence de chaque caractère, puis trouver le caractère avec la fréquence la plus élevée, et si plusieurs caractères ont la même fréquence, imprimer ce caractère et renvoyer le dernier caractère .

Exemple

#include <iostream>
using namespace std;
// creating a class to have a structure for linked list nodes 
class Node{
   public:
   char data; // variable to store the characters
   Node* next = NULL; // variable to store the address of the next node     
   Node(char cur){
      data = cur;
   }
};
// function to print the elements of the linked list 
void printLL(Node* head){   
   // creating a temporary pointer 
   Node* temp = head;    
   while(temp != nullptr){
      cout<<temp->data<<" -> ";
      temp = temp->next;
   }
   cout<<"NULL"<<endl;
}
// function to find the max frequency 
void maxFreq(Node* head){
   // traversing over the linked list for each character 
   // starting from the first character to the last character     
   int ans = 0; // variable to store the maximum frequency 
   char char_ans;
   Node* temp_first = head; // variable to store the current first node     
   while(temp_first != nullptr){
      int cur = 0; // variable to store the frequency of the current character 
      Node* temp = temp_first;        
      while(temp != nullptr){
         if(temp->data == temp_first->data){
            cur++;
         }
         temp = temp->next;
      }
      if(ans < cur){
         ans = cur;
         char_ans = temp_first->data;
      }
      temp_first = temp_first->next;
   }
   cout<<"The last character in the given linked list is '"<<char_ans<<"' with the frequency of "<< ans<<endl;
}
// main function 
int main(){
   // defining the linked list 
   Node* head = new Node('a');
   head->next = new Node('b');
   head->next->next = new Node('b');
   head->next->next->next = new Node('c');
   head->next->next->next->next = new Node('d');
   head->next->next->next->next->next = new Node('d');
   head->next->next->next->next->next->next = new Node('d');  
   cout<<"The given linked list is: "<<endl;
   printLL(head);   
   maxFreq(head);
   return 0;
}

Sortie

The given linked list is: 
a -> b -> b -> c -> d -> d -> d -> NULL
The last character in the given linked list is 'd' with the frequency of 3

Complexité temporelle

 : O(N*N), où N est la taille de la liste chaînée.

Complexité spatiale : O(1)

Méthode 2 : Utiliser un tableau de comptage

L'idée de cette approche est que nous maintiendrons un tableau de décomptes dans lequel nous stockerons la fréquence de chaque caractère, puis parcourrons le tableau et trouverons le caractère de fréquence la plus élevée. Si plusieurs caractères ont la même fréquence, imprimez ce caractère puis renvoyez le dernier caractère.

Exemple

#include <iostream>
using namespace std;
// creating a class to have a structure for linked list nodes 
class Node{
   public:
   char data; // variable to store the characters
   Node* next = NULL; // variable to store the address of the next node     
   Node(char cur){
      data = cur;
   }
};
// function to print the elements of the linked list 
void printLL(Node* head){    
   // creating a temporary pointer 
   Node* temp = head;    
   while(temp != nullptr){
      cout<<temp->data<<" -> ";
      temp = temp->next;
   }
   cout<<"NULL"<<endl;
}
// function to find the max frequency 
void maxFreq(Node* head){
   int ans = 0; // variable to store the maximum frequency 
   char char_ans;    
   // traversing over the linked list for each lowercase character 
   for(char i = 'a'; i<= 'z'; i++){
      Node* temp = head;
      int cur = 0; // variable to store the frequency of the current character 
      while(temp != nullptr){
         if(temp->data == i){
            cur++;
         }
         temp = temp->next;
      }
      if(ans <= cur){
         ans = cur;
         char_ans = i;
      }
   }     
   cout<<"The last character in the given linked list is '"<<char_ans<<"' with the frequency of "<< ans<<endl;
}
int main(){
   // defining the linked list 
   Node* head = new Node('a');
   head->next = new Node('b');
   head->next->next = new Node('b');
   head->next->next->next = new Node('c');
   head->next->next->next->next = new Node('e');
   head->next->next->next->next->next = new Node('d');
   head->next->next->next->next->next->next = new Node('d');  
   cout<<"The given linked list is: "<<endl;
   printLL(head);   
   maxFreq(head);
   return 0;
}

Sortie

The given linked list is: 
a -> b -> b -> c -> e -> d -> d -> NULL
The last character in the given linked list is 'd' with the frequency of 2

Complexité temporelle

O(N), où N est la taille de la liste chaînée.

Complexité spatiale : O(N), où N est la taille de la liste chaînée.

Conclusion

Nous discutons ici de la façon de trouver les caractères les plus fréquents dans une liste chaînée. Pour trouver l’occurrence maximale de caractères, nous avons discuté de deux méthodes. La première méthode utilise une boucle while pour chaque caractère de la liste chaînée donnée et la deuxième méthode utilise une boucle for pour chaque caractère minuscule et maintient le décompte.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!