Po tablicach drugą najpopularniejszą strukturą danych jest Lista połączona. Lista połączona to liniowa struktura danych, składająca się z łańcucha węzłów, w których każdy węzeł zawiera wartość i wskaźnik do następnego węzła w łańcuchu. W tym artykule zobaczmy, jak zaimplementować połączoną listę w C.
Co to jest lista połączona w C?
Lista połączona to liniowa struktura danych. Każda połączona lista składa się z dwóch części: sekcji danych i sekcji adresu, w której znajduje się adres następnego elementu listy, nazywanego węzłem.
Rozmiar połączonej listy nie jest ustalony, a elementy danych można dodawać w dowolnej lokalizacji na liście. Wadą jest to, że aby dostać się do węzła, musimy przejść całą drogę od pierwszego węzła do wymaganego przez nas węzła. Lista połączona jest jak tablica, ale w przeciwieństwie do tablicy nie jest przechowywana sekwencyjnie w pamięci.
Najpopularniejsze typy połączonej listy to:
Przykład listy połączonej
Format: [dane, adres]
Głowa -> [3,1000] -> [43,1001] -> [21,1002]
W tym przykładzie liczba 43 występuje w lokalizacji 1000, a adres w poprzednim węźle. Tak jest reprezentowana lista połączona.
Podstawowe funkcje list połączonych
Istnieje wiele funkcji, które można zaimplementować na połączonej liście w C. Spróbujmy je zrozumieć za pomocą przykładowego programu.Najpierw tworzymy listę, wyświetlamy ją, wstawiamy w dowolnym miejscu, usuwamy lokalizację. Poniższy kod pokaże Ci, jak wykonywać operacje na liście.
#include #include void create () void display () void insert_begin () void insert_end () void insert_pos () void delete_begin () void delete_end () void delete_pos () struct node {int info struct node * next} struct node * start = NULL int main () {int choice while (1) {printf ('n MENU n') printf ('n 1.Create n') printf ('n 2.Display n') printf ('n 3.Insert at początek n ') printf (' n 4.Wstawianie na końcu n ') printf (' n 5.Wstawianie w określonej pozycji n ') printf (' n 6.Usuń od początku n ') printf (' n 7.Delete od końca n ') printf (' n 8. Usuń z określonej pozycji n ') printf (' n 9. Exit n ') printf (' n ----------------- --------------------- n ') printf (' Wpisz swój wybór: t ') scanf ('% d ', & choice) switch (choice) {przypadek 1 : create () break case 2: display () break case 3: insert_begin () break case 4: insert_end () break case 5: insert_pos () break case 6: delete_begin () break case 7: delete_end () break case 8: delete_pos () break case 9: exit (0) break default: printf ('n Wrong Choice: n') break}} return 0} voi d create () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') exit (0) } printf ('nWprowadź wartość danych dla węzła: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n ') return} else {ptr = start printf (' nElementy listy to: n ') while (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> next}}} void insert_begin () {struct node * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nWprowadź wartość danych dla węzła: t ') scanf ('% d ', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {temp-> next = start start = temp }} void insert_end () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} p rintf ('nWprowadź wartość danych dla węzła: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void insert_pos () {struct node * ptr, * temp int i, pos temp = (struct node *) malloc ( sizeof (węzeł struktury)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nWprowadź położenie nowego węzła do wstawienia: t') scanf ('% d' , & pos) printf ('nWprowadź wartość danych węzła: t') scanf ('% d', & temp-> info) temp-> next = NULL if (pos == 0) {temp-> next = start start = temp} else {for (i = 0, ptr = startinext if (ptr == NULL) {printf ('nPosition not found: [Handle with care] n') return}} temp-> next = ptr-> next ptr -> next = temp}} void delete_begin () {struct node * ptr if (ptr == NULL) {printf ('nList is Empty: n') return} else {ptr = start start = start-> next printf (' nUsunięty element to:% dt ', ptr-> info) free (ptr)}} void delete_end () {struct node * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') exit (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ('nUsunięty element to:% dt', ptr-> info) free (ptr)} else {ptr = start while (ptr- > next! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('nUsunięty element to:% dt', ptr-> info) free (ptr)}} void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} else {printf ('nWprowadź pozycję węzła do usunięcia : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nUsunięty element to:% dt ', ptr-> info) free (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nUsunięty element to: % dt ', ptr-> info) free (ptr)}}}Pierwsza część tego kodu to tworzenie struktury. Tworzona jest połączona struktura listy, która może przechowywać dane i adresy tak, jak tego potrzebujemy. Ma to na celu dać kompilatorowi wyobrażenie o tym, jak powinien wyglądać węzeł.
węzeł struktury {int info węzeł struktury * next}W strukturze mamy zmienną danych o nazwie info do przechowywania danych i zmienną wskaźnikową wskazującą na adres. Istnieje wiele operacji, które można wykonać na połączonej liście, na przykład:
- Stwórz()
- pokaz()
- insert_begin ()
- insert_end ()
- ] insert_pos ()
- delete_begin ()
- delete_end ()
- delete_pos ()
Funkcje te są wywoływane przez funkcję główną sterowaną menu. W funkcji głównej pobieramy dane wejściowe od użytkownika w oparciu o operację, którą użytkownik chce wykonać w programie. Dane wejściowe są następnie wysyłane do obudowy przełącznika i na podstawie danych wejściowych użytkownika.
Na podstawie wprowadzonych danych zostanie wywołana funkcja. Następnie mamy różne funkcje, które należy rozwiązać. Przyjrzyjmy się każdej z tych funkcji.
Utwórz funkcję
Po pierwsze, istnieje funkcja tworzenia, która służy do tworzenia połączonej listy. To jest podstawowy sposób tworzenia połączonej listy. Spójrzmy na kod.
void create () {struct node * temp, * ptr printf ('nWprowadź wartość danych dla węzła: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL ) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}}Wynik
Najpierw tworzone są dwa wskaźniki typu node, ptr i temp . Bierzemy wartość, która jest potrzebna do dodania do połączonej listy od użytkownika i przechowujemy ją w części informacyjnej zmiennej temp i przypisujemy temp of next czyli część adresu do null. Na początku listy znajduje się wskaźnik początku. Następnie sprawdzamy początek listy. Jeśli początek listy jest pusty, przypisujemy temp do wskaźnika początkowego. W przeciwnym razie przechodzimy do ostatniego punktu, w którym dane zostały dodane.
W tym celu przypisujemy ptr wartość początkową i przechodzimy do ptr-> next = null . Następnie przypisujemy ptr-> next adres temp. W podobny sposób jest podany kod wstawiania na początku, wstawiania na końcu i wstawiania w określonym miejscu.
Funkcja wyświetlania
Oto kod funkcji wyświetlania.
jak zrobić plik w java
void display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n') return} else {ptr = start printf ('n Elementy listy to: n') while (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> next}}}Wynik
W funkcji wyświetlania najpierw sprawdzamy, czy lista jest pusta i zwracamy, jeśli jest pusta. W następnej części przypisujemy wartość początkową ptr. Następnie uruchamiamy pętlę, aż ptr osiągnie wartość null i drukujemy element danych dla każdego węzła, aż ptr będzie równe zeru, co oznacza koniec listy.
Usuń funkcję
Oto fragment kodu umożliwiający usunięcie węzła z połączonej listy.
void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nLista jest pusta: n') exit (0)} else {printf ('nWprowadź pozycję węzeł do usunięcia: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nUsunięty element to:% dt ', ptr-> info ) free (ptr)} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nThe usunięty element to:% dt ', ptr-> info) free (ptr)}}}Wynik
W procesie usuwania najpierw sprawdza, czy lista jest pusta, jeśli tak, to istnieje. Jeśli nie jest pusta, prosi użytkownika o usunięcie pozycji. Gdy użytkownik wejdzie na stanowisko, sprawdza, czy jest to pierwsza pozycja, jeśli tak, to przypisuje ptr aby rozpocząć i przenosi wskaźnik początkowy do następnej lokalizacji i usuwa ptr. Jeśli pozycja nie jest zerem , następnie uruchamia pętlę for od 0 aż do pozycji wprowadzonej przez użytkownika i zapisanej w pliku poz zmienna. Istnieje instrukcja if, aby zdecydować, czy wprowadzona pozycja nie jest obecna. Jeśli ptr jest równe null , to nie ma go.
My przypisz ptr do temp w pętli for, a ptr przechodzi do następnej części. Po tym, gdy pozycja zostanie znaleziona. Tworzymy zmienną temp, która będzie przechowywać wartość ptr-> next pomijając w ten sposób ptr. Następnie ptr jest usuwany. Podobnie można to zrobić dla usunięcia pierwszego i ostatniego elementu.
Lista podwójnie połączona
Nazywa się to listą podwójnie połączoną, ponieważ są dwie wskaźniki , jeden punkt do następnego węzła, a inne do poprzedniego węzła. Operacje wykonywane na podwójnie połączonej liście są podobne do operacji na pojedynczo połączonej liście. Oto kod do podstawowych operacji.
#include #include struct Węzeł typedef struct Node * PtrToNode typedef PtrToNode Lista typedef PtrToNode Pozycja struct Węzeł {int e Pozycja poprzednia pozycja next} void Insert (int x, List l, Position p) {Position TmpCell TmpCell = (struct Node *) malloc (sizeof (struct Node)) if (TmpCell == NULL) printf ('Memory out of spacen') else {TmpCell-> e = x TmpCell-> previous = p TmpCell-> next = p-> next p-> next = TmpCell}} void Usuń (int x, Lista l) {Pozycja p, p1, p2 p = Znajdź (x, l) if (p! = NULL) {p1 = p -> poprzednie p2 = p -> następne p1 - > next = p -> next if (p2! = NULL) // jeśli węzeł nie jest ostatnim węzłem p2 -> previous = p -> previous} else printf ('Element nie istnieje !!! n')} void Wyświetl (Lista l) {printf ('Elementami listy są:') Pozycja p = l-> następny while (p! = NULL) {printf ('% d ->', p-> e) p = p- > next}} int main () {int x, pos, ch, i List l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> previous = NULL l-> next = NULL List p = l printf ('PODWÓJNIE POWIĄZANA LISTA WDROŻENIA L IST ADTnn ') do {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnnWprowadź wybór :: ') scanf ('% d ', & ch) switch (ch) {case 1: p = l printf (' Wpisz element do wstawienia :: ') scanf ('% d', & x) printf ('Podaj pozycję elementu ::') scanf ('% d', & pos) for (i = 1 inext} Insert (x, l, p) break case 2: p = l printf ('Enter the element to delete ::') scanf ('% d', & x) Delete (x, p) break case 3: Display (l) break}} while (rozdz<4) } Wynik
Jak widać, koncepcja operacji jest dość prosta. Lista podwójnie połączona ma takie same operacje, jak lista pojedynczo połączona w języku programowania C. Jedyną różnicą jest to, że istnieje inna zmienna adresowa, która pomaga lepiej przechodzić przez listę w podwójnie połączonej liście.
Mam nadzieję, że zrozumiałeś, jak wykonywać podstawowe operacje na liście pojedynczo i podwójnie połączonej w C.
Jeśli chcesz nauczyć się listy połączonej w Javie, tutaj jest .
Jeśli napotkasz jakieś pytania, nie krępuj się zadawać je w sekcji komentarzy w „Powiązanej liście w C”, a nasz zespół z przyjemnością odpowie.