Meni

Povezana podatkovna struktura seznama v jeziku C ++ z ilustracijo

  • Glavni
  • Drugo
  • Povezana podatkovna struktura seznama v jeziku C ++ z ilustracijo

linked list data structure c with illustration

Preizkusite Naš Instrument Za Odpravo Težav

Podrobna študija povezanega seznama v jeziku C ++.

Povezani seznam je linearna dinamična podatkovna struktura za shranjevanje podatkovnih postavk. V prejšnjih temah o osnovnem C ++ smo že videli nize. Vemo tudi, da so nizi linearna podatkovna struktura, ki hrani podatkovne postavke na sosednjih lokacijah.

Za razliko od nizov povezani seznam ne shranjuje podatkovnih postavk na sosednjih pomnilniških mestih.

Povezani seznam je sestavljen iz elementov, imenovanih 'vozlišča', ki vsebujejo dva dela. Prvi del shrani dejanske podatke, drugi del pa ima kazalec, ki kaže na naslednje vozlišče. Ta struktura se ponavadi imenuje 'Enotno povezan seznam'.

=> Tukaj si oglejte najboljše vadnice za C ++.

POVEZANI SEZNAM

Kaj se boste naučili:

Povezani seznam v jeziku C ++

Podrobno si bomo ogledali posamezno povezan seznam v tej vadnici.

Naslednji diagram prikazuje strukturo posamezno povezanega seznama.

struktura posamezno povezanega seznama

Kot je prikazano zgoraj, se prvo vozlišče povezanega seznama imenuje 'glava', zadnje vozlišče pa 'rep'. Kot vidimo, bo imelo zadnje vozlišče povezanega seznama naslednji kazalec kot nično, saj ne bo imelo nobenega naslova pomnilnika.

Ker ima vsako vozlišče kazalec na naslednje vozlišče, podatkovnih elementov na povezanem seznamu ni treba hraniti na sosednjih lokacijah. Vozlišča so lahko razpršena v pomnilniku. Do vozlišč lahko dostopamo kadar koli, saj bo vsako vozlišče imelo naslednje vozlišče.

Podatkovne postavke lahko dodamo na povezani seznam in jih enostavno izbrišemo s seznama. Tako je mogoče dinamično povečati ali skrčiti povezani seznam. Na povezanem seznamu ni zgornje omejitve števila podatkovnih postavk. Dokler je na voljo pomnilnik, lahko na povezani seznam dodamo toliko podatkovnih elementov.

Poleg enostavnega vstavljanja in brisanja povezani seznam ne zapravlja tudi prostora v pomnilniku, saj nam ni treba predhodno določiti, koliko elementov potrebujemo na povezanem seznamu. Edini prostor, ki ga zasede povezani seznam, je za shranjevanje kazalca na naslednje vozlišče, ki doda malo režijskih stroškov.

Nato bomo razpravljali o različnih operacijah, ki jih je mogoče izvesti na povezanem seznamu.

Operacije

Tako kot druge podatkovne strukture lahko tudi za povezani seznam izvajamo različne operacije. Toda v nasprotju z nizi, v katerih lahko do elementa dostopamo neposredno z uporabo podpisnika, tudi če je nekje vmes, ne moremo narediti enakega naključnega dostopa s povezanim seznamom.

Če želimo dostopati do katerega koli vozlišča, moramo od začetka prečkati povezani seznam in šele nato lahko dostopamo do želenega vozlišča. Izkazalo se je, da je naključen dostop do podatkov s povezanega seznama drag.

Na povezanem seznamu lahko izvajamo različne operacije, kot je navedeno spodaj:

# 1) Vstavljanje

Postopek vstavljanja povezanega seznama doda element na povezani seznam. Čeprav se sliši preprosto, glede na strukturo povezanega seznama vemo, da moramo vsakič, ko je na povezan seznam dodan podatkovni element, spremeniti naslednje kazalce prejšnjega in naslednjega vozlišča novega elementa, ki smo ga vstavili.

testni načrt in testna razlika

Druga stvar, ki jo moramo upoštevati, je kraj, kamor bomo dodali novo podatkovno postavko.

Na povezanem seznamu so trije položaji, kamor lahko dodate podatkovni element.

# 1) Na začetku povezanega seznama

Povezani seznam je prikazan spodaj 2-> 4-> 6-> 8-> 10. Če želimo dodati novo vozlišče 1, kot prvo vozlišče seznama, bo glava, ki kaže na vozlišče 2, zdaj usmerjena na 1, naslednji kazalec vozlišča 1 pa bo imel pomnilniški naslov vozlišča 2, kot je prikazano spodaj slika.

Vstavitev na začetku

Tako novi povezani seznam postane 1-> 2-> 4-> 6-> 8-> 10.

# 2) Po danem vozlišču

Tu je podano vozlišče in za dano vozlišče moramo dodati novo vozlišče. Na spodnjem povezanem seznamu a-> b-> c-> d -> e, če želimo vozlišče f dodati za vozliščem c, bo povezan seznam videti tako:

Vstavitev za dano vozlišče

Tako v zgornjem diagramu preverimo, ali je dano vozlišče prisotno. Če je prisoten, ustvarimo novo vozlišče f. Nato usmerimo naslednji kazalec vozlišča c na novo vozlišče f. Naslednji kazalec vozlišča f zdaj kaže na vozlišče d.

# 3) Na koncu povezanega seznama

V tretjem primeru na konec povezanega seznama dodamo novo vozlišče. Razmislimo, da imamo isti povezan seznam a-> b-> c-> d-> e in na konec seznama moramo dodati vozlišče f. Po dodajanju vozlišča bo povezan seznam videti, kot je prikazano spodaj.

Vstavitev na koncu povezanega seznama

Tako ustvarimo novo vozlišče f. Nato je kazalec repa, ki kaže na nulo, usmerjen na f, naslednji kazalec vozlišča f pa na nič. V spodnji program C ++ smo implementirali vse tri vrste vstavnih funkcij.

V jeziku C ++ lahko povezani seznam razglasimo kot strukturo ali kot razred. Razglasitev povezanega seznama kot strukture je tradicionalna izjava v slogu C. Povezani seznam kot razred se uporablja v sodobnem jeziku C ++, večinoma pri uporabi standardne knjižnice predlog.

V naslednjem programu smo uporabili strukturo za prijavo in ustvarjanje povezanega seznama. Kot člani bodo imeli podatke in kazalec na naslednji element.

#include using namespace std; // A linked list node struct Node { int data; struct Node *next; }; //insert a new node in front of the list void push(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; /* 2. assign data to node */ newNode->data = node_data; /* 3. set next of new node as head */ newNode->next = (*head); /* 4. move the head to point to the new node */ (*head) = newNode; } //insert new node after a given node void insertAfter(struct Node* prev_node, int node_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { coutnext = prev_node->next; /* 5. move the next of prev_node as new_node */ prev_node->next = newNode; } /* insert new node at the end of the linked list */ void append(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; struct Node *last = *head; /* used in step 5*/ /* 2. assign data to the node */ newNode->data = node_data; /* 3. set next pointer of new node to null as its the last node*/ newNode->next = NULL; /* 4. if list is empty, new node becomes first node */ if (*head == NULL) { *head = newNode; return; } /* 5. Else traverse till the last node */ while (last->next != NULL) last = last->next; /* 6. Change the next of last node */ last->next = newNode; return; } // display linked list contents void displayList(struct Node *node) { //traverse the list to display each node while (node != NULL) { coutnext; } if(node== NULL) cout

Izhod:

Končni povezani seznam:

30–> 20–> 50–> 10–> 40–> nično

Nato izvedemo operacijo vstavljanja povezanega seznama v Javi. V jeziku Java je povezan seznam izveden kot razred. Spodnji program je po logiki podoben programu C ++, edina razlika je v tem, da za povezani seznam uporabljamo razred.

class LinkedList { Node head; // head of list //linked list node declaration class Node { int data; Node next; Node(int d) {data = d; next = null; } } /* Insert a new node at the front of the list */ public void push(int new_data) { //allocate and assign data to the node Node newNode = new Node(new_data); //new node becomes head of linked list newNode.next = head; //head points to new node head = newNode; } // Given a node,prev_node insert node after prev_node public void insertAfter(Node prev_node, int new_data) { //check if prev_node is null. if (prev_node == null) { System.out.println('The given node is required and cannot be null'); return; } //allocate node and assign data to it Node newNode = new Node(new_data); //next of new Node is next of prev_node newNode.next = prev_node.next; //prev_node->next is the new node. prev_node.next = newNode; } //inserts a new node at the end of the list public void append(intnew_data) { //allocate the node and assign data Node newNode = new Node(new_data); //if linked list is empty, then new node will be the head if (head == null) { head = new Node(new_data); return; } //set next of new node to null as this is the last node newNode.next = null; // if not the head node traverse the list and add it to the last Node last = head; while (last.next != null) last = last.next; //next of last becomes new node last.next = newNode; return; } //display contents of linked list public void displayList() { Node pnode = head; while (pnode != null) { System.out.print(pnode.data+'-->'); pnode = pnode.next; } if(pnode == null) System.out.print('null'); } } //Main class to call linked list class functions and construct a linked list class Main{ public static void main(String() args) { /* create an empty list */ LinkedList lList = new LinkedList(); // Insert 40. lList.append(40); // Insert 20 at the beginning. lList.push(20); // Insert 10 at the beginning. lList.push(10); // Insert 50 at the end. lList.append(50); // Insert 30, after 20. lList.insertAfter(lList.head.next, 30); System.out.println(' Final linked list: '); lList. displayList (); } }

Izhod:

Končni povezani seznam:

10–> 20–> 30–> 40–> 50–> nično

Tako v zgornjem programu, kot sta C ++ in Java, imamo ločene funkcije za dodajanje vozlišča pred seznamom, koncem seznama in med seznami v vozlišču. Na koncu natisnemo vsebino seznama, ustvarjenega z uporabo vseh treh metod.

# 2) Izbris

Tako kot vstavljanje tudi brisanje vozlišča s povezanega seznama vključuje različne položaje, od koder je vozlišče mogoče izbrisati. S povezanega seznama lahko izbrišemo prvo vozlišče, zadnje vozlišče ali naključno kth vozlišče. Po izbrisu moramo naslednji kazalec in druge kazalce na povezanem seznamu ustrezno prilagoditi, da ostane povezan seznam nedotaknjen.

V naslednji izvedbi C ++ smo podali dva načina brisanja, to je brisanje prvega vozlišča na seznamu in brisanje zadnjega vozlišča na seznamu. Najprej ustvarimo seznam z dodajanjem vozlišč v glavo. Nato po vstavitvi in ​​vsakem brisanju prikažemo vsebino seznama.

#include using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; //delete first node in the linked list Node* deleteFirstNode(struct Node* head) { if (head == NULL) return NULL; // Move the head pointer to the next node Node* tempNode = head; head = head->next; delete tempNode; return head; } //delete last node from linked list Node* removeLastNode(struct Node* head) { if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } // first find second last node Node* second_last = head; while (second_last->next->next != NULL) second_last = second_last->next; // Delete the last node delete (second_last->next); // set next of second_last to null second_last->next = NULL; return head; } // create linked list by adding nodes at head void push(struct Node** head, int new_data) { struct Node* newNode = new Node; newNode->data = new_data; newNode->next = (*head); (*head) = newNode; } // main function int main() { /* Start with the empty list */ Node* head = NULL; // create linked list push(&head, 2); push(&head, 4); push(&head, 6); push(&head, 8); push(&head, 10); Node* temp; cout<<'Linked list created '

Izhod:

Ustvarjen je povezan seznam

10–> 8–> 6–> 4–> 2–
> NULL

Povezan seznam po brisanju glavnega vozlišča

8–> 6–> 4–> 2–
> NULL

Povezan seznam po brisanju zadnjega vozlišča

8–> 6–> 4–> NULL

Naslednja je izvedba Java za brisanje vozlišč s povezanega seznama. Izvedbena logika je enaka kot v programu C ++. Edina razlika je v tem, da je povezani seznam prijavljen kot razred.

class Main { // Linked list node / static class Node { int data; Node next; }; // delete first node of linked list static Node deleteFirstNode(Node head) { if (head == null) return null; // Move the head pointer to the next node Node temp = head; head = head.next; return head; } // Delete the last node in linked list static Node deleteLastNode(Node head) { if (head == null) return null; if (head.next == null) { return null; } // search for second last node Node second_last = head; while (second_last.next.next != null) second_last = second_last.next; // set next of second last to null second_last.next = null; return head; } // Add nodes to the head and create linked list static Node push(Node head, int new_data) { Node newNode = new Node(); newNode.data = new_data; newNode.next = (head); (head) = newNode; return head; } //main function public static void main(String args()) { // Start with the empty list / Node head = null; //create linked list head = push(head, 1); head = push(head, 3); head = push(head, 5); head = push(head, 7); head = push(head, 9); Node temp; System.out.println('Linked list created :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteFirstNode(head); System.out.println('Linked list after deleting head node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteLastNode(head); System.out.println('Linked list after deleting last node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); } }

Izhod:

Ustvarjen je povezan seznam:

9–> 7–> 5–> 3–> 1–
> nično

Povezan seznam po brisanju glavnega vozlišča:

7–> 5–> 3–> 1–
> nično

Povezan seznam po brisanju zadnjega vozlišča:

7–> 5–> 3–> nično

Preštej število vozlišč

Postopek za štetje števila vozlišč je mogoče izvesti med prečkanjem povezanega seznama. V zgornji izvedbi smo že videli, da moramo vedno, ko moramo vstaviti / izbrisati vozlišče ali prikazati vsebino povezanega seznama, prečkati povezani seznam od začetka.

Če obdržimo števec in ga povečamo, ko prečkamo vsako vozlišče, se nam prikaže število vozlišč, ki so prisotna na povezanem seznamu. Bralcem bomo prepustili ta program.

Polja in povezani seznami

Po ogledu delovanja in izvajanja povezanega seznama primerjajmo, kako so nizi in povezani seznami pošteni v primerjavi med seboj.

PoljaPovezani seznami
Polja imajo fiksno velikostVelikost povezanega seznama je dinamična
Vstavljanje novega elementa je dragoVstavljanje / brisanje je lažje
Dovoljen je naključni dostopNaključen dostop ni mogoč
Elementi so na sosednji lokacijiElementi nimajo sosednje lokacije
Za naslednji kazalec ni potreben dodaten prostorZa naslednji kazalec je potreben dodaten pomnilniški prostor

Aplikacije

Ker se niza in povezani seznami uporabljajo za shranjevanje predmetov in so linearne podatkovne strukture, lahko obe strukturi na več načinov aplikacij uporabljamo na podobne načine.

Nekatere aplikacije za povezane sezname so naslednje:

  • Povezani seznam se lahko uporablja za izvajanje nizov in čakalnih vrst.
  • Povezani seznam lahko uporabimo tudi za izvajanje grafov, kadar koli moramo grafi predstavljati kot sezname sosednosti.
  • Matematični polinom se lahko shrani kot povezan seznam.
  • V primeru tehnike razprševanja se vedra, ki se uporabljajo pri razpršitvi, izvajajo s pomočjo povezanih seznamov.
  • Kadar koli program zahteva dinamično dodeljevanje pomnilnika, lahko uporabimo povezan seznam, saj povezani seznami v tem primeru delujejo učinkoviteje.

Zaključek

Povezani seznami so podatkovne strukture, ki se uporabljajo za linearno shranjevanje podatkovnih postavk, vendar nespremenljivih lokacij. Povezani seznam je zbirka vozlišč, ki vsebujejo podatkovni del in naslednji kazalec, ki vsebuje naslov pomnilnika naslednjega elementa na seznamu.

Naslednji kazalec zadnjega elementa na seznamu je nastavljen na NULL in s tem označuje konec seznama. Prvi element seznama se imenuje Head. Povezani seznam podpira različne operacije, kot so vstavljanje, brisanje, preusmerjanje itd. V primeru dinamičnega dodeljevanja pomnilnika imajo prednostni seznami prednost pred nizi.

Povezani seznami so dragi, kar zadeva njihovo prečkanje, saj ne moremo naključno dostopati do elementov, kot so nizi. Vendar pa so postopki vstavljanja in brisanja cenejši v primerjavi z nizi.

V tej vadnici smo izvedeli vse o linearnih povezanih seznamih. Povezani seznami so lahko tudi krožni ali dvojni. Te sezname bomo poglobili v naslednjih vajah.

=> Poglejte tukaj za celotno serijo usposabljanj za C ++.

Priporočeno branje

^