Circulaire gekoppelde lijst: voordelen met C-programmavoorbeeld

Inhoudsopgave:

Anonim

Wat is een circulaire gekoppelde lijst?

Een circulaire gekoppelde lijst is een reeks knooppunten die zo zijn gerangschikt dat elk knooppunt naar zichzelf kan worden herleid. Hier is een "knooppunt" een zelfreferentieel element met verwijzingen naar een of twee knooppunten in de onmiddellijke nabijheid.

Hieronder ziet u een afbeelding van een cirkelvormige gekoppelde lijst met 3 knooppunten.

Hier kunt u zien dat elk knooppunt herleidbaar is tot zichzelf. Het bovenstaande voorbeeld is een circulaire enkelvoudig gelinkte lijst.

Opmerking: de meest eenvoudige cirkelvormige gekoppelde lijst is een knoop die alleen naar zichzelf herleidt, zoals weergegeven

In deze zelfstudie met circulaire gekoppelde lijst leert u:

  • Wat is een circulaire gekoppelde lijst?
  • Basisbewerkingen
  • Invoegbewerking
  • Verwijderingsbewerking
  • Doorlopen van een circulaire gekoppelde lijst
  • Voordelen van Circular Linked List
  • Enkelvoudig gekoppelde lijst als een circulaire gekoppelde lijst
  • Toepassingen van de circulaire gekoppelde lijst

Basisbewerkingen

De basisbewerkingen op een circulaire gekoppelde lijst zijn:

  1. Invoeging
  2. Schrapping en
  3. Traversal
  • Invoegen is het proces waarbij een knooppunt op een opgegeven positie in de circulaire gekoppelde lijst wordt geplaatst.
  • Verwijderen is het proces waarbij een bestaand knooppunt uit de gekoppelde lijst wordt verwijderd. Het knooppunt kan worden geïdentificeerd door het voorkomen van zijn waarde of door zijn positie.
  • Het doorlopen van een circulaire gekoppelde lijst is het proces van het weergeven van de volledige inhoud van de gekoppelde lijst en terugkeren naar het bronknooppunt.

In de volgende sectie zult u het invoegen van een knooppunt en de soorten invoeging die mogelijk zijn in een circulaire enkelvoudig gekoppelde lijst begrijpen.

Invoegbewerking

In eerste instantie moet u één knooppunt maken dat naar zichzelf wijst, zoals weergegeven in deze afbeelding. Zonder dit knooppunt maakt het invoegen het eerste knooppunt.

Vervolgens zijn er twee mogelijkheden:

  • Invoegen op de huidige positie van de circulaire gekoppelde lijst. Dit komt overeen met invoeging aan het begin van het einde van een gewone enkelvoudige gekoppelde lijst. In een circulaire gekoppelde lijst zijn het begin en het einde hetzelfde.
  • Invoegen na een geïndexeerd knooppunt. Het knooppunt moet worden geïdentificeerd door een indexnummer dat overeenkomt met zijn elementwaarde.

Voor het invoegen aan het begin / einde van de circulaire gekoppelde lijst, dat wil zeggen op de positie waar het allereerste knooppunt werd toegevoegd,

  • U moet de bestaande zelfkoppeling naar het bestaande knooppunt verbreken
  • De volgende aanwijzer van het nieuwe knooppunt zal naar het bestaande knooppunt linken.
  • De volgende aanwijzer van het laatste knooppunt zal naar het ingevoegde knooppunt wijzen.

OPMERKING: De aanwijzer die de tokenmaster is of het begin / einde van de cirkel kan worden gewijzigd. Het zal nog steeds terugkeren naar hetzelfde knooppunt tijdens een traversal, die verderop wordt besproken.

De stappen in (a) i-iii worden hieronder weergegeven:

(Bestaand knooppunt)

STAP 1) Verbreek de bestaande link

STAP 2) Maak een voorwaartse link (van een nieuw knooppunt naar een bestaand knooppunt)

STAP 3) Maak een luslink naar het eerste knooppunt

Vervolgens probeert u in te voegen na een knooppunt.

Laten we bijvoorbeeld "VALUE2" invoegen na het knooppunt met "VALUE0". Laten we aannemen dat het startpunt het knooppunt is met "VALUE0".

  • U moet de lijn tussen het eerste en tweede knooppunt doorbreken en het knooppunt met "VALUE2" ertussen plaatsen.
  • De volgende aanwijzer van het eerste knooppunt moet naar dit knooppunt linken, en de volgende aanwijzer van dit knooppunt moet naar het eerdere tweede knooppunt verwijzen.
  • De rest van het arrangement blijft ongewijzigd. Alle knooppunten zijn herleidbaar tot zichzelf.

OPMERKING: aangezien er een cyclische opstelling is, omvat het invoegen van een knooppunt dezelfde procedure voor elk knooppunt. De wijzer die een cyclus voltooit, voltooit de cyclus net als elk ander knooppunt.

Dit wordt hieronder weergegeven:

(Laten we zeggen dat er maar twee knooppunten zijn. Dit is een triviaal geval)

STAP 1) Verwijder de binnenste schakel tussen de verbonden knooppunten

STAP 2) Verbind het linkerknooppunt met het nieuwe knooppunt

STAP 3) Verbind het nieuwe knooppunt met het rechterknooppunt.

Verwijderingsbewerking

Laten we uitgaan van een circulaire gekoppelde lijst met drie knooppunten. De gevallen voor verwijdering worden hieronder gegeven:

  • Het huidige element verwijderen
  • Verwijdering na een element.

Verwijderen aan het begin / einde:

  1. Ga vanaf het laatste knooppunt naar het eerste knooppunt.
  2. Om vanaf het einde te verwijderen, zou er slechts één doorloopstap moeten zijn, van het laatste knooppunt naar het eerste knooppunt.
  3. Verwijder de link tussen het laatste knooppunt en het volgende knooppunt.
  4. Koppel het laatste knooppunt aan het volgende element van het eerste knooppunt.
  5. Maak het eerste knooppunt vrij.

(Bestaande setup)

STAP 1 ) Verwijder de ronde schakel

STAPPEN 2) Verwijder de link tussen het eerste en het volgende, koppel het laatste knooppunt met het knooppunt dat volgt op het eerste

STAP 3) Maak de toewijzing van het eerste knooppunt vrij / verwijder de toewijzing

Verwijdering na een knoop:

  1. Beweeg tot het volgende knooppunt het knooppunt is dat moet worden verwijderd.
  2. Ga naar het volgende knooppunt en plaats een aanwijzer op het vorige knooppunt.
  3. Verbind het vorige knooppunt met het knooppunt na het huidige knooppunt met behulp van de volgende aanwijzer.
  4. Maak het huidige (ontkoppelde) knooppunt vrij.

STAP 1) Laten we zeggen dat we een knooppunt met "VALUE1" moeten verwijderen.

STAP 2) Verwijder de link tussen het vorige knooppunt en het huidige knooppunt. Koppel het vorige knooppunt met het volgende knooppunt dat wordt aangewezen door het huidige knooppunt (met VALUE1).

STAP 3) Maak de huidige node vrij of verwijder de toewijzing.

Doorlopen van een circulaire gekoppelde lijst

Om een ​​cirkelvormige gekoppelde lijst te doorlopen, beginnend bij een laatste aanwijzer, controleert u of de laatste aanwijzer zelf NULL is. Als deze voorwaarde niet waar is, controleer dan of er maar één element is. Anders beweegt u met een tijdelijke aanwijzer totdat de laatste aanwijzer weer wordt bereikt, of zo vaak als nodig is, zoals weergegeven in de onderstaande GIF.

Voordelen van Circular Linked List

Enkele voordelen van circulair gekoppelde lijsten zijn:

  1. Geen vereiste voor een NULL-toewijzing in de code. De circulaire lijst verwijst nooit naar een NULL-aanwijzer, tenzij de toewijzing volledig is opgeheven.
  2. Circulair gekoppelde lijsten zijn voordelig voor eindbewerkingen aangezien begin en einde samenvallen. Algoritmen zoals de Round Robin-planning kunnen processen die op een circulaire manier in de wachtrij staan, netjes elimineren zonder bungelende of NULL-verwijzingen tegen te komen.
  3. Circulair gekoppelde lijst voert ook alle reguliere functies van een enkelvoudig gekoppelde lijst uit. In feite kunnen circulaire dubbelgekoppelde lijsten die hieronder worden besproken, zelfs de noodzaak van een volledige doorgang om een ​​element te lokaliseren, overbodig maken. Dat element zou hooguit precies het tegenovergestelde zijn van het begin en zou slechts de helft van de gekoppelde lijst invullen.

Enkelvoudig gekoppelde lijst als een circulaire gekoppelde lijst

U wordt aangemoedigd om te proberen de onderstaande code te lezen en te implementeren. Het presenteert de aanwijzer-rekenkunde die is gekoppeld aan circulaire gekoppelde lijsten.

#include#includestruct node{int item;struct node *next;};struct node* addToEmpty(struct node*,int);struct node *insertCurrent(struct node *, int);struct node *insertAfter(struct node *, int, int);struct node *removeAfter(struct node *, int);struct node *removeCurrent(struct node *);void peek(struct node *);int main(){…

Toelichting code:

  1. De eerste twee regels code zijn de benodigde header-bestanden.
  2. De volgende sectie beschrijft de structuur van elk zelfreferentieknooppunt. Het bevat een waarde en een pointer van hetzelfde type als de structuur.
  3. Elke structuur koppelt herhaaldelijk aan structuurobjecten van hetzelfde type.
  4. Er zijn verschillende functieprototypes voor:
    1. Een element toevoegen aan een lege gekoppelde lijst
    2. Invoegen op de huidige puntige positie van een circulaire gekoppelde lijst.
    3. Invoegen na een bepaalde geïndexeerde waarde in de gekoppelde lijst.
    4. Verwijderen / verwijderen na een bepaalde geïndexeerde waarde in de gekoppelde lijst.
    5. Verwijderen op de huidige puntige positie van een circulaire gekoppelde lijst
  5. De laatste functie drukt elk element af via een cirkelvormige doorgang in elke staat van de gekoppelde lijst.
int main(){struct node *last = NULL;last = insertCurrent(last,4);last = removeAfter(last, 4);peek(last);return 0;}struct node* addToEmpty(struct node*last, int data){struct node *temp = (struct node *)malloc(sizeof( struct node));temp->item = data;last = temp;last->next = last;return last;}struct node *insertCurrent(struct node *last, int data)

Toelichting code:

  1. Wijs voor de addEmpty-code een leeg knooppunt toe met behulp van de malloc-functie.
  2. Voor dit knooppunt plaatst u de gegevens in de tijdelijke variabele.
  3. Wijs de enige variabele toe en koppel deze aan de tijdelijke variabele
  4. Retourneer het laatste element naar de main () / toepassingscontext.
struct node *insertCurrent(struct node *last, int data){if(last == NULL){return addToEmpty(last, data);}struct node *temp = (struct node *)malloc(sizeof( struct node));temp -> item = data;temp->next = last->next;last->next = temp;return last;}struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;…

Verklaring van code

  1. Als er geen element is om in te voegen, moet u ervoor zorgen dat u dit toevoegt aan een lege lijst en de controle teruggeeft.
  2. Maak een tijdelijk element om achter het huidige element te plaatsen.
  3. Koppel de verwijzingen zoals weergegeven.
  4. Retourneer de laatste aanwijzer zoals in de vorige functie.
… struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;if (last == NULL){return addToEmpty(last, item);}do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found. Please try again");…

Toelichting code:

  1. Als er geen element in de lijst staat, negeer dan de gegevens, voeg het huidige item toe als het laatste item in de lijst en geef de controle terug
  2. Zorg er voor elke iteratie in de do-while-lus voor dat er een vorige pointer is die het laatst doorlopen resultaat bevat.
  3. Alleen dan kan de volgende traversal plaatsvinden.
  4. Als de gegevens worden gevonden, of als de temperatuur teruggaat naar de laatste aanwijzer, wordt de do-while beëindigd. Het volgende gedeelte van de code bepaalt wat er met het item moet worden gedaan.
… if(temp->item != data){printf("Element not found. Please try again");return last;}else{newnode = (struct node *)malloc(sizeof(struct node));newnode->item = item;prev->next = newnode;newnode->next = temp;}return last;}struct node *removeCurrent(struct node *last)…

Toelichting code:

  1. Als de volledige lijst is doorlopen, maar het item is niet gevonden, geeft u het bericht "item niet gevonden" weer en geeft u de bediening terug aan de beller.
  2. Als er een knooppunt is gevonden en / of het knooppunt is nog niet het laatste knooppunt, maak dan een nieuw knooppunt aan.
  3. Koppel het vorige knooppunt aan het nieuwe knooppunt. Koppel het huidige knooppunt met temp (de traversale variabele).
  4. Dit zorgt ervoor dat het element achter een bepaald knooppunt in de circulaire gekoppelde lijst wordt geplaatst. Ga terug naar de beller.
struct node *removeCurrent(struct node *last){if(last == NULL){printf("Element Not Found");return NULL;}struct node *temp = last->next;last->next = temp->next;free(temp);return last;}struct node *removeAfter(struct node *last, int data)

Verklaring van code

  1. Om alleen het laatste (huidige) knooppunt te verwijderen, controleert u of deze lijst leeg is. Als dit het geval is, kan geen enkel element worden verwijderd.
  2. De tijdelijke variabele gaat slechts één link vooruit.
  3. Koppel de laatste aanwijzer aan de aanwijzer na de eerste.
  4. Bevrijd de tijdelijke wijzer. De toewijzing van de niet-gekoppelde laatste aanwijzer wordt ongedaan gemaakt.
struct node *removeAfter(struct node *last,int data){struct node *temp = NULL,*prev = NULL;if (last == NULL){printf("Linked list empty. Cannot remove any element\n");return NULL;}temp = last->next;prev = temp;do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found");…

Verklaring van code

  1. Controleer, net als bij de vorige verwijderingsfunctie, of er geen element is. Als dit waar is, kan geen enkel element worden verwijderd.
  2. Aanwijzers krijgen specifieke posities toegewezen om het te verwijderen element te lokaliseren.
  3. De wijzers worden achter elkaar naar voren gebracht. (vorige achter temp)
  4. Het proces gaat door totdat een element is gevonden, of het volgende element keert terug naar de laatste pointer.
if(temp->item != data){printf("Element not found");return last;}else{prev->next = temp->next;free(temp);}return last;}void peek(struct node * last){struct node *temp = last;if (last == NULL){return;

Toelichting programma

  1. Als het element wordt gevonden nadat het de volledige gekoppelde lijst heeft doorlopen, wordt er een foutmelding weergegeven waarin staat dat het item niet is gevonden.
  2. Anders wordt het element ontkoppeld en vrijgegeven in stap 3 en 4.
  3. De vorige aanwijzer is gekoppeld aan het adres dat als "volgende" wordt aangeduid door het te verwijderen element (temp).
  4. De tijdelijke pointer wordt daarom ongedaan gemaakt en vrijgegeven.
… void peek(struct node * last){struct node *temp = last;if (last == NULL){return;}if(last -> next == last){printf("%d-", temp->item);}while (temp != last){printf("%d-", temp->item);temp = temp->next;}}

Verklaring van code

  1. Het gluren of doorkruisen is niet mogelijk als er nul nodig is. De gebruiker moet een knooppunt toewijzen of invoegen.
  2. Als er slechts één knooppunt is, hoeft u niet te doorlopen, kan de inhoud van het knooppunt worden afgedrukt en wordt de while-lus niet uitgevoerd.
  3. Als er meer dan één knooppunt is, drukt de temp het hele item tot het laatste element af.
  4. Op het moment dat het laatste element is bereikt, wordt de lus beëindigd en retourneert de functie de aanroep van de hoofdfunctie.

Toepassingen van de circulaire gekoppelde lijst

  • Implementatie van round-robin-planning in systeemprocessen en circulaire planning in snelle grafische afbeeldingen.
  • Planning van tokenringen in computernetwerken.
  • Het wordt gebruikt in display-eenheden zoals winkelborden die continu gegevens moeten doorlopen.