Okrągła lista połączona: zalety i wady
Sara Chen
Co to jest cykliczna lista połączona?
Lista połączona cyklicznie to sekwencja węzłów ułożonych w taki sposób, że każdy węzeł można prześledzić do siebie. Tutaj „węzeł” jest elementem samoodnoszącym się ze wskaźnikami do jednego lub dwóch węzłów w jego bezpośrednim sąsiedztwie.
Poniżej znajduje się ilustracja okrągłej listy połączonej z 3 węzłami.
Tutaj widać, że każdy węzeł można odnaleźć sam w sobie. Powyższy przykład to cykliczna, pojedynczo połączona lista.
Uwaga: Najprostsza cykliczna lista z linkami to węzeł, który śledzi tylko siebie, jak pokazano
Basic Operana listach połączonych cyklicznie
Podstawowe operacje na liście cyklicznej to:
- Wprowadzenie
- Usunięcie i
- Przemierzanie
- Wstawianie to proces umieszczania węzła w określonej pozycji na liście połączonej cyklicznie.
- Usuwanie to proces usuwania istniejącego węzła z połączonej listy. Węzeł można zidentyfikować po wystąpieniu jego wartości lub po jego położeniu.
- Przechodzenie przez cykliczną listę połączoną to proces wyświetlania zawartości całej połączonej listy i powrotu do węzła źródłowego.
W następnej sekcji poznasz wstawianie węzła i możliwe rodzaje wstawiania w przypadku cyklicznej listy pojedynczo połączonej.
Wprowadzenie Operacja
Początkowo musisz utworzyć jeden węzeł, który będzie wskazywał na siebie, jak pokazano na tym obrazku. Bez tego węzła wstawienie tworzy pierwszy węzeł.
Dalej są dwie możliwości:
- Wstawienie w bieżącej pozycji listy połączonej cyklicznie. Odpowiada to wstawieniu na początku końca zwykłej, pojedynczej listy połączonej. Na liście połączonej cyklicznie początek i koniec są takie same.
- Wstawienie po indeksowanym węźle. Węzeł powinien być identyfikowany poprzez numer indeksu odpowiadający wartości jego elementu.
Aby wstawić na początku/końcu listy połączonej cyklicznie, czyli w miejscu, w którym dodano pierwszy w historii węzeł,
- Będziesz musiał przerwać istniejące połączenie własne z istniejącym węzłem
- Następny wskaźnik nowego węzła będzie połączony z istniejącym węzłem.
- Następny wskaźnik ostatniego węzła będzie wskazywał wstawiony węzeł.
UWAGA: Wskaźnik będący wzorcem tokenu lub początkiem/końcem okręgu można zmienić. Nadal powróci do tego samego węzła podczas przechodzenia, co omówiono wcześniej.
Kroki z (a) i-iii pokazano 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 pętlę do pierwszego węzła
Następnie spróbujesz wstawić po węźle.
Na przykład wstawmy „WARTOŚĆ2” po węźle z „WARTOŚĆ0”. Załóżmy, że punktem początkowym jest węzeł z „WARTOŚĆ0”.
- Będziesz musiał przerwać linię między pierwszym a drugim węzłem i umieścić pomiędzy nimi węzeł z „WARTOŚCIĄ2”.
- 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.
- Pozostała część układu pozostaje bez zmian. Wszystkie węzły są identyfikowalne dla siebie.
UWAGA: Ponieważ istnieje układ cykliczny, wstawianie węzła wymaga tej samej procedury dla dowolnego węzła. Wskaźnik kończący cykl kończy cykl tak samo jak każdy inny węzeł.
Pokazano to poniżej:
(Powiedzmy, że są tylko dwa węzły. To trywialny przypadek)
KROK 1) Usuń wewnętrzne połączenie między połączonymi węzłami
KROK 2) Połącz węzeł po lewej stronie z nowym węzłem
KROK 3) Połącz nowy węzeł z węzłem po prawej stronie.
usunięcie Operacja
Załóżmy, że lista jest 3-węzłowa, z połączeniami kołowymi. Przypadki usunięcia podano poniżej:
- Usuwanie bieżącego elementu
- Usunięcie po elemencie.
Skreślenie na początku/końcu:
- Przejdź do pierwszego węzła z ostatniego węzła.
- Aby usunąć z końca, powinien istnieć tylko jeden krok przejścia, od ostatniego węzła do pierwszego węzła.
- Usuń połączenie między ostatnim węzłem a następnym węzłem.
- Połącz ostatni węzeł z kolejnym elementem pierwszego węzła.
- Uwolnij pierwszy węzeł.
(Istniejąca konfiguracja)
KROK 1) Usuń okrągłe łącze
KROKI 2) Usuń połączenie między pierwszym a kolejnym węzłem, połącz ostatni węzeł z węzłem następującym po pierwszym
KROK 3) Uwolnij /deallocate pierwszy węzeł
Usuwanie po węźle:
- Przejdź do następnego węzła, który ma zostać usunięty.
- Przejdź do następnego węzła, umieszczając wskaźnik na poprzednim węźle.
- Połącz poprzedni węzeł z węzłem następującym po bieżącym węźle, używając jego następnego wskaźnika.
- Uwolnij bieżący (odłączony) węzeł.
KROK 1) Załóżmy, że musimy usunąć węzeł z „VALUE1”.
KROK 2) Usuń połączenie pomiędzy poprzednim węzłem a bieżącym węzłem. Połącz jego poprzedni węzeł z następnym węzłem wskazanym przez bieżący węzeł (z WARTOŚCIĄ1).
KROK 3) Uwolnij lub zwolnij bieżący węzeł.
Przechodzenie przez cykliczną listę połączoną
Aby przejść przez listę powiązaną cyklicznie, zaczynając od ostatniego wskaźnika, sprawdź, czy sam ostatni wskaźnik jest NULL. Jeśli ten warunek jest fałszywy, sprawdź, czy jest tylko jeden element. W przeciwnym razie przejdź przez tymczasowy wskaźnik, aż do ponownego osiągnięcia ostatniego wskaźnika lub tyle razy, ile potrzeba, jak pokazano na poniższym GIF-ie.
Zalety cyklicznej listy połączonej
Oto niektóre zalety list połączonych cyklicznie:
- Brak wymogu przypisania wartości NULL w kodzie. Lista cykliczna nigdy nie wskazuje na wskaźnik NULL, chyba że całkowicie zwolniono przydział.
- Listy cykliczne są korzystne w przypadku operacji końcowych, ponieważ początek i koniec pokrywają się. Algorithms takie jak planowanie okrężne może starannie wyeliminować procesy, które są kolejkowane w sposób cykliczny, bez napotykania wskaźników wiszących lub referencyjnych NULL.
- Lista połączona cyklicznie wykonuje również wszystkie zwykłe funkcje listy pojedynczo połączonej. Faktycznie, okrągłe listy podwójnie powiązane omówione poniżej mogą nawet wyeliminować potrzebę przemieszczania się na całej długości w celu zlokalizowania elementu. Element ten byłby co najwyżej dokładnie przeciwny do początku, uzupełniając zaledwie połowę połączonej listy.
Wady cyklicznej listy połączonej
Poniżej przedstawiono wady korzystania z cyklicznej listy połączonej:
- Listy kołowe są bardziej złożone w porównaniu do listy pojedynczo połączone.
- RevRodzaj listy cyklicznej jest bardziej złożony niż listy pojedyncze lub podwójne.
- Jeśli nie zostanie potraktowany ostrożnie, kod może zatoczyć nieskończoną pętlę.
- Trudniej znaleźć koniec listy i kontrolować pętlę.
- Wstawiając na początku, musimy przejść przez całą listę, aby znaleźć ostatni węzeł. (Perspektywa wdrożenia)
Lista pojedynczo połączona jako lista połączona cyklicznie
Zachęcamy do podjęcia próby przeczytania i wdrożenia poniższego kodu. Przedstawia arytmetykę wskaźników związaną z listami połączonymi cyklicznie.
#include<stdio.h>
#include<stdlib.h>
struct 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:
- Pierwsze dwie linie kodu to niezbędne pliki nagłówkowe.
- Następna sekcja opisuje strukturę każdego węzła samoodwołującego się. Zawiera wartość i wskaźnik tego samego typu co struktura.
- Każda konstrukcja wielokrotnie łączy się z obiektami struktury tego samego typu.
- Istnieją różne prototypy funkcji dla:
- Dodawanie elementu do pustej listy połączonej
- Wstawianie na obecnie wskazany pozycja okrągłej listy połączonej.
- Wstawianie po konkretnym zindeksowane wartość na połączonej liście.
- Usuwanie/Usuwanie po konkretnym zindeksowane wartość na połączonej liście.
- Usuwanie w aktualnie wskazanej pozycji listy połączonej cyklicznie
- Ostatnia funkcja drukuje każdy element poprzez przechodzenie cykliczne 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:
- W przypadku kodu addEmpty przydziel pusty węzeł za pomocą funkcji malloc.
- W przypadku tego węzła umieść dane w zmiennej temp.
- Przypisz i połącz jedyną zmienną ze zmienną temp
- 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
- Jeśli nie ma elementu do wstawienia, pamiętaj o dodaniu go do pustej listy i zwróceniu kontroli.
- Utwórz element tymczasowy, który zostanie umieszczony po bieżącym elemencie.
- Połącz wskaźniki, jak pokazano.
- Zwróć ostatni wskaźnik, 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:
- Jeśli na liście nie ma żadnego elementu, zignoruj dane, dodaj bieżący element jako ostatni element na liście i zwróć kontrolę
- Przy każdej iteracji pętli do-while upewnij się, że istnieje poprzedni wskaźnik przechowujący wynik ostatniego przejścia.
- Dopiero wtedy będzie można przystąpić do kolejnego przejazdu.
- Jeśli dane zostaną znalezione lub temp osiągnie ostatni wskaźnik, operacja do-while zakończy się. 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:
- Jeżeli przeszukano całą listę, a pozycja nie została znaleziona, wyświetl komunikat „nie znaleziono pozycji”, a następnie zwróć kontrolę dzwoniącemu.
- Jeśli znaleziono węzeł i/lub węzeł ten nie jest jeszcze ostatnim węzłem, utwórz nowy węzeł.
- Połączyć poprzedni węzeł z nowym węzłem. Połącz bieżący węzeł z temp (zmienną przechodzenia).
- Zapewnia to, że element zostanie umieszczony po określonym węźle na liście połączonej cyklicznie. Wróć do rozmówcy.
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
- Aby usunąć tylko ostatni (bieżący) węzeł, sprawdź, czy ta lista jest pusta. Jeżeli tak, to nie można usunąć żadnego elementu.
- Zmienna temp po prostu przechodzi o jedno łącze do przodu.
- Połącz ostatni wskaźnik ze wskaźnikiem znajdującym się po pierwszym.
- Uwolnij wskaźnik temperatury. Cofa przydział niepołączonego ostatniego wskaźnika.
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
- Podobnie jak w przypadku poprzedniej funkcji usuwania, sprawdź, czy nie ma elementu. Jeśli to prawda, nie można usunąć żadnego elementu.
- wskaźniki przypisane są określone pozycje umożliwiające zlokalizowanie elementu do usunięcia.
- Wskaźniki są wysunięte, jeden za drugim. (poprzedni za temp)
- Proces trwa do momentu znalezienia elementu lub powrotu następnego elementu 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;
Wyjaśnienie programu
- Jeśli element zostanie znaleziony po przeszukaniu całej listy powiązanej, zostanie wyświetlony komunikat o błędzie informujący, że element nie został znaleziony.
- W przeciwnym wypadku element zostanie odłączony i zwolniony w krokach 3 i 4.
- Poprzedni wskaźnik jest powiązany z adresem wskazanym jako „next” przez element do usunięcia (temp).
- W związku z tym wskaźnik temp zostaje zwolniony i zwolniony.
...
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
- Podglądanie lub przechodzenie nie jest możliwe, jeśli potrzebne jest zero. Użytkownik musi przydzielić lub wstawić węzeł.
- 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.
- Jeśli jest więcej niż jeden węzeł, temp drukuje cały element aż do ostatniego elementu.
- W momencie osiągnięcia ostatniego elementu pętla kończy się, a funkcja zwraca wywołanie funkcji głównej.
Zastosowania cyklicznej listy połączonej
- Implementacja planowania okrężnego w procesach systemowych i planowania okrężnego w szybkiej grafice.
- Harmonogramowanie token ring w sieciach komputerowych.
- Jest stosowany w wyświetlaczach, takich jak tablice sklepowe, które wymagają ciągłego przeglądania danych.
