Tartalom

• Összehasonlító táblázat
• A tömb meghatározása
• Nézzük meg néhány, a tömbökre emlékezetes fogalmat:
• A tömbökön végrehajtott műveletek a következők:
• Példa
• A kapcsolt lista meghatározása
• A kapcsolt listán végrehajtott műveletek a következők:
• Példa
• Következtetés

A fő különbség a Sor és Kapcsolódó lista szerkezetükre tekintettel. Tömbök vannak index alapú adatszerkezet, ahol minden elem egy indexhez van társítva. Másrészt a kapcsolt lista támaszkodik referenciák ahol minden csomópont az adatokból és az előző és a következő elemre mutató hivatkozásokból áll.

Alapvetõen egy tömb hasonló adatobjektumok halmaza, amelyeket szekvenciális memória helyeken tárolnak egy közös címsor alatt vagy változó néven.

Míg a csatolt lista olyan adatszerkezet, amely az elemek sorozatát tartalmazza, ahol minden elem kapcsolódik a következő elemhez. A kapcsolt lista elemében két mező található. Az egyik az Adat mező, a másik pedig a Kapcsolat mező. Az Adat mező a tárolni és feldolgozni kívánt tényleges értéket tartalmazza. Ezenkívül a link mező tartalmazza a csatolt lista következő adatelemének címét. Egy adott csomópont eléréséhez használt címet mutatónak hívunk.

Egy másik jelentős különbség a tömb és a csatolt lista között az, hogy a tömbnek rögzített mérete van, és azt előzetesen be kell jelenteni, de a Linked List nem korlátozódik a méretre, és kibővül és összehúzódik a végrehajtás során.

1. Összehasonlító táblázat
2. Meghatározás
3. Főbb különbségek
4. Következtetés

Összehasonlító táblázat

Az összehasonlítás alapja	Sor	Kapcsolódó lista
Alapvető	Ez egy rögzített számú adatelem következetes halmaza.	Rendezett készlet, amely változó számú adatelemet tartalmaz.
Méret	A nyilatkozat során meghatározták.	Nem kell megadni; növekedni és zsugorodni végrehajtás közben.
Tárolási allokáció	Az elem helyét a fordítási idő alatt osztják el.	Az elem pozícióját hozzárendeljük futási idő alatt.
Az elemek sorrendje	Tárolják egymás után	Véletlenszerűen tárolva
Az elem elérése	Közvetlen vagy véletlenszerűen elérhető, azaz adja meg a tömbindexet vagy az alindexet.	Szekvenciálisan hozzáférhető, azaz a mutató által a lista első csomópontjától induló mozgás.
Az elem beillesztése és törlése	Viszonylag lassú, mivel váltásra van szükség.	Könnyebb, gyors és hatékony.
keresés	Bináris keresés és lineáris keresés	lineáris keresés
Memória szükséges	Kevésbé	Több
Memóriahasználat	Hatástalan	Hatékony

A tömb meghatározása

A tömb meghatározása egy meghatározott számú homogén elem vagy adatelem halmaza. Ez azt jelenti, hogy a tömb csak egy típusú adatot tartalmazhat, akár az egész számot, mind a lebegőpontos számot, vagy az összes karaktert. A tömb deklarálása a következő:
int a;
Ahol az int az adattípust vagy az elem elemeket határozza meg, tömb tárolja. Az „a” egy tömb neve, a szögletes zárójelben megadott szám pedig a tömb által tárolható elemek száma, ezt a tömb méretének vagy hosszának is nevezik.

Nézzük meg néhány, a tömbökre emlékezetes fogalmat:

• A tömb egyes elemei a tömb nevének leírásával érhetők el, amelyet index vagy alindex követ (az elem helyének meghatározása a tömbben) a szögletes zárójelben. Például a tömb ötödik elemének lekérdezéséhez egy a állítást kell írni.
• A tömb elemeit mindenképpen egymást követő memóriahelyen tárolják.
• A tömb legelső elemének nulla indexe van. Ez azt jelenti, hogy az első és az utolsó elem lesz a, illetve az elem.
• A tömbben tárolható elemek számát, azaz a tömb méretét vagy hosszát a következő egyenlet adja meg:
  (felső határ - alsó határ) + 1
  A fenti tömb esetében ez (9-0) + 1 = 10 lenne. Ahol 0 a tömb alsó határa, és 9 a tömb felső határa.
• A tömbök a hurkon keresztül olvashatók vagy írhatók. Ha elolvassa az egydimenziós tömböt, akkor egy hurkot igényel az olvasáshoz, a másikt pedig a tömb írásához (hozzáadásához), például:
  a. Tömb olvasásához
  (i = 0; i <= 9; i ++)
  {scanf („% d”, & a); }
  b. Tömb írására
  (i = 0; i <= 9; i ++)
  {f („% d”, a); }
• 2D-s tömb esetén két hurokra lenne szükség, és hasonlóan az n-dimenziós tömbnek n hurokra lenne szüksége.

A tömbökön végrehajtott műveletek a következők:

1. Tömb létrehozása
2. Egy tömb áthaladása
3. Új elemek beillesztése
4. A szükséges elemek törlése.
5. Egy elem módosítása.
6. Tömbök egyesítése

Példa

A következő program szemlélteti a tömb olvasását és írását.

#include
#include
érvénytelen fő ()
{
int a, i;
f ("Írja be a tömböt");
(i = 0; i <= 9; i ++)
{
scanf ("% d", & a);
}
f ("Írja be a tömböt");
(i = 0; i <= 9; i ++)
{
f ("% d n", a);
}
getch ();
}

A kapcsolt lista meghatározása

A kapcsolt lista az egyes, egymással összekapcsolt adatelemek különleges listája. Ebben minden elem a következő elemre mutat, amely a logikai sorrendet képviseli. Minden elemet csomópontnak hívunk, amely két részből áll.

INFO rész, amely az információkat tárolja, és a PONT, amely a következő elemre mutat. Mint tudod a cím tárolására, van egy egyedi adatszerkezetünk C-ben, úgynevezett mutatók. Ezért a lista második mezőjének mutató típusúnak kell lennie.

Az összekapcsolt listák típusai: Egyszeresen összekapcsolt lista, Kettős módon összekapcsolt lista, Körkörös módon összekapcsolt lista, Kör alakban kettős módon összekapcsolt lista.

A kapcsolt listán végrehajtott műveletek a következők:

1. Teremtés
2. elmozdulási
3. beszúrás
4. Törlés
5. keresés
6. láncolat
7. Kijelző

Példa

A következő kivonat szemlélteti egy összekapcsolt lista létrehozását:

struct csomópont
{
int num;
stukk csomópont * következő;
}
start = NULL;
érvénytelen létrehozás ()
{
typedef struct node NODE;
NODE * p, * q;
char választás;
első = NULL;
csinál
{
p = (NODE *) malloc (méret (NODE));
f ("Írja be az adatelemet n");
scanf ("% d", & p -> num);
if (p == NULL)
{
q = kezdés;
míg (q -> következő! = NULL)
{q = q -> következő
}
p -> következő = q -> következő;
q -> = p;
}
más
{
p -> következő = kezdés;
start = p;
}
f ("Folytatni szeretné (y vagy n betűt?)? n");
scanf ("% c", és választás);
}
míg ((választás == y) || (választás == y));
}

1. Egy tömb az adatszerkezet hasonló típusú adatelemek gyűjteményét tartalmazza, míg a Linked listát nem primitív adatszerkezetnek tekintjük csomópontként ismert rendezetlen összekapcsolt elemek gyűjteményét.
2. A tömbben az elemek indexekhez tartoznak, azaz ha a negyedik elembe akar bejutni, akkor meg kell írni a változó nevét indexével vagy helyével a szögletes zárójelben.
   Egy összekapcsolt listában azonban a fejről kell kezdenie, és végig kell dolgoznia, amíg el nem éri a negyedik elemet.
3. Míg az elemek tömbjének elérése gyors, míg a Linked lista lineáris időt vesz igénybe, így kissé lassabb.
4. Az olyan műveletek, mint a tömbök beillesztése és törlése, sok időt vesznek igénybe. Másrészt ezeknek a műveleteknek a végrehajtása a kapcsolódó listákban gyors.
5. A tömbök rögzített méretűek. Ezzel szemben a kapcsolt listák dinamikusak és rugalmasak, és kibővíthetik és csökkenthetik méretüket.
6. Egy tömbben a memória a fordítási idő alatt van hozzárendelve, míg a Linked listában a végrehajtás vagy a futási idő alatt lesz hozzárendelve.
7. Az elemeket egymás után tárolják tömbökben, míg véletlenszerűen a Linked listákban.
8. A memóriaigény kevésbé annak köszönhető, hogy a tényleges adatokat a tömb indexében tárolják. Ellenkezőleg, a további következő és korábbi hivatkozási elemek tárolása miatt további memóriára van szükség a kapcsolt listákban.
9. Ezen felül a memória kihasználása nem hatékony a tömbben. Ezzel szemben a memóriahasználat hatékony a tömbben.

Következtetés

A tömb és a kapcsolt lista az adatstruktúrák típusai különböznek felépítésük, hozzáférési és kezelési módszereik, memóriaigényük és felhasználásuk szempontjából. És különös előnyei és hátrányai vannak a megvalósításhoz képest. Következésképpen bármelyik igény igény szerint felhasználható.