Lista połączona cyklicznie: Zalety z przykładem programu w C.

Spisie treści:

Anonim

Co to jest lista połączona cyklicznie?

Lista połączona cyklicznie to sekwencja węzłów ułożona w taki sposób, że każdy węzeł można odtworzyć do siebie samego. Tutaj „węzeł” jest elementem odwołującym się do samego siebie ze wskaźnikami do jednego lub dwóch węzłów w bezpośrednim sąsiedztwie iI.

Poniżej przedstawiono listę połączoną cyklicznie z 3 węzłami.

Tutaj możesz zobaczyć, że każdy węzeł można odtworzyć do siebie. Przykład pokazany powyżej jest okrągłą, pojedynczo połączoną listą.

Uwaga: Najprostsza połączona lista cykliczna to węzeł, który śledzi tylko siebie, jak pokazano

W tym samouczku dotyczącym okrągłej listy z linkami dowiesz się:

  • Co to jest lista połączona cyklicznie?
  • Podstawowe operacje
  • Operacja wstawiania
  • Operacja usunięcia
  • Przechodzenie przez listę połączoną kołowo
  • Zalety listy połączonej cyklicznie
  • Lista połączona pojedynczo jako lista połączona cyklicznie
  • Zastosowania listy okólnikowej

Podstawowe operacje

Podstawowe operacje na okrężnej liście połączonej to:

  1. Wprowadzenie
  2. Usunięcie i
  3. Traversal
  • Wstawianie to proces umieszczania węzła w określonej pozycji na okrężnej liście połączonej.
  • Usuwanie to proces usuwania istniejącego węzła z połączonej listy. Węzeł można zidentyfikować na podstawie wystąpienia jego wartości lub położenia.
  • Przeglądanie listy połączonej cyklicznie to proces wyświetlania całej zawartości listy połączonej i odtwarzania z powrotem do węzła źródłowego.

W następnej sekcji zrozumiesz wstawianie węzłów i typy wstawiania możliwe na kołowej liście pojedynczo połączonej.

Operacja wstawiania

Początkowo musisz utworzyć jeden węzeł, który wskazuje na siebie, jak pokazano na tym obrazku. Bez tego węzła wstawianie tworzy pierwszy węzeł.

Następnie istnieją dwie możliwości:

  • Wstawienie w bieżącej pozycji listy połączonej cyklicznie. Odpowiada to wstawieniu na początku końca zwykłej listy połączonej liczby pojedynczej. Na liście połączonej cyklicznie początek i koniec są takie same.
  • Wstawienie za indeksowanym węzłem. Węzeł powinien być oznaczony numerem indeksu odpowiadającym wartości jego elementu.

Do wstawiania na początku / końcu listy połączonej cyklicznie, czyli w miejscu, w którym został dodany pierwszy w historii węzeł,

  • Będziesz musiał przerwać istniejące łącze własne do istniejącego węzła
  • Następny wskaźnik nowego węzła będzie łączył się z istniejącym węzłem.
  • Następny wskaźnik ostatniego węzła będzie wskazywał na wstawiony węzeł.

UWAGA: Wskaźnik będący głównym tokenem lub początek / koniec koła można zmienić. Nadal powróci do tego samego węzła podczas przemierzania omówionego wcześniej.

Kroki w (a) i-iii są pokazane poniżej:

(Istniejący węzeł)

KROK 1) Przerwij istniejące łącze

KROK 2) Utwórz łącze do przodu (z nowego węzła do istniejącego węzła)

KROK 3) Utwórz łącze pętlowe do pierwszego węzła

Następnie spróbujesz wstawić za węzłem.

Na przykład wstawmy „VALUE2” po węźle z „VALUE0”. Załóżmy, że punktem początkowym jest węzeł z „VALUE0”.

  • Będziesz musiał przerwać linię między pierwszym a drugim węzłem i umieścić węzeł z „VALUE2” pomiędzy.
  • Następny wskaźnik pierwszego węzła musi łączyć się z tym węzłem, a następny wskaźnik tego węzła musi łączyć się z wcześniejszym drugim węzłem.
  • Reszta aranżacji pozostaje niezmieniona. Wszystkie węzły są odtwarzalne dla siebie.

UWAGA: Ponieważ istnieje układ cykliczny, wstawianie węzła obejmuje tę samą procedurę dla każdego węzła. Wskaźnik kończący cykl kończy cykl tak jak każdy inny węzeł.

Jest to pokazane poniżej:

(Powiedzmy, że są tylko dwa węzły. To trywialny przypadek)

KROK 1) Usuń wewnętrzne łącze między połączonymi węzłami

KROK 2) Podłącz lewy węzeł boczny do nowego węzła

KROK 3) Podłącz nowy węzeł do prawego węzła bocznego.

Operacja usunięcia

Załóżmy, że mamy listę połączoną cyklicznie z 3 węzłami. Przypadki usunięcia podano poniżej:

  • Usuwanie aktualnego elementu
  • Usunięcie po elemencie.

Usunięcie na początku / końcu:

  1. Przejdź do pierwszego węzła z ostatniego węzła.
  2. Aby usunąć od końca, powinien być tylko jeden krok przechodzenia, od ostatniego węzła do pierwszego węzła.
  3. Usuń łącze między ostatnim węzłem a następnym węzłem.
  4. Połącz ostatni węzeł z następnym elementem pierwszego węzła.
  5. Uwolnij pierwszy węzeł.

(Istniejąca konfiguracja)

KROK 1 ) Zdejmij okrągłe ogniwo

KROKI 2) Usuń połączenie między pierwszym a następnym, połącz ostatni węzeł z węzłem następującym po pierwszym

KROK 3) Zwolnij / zwolnij pierwszy węzeł

Usunięcie po węźle:

  1. Przejdź do następnego węzła, który ma zostać usunięty.
  2. Przejdź do następnego węzła, umieszczając wskaźnik na poprzednim węźle.
  3. Połącz poprzedni węzeł z węzłem za obecnym węzłem, używając jego następnego wskaźnika.
  4. Zwolnij bieżący (oddzielony) węzeł.

KROK 1) Powiedzmy, że musimy usunąć węzeł z „VALUE1”.

KROK 2) Usuń połączenie między poprzednim węzłem a bieżącym węzłem. Połącz jego poprzedni węzeł z następnym węzłem wskazywanym przez bieżący węzeł (z VALUE1).

KROK 3) Zwolnij lub zwolnij bieżący węzeł.

Przechodzenie przez listę połączoną kołowo

Aby przejść przez okrągłą połączoną listę, zaczynając od ostatniego wskaźnika, sprawdź, czy ostatni wskaźnik ma wartość NULL. Jeśli ten warunek jest fałszywy, sprawdź, czy jest tylko jeden element. W przeciwnym razie przechodź za pomocą tymczasowego wskaźnika, aż do ponownego osiągnięcia ostatniego wskaźnika lub tyle razy, ile potrzeba, jak pokazano na poniższym GIF-ie.

Zalety listy połączonej cyklicznie

Oto niektóre zalety list z linkami cyklicznymi:

  1. Brak wymogu przypisania wartości NULL w kodzie. Lista cykliczna nigdy nie wskazuje wskaźnika o wartości NULL, chyba że zostanie całkowicie zwolniona.
  2. Listy połączone cyklicznie są korzystne dla operacji końcowych, ponieważ początek i koniec pokrywają się. Algorytmy, takie jak planowanie Round Robin, mogą starannie eliminować procesy, które są kolejkowane w sposób cykliczny, bez napotykania wiszących lub referencyjnych wskaźników NULL.
  3. Lista połączona cyklicznie pełni również wszystkie zwykłe funkcje listy połączonej pojedynczo. W rzeczywistości okrągłe podwójnie połączone listy omówione poniżej mogą nawet wyeliminować potrzebę przechodzenia przez całą długość w celu zlokalizowania elementu. Ten element byłby co najwyżej dokładnie odwrotny do początku, wypełniając tylko połowę połączonej listy.

Lista pojedynczo połączona jako lista połączona kołowo

Zachęcamy do próby przeczytania i zaimplementowania poniższego kodu. Przedstawia arytmetykę wskaźnika powiązaną z listami połączonymi cyklicznie.

#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(){…

Wyjaśnienie kodu:

  1. Pierwsze dwa wiersze kodu to niezbędne pliki nagłówkowe.
  2. W następnej sekcji opisano strukturę każdego węzła odwołującego się do siebie. Zawiera wartość i wskaźnik tego samego typu co struktura.
  3. Każda struktura wielokrotnie łączy się z obiektami struktury tego samego typu.
  4. Istnieją różne prototypy funkcji dla:
    1. Dodawanie elementu do pustej połączonej listy
    2. Wstawianie w aktualnie wskazanej pozycji okrągłej połączonej listy.
    3. Wstawianie po określonej indeksowanej wartości na połączonej liście.
    4. Usuwanie / usuwanie po określonej indeksowanej wartości na połączonej liście.
    5. Usuwanie w aktualnie wskazanej pozycji okrągłej listy połączonej
  5. Ostatnia funkcja drukuje każdy element poprzez cykliczne przejście w dowolnym stanie połączonej listy.
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)

Wyjaśnienie kodu:

  1. W przypadku kodu addEmpty przydziel pusty węzeł za pomocą funkcji malloc.
  2. W przypadku tego węzła umieść dane w zmiennej tymczasowej.
  3. Przypisz i połącz jedyną zmienną ze zmienną tymczasową
  4. Zwróć ostatni element do kontekstu main () / aplikacji.
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;…

Wyjaśnienie kodu

  1. Jeśli nie ma elementu do wstawienia, powinieneś upewnić się, że dodajesz go do pustej listy i zwracasz kontrolkę.
  2. Utwórz element tymczasowy, który zostanie umieszczony po obecnym elemencie.
  3. Połącz wskaźniki, jak pokazano.
  4. Zwróć ostatni wskaźnik, tak jak w poprzedniej funkcji.
… 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");…

Wyjaśnienie kodu:

  1. Jeśli nie ma elementu na liście, zignoruj ​​dane, dodaj bieżącą pozycję jako ostatnią pozycję na liście i zwróć kontrolkę
  2. Dla każdej iteracji w pętli do-while upewnij się, że istnieje poprzedni wskaźnik, który przechowuje ostatni przeszedł wynik.
  3. Dopiero wtedy może nastąpić następne przejście.
  4. Jeśli dane zostaną znalezione lub temp dojdzie do ostatniego wskaźnika, operacja do-while zostaje zakończona. Następna sekcja kodu decyduje, co należy zrobić z elementem.
… 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)…

Wyjaśnienie kodu:

  1. Jeśli przeszedł całą listę, a element nie został znaleziony, wyświetl komunikat „nie znaleziono elementu”, a następnie zwróć sterowanie dzwoniącemu.
  2. Jeśli zostanie znaleziony węzeł i / lub węzeł nie jest jeszcze ostatnim węzłem, utwórz nowy węzeł.
  3. Połącz poprzedni węzeł z nowym węzłem. Połącz bieżący węzeł z temp (zmienną przechodzenia).
  4. Gwarantuje to, że element zostanie umieszczony po określonym węźle na okrężnej liście połączonej. Wróć do dzwoniącego.
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)

Wyjaśnienie kodu

  1. Aby usunąć tylko ostatni (bieżący) węzeł, sprawdź, czy ta lista jest pusta. Jeśli tak, to żadnego elementu nie można usunąć.
  2. Zmienna tymczasowa przechodzi tylko o jedno łącze do przodu.
  3. Połącz ostatni wskaźnik ze wskaźnikiem po pierwszym.
  4. Uwolnij wskaźnik tymczasowy. Zwalnia niepołączony ostatni wskaźnik.
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");…

Wyjaśnienie kodu

  1. Podobnie jak w przypadku poprzedniej funkcji usuwania, sprawdź, czy nie ma elementu. Jeśli to prawda, żaden element nie może zostać usunięty.
  2. Wskaźniki mają przypisane określone pozycje, aby zlokalizować element do usunięcia.
  3. Wskaźniki są zaawansowane, jedna za drugą. (poprz. za temp.)
  4. Proces jest kontynuowany, aż zostanie znaleziony element lub następny element powróci do ostatniego wskaźnika.
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;

Objaśnienie programu

  1. Jeśli element znaleziony po przejściu przez całą połączoną listę zostanie wyświetlony komunikat o błędzie informujący, że element nie został znaleziony.
  2. W przeciwnym razie element jest oddzielany i zwalniany w krokach 3 i 4.
  3. Poprzedni wskaźnik jest powiązany z adresem wskazywanym jako „następny” przez element do usunięcia (tymczasowy).
  4. W związku z tym wskaźnik tymczasowy jest zwalniany i zwalniany.
… 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;}}

Wyjaśnienie kodu

  1. Podglądanie lub przechodzenie nie jest możliwe, jeśli nie są potrzebne. Użytkownik musi przydzielić lub wstawić węzeł.
  2. Jeśli jest tylko jeden węzeł, nie ma potrzeby przechodzenia, zawartość węzła może zostać wydrukowana, a pętla while nie jest wykonywana.
  3. Jeśli istnieje więcej niż jeden węzeł, szablon tymczasowy drukuje cały element aż do ostatniego elementu.
  4. W momencie osiągnięcia ostatniego elementu pętla się kończy, a funkcja zwraca wywołanie funkcji głównej.

Zastosowania listy okólnikowej

  • Wdrażanie harmonogramów okrężnych w procesach systemowych i harmonogramów cyklicznych w szybkiej grafice.
  • Szeregowanie pierścieni tokenów w sieciach komputerowych.
  • Jest używany w jednostkach wyświetlających, takich jak tablice sklepowe, które wymagają ciągłego przeglądania danych.