A tömbök után a második legnépszerűbb adatstruktúra a Linked List. A kapcsolt lista egy lineáris adatstruktúra, amely csomópontok láncolatából áll, amelyben minden csomópont tartalmaz egy értéket és egy mutatót a lánc következő csomópontjára. Ebben a cikkben nézzük meg, hogyan lehet egy összekapcsolt listát C-ben megvalósítani.
Mi a linkelt lista a C-ben?
A kapcsolt lista egy lineáris adatstruktúra. Minden összekapcsolt listának két része van, az adat szakasz és a cím szakasz, amely a lista következő elemének címét tartalmazza, amelyet csomópontnak hívnak.
A linkelt lista mérete nincs rögzítve, és az adatok a lista bármely helyén hozzáadhatók. Hátránya, hogy egy csomópont eléréséhez át kell haladnunk az első csomóponttól a kívánt csomópontig. A csatolt lista olyan, mint egy tömb, de egy tömbtől eltérően nem tárolódik egymás után a memóriában.
A linkelt lista legnépszerűbb típusai:
fájlok használata a Java-ban
Példa összekapcsolt listára
Formátum: [adatok, cím]
Fej -> [3,1000] -> [43,1001] -> [21,1002]
A példában a 43-as szám az 1000-es helyen van, a cím pedig az előző csomópontban van. Így van ábrázolva egy összekapcsolt lista.
Csatolt lista alapvető funkciói
A C-ben lévő összekapcsolt listán több funkció is megvalósítható. Próbáljuk megérteni őket egy példa program segítségével.Először létrehozunk egy listát, megjelenítjük, beillesztünk bármilyen helyre, törölünk egy helyet. A következő kód megmutatja, hogyan kell végrehajtani a listán szereplő műveleteket.
#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 csomópont {int info struct csomópont * következő} struct csomópont * 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. a kezdő n ') printf (' n 4.Insert in n 'n') printf ('n 5.Beillesztés az n meghatározott pozícióba') printf ('n 6.Delete from n elejétől') printf ('n 7.Delete n ') végéből n) printf (' n 8.Törlés az n megadott pozícióból ') printf (' n 9.Exit n ') printf (' n ----------------- --------------------- n ') printf (' Írja be a választást: t ') scanf ('% d ', & choice) kapcsoló (választás) {eset 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 csomópont * temp, * ptr temp = (struct csomópont *) malloc (sizeof (struct csomópont)) if (temp == NULL) {printf ('nOUT of Memory Space: n') exit (0) } printf ('nAdja meg a csomópont adatértékét: 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 csomópont * ptr if (start == NULL) {printf ('nList üres: n ') return} else {ptr = printf indítása (' nA lista elemei: n '), míg (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> next}}} void insert_begin () {struct csomópont * temp temp = (struct csomópont *) malloc (sizeof (struct csomópont)) if (temp == NULL) {printf ('n A memóriaterületen kívül: n') visszatér} printf ('n a csomópont adatértéke: t ') scanf ('% d ', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {temp-> next = start start = temp }} void insert_end () {struct csomópont * temp, * ptr temp = (struct csomópont *) malloc (sizeof (struct csomópont)) if (temp == NULL) {printf ('n A memóriaterületen kívül: n') visszatér} o rintf ('nAdja meg a csomópont adatértékét: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> következő! = NULL) {ptr = ptr-> következő} ptr-> next = temp}} void insert_pos () {struct csomópont * ptr, * temp int i, pos temp = (struct csomópont *) malloc ( sizeof (struct node)) if (temp == NULL) {printf ('n A memóriaterület nem: n') return} printf ('nAdja meg a beillesztendő új csomópont helyzetét: t') scanf ('% d' , & pos) printf ('nAdja meg a csomópont adatértékét: 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 ('nPozíció nem található: [Óvatosan kezelje] n') return}} temp-> következő = ptr-> következő ptr -> next = temp}} void delete_begin () {struct csomópont * ptr if (ptr == NULL) {printf ('nList is üres: n') return} else {ptr = start start = start-> next printf (' nA törölt elem a következő:% dt ', ptr-> info) szabad (ptr)}} void delete_end () {struct csomópont * temp, * ptr if (start == NULL) {printf (' nList is üres: ') exit (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ('nA törölt elem:% dt', ptr-> info) ingyenes (ptr)} else {ptr = start while (ptr- > következő! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('nA törölt elem:% dt', ptr-> info) ingyenes (ptr)}} void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nA lista üres: n') exit (0)} else {printf ('nAdja meg a törölni kívánt csomópont helyzetét : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nA törölt elem:% dt ', ptr-> info) ingyenes (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nA törölt elem: % dt ', ptr-> info) ingyenes (ptr)}}}A kód első része létrehoz egy struktúrát. Összekapcsolt listaszerkezet jön létre, hogy megtartsa az adatokat és a címet, amire szükségünk van. Ez azért történik, hogy a fordító képet kapjon arról, hogy milyen legyen a csomópont.
struct csomópont {int info struct csomópont * következő}A struktúrában van egy adatváltozó, az úgynevezett info az adatok tárolására, és egy mutatóváltozó, amely a címre mutat. Különböző műveletek hajthatók végre egy összekapcsolt listán, például:
- teremt()
- kijelző()
- insert_begin ()
- insert_end ()
- ] insert_pos ()
- delete_begin ()
- delete_end ()
- delete_pos ()
Ezeket a funkciókat a menü által vezérelt fő funkció hívja meg. A fő funkcióban a felhasználótól veszünk inputot annak alapján, hogy a felhasználó milyen műveletet szeretne végrehajtani a programban. Ezután a bemenetet elküldi a kapcsolótáskának, és a felhasználói bevitel alapján.
A megadott bemenet alapján a függvény meghívásra kerül. Ezután különböző funkciók vannak, amelyeket meg kell oldani. Vessünk egy pillantást ezekre a funkciókra.
Funkció létrehozása
Először is van egy létrehozási függvény a csatolt lista létrehozásához. Ez az összekapcsolt lista létrehozásának alapvető módja. Nézzük meg a kódot.
void create () {struct csomópont * temp, * ptr printf ('nAdja meg a csomópont adatértékét: 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}}Kimenet
Először két mutató jön létre a típusból csomópont, ptr és temp . A csatolt listához hozzáadandó értéket a felhasználótól vesszük, és a temp változó info részében tároljuk, és a következő értéket, amely a cím része, null-hoz rendeljük. Van egy kezdő mutató, amely a lista elejét tartja. Ezután ellenőrizzük a lista elejét. Ha a lista kezdete null, akkor a kezdő mutatóhoz temp-ot rendelünk. Ellenkező esetben átmegyünk az utolsó ponthoz, ahová az adatokat hozzáadtuk.
Ehhez hozzárendeljük a ptr kezdőértékét és a traverse till-et ptr-> következő = null . Ezután kijelöljük ptr-> következő a hőmérséklet címe Hasonló módon van megadva kód az elején történő behelyezéshez, a végén történő behelyezéshez és a megadott helyre történő behelyezéshez.
Kijelző funkció
Itt van a megjelenítési funkció kódja.
void display () {struct csomópont * ptr if (start == NULL) {printf ('nList is empty: n') return} else} else {ptr = printf indítása ('nA lista elemei: n') míg (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> következő}}}Kimenet
A megjelenítési funkcióban először ellenőrizzük, hogy a lista üres-e, és visszatérünk, ha üres. A következő részben a kezdeti értéket hozzárendeljük a ptr-hez. Ezután futtatunk egy ciklust, amíg a ptr null értéke nem lesz, és kinyomtatjuk az egyes csomópontok adatelemét, amíg a ptr null, ami megadja a lista végét.
Funkció törlése
Itt található a kódrészlet egy csomópont törléséhez a csatolt listából.
void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nA lista üres: n') exit (0)} else {printf ('nAdja meg a törlendő csomópont: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nTörölt elem:% dt ', ptr-> info ) free (ptr)} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> következő printf ('nThe a törölt elem:% dt ', ptr-> info) ingyenes (ptr)}}}Kimenet
A törlési folyamat során először ellenőrzi, hogy a lista üres-e, ha igen, akkor létezik. Ha nem üres, akkor a pozíció törlését kéri a felhasználótól. Miután a felhasználó belépett a pozícióba, ellenőrzi, hogy ez az első pozíció, ha igen, akkor hozzárendeli ptr az indításhoz és a kezdőmutató áthelyezéséhez a következő helyre, és törli a ptr. Ha a pozíció nem nulla , akkor egy for for ciklust futtat 0-tól egészen a felhasználó által beírt és a pozíció változó. Van egy if nyilatkozat annak eldöntésére, hogy a beírt pozíció nincs-e jelen. Ha A ptr értéke null , akkor nincs jelen.
Mi rendelje a ptr-t a temp-hoz a for ciklusban, és a ptr továbblép a következő részre. Ezek után, amikor a pozíció megtalálható. A temp változót megtartjuk az értékének megtartására ptr-> következő így kihagyva a ptr-t. Ezután a ptr törlődik. Hasonlóképpen meg lehet csinálni az első és az utolsó elem törlésére.
Kétségkívül összekapcsolt lista
Kétszer linkelt listának hívják, mert kettő van mutatók , egy pont a következő csomópontra, más pontok pedig az előző csomópontra. A kettős összekapcsolással végrehajtott műveletek hasonlóak az egyenként összekapcsolt listához. Itt van az alapvető műveletek kódja.
#include #include struct Csomópont typedef struct Csomópont * PtrToNode typedef PtrToNode List typedef PtrToNode Pozíció struktúra csomópont {int e Pozíció előző pozíció következő} void Insert (int x, List l, Pozíció p) {Position TmpCell TmpCell = (struct Node *) malloc (sizeof (struct Node)) if (TmpCell == NULL) printf ('Memória elfogyott a térből') else {TmpCell-> e = x TmpCell-> előző = p TmpCell-> következő = p-> következő p-> következő = TmpCell}} void Törlés (int x, L lista) {p, p1, p2 pozíció p = Find (x, l) if (p! = NULL) {p1 = p -> előző p2 = p -> következő p1 - > next = p -> next if (p2! = NULL) // ha a csomópont nem az utolsó csomópont p2 -> előző = p -> előző} else printf ('Elem nem létezik !!! n')} érvénytelen Megjelenítés (L lista) {printf ('A listaelem ::') Pozíció p = l-> következő, míg (p! = NULL) {printf ('% d ->', p-> e) p = p- > következő}} int main () {int x, pos, ch, i Lista l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> előző = NULL l-> next = NULL List p = l printf ('L. KETTŐSEN CSATLAKOZOTT LISTA FELVÉTELE IST ADTnn ') do {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnn Adja meg a választás :: ') scanf ('% d ', & ch) kapcsolót (ch) {eset 1: p = l printf (' Írja be a beillesztendő elemet :: ') scanf ('% d', & x) printf ('Írja be az :: elem helyét') scanf ('% d', & pos) (i = 1 ikövetkező} Insert (x, l, p) break case 2: p = l printf ('Írja be a törlendő elemet ::') scanf ('% d', & x) Delete (x, p) break case 3: Display (l) törés}} közben (ch<4) } Kimenet
Tehát, amint láthatja, a műveletek fogalma meglehetősen egyszerű. A kétszeresen összekapcsolt listának ugyanazok a műveletei vannak, mint az egyszeresen összekapcsolt listának a C programozási nyelven. Az egyetlen különbség az, hogy van egy másik címváltozó, amely segít jobban átlépni a listát egy kétszeresen összekapcsolt listában.
Remélem, megértette, hogyan kell elvégezni az alapvető műveleteket a C-ben szereplő, kettős linkkel ellátott listán.
Ha szeretné megtanulni a Linkelt listát Java-ban, itt van a .
Ha bármilyen kérdése merülne fel, nyugodtan tegye fel minden kérdését a „Csatolt lista C-ben” megjegyzés rovatban, és csapatunk örömmel válaszol.