Slett duplikatnodene fra en usortert koblet liste

I denne artikkelen skal vi se de forskjellige tilnærmingene for å slette duplikatknutene fra den koblede listen ved hjelp av C ++ -programmeringen. La oss starte med en forklaring på hva "duplikatnodene" i en lenket liste betyr.

Vi får en usortert koblet liste i denne utfordringen og ba om å slette duplikatmedlemmer fra listen. La oss bruke noen eksempler for å forsøke å forstå problemet.

Inngangen usortert koblet liste er som følger:

Elementene 8, 10 og 9 vises mer enn en gang i den koblede listen, som sett i forrige liste. Dette indikerer at det er duplikater på 8, 10 og 9 i den koblede listen som vi må eliminere. Den koblede listen er som følger når dupliserte oppføringene er fjernet fra listen:

En rask og enkel måte å finne ut av er å sammenligne alle mulige par noder på listen for å se om de har samme informasjon. Når informasjonen deres sammenfaller, blir vi kvitt den andre noden ved å slette den. Men denne tilnærmingen er mer tidkrevende.

Bedre effektivitet er mulig å bruke Hashing. Målet er å jobbe gjennom den medfølgende listen og legge til hver node til et sett mens du går. Hvis den viste noden vises i det forrige settet, kan den trygt se bort fra. Når prosessen er fullført, vil listen ikke lenger inneholde noen dupliserte noder.

La oss forstå hver tilnærming i detalj.

Tilnærming 1: Bruke to løkker

Algoritme trinn

1. Lag en koblet listefunksjon, "CreatElinkedList“, Som kan lage en lenket liste.
2. Lag en funksjon som heter “Deleteduplicatesnodes”Som kan slette duplikatnoden fra den koblede listen.
3. Lag to lokale pekere, PTR1 og PTR2, inne i “Deleteduplicatesnodes”Funksjon.
4. Tilordne PTR1 = headnode og PTR2 = NULL Verdier, der PTR1 brukes til å spore noden hvis duplikater må sjekkes og PTR2 brukes til å krysse hver node på den koblede listen for å sjekke om noen nodedata er de samme som PTR1 -nodedata.
5. Nested Loop Pointer PTR2 fortsetter å krysse hele den koblede listeknuten til den finner NULL.
6. Hvis PTR1 -nodedataene ligner på noden Node Data Node, slett den noden fra den koblede listen.
7. Hvis ikke, øker du PTR1-> Neste og sjekk neste nodes data for duplikater.
8. Trinn 4 til 7 gjentas til PTR1 ikke er lik null, noe som indikerer at den nådde slutten av den koblede listen.
9. Til slutt skriver vi ut den koblede listen.
10. Slutten av algoritmen.

C ++ kodeimplementering (ved hjelp av to løkker)

Produksjon:

Forklaring:

Linjer 21 til 52: Vi lager en funksjon med navnet "CreatElinkedList". Vi passerer to parametere (en headnode -peker til pekeren og en verdi) i den funksjonen. Som vist i det foregående programmet, oppretter den først en ny node med en verdi (som vi har bestått) og en nodeadresse med en nullverdi.

/* Opprett en ny node*/
Node* newNode = new node ();
Node * lastNode = * headnode;
newNode-> data = verdi; / * Legge til dataene */
/* Adresse til denne nye noden holdt intialt null*/
newNode-> neste = null;

Deretter sjekker det å se om headnode -referansen er null. Hvis det er, blir den nyopprettede noden hodet.

/* Kontrollere headnode -referansen er null eller ikke.
Hvis ja, vil newnoden bli headnode*/
if (*headnode == null)
*headnode = newNode;
komme tilbake;

Hvis headnode -referansen ikke er null, legger den seg til lastnoden til den koblede listen. Adressen til denne nyopprettede newnoden er tildelt The LastNode, slik at den kan begynne å peke på den nyopprettede newnoden.

/* Hvis ikke, så vil dette mens Loop vil
Utfør og finn lenket til de koblede
liste, slik at nyopprettet newnode legger til sist*/
mens (lastNode-> neste != Null)
lastNode = lastNode-> neste;

Nå blir den nyopprettede newnoden sistnoden. Denne prosessen fortsetter til den tid når vi kaller denne funksjonen.

De foregående trinnene oppretter den koblede listen i henhold til våre krav. Nå sletter vi duplikatknutene fra den koblede listen.

Linjer 57 til 75: Vi oppretter en funksjon som heter “DeleteduplicatesNodes” som godtar en parameter som er headnode -pekeren til den koblede listen. Vi lager to variabler på lokalt nivå, PTR1 og PTR2, for å spore den koblede listen når vi sløyfe den for å finne ut duplikatene i den koblede listen. Vi initialiserer PTR1 med headnode siden dette vil være den øvre sløyfen, og PTR2 med nullverdien.

ptr1 = headnode;

PTR1: Denne variabelen er i den ytre sløyfen og sporer elementene hvis duplikater vi skal sjekke.

PTR2: Denne variabelen er inne i løkken og fortsetter å sjekke hver nodeens data for å finne ut om den samsvarer med PTR1 Hold Data. Hvis det samsvarer, fjernes duplikatene fra den koblede listen. Dette er sjekket og fortsetter til den ikke når den siste noden hvis verdien er null.

Når ptr2-> neste == null, nestet mens sløyfen ender og ytre mens sløyfen øker ptr1 = ptr1-> neste med neste nodedata.

Merk: PTR2 slutter når PTR1 sløyfen er over fordi PTR2 er inne i PTR1 -sløyfen.

mens (PTR1 != Null && ptr1-> Neste != Null)
ptr2 = ptr1;
mens (ptr2-> neste != Null)
/* Hvis funnet, vil koden slette nedenfor
duplikater node*/
if (ptr1-> data == ptr2-> next-> data)
duplikat = ptr2-> neste;
ptr2-> neste = ptr2-> neste-> Neste;
slett (duplikat);
annet /* Hvis ikke funnet, vil PTR2 oppdateres til
til neste node*/
ptr2 = ptr2-> neste;

ptr1 = ptr1-> neste;

Linjer 78 til 84: Dette viser den endelige koblede listen uten duplisering. I så fall passerer vi headnode som en parameter som er adressen til den koblede listen.

/* Denne funksjonen vil skrive ut den koblede listen*/
void display (node* node)
mens (node-> neste)
printf ("%d ->", node-> data);
node = node-> neste;

printf ("%d", node-> data);

Tilnærming 2: Hashing -metode

Algoritme trinn

1. Lag en koblet listefunksjon, “CreatElinkedList”, som kan lage en koblet liste.
2. Lag en funksjon som kalles “DeleteduplicatesNodes” som kan slette duplikatnoden fra den koblede listen.
3. Lag to lokale pekere, CurrentNode og forrige NODE, inne i "DeleteduplicatesNodes" -funksjonen.
4. Lag et usortert hasjsett inne i "Deleteduplicatesnodes".
5. Tilordne CurrentNode = HeadNode og forrige node = nullverdier der CurrentNode brukes til å spore noden hvis duplikater må sjekkes og forrige.
6. Mens Loop krysser hele den koblede listeknuten til CurrentNode == NULL.
7. Hvis CurrentNode -dataene allerede er i hashsettet, blir noden slettet.
8. Hvis ikke, legger det til at Nodes data til hasjsettet.
9. Trinn 5 til 8 gjentas til CurrentNode ikke er lik null, noe som indikerer at den nådde slutten av den koblede listen.
10. Til slutt skriver vi ut den koblede listen.
11. Slutten av algoritmen.

C ++ kodeimplementering (ved hjelp av hasjmetoden)

Produksjon:

Linjer 26 til 52: Vi oppretter en funksjon med navnet "CreatElinkedList". I den funksjonen passerer vi to parametere (en headnode -peker til pekeren og en verdi). Som vist i det foregående programmet, oppretter den først en ny node med en verdi (som vi har bestått) og en adresse med en nullverdi.

/* Opprett en ny node*/
Node* newNode = new node ();
Node * lastNode = * headnode;
newNode-> data = verdi; / * Legge til dataene */
/* Adresse til denne nye noden holdt intialt null*/
newNode-> neste = null;

Deretter sjekker det å se om headnode -referansen er null. Hvis det er, blir den nyopprettede noden hodet.

/* Kontrollere headnode -referansen er null eller ikke.
Hvis ja, vil newnoden bli headnode*/
if (*headnode == null)
*headnode = newNode;
komme tilbake;

Hvis headnode -referansen ikke er null, legger den seg til lastnoden til den koblede listen. Adressen til denne nyopprettede newnoden er tildelt The LastNode, slik at den kan begynne å peke på den nyopprettede newnoden.

/* Hvis ikke, så vil dette mens Loop vil
Utfør og finn lenket til de koblede
liste, slik at nyopprettet newnode legger til sist*/
mens (lastNode-> neste != Null)
lastNode = lastNode-> neste;

Nå blir den nyopprettede newnoden sistnoden. Denne prosessen fortsetter til den tid når vi kaller denne funksjonen.

De foregående trinnene oppretter den koblede listen i henhold til våre krav. Nå sletter vi duplikatknutene fra den koblede listen.

Linjer 57 til 75: Vi oppretter en funksjon som heter “DeleteduplicatesNodes” som godtar en parameter som er headnode -pekeren til den koblede listen. Vi lager en usortert hashset hasj. Vi lager også to variabler på lokalt nivå, CurrentNode og Forrige node, For å spore den koblede listen når vi sløyfe den for å finne ut duplikatene i den koblede listen. Vi initialiserer CurrentNode med headnode siden dette vil være den øvre sløyfen, og forrige node med nullverdien.

struct node* currentNode = headnode;
struct node* forrige node = null;

CurrentNode: Denne variabelen er i den ytre sløyfen og sporer elementene hvis duplikater vi skal sjekke.

Forrige node: Dette håndterer CurrentNode's forrige node. Vi oppretter en stundsløyfe som kjøres til CurrentNode ikke finner nullverdien, noe som betyr på slutten av den koblede listen. Hvis CurrentNode -dataene allerede er på hasjkartet, må du tilordne verdien av CurrentNode's Neste peker til Forrige node Neste peker.

forrige node-> neste = currentNode-> neste;

Hvis ikke, legg til dataene fra CurrentNode på hasjkartet og lag Forrige node lik CurrentNode.

annet
hash.Sett inn (CurrentNode-> Data);
ForrigeNode = CurrentNode;

På slutten, tilordne verdien av neste peker i forrige node til CurrentNode.

mens (CurrentNode != Null)
/* Hvis gjeldende nodedata som allerede er besøkt, så er dette
koden vil slette den noden
*/
hvis (hash.Finn (CurrentNode-> Data) != Hash.slutt())
forrige node-> neste = currentNode-> neste;
slett (currentNode);

/*
Hvis ikke besøkte CurrentNode -data, så
sett inn i hasj
*/
annet
hash.Sett inn (CurrentNode-> Data);
ForrigeNode = CurrentNode;

CurrentNode = forrige Node-> Neste;

Linjer 84 til 90: Dette viser den endelige koblede listen uten duplisering. I så fall passerer vi headnode som en parameter som er adressen til den koblede listen.

/* Denne funksjonen vil skrive ut den koblede listen*/
void display (node* node)
mens (node-> neste)
printf ("%d ->", node-> data);
node = node-> neste;

printf ("%d", node-> data);

Konklusjon

I den første metoden, for å bli kvitt duplikatene, bruker vi to løkker: en ytre sløyfe som itererer over den koblede listen og velger et element, og en andre sløyfe som itererer over det elementet for å se etter eventuelle duplikater. Så snart en duplikat blir oppdaget, blir den slettet fra listen. Denne metoden bruker en nestet sløyfe for å undersøke og eliminere duplikater fra en usortert koblet liste som øker tidskompleksiteten i prosessen. Tidskompleksitet er o (n²).

I den andre metoden kan hashing brukes til å minimere den tidsmessige kompleksiteten ved å fjerne duplikatene fra en usortert koblet liste. I dette tilfellet, hvis noden vises i Hashmap to ganger, er det en duplisering og den første forekomsten skal slettes. Hvis en node mangler på kartet, er det fordi det er en ny som må legges til. Det tar i gjennomsnitt O (n) tid å gå over en koblet liste over lengde “n” og sjekker om nodene er på kartet. Den tidsmessige kompleksiteten for å slå opp en verdi i en hasjbord er O (1). Tatt i betraktning de nevnte forutsetningene sammen, er den totale tidskompleksiteten O (n).