Po poliach je druhou najpopulárnejšou dátovou štruktúrou Prepojený zoznam. Prepojený zoznam je lineárna dátová štruktúra vytvorená z reťazca uzlov, v ktorých každý uzol obsahuje hodnotu a smerník na ďalší uzol v reťazci. V tomto článku sa pozrime, ako implementovať prepojený zoznam v jazyku C.
Čo je prepojený zoznam v jazyku C?
Prepojený zoznam je lineárna dátová štruktúra. Každý prepojený zoznam má dve časti, časť s údajmi a časť s adresou, ktorá obsahuje adresu nasledujúceho prvku v zozname, ktorý sa nazýva uzol.
Veľkosť prepojeného zoznamu nie je pevná a dátové položky je možné pridávať na ľubovoľné miesta v zozname. Nevýhodou je, že aby sme sa dostali do uzla, musíme prejsť úplne z prvého uzla do uzla, ktorý požadujeme. Prepojený zoznam je ako pole, ale na rozdiel od poľa sa neukladá postupne do pamäte.
Najpopulárnejšie typy prepojeného zoznamu sú:
Príklad prepojeného zoznamu
Formát: [údaje, adresa]
Hlava -> [3 000] -> [43 1001] -> [21 1002]
V príklade je číslo 43 prítomné na mieste 1000 a adresa je prítomná na v predchádzajúcom uzle. Takto je znázornený prepojený zoznam.
Základné funkcie prepojeného zoznamu
Existuje niekoľko funkcií, ktoré možno implementovať do prepojeného zoznamu v C. Pokúsme sa im porozumieť pomocou ukážkového programu.Najskôr vytvoríme zoznam, zobrazíme ho, vložíme na ľubovoľné miesto, miesto odstránime. Nasledujúci kód vám ukáže, ako vykonávať operácie v zozname.
#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. Vložte na začiatok n ') printf (' n 4. Vložte na koniec n ') printf (' n 5. Vložte na zadanú pozíciu n ') printf (' n 6. Odstrániť z začiatku n ') printf (' n 7. Odstrániť od konca n ') printf (' n 8. Odstrániť z určenej polohy n ') printf (' n 9. Ukončiť n ') printf (' n ----------------- --------------------- n ') printf (' Zadajte svoj výber: t ') prepínač scanf ('% d ', & choice) (výber) {prípad 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 Chybná voľba: n') break}} návrat 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 ('nZadajte hodnotu dát pre uzol: 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 je prázdny: n ') return} else {ptr = start printf (' nThe List elements are: 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 ('nEnter the údajová hodnota pre uzol: 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 ('nZadajte údajovú hodnotu pre uzol: 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 (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nZadajte pozíciu pre nový uzol, ktorý sa má vložiť: t') scanf ('% d' , & pos) printf ('nZadajte údajovú hodnotu uzla: 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 (' nVymazaný prvok je:% 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 ('nVymazany element je:% dt', ptr-> info) zadarmo (ptr)} else {ptr = start while (ptr- > next! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('nVymazaný element je:% 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 ('nZadajte pozíciu uzla, ktorý sa má vymazať. : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nVymazaný prvok je:% dt ', ptr-> info) zadarmo (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nVymazaný prvok je: % dt ', ptr-> informácie) zadarmo (ptr)}}}Prvá časť tohto kódu je vytvorenie štruktúry. Prepojená štruktúra zoznamu je vytvorená tak, aby mohla obsahovať údaje a adresu podľa potreby. Toto je urobené, aby kompilátor získal predstavu o tom, ako by mal uzol byť.
štruktúrovaný uzol {int informačný štruktúrovaný uzol * ďalšie}V štruktúre máme dátovú premennú s názvom info na uchovanie údajov a premennú ukazovateľa, ktorá smeruje na adresu. S prepojeným zoznamom je možné robiť rôzne operácie, napríklad:
- vytvoriť ()
- display ()
- insert_begin ()
- insert_end ()
- ] insert_pos ()
- delete_begin ()
- delete_end ()
- delete_pos ()
Tieto funkcie sa vyvolávajú hlavnou funkciou ovládanou pomocou ponuky. V hlavnej funkcii prijímame vstupy od používateľov na základe toho, akú operáciu chce používateľ v programe vykonať. Vstup sa potom odošle do skrinky prepínača a na základe vstupu používateľa.
Na základe poskytnutého vstupu sa bude funkcia volať. Ďalej máme rôzne funkcie, ktoré je potrebné vyriešiť. Pozrime sa na každú z týchto funkcií.
Vytvoriť funkciu
Najprv je potrebné vytvoriť funkciu na vytvorenie prepojeného zoznamu. Toto je základný spôsob vytvárania prepojeného zoznamu. Pozrime sa na kód.
void create () {struct node * temp, * ptr printf ('nZadajte hodnotu údajov pre uzol: 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}}Výkon
ako implementovať hashmapu
Najskôr sa vytvoria dva ukazovatele typu uzol, ptr a teplota . Vezmeme od používateľa hodnotu, ktorú je potrebné pridať do prepojeného zoznamu, a uložíme ju do informačnej časti premennej temp a priradíme temp ďalšej, ktorá je časťou adresy, na null. Na začiatku zoznamu sa nachádza ukazovateľ spustenia. Potom skontrolujeme začiatok zoznamu. Ak je začiatok zoznamu nulový, potom začiatočnému ukazovateľovi priradíme temp. V opačnom prípade prejdeme do posledného bodu, kde boli pridané údaje.
Za týmto účelom priradíme ptr začiatočnú hodnotu a prechádzame do ptr-> next = null . Potom priradíme ptr-> ďalší adresa tepl. Podobným spôsobom je zadaný kód pre vloženie na začiatok, vloženie na koniec a vloženie na určené miesto.
Funkcia displeja
Tu je kód pre funkciu zobrazenia.
void display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n') return} else {ptr = start printf ('nThe List elements are: n') while (ptr! = NULL) {printf ('% dt', ptr-> informácie) ptr = ptr-> ďalšie}}}Výkon
Vo funkcii zobrazenia najskôr skontrolujeme, či je zoznam prázdny, a vrátime sa, ak je prázdny. V ďalšej časti priradíme začiatočnú hodnotu k ptr. Potom spustíme slučku, kým ptr nebude mať hodnotu null, a vytlačíme dátový prvok pre každý uzol, až kým nebude mať ptr hodnotu null, ktorá určuje koniec zoznamu.
Odstrániť funkciu
Tu je útržok kódu na odstránenie uzla z prepojeného zoznamu.
void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} else {printf ('nZadajte pozíciu uzol, ktorý sa má vymazať: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nVymazaný prvok je:% dt ', ptr-> informácie ) free (ptr)} else {ptr = start for (i = 0intext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nThe odstránený prvok je:% dt ', ptr-> info) free (ptr)}}}Výkon
V procese mazania najskôr skontroluje, či je zoznam prázdny, ak áno, či existuje. Ak nie je prázdny, požiada používateľa o vymazanie pozície. Akonáhle užívateľ vstúpi na pozíciu, skontroluje, či je to prvá pozícia, ak áno, ktorú priradí ptr na spustenie a presunie začiatočný ukazovateľ na ďalšie miesto a vymaže ptr. Ak pozícia nie je nula , potom spustí cyklus for od 0 po celú cestu do polohy zadanej používateľom a uloženej v poz premenná. Ak zadaná pozícia nie je prítomná, existuje príkaz if. Ak ptr sa rovná null , potom nie je prítomný.
My priradiť ptr k tepl v slučke for a ptr potom prejde na ďalšiu časť. Potom, keď sa nájde poloha. Premennú typu dočasne urobíme tak, aby udržiavala hodnotu ptr-> ďalší teda preskočenie ptr. Potom sa ptr vymaže. Podobne to možno urobiť pri prvom a poslednom odstránení prvku.
Dvojnásobne prepojený zoznam
Tento zoznam sa nazýva dvojnásobne prepojený, pretože existujú dva ukazovatele , jeden bod na ďalší uzol a ďalšie na predchádzajúci uzol. Operácie vykonávané v dvojitom prepojení sú podobné ako v prípade jednotlivo prepojeného zoznamu. Tu je kód pre základné operácie.
#include #include struct Uzol typedef struct Uzol * PtrToNode typedef PtrToNode Zoznam typedef PtrToNode Pozícia struct Uzol {int e Pozícia predchádzajúca Pozícia nasledujúca} void Vložiť (int x, Zoznam l, Pozícia p) {Pozícia 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 Delete (int x, List l) {Position p, p1, p2 p = Find (x, l) if (p! = NULL) {p1 = p -> previous p2 = p -> next p1 - > next = p -> next if (p2! = NULL) // ak uzol nie je posledným uzlom p2 -> previous = p -> previous} else printf ('Element neexistuje !!! n')} void Displej (Zoznam l) {printf ('Prvky zoznamu sú ::') Pozícia p = l-> ďalší while (p! = NULL) {printf ('% d ->', p-> e) p = p- > next}} int main () {int x, pos, ch, i Zoznam l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> predchádzajúci = NULL l-> ďalší = NULL Zoznam p = l printf ('IMPLEMENTÁCIA ZOZNAMU DVOJNÁSOBNE SPOJENÉHO ZOZNAMU L IST ADTnn ') do {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnn Zadajte výber :: ') scanf ('% d ', & ch) prepínač (ch) {prípad 1: p = l printf (' Zadajte vložený prvok :: ') scanf ('% d', & x) printf ('Zadajte pozíciu prvku ::') scanf ('% d', & pos) pre (i = 1 inext} Vložte (x, l, p) zlomový prípad 2: p = l printf ('Zadajte prvok, ktorý sa má vymazať ::') scanf ('% d', & x) Odstrániť (x, p) zlomový prípad 3: Zobraziť (l) break}} while (kap<4) } Výkon
Ako teda vidíte, koncept operácií je dosť jednoduchý. Zoznam, ktorý je dvojnásobne prepojený, má rovnaké operácie ako zoznam so samostatným odkazom, ktorý je uvedený v programovacom jazyku C. Jediný rozdiel je v tom, že existuje iná premenná adresy, ktorá pomáha pri lepšom prechádzaní zoznamu v zozname, ktorý je dvojnásobne prepojený.
Dúfam, že ste pochopili, ako vykonávať základné operácie na jednotlivo a dvojnásobne prepojenom zozname v C.
Ak sa chcete naučiť prepojený zoznam v prostredí Java, tu je a .
Ak narazíte na akékoľvek otázky, neváhajte sa ich opýtať v sekcii komentárov v „Prepojenom zozname v C“ a náš tím na ne rád odpovie.