Contare il verificarsi del valore di ricerca in un elenco collegato in C ++

Nell'informatica, il conteggio delle istanze di un certo valore in un elenco collegato è un'operazione tipica. Trovare la frequenza di un elemento in un elenco viene spesso eseguito in modo che possa essere utilizzato per l'analisi dei dati, la ricerca e l'ordinamento, tra le altre cose. In un elenco collegato, calcolare il numero di volte in cui un valore appare spesso significa attraversare l'elenco e determinare se il valore di ciascun nodo corrisponde al valore target. Ogni volta che viene scoperta una corrispondenza, viene quindi aumentato il numero di eventi di conteggio. Algoritmi iterativi, ricorsivi e basati su hash possono essere tutti usati per eseguire questa procedura, ognuno con i propri benefici e svantaggi.

In C ++, ci sono numerosi modi per determinare la frequenza con cui un elemento appare in un elenco collegato che include quanto segue:

Metodo iterativo: La tecnica iterativa controlla il campo dati di ciascun nodo mentre attraversa l'elenco collegato per contare le ripetizioni del valore desiderato.

Metodo ricorsivo: L'elenco collegato viene iterato tramite l'utilizzo di una funzione ricorsiva per contare le ripetizioni del valore target.

Metodo della tabella hash: La frequenza del valore target viene restituita utilizzando la tecnica della tabella hash che memorizza la frequenza di ciascun elemento nell'elenco collegato in una tabella hash.

Approccio 1: metodo iterativo

Il metodo iterativo è un approccio per risolvere un problema in cui un'attività viene ripetuta fino a quando non viene soddisfatta una determinata condizione. Implica una sequenza di istruzioni che vengono eseguite ripetutamente, un numero specifico di volte o fino a quando una condizione specifica è soddisfatta. In questo metodo, la soluzione è ottenuta eseguendo una sequenza di calcoli, ciascuno di essi basi sui risultati del calcolo precedente.

Il metodo iterativo può essere utilizzato per risolvere una vasta gamma di problemi, dai semplici calcoli aritmetici a algoritmi complessi. È spesso preferito sul metodo ricorsivo perché è più semplice, più facile da capire e richiede meno sovraccarico in termini di utilizzo della memoria.

// Completa il programma per l'inserimento in un elenco collegato in C++
#includere
Utilizzo dello spazio dei nomi std;
nodo di classe

pubblico:
Int Data;
Nodo *Next;
;
int CountCCurrences (nodo ** headnode, int item)
int count = 0;
Nodo *corrente = *headnode;
mentre (corrente != Null)
if (current-> data == item)
conta ++;

Current = Current-> Next;

Conteggio di ritorno;

void insertatbeginningLinkedList (nodo ** headnode, int data)
// Crea dinamicamente la memoria per questo newnode
Nodo* newNode = new node ();
newnode-> data = data;
newnode-> next = *headnode;
*headnode = newnode;
cout << newNode->dati << " inserted data successfully"
"Nell'elenco collegato" << endl;

void printLinkedList (nodo* nodo)
cout << "\n";
// mentre la condizione si fermerà quando nodo == null
mentre (nodo!= Null)
cout << node->dati << " "; node = node->Prossimo;

cout << "\n" << endl;

int main ()

Nodo* headnode = null;
insertatBeginningLinkedList (& HeadNode, 10);
insertatBeginningLinkedList (& HeadNode, 9);
insertatBeginningLinkedList (& HeadNode, 8);
insertatBeginningLinkedList (& HeadNode, 12);
insertatBeginningLinkedList (& Headnode, 19);
insertatBeginningLinkedList (& HeadNode, 8);
PrintLinkEdList (HeadNode);
int search_item = 8;
cout<<"The number of times "<cout<restituzione 0;

Produzione:

10 Dati inseriti Elenco collegato correttamente
9 Dati inseriti Elenco collegato correttamente
8 Dati inseriti Elenco collegato correttamente
12 Dati inseriti Elenco collegato correttamente
19 Dati inseriti Elenco collegato correttamente
8 Dati inseriti Elenco collegato correttamente
8 19 12 8 9 10
Il numero di volte 8 si verifica è 2

Spiegazione:

Un metodo iterativo per contare le occorrenze di un elemento specifico in un elenco collegato è implementato nel codice precedente.

Il primo passo è definire la classe "nodo" che ha due variabili membri: "dati" che vengono utilizzati per contenere il valore di ciascun nodo e "successivo" che è un riferimento al nodo dopo nell'elenco.

Un dati interi e un doppio puntatore al nodo della testa dell'elenco collegato vengono passati alla funzione insertBeginningLinkedList (). Utilizzando il nuovo nodo (), la memoria di un nuovo nodo viene creata dinamicamente e i dati vengono quindi assegnati al nuovo nodo. Successivamente, aggiorna il nodo principale in modo che sia il nuovo nodo impostando il puntatore successivo del nuovo nodo sul nodo principale precedente.

Il puntatore del nodo della testa dell'elenco collegato e l'elemento da cercare sono i due input dati alla funzione CountCurrences (). La funzione restituisce quante volte l'elemento appare nell'elenco collegato. La funzione inizia impostando la variabile di conteggio su 0 e il riferimento della variabile corrente al nodo principale dell'elenco collegato. Il metodo inizia quindi un ciclo while, che funziona fino a quando la "corrente" non è nulla, un segno che la fine dell'elenco è ancora a portata. La funzione determina se il campo di dati del nodo corrente è uguale al valore dell'obiettivo per ciascuna iterazione del loop (elemento). La variabile di conteggio è aumentata. Se lo è, il ciclo continua fino a quando non abbiamo visitato tutti i nodi nell'elenco, quando la "corrente" viene modificata per indicare il seguente nodo. La funzione restituisce il valore finale del conteggio, che indica il numero di volte in cui l'articolo appare nell'elenco, quando il ciclo è stato completato.

PrintLinkedList (): stampare i valori di tutti i nodi nell'elenco collegato. Prende un puntatore al primo nodo nell'elenco come input.

Nella funzione principale (), viene creato un elenco collegato vuoto inizializzando il nodo principale su null. La funzione utilizza quindi la funzione InsertBeginningLinkedList per inserire diversi valori nell'elenco. Infine, l'elenco viene stampato e il numero di occorrenze del numero 8 viene conteggiato e visualizzato utilizzando le funzioni di CountCurrences e PrintLinkedList.

Attraversiamo l'elenco completo solo una volta. Quindi, la complessità temporale del nostro metodo è O (n), dove n è il numero di nodi nell'elenco.

Approccio 2: metodo ricorsivo

Un metodo ricorsivo è una funzione che si chiama subroutine. L'idea alla base della ricorsione è quella di abbattere un problema in piccoli sottoproblemi fino a quando non diventa abbastanza semplice da essere risolto direttamente. La funzione ricorsiva combina quindi le soluzioni ai sottoproblemi per formare la soluzione al problema originale. Nell'informatica, la ricorsione è ampiamente utilizzata in molti algoritmi e strutture di dati, come l'ordinamento e la ricerca, per ridurre la complessità di risolvere grandi problemi dividendoli in sottoproblemi più piccoli e più facili da risolvere.

#includere
Utilizzo dello spazio dei nomi std;
nodo di classe

pubblico:
Int Data;
Nodo *Next;
;
int CounCCurrenceSRecursive (nodo *headnode, int item)
if (headnode == null)
restituzione 0;

int count = CountCurrenceSRecursive (headnode-> next, elemento);
if (headnode-> data == item)
conta ++;

Conteggio di ritorno;

int main ()
Nodo *headnode = nuovo nodo;
Nodo *secondnode = nuovo nodo;
Nodo *ThirdNode = nuovo nodo;
headnode-> data = 11;
HeadNode-> Next = SecondNode;
SecondNode-> Data = 12;
SecondNode-> Next = ThirdNode;
ThirdNode-> data = 11;
ThirdNode-> Next = null;
int target = 11;
int count = CountCurrencesRecursive (HeadNode, Target);
cout << "Count of " << target << " is: " << count << endl;
restituzione 0;

Produzione:

Il conteggio di 11 è: 2

Spiegazione:

1. La classe nodo, che ha i dati dei membri e successivamente, viene utilizzata per definire un elenco collegato.
2. Un riferimento alla testa dell'elenco collegato e all'elemento da contare sono i due input del metodo CountCurrenceSRecursive ().
3. Quando la testa è uguale a null, il caso iniziale della ricorsione, che fa tornare 0, restituisce 0.
4. RECURIVAMENTE, la funzione si chiama utilizzando il nodo consecutivo dell'elenco collegato.
5. Se i dati del nodo corrente corrispondono al bersaglio dopo la chiamata ricorsiva, il conteggio è aumentato.
6. La funzione restituisce il conteggio totale.
7. L'elemento target è impostato su 11 e un elenco collegato con tre nodi è costruito nella funzione principale.
8. Chiamare il conteccurrencesRecursive () con la testa dell'elenco collegato e l'elemento target come parametri produce il conteggio dell'elemento target.

Approccio 3: metodo della tabella hash

Una struttura di dati chiamata tabella hash consente di eseguire le ricerche di coppia di valore chiave di caso medio in tempo costante O (1). Funziona usando una chiave per calcolare un indice in un array di slot o secchi, da cui è possibile trovare il valore necessario. La tabella hash memorizza le coppie di valore chiave, che sono quindi divise in base alla funzione hash su una varietà di secchi.

Un'implementazione della tabella hash per C ++ è resa possibile dalla mappa non ordinata della libreria di modelli standard (STL). La coppia di valore chiave di archiviazione e recupero può essere eseguita con questo in modo rapido ed efficace. Con la seguente sintassi, viene dichiarato un non ordinato_map:

#includere
UNORDERD_MAP hashtable;

Dove "chiave" indica il tipo di chiavi in ​​una tabella hash e "valore" indica il tipo di valori che sono archiviati all'interno. Utilizzando l'operatore di staffa quadrata [], UNORDERD_MAP consente l'inserimento, la cancellazione e la ricerca della coppia di valore chiave rapido ed efficace. Ad esempio, puoi fare quanto segue per aggiungere una coppia di valore chiave a un non ordinato_map:

hashtable [key] = value;

Il calcolo del valore di hash e il posizionamento della coppia di valore chiave nel secchio appropriato sono entrambi gestiti automaticamente da non ordined_map.

#includere
#includere
Utilizzo dello spazio dei nomi std;
nodo di classe

pubblico:
Int Data;
Nodo *Next;
;
int CountCurrenceShash (nodo *head, int target)
std :: non ordered_map frequenza;
Nodo *corrente = testa;
mentre (corrente != Null)
frequenza [corrente-> data] ++;
Current = Current-> Next;

frequenza di ritorno [target];

int main ()
Nodo *headnode = nuovo nodo;
Nodo *secondnode = nuovo nodo;
Nodo *ThirdNode = nuovo nodo;
headnode-> data = 11;
HeadNode-> Next = SecondNode;
SecondNode-> Data = 12;
SecondNode-> Next = ThirdNode;
ThirdNode-> data = 11;
ThirdNode-> Next = null;
int target = 11;
int count = CountCuRrenceShsh (headnode, target);
cout << "Count of " << target << " is: " << count << endl;
restituzione 0;

Produzione:

Il conteggio di 11 è: 2

Spiegazione:
L'approccio della tabella hash per il conteggio delle occorrenze è implementato dalla funzione CountCuRurrenceSh (). Crea una frequenza non ordinata_map e imposta il suo stato iniziale su una mappa vuota. La funzione aggiorna quindi il conteggio di ciascun valore di dati nella mappa della frequenza mentre si itera attraverso l'elenco collegato. Viene quindi restituito il conteggio del valore target nella mappa della frequenza.

La funzione dichiara quindi un puntatore chiamato "corrente" e lo inizializza alla testa dell'elenco collegato. Finché la "corrente" non è nulla, un ciclo while viene aggiunto nella funzione. La funzione imposta la "corrente" su corrente-> accanto per avanzare al nodo successivo nell'elenco collegato dopo aver aumentato il conteggio di corrente-> dati nella mappa della frequenza per ciascuna iterazione del loop.

La funzione restituisce quindi il conteggio del valore target nella mappa della frequenza, che è uguale al numero di volte che il valore target appare nell'elenco collegato, una volta completato il ciclo while.

La funzione principale crea tre oggetti nodi, ciascuno che rappresenta un nodo nell'elenco collegato. Il primo nodo è assegnato con il valore 11 e il suo prossimo puntatore è impostato per puntare al secondo nodo. Allo stesso modo, il secondo nodo è assegnato con il valore 12 e il suo prossimo puntatore è impostato per puntare al terzo nodo. Il terzo nodo è assegnato con il valore 11 e il suo puntatore successivo è impostato su NULL per indicare la fine dell'elenco collegato.

Successivamente, il capo dell'elenco collegato e il valore target vengono passati come parametri quando si chiama CountCurrenceSh () per recuperare il conteggio del valore 11. L'uscita viene quindi stampata sulla console.

Conclusione

La tabella iterativa, l'hash e la ricorsione sono i tre modi più popolari per contare le istanze di un valore particolare in un elenco collegato in C++. Nell'approccio iterativo, l'elenco collegato viene in giro e una variabile di conteggio viene aumentata ogni volta che un nodo che contiene il valore desiderato viene scoperto. La frequenza degli elementi nell'elenco collegato è memorizzata come coppie di valore chiave utilizzando la tecnica della tabella hash che utilizza una struttura dei dati della mappa non ordinata. Il metodo della tabella hash è appropriato per elenchi collegati più grandi e offre velocità di ricerca rapide. Il metodo di ricorsione include invocare ripetutamente una funzione su ciascun nodo nell'elenco collegato per rompere il problema in sotto-problemi più piccoli. Quando viene raggiunta la fine dell'elenco collegato, viene restituito un conteggio raccolto in tutte le chiamate alla funzione.