Po polích je druhou nejoblíbenější datovou strukturou Propojený seznam. Propojený seznam je lineární datová struktura vytvořená z řetězce uzlů, v nichž každý uzel obsahuje hodnotu a ukazatel na další uzel v řetězci. V tomto článku se podívejme, jak implementovat propojený seznam v jazyce C.
Co je to propojený seznam v C?
Propojený seznam je lineární datová struktura. Každý propojený seznam má dvě části, část dat a část adresy, která obsahuje adresu dalšího prvku v seznamu, který se nazývá uzel.
Velikost propojeného seznamu není pevná a datové položky lze přidat na libovolné místo v seznamu. Nevýhodou je, že abychom se dostali do uzlu, musíme přejet až k prvnímu uzlu do uzlu, který požadujeme. Propojený seznam je jako pole, ale na rozdíl od pole se neukládá postupně do paměti.
Nejpopulárnější typy propojeného seznamu jsou:
Příklad propojeného seznamu
Formát: [data, adresa]
Hlava -> [3 000] -> [43 1001] -> [21 1002]
V příkladu je číslo 43 přítomno na místě 1000 a adresa je přítomna na v předchozím uzlu. Takto je znázorněn propojený seznam.
Základní funkce propojeného seznamu
Existuje několik funkcí, které lze implementovat do propojeného seznamu v C. Pokusme se jim porozumět pomocí ukázkového programu.Nejprve vytvoříme seznam, zobrazíme jej, vložíme na libovolné místo, odstraníme místo. Následující kód vám ukáže, jak provádět operace v seznamu.
#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 volba while (1) {printf ('n MENU n') printf ('n 1. Create n') printf ('n 2. Display n') printf ('n 3. Vložte na začátek n ') printf (' n 4. Vložit na konec n ') printf (' n 5. Vložit na zadanou pozici n ') printf (' n 6. Odstranit od začátku n ') printf (' n 7. Odstranit od konce n ') printf (' n 8. Odstranit ze zadané polohy n ') printf (' n 9. Ukončit n ') printf (' n ----------------- --------------------- n ') printf (' Zadejte svůj výběr: t ') přepínač scanf ('% d ', & choice) (výběr) {případ 1 : create () případ přerušení 2: display () případ přerušení 3: insert_begin () případ přerušení 4: insert_end () případ přerušení 5: insert_pos () případ přerušení 6: delete_begin () případ přerušení 7: delete_end () případ přerušení 8: delete_pos () případ přerušení 9: exit (0) konec výchozí: printf ('n Špatná volba: n') konec}} 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 ('nZadejte hodnotu dat pro uzel: 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 ') návrat} else {ptr = start printf (' nListové prvky jsou: n ') while (ptr! = NULL) {printf ('% dt ', ptr-> informace) ptr = ptr-> další}}} 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 datová hodnota pro uzel: 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} str rintf ('nZadejte hodnotu dat pro uzel: 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 ('nZadejte pozici pro nový uzel, který má být vložen: t') scanf ('% d' , & pos) printf ('nZadejte hodnotu dat uzlu: 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ý prvek 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 ('nVymazaný prvek je:% dt', ptr-> informace) zdarma (ptr)} else {ptr = start while (ptr- > next! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('nVymazaný prvek je:% dt', ptr-> informace) 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 ('nZadejte polohu uzlu, který má být smazán : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nVymazaný prvek je:% dt ', ptr-> informace) zdarma (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nVymazaný prvek je: % dt ', ptr-> informace) zdarma (ptr)}}}První částí tohoto kódu je vytvoření struktury. Propojená struktura seznamu je vytvořena tak, aby mohla obsahovat data a adresu tak, jak to potřebujeme. To se provádí proto, aby kompilátor získal představu o tom, jak by uzel měl být.
strukturovaný uzel {int info strukturovaný uzel * další}Ve struktuře máme datovou proměnnou nazvanou info pro uložení dat a proměnnou ukazatele, která ukazuje na adresu. Na propojeném seznamu lze provádět různé operace, například:
- vytvořit()
- Zobrazit()
- insert_begin ()
- insert_end ()
- ] insert_pos ()
- delete_begin ()
- delete_end ()
- delete_pos ()
Tyto funkce jsou vyvolány hlavní funkcí ovládanou pomocí nabídky. V hlavní funkci vezmeme vstup od uživatele na základě toho, jakou operaci chce uživatel v programu provést. Vstup je poté odeslán do skříně přepínače a na základě vstupu uživatele.
Na základě zadaného vstupu bude funkce volána. Dále máme různé funkce, které je třeba vyřešit. Podívejme se na každou z těchto funkcí.
Vytvořit funkci
Nejprve existuje funkce vytvoření pro vytvoření propojeného seznamu. Toto je základní způsob vytváření propojeného seznamu. Pojďme se podívat na kód.
void create () {struct node * temp, * ptr printf ('nZadejte hodnotu dat pro uzel: 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ýstup
jak vygenerovat náhodný řetězec v javě
Nejprve se vytvoří dva ukazatele typu uzel, ptr a teplota . Vezmeme hodnotu, kterou je třeba přidat do propojeného seznamu od uživatele, a uložíme ji do informační části proměnné temp a přiřadíme temp další, což je část adresy na null. Na začátku seznamu je ukazatel začátku. Poté zkontrolujeme začátek seznamu. Pokud je začátek seznamu nulový, pak přiřadíme temp počátečnímu ukazateli. Jinak přejdeme do posledního bodu, kde byla přidána data.
Za tímto účelem přiřadíme ptr počáteční hodnotu a přejdeme do ptr-> next = null . Poté přiřadíme ptr-> další adresa teploty Podobným způsobem je zadán kód pro vložení na začátek, vložení na konec a vložení na určené místo.
Funkce displeje
Zde je kód pro funkci zobrazení.
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-> informace) ptr = ptr-> další}}}Výstup
Ve funkci zobrazení nejprve zkontrolujeme, zda je seznam prázdný, a vrátíme se, pokud je prázdný. V další části přiřadíme počáteční hodnotu ptr. Poté spustíme smyčku, dokud není ptr null, a vytiskneme datový prvek pro každý uzel, dokud ptr nebude null, což určuje konec seznamu.
Funkce mazání
Zde je úryvek kódu k odstranění uzlu z propojeného seznamu.
void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} else {printf ('nZadejte pozici uzel k odstranění: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> další printf (' nVymazaný prvek je:% dt ', ptr-> informace ) free (ptr)} else {ptr = start for (i = 0intext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nThe odstraněný prvek je:% dt ', ptr-> informace) zdarma (ptr)}}}Výstup
V procesu mazání nejprve zkontroluje, zda je seznam prázdný, pokud ano, existuje. Pokud není prázdný, požádá uživatele o vymazání pozice. Jakmile uživatel zadá pozici, zkontroluje, zda se jedná o první pozici, pokud ano, přiřadí ji ptr spustit a přesune počáteční ukazatel na další místo a odstraní ptr. Pokud pozice není nula , poté spustí smyčku for od 0 až do polohy zadané uživatelem a uložené v souboru poz proměnná. Pokud není zadaná pozice přítomna, existuje příkaz if. Li ptr se rovná null , pak není přítomen.
My přiřadit ptr temp ve smyčce for a ptr pak přejde na další část. Poté, když je nalezena pozice. Uděláme dočasnou proměnnou, abychom udrželi hodnotu ptr-> další čímž přeskočíte ptr. Poté je ptr odstraněn. Podobně to lze provést pro první a poslední odstranění prvku.
Dvojnásobně propojený seznam
Říká se tomu dvojnásobně propojený seznam, protože existují dva ukazatele , jeden bod na další uzel a další na předchozí uzel. Operace prováděné v dvojnásobně propojeném jsou podobné jako u jednotlivě propojeného seznamu. Tady je kód pro základní operace.
#include #include struct Uzel typedef struct Uzel * PtrToNode typedef PtrToNode Seznam typedef PtrToNode Pozice struct Uzel {int e Pozice předchozí Pozice další} void Vložit (int x, Seznam l, Pozice p) {Pozice 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) {Pozice p, p1, p2 p = Najít (x, l) if (p! = NULL) {p1 = p -> předchozí p2 = p -> další p1 - > next = p -> next if (p2! = NULL) // pokud uzel není posledním uzlem p2 -> previous = p -> previous} else printf ('Element neexistuje !!! n')} void Zobrazit (Seznam l) {printf ('Prvky seznamu jsou ::') Pozice p = l-> další while (p! = NULL) {printf ('% d ->', p-> e) p = p- > next}} int main () {int x, pos, ch, i Seznam l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> předchozí = NULL l-> další = NULL Seznam p = l printf ('IMPLEMENTACE SEZNAMU DVOJÍCH PŘIPOJENÝCH SEZNAMŮ L IST ADTnn ') do {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnn Zadejte volbu :: ') scanf ('% d ', & ch) přepínač (ch) {případ 1: p = l printf (' Zadejte vložený prvek :: ') scanf ('% d', & x) printf ('Zadejte pozici prvku ::') scanf ('% d', & pos) pro (i = 1 idalší} Vložit (x, l, p) případ přerušení 2: p = l printf ('Zadejte prvek, který má být odstraněn ::') scanf ('% d', & x) Odstranit (x, p) případ přerušení 3: Zobrazit (l) break}} while (kap<4) } Výstup
Jak vidíte, koncept operací je docela jednoduchý. Seznam s dvojnásobným propojením má stejné operace jako seznam se samostatným propojením v programovacím jazyce C. Jediný rozdíl je v tom, že existuje další proměnná adresy, která pomáhá lépe procházet seznam v seznamu, který je dvojnásobně propojen.
Doufám, že jste pochopili, jak provádět základní operace na jednotlivě a dvojnásobně propojeném seznamu v C.
Pokud se chcete naučit odkazovaný seznam v Javě, zde je a .
Pokud narazíte na jakékoli dotazy, neváhejte se zeptat na všechny své dotazy v sekci komentářů v „Propojeném seznamu v C“ a náš tým vám rád odpoví.