Tell forekomst av søkeverdi i en koblet liste i C ++

I informatikk er å telle forekomster av en viss verdi i en lenket liste en typisk operasjon. Å finne et elements frekvens i en liste blir ofte gjort slik at den kan brukes til dataanalyse, søk og sortering, blant annet. I en lenket liste, betyr beregning av antall ganger en verdi ofte å krysse listen og avgjøre om hver nodeens verdi samsvarer med målverdien. Hver gang en kamp blir oppdaget, økes antallet telleforekomster deretter. Iterative, rekursive og hashbaserte algoritmer kan alle brukes til å utføre denne prosedyren, hver med sine egne fordeler og ulemper.

I C ++ er det mange måter å bestemme hvor ofte et element vises i en koblet liste inkludert følgende:

Iterativ metode: Den iterative teknikken sjekker datafeltet til hver node når den krysser den koblede listen for å telle repetisjonene av ønsket verdi.

Rekursiv metode: Den koblede listen er iterert gjennom å bruke en rekursiv funksjon for å telle repetisjonene av målverdien.

Hash -tabellmetode: Hyppigheten av målverdien returneres ved hjelp av hasjtabellteknikken som lagrer hyppigheten til hvert element i den koblede listen i en hasjtabell.

Tilnærming 1: Iterativ metode

Den iterative metoden er en tilnærming for å løse et problem der en oppgave gjentas til en viss tilstand er oppfylt. Det innebærer en sekvens av instruksjoner som utføres gjentatte ganger, enten et spesifisert antall ganger eller til en spesifikk tilstand er oppfylt. I denne metoden oppnås løsningen ved å utføre en sekvens av beregninger, hver bygning på resultatene fra forrige beregning.

Den iterative metoden kan brukes til å løse et bredt spekter av problemer, fra enkle aritmetiske beregninger til komplekse algoritmer. Det er ofte foretrukket fremfor den rekursive metoden fordi den er mer enkel, lettere å forstå, og krever mindre overhead når det gjelder minnebruk.

// Komplett program for innsetting i en koblet liste i C++
#inkludere
ved hjelp av navneområdet STD;
Klasseknute

offentlig:
int -data;
Node *Neste;
;
int countoccurrences (node ​​** headnode, int element)
int count = 0;
Node *strøm = *headnode;
mens (strøm != Null)
if (current-> data == element)
telle ++;

Nåværende = strøm-> Neste;

returantall;

void insertatbeginningLinkedList (node ​​** headnode, int data)
// Lag minne dynamisk for denne newnoden
Node* newNode = new node ();
newNode-> data = data;
newNode-> next = *headnode;
*headnode = newNode;
cout << newNode->data << " inserted data successfully"
"Into Linked List" << endl;

void printlinkedList (node* node)
cout << "\n";
// mens tilstanden vil stoppe når node == null
mens (node!= Null)
cout << node->data << " "; node = node->neste;

cout << "\n" << endl;

int main ()

Node* 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<retur 0;

Produksjon:

10 innsatte data med hell i koblet liste
9 Sett inn data med hell i koblet liste
8 innsatte data med hell i koblet liste
12 innsatte data med hell i koblet liste
19 innsatte data med hell i koblet liste
8 innsatte data med hell i koblet liste
8 19 12 8 9 10
Antall ganger 8 oppstår er 2

Forklaring:

En iterativ metode for å telle forekomstene til et spesifikt element i en koblet liste implementeres i forrige kode.

Det første trinnet er å definere "Node" -klassen som har to medlemsvariabler: "data" som brukes til å holde verdien av hver node og "neste", som er en referanse til noden etter den i listen.

En heltalldata og en dobbel peker til den koblede listens hodeknute blir sendt til InsertatBeginningLinkedList () -funksjonen. Ved hjelp av den nye noden () opprettes en ny nodes minne dynamisk, og dataene blir deretter tilordnet den nye noden. Senere oppdaterer den hodeknuten slik at det er den nye noden ved å sette den nye nodenes neste peker til forrige hodeknute.

Linked List's Head Node Pointer og elementet du skal søke etter er de to inngangene som er gitt til Countoccurrences () -funksjonen. Funksjonen returnerer hvor mange ganger varen du vises i den koblede listen. Funksjonen begynner med å stille tellevariabelen til 0 og gjeldende variabels referanse til hodeknuten til den koblede listen. Metoden starter deretter en stundsløyfe, som går så lenge den "strømmen" ikke er null, et tegn på at listenes slutt fortsatt er i rekkevidde. Funksjonen bestemmer om datafeltet til den gjeldende noden tilsvarer målverdien for hver iterasjon av loopen (elementet). Tellevariabelen økes. Hvis det er det, fortsetter sløyfen til vi har besøkt hver node på listen, da den "strømmen" blir endret for å peke på følgende node. Funksjonen returnerer den endelige verdien av tellingen, som angir antall ganger varen vises på listen, når løkken er fullført.

PrintlinkedList (): Skriver ut verdiene til alle noder i den koblede listen. Det tar en peker til den første noden i listen som en inndata.

I Main () -funksjonen opprettes en tom koblet liste ved å initialisere hodeknuten til NULL. Funksjonen bruker deretter InsertatBeginningLinkedList -funksjonen for å sette inn flere verdier i listen. Til slutt skrives listen og antall forekomster av nummer 8 telles og vises ved hjelp av countoccurrences og printlinkedlist -funksjoner.

Vi krysser den komplette listen bare en gang. Derfor er den tidsmessige kompleksiteten til metoden vår o (n), hvor n er antall noder på listen.

Tilnærming 2: Rekursiv metode

En rekursiv metode er en funksjon som kaller seg som en subroutine. Ideen bak rekursjon er å dele ned et problem i mindre delproblemer til det blir enkelt nok til å løses direkte. Den rekursive funksjonen kombinerer deretter løsningene til underproblemene for å danne løsningen til det opprinnelige problemet. I informatikk er rekursjon mye brukt i mange algoritmer og datastrukturer, for eksempel sortering og søk, for å redusere kompleksiteten ved å løse store problemer ved å dele dem i mindre, enklere å løse underproblemer.

#inkludere
ved hjelp av navneområdet STD;
Klasseknute

offentlig:
int -data;
Node *Neste;
;
int countoccurrenceRecursive (node ​​*headnode, int element)
if (headnode == null)
retur 0;

int count = countoccurrenceRecursive (headnode-> neste, vare);
if (headnode-> data == element)
telle ++;

returantall;

int main ()
Node *headnode = ny node;
Node *SecondNode = ny node;
Node *ThirdNode = ny node;
headnode-> data = 11;
headnode-> next = SecondNode;
SecondNode-> Data = 12;
SecondNode-> Next = ThirdNode;
ThirdNode-> Data = 11;
ThirdNode-> neste = null;
int -mål = 11;
int count = countoccurrenceRecursive (headnode, mål);
cout << "Count of " << target << " is: " << count << endl;
retur 0;

Produksjon:

Antall 11 er: 2

Forklaring:

1. Nodeklassen, som har medlemsdata og neste, brukes til å definere en koblet liste.
2. En referanse til den koblede listenes hode og elementet som skal telle er de to inngangene til countoccurrenceRecursive () -metoden.
3. Når hodet tilsvarer null, returnerer rekursjonens første sak, som får den til å returnere 0, returnerer 0.
4. Rekursivt kaller funksjonen seg ved å bruke den koblede listenes påfølgende node.
5. Hvis gjeldende nodes data samsvarer med målet etter den rekursive samtalen, økes tellingen.
6. Funksjonen returnerer totaltellingen.
7. Målelementet er satt til 11 og en koblet liste med tre noder er konstruert i hovedfunksjonen.
8. Ringer countoccurrenceRecursive () med hodet på den koblede listen og målelementet som parametere gir antallet målelementet.

Tilnærming 3: Hash -tabellmetode

En datastruktur som kalles en hash-tabell gjør det mulig å utføre innslag av nøkkelverdipar i konstant tid O (1). Den fungerer ved å bruke en nøkkel for å beregne en indeks til en rekke spor eller bøtter, hvorfra den nødvendige verdien kan bli funnet. Hashbordet lagrer nøkkelverdiparene, som deretter blir delt opp i henhold til hasjfunksjonen på tvers av en rekke bøtter.

En hash -tabellimplementering for C ++ er muliggjort av standardmalbibliotekets (STL) uordnede kart. Nøkkelverdiparet lagring og gjenfinning kan gjøres med dette raskt og effektivt. Med følgende syntaks er det erklært en uordnede_map:

#inkludere
uordnede_map hashtable;

Der "nøkkel" betegner typen nøkler i en hasjbord, og "verdi" betegner typen verdier som er lagret i. Ved hjelp av den firkantede braketoperatøren [], muliggjør UnorDeD_MAP den raske og effektive innsetting av nøkkelverdipar, sletting og oppslag. For eksempel kan du gjøre følgende for å legge til et nøkkelverdipar til en uordnede_map:

hashtable [nøkkel] = verdi;

Beregningen av hasjverdien og plasseringen av nøkkelverdi-paret i den aktuelle bøtta blir begge håndtert automatisk av Unordered_Map.

#inkludere
#inkludere
ved hjelp av navneområdet STD;
Klasseknute

offentlig:
int -data;
Node *Neste;
;
int countoccurrenceshash (node ​​*head, int Target)
std :: uordnede_map Frekvens;
Node *strøm = hode;
mens (strøm != Null)
frekvens [gjeldende-> data] ++;
Nåværende = strøm-> Neste;

returfrekvens [mål];

int main ()
Node *headnode = ny node;
Node *SecondNode = ny node;
Node *ThirdNode = ny node;
headnode-> data = 11;
headnode-> next = SecondNode;
SecondNode-> Data = 12;
SecondNode-> Next = ThirdNode;
ThirdNode-> Data = 11;
ThirdNode-> neste = null;
int -mål = 11;
int count = countoccurrenceshash (headnode, mål);
cout << "Count of " << target << " is: " << count << endl;
retur 0;

Produksjon:

Antall 11 er: 2

Forklaring:
Hash -tabellen tilnærming for å telle forekomstene implementeres av countoccurrenceshash () -funksjonen. Det skaper en uordnede_mapfrekvens og setter sin opprinnelige tilstand til et tomt kart. Funksjonen oppdaterer deretter tellingen for hver dataverdi i frekvenskartet mens du er itererer gjennom den koblede listen. Antallet for målverdien i frekvenskartet blir deretter returnert.

Funksjonen erklærer deretter en peker kalt "strøm" og initialiserer den til den koblede listenes hode. Så lenge den "strømmen" ikke er null, legges en stundsløyfe i funksjonen. Funksjonen setter "strømmen" til strøm-> ved siden av for å gå videre til neste node i den koblede listen etter å ha økt antallet gjeldende-> data i frekvenskartet for hver iterasjon av loopen.

Funksjonen returnerer deretter antallet målverdien i frekvenskartet, som er lik antall ganger målverdien vises i den koblede listen, når Loop er fullført.

Hovedfunksjonen oppretter tre nodeobjekter, som hver representerer en node i den koblede listen. Den første noden er tilordnet med verdien 11, og den neste pekeren er satt til å peke på den andre noden. Tilsvarende tildeles den andre noden med verdien 12, og den neste pekeren er satt til å peke på den tredje noden. Den tredje noden er tildelt med verdien 11 og den neste pekeren er satt til NULL for å indikere slutten av den koblede listen.

Deretter sendes hodet på den koblede listen og målverdien som parametere når du ringer countoccurrenceshash () for å hente antallet verdien 11. Utgangen skrives deretter ut til konsollen.

Konklusjon

Iterativ, hash -tabell og rekursjon er de tre mest populære måtene å telle forekomstene av en bestemt verdi i en koblet liste i C++. I den iterative tilnærmingen er den koblede listen loopet rundt, og en tellevariabel økes hver gang en node som inneholder ønsket verdi blir oppdaget. Hyppigheten av elementene i den koblede listen lagres som nøkkelverdipar ved bruk av hash-tabellteknikken som benytter seg av en uordnet kartdatastruktur. Hash-tabellmetoden er passende for større koblede lister og tilbyr raske oppslagshastigheter. Rekursjonsmetoden inkluderer å påkalle en funksjon på hver node i den koblede listen gjentatte ganger for å dele problemet i mindre underproblemer. Når den koblede listen er slutt, blir en telling som samles på tvers av alle samtaler til funksjonen returnert.