Kihagyás

Láncolt lista

Listák

Ahogy azt láthattuk, a tömb egy igen hatékony eszköz akkor, amikor adott elemtípusú elemek sokaságát kell eltároljuk. Ezzel az adatszerkezettel hatékonyan tudjuk elérni a tömbben tárolt adatokat. Azonban ha sokszor kell törölnünk és beszúrnunk elemeket a tömbbe, látni fogjuk, hogy ez tömbök esetében nem annyira hatákony, különösen ha a tömb mérete nagy.

Az ilyen esetekben lehet megoldás a Lista adatszerkezet.

Listák esetében az elemek elérése persze nem lesz annyira triviális, mint a tömböknél, itt egy aktuális elemet tudunk kijelölni, amely elemtől be tudjuk járni a teljes listát. Neve

Lista, mint absztrakt adattípus

Jelöljük az \(elemtip\) alaptípusból képzett Lista típust \(lista\)-val, és a lista egy helyét meghatározó típust \(pozicio\)-val.

Egy listát a következő műveletek határoznak meg:

Művelet megnevezése Művelet leírása
Létesít(\(\leftarrow\) l:lista) Egy üres lista létesítése és visszaadása az l változóban.
Megszüntet(\(\leftrightarrow\) l:lista) Az l lista megszüntetése.
Kiolvas(\(\rightarrow\) p:pozicio; \(\leftarrow\) x:elemtip) A p pozíción lévő érték kiolvasása adott x, elemtip típusú változóba.
Módosít(\(\rightarrow\) p:pozicio; \(\rightarrow\) x:elemtip) A p pozíción lévő eleme értékének módosítása x-re.
Beszúr(\(\leftrightarrow\) l:lista; \(\rightarrow\) p:pozicio; \(\rightarrow\) x:elemtip) Az adott l listába a p pozíció elé szúrjuk be az x értéket.
Töröl(\(\leftrightarrow\) l:lista; \(\rightarrow\) p:pozicio) Töröljük az l lista p pozícióján lévő elemét.
Következő(\(\rightarrow\) l:lista; \(\rightarrow\) p:pozicio; \(\leftarrow\) n:pozicio) Az l lista p pozícióját követő pozíciót adja vissza n-ben.
Értékadás(\(\leftarrow\) lhs:lista; \(\rightarrow\) rhs:lista) Értékadó művelet: az lhs változó felveszi az rhs kifejezés értékét.

Láncolt lista, virtuális adattípus

A lista egy megvalósítása lehet a láncolt lista, ahol a lista elemeit egymás után láncoljuk. Minden elem ismeri a lista következő elemet (esetleg az előzőt is), illetve adott a lista első eleme, amelytől elindulva bejárhatjuk a listát. Az elérési információ általában egy pointerrel adott, amely a következő elemre, mint dinamikus változóra hivatkozik.

kep

Egy adott elem megkeresése persze nehézkes lehet, de új elemet felvenni, vagy meglevőt törölni relatív kis költséggel lehet.

A műveleteket most is absztrakt módon írjuk le egy külön headerben (lanc_t.h), megadva mellette a listát leíró adatszerkezetet:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#ifndef LANC_H
#define LANC_H

typedef ???    elem_t;          /* a lista_t elemtípusa */
typedef struct cella_t {
    elem_t adat;                            /* adatelem */
    struct cella_t *csat;          /* a következő elem  */
} cella_t;
typedef struct cella_t *pozicio_t;
typedef pozicio_t lista_t;

/* A műveletek deklarációja:                            */
void letesit(lista_t *l);
void megszuntet(lista_t *l);
void kiolvas(pozicio_t p, elem_t *x);
void modosit(pozicio_t p, elem_t x);
void beszur(lista_t *l, pozicio_t p, elem_t x);
void torol(lista_t *l, pozicio_t p);
void kovetkezo(pozicio_t p, pozicio_t *n);
void ertekadas(lista_t *lhs, lista_t rhs);

#endif // LANC_H

A konkrét megvalósítás láncolt lista esetében pedig:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdlib.h>
#include "lanc_t.h"

void letesit(lista_t *l) {
    *l = NULL;
}

void megszuntet(lista_t *l) {
    pozicio_t p = *l;
    while(p) {
        p = p->csat;
        free(*l);
        *l = p;
    }
}

void kiolvas(pozicio_t p, elem_t *x) {
    *x = p->adat;
}

void modosit(pozicio_t p, elem_t x) {
    p->adat = x;
}

void beszur(lista_t *l, pozicio_t p, elem_t x) {
    pozicio_t q = *l;
    if(q == p) {
        q = *l = malloc(sizeof(cella_t));
    } else {
        while(q->csat != p) {
            q = q->csat;
        }
        q->csat = malloc(sizeof(cella_t));
        q = q->csat;
    }
    q->csat = p;
    q->adat = x;
}

void torol(lista_t *l, pozicio_t p) {
    pozicio_t q = *l;
    if(q == p) {
        *l = p->csat;
    } else {
        while(q->csat != p) {
            q = q->csat;
        }
        q->csat = p->csat;
    }
    free(p);
}

void kovetkezo(pozicio_t p, pozicio_t *n) {
    *n = p->csat;
}

void ertekadas(lista_t *lhs, lista_t rhs) {
    megszuntet(lhs);
    if(!rhs) {
        *lhs = NULL;
        return;
    }
    pozicio_t p;
    *lhs = p = malloc(sizeof(cella_t));
    p->adat = rhs->adat;
    while((rhs = rhs->csat)) {
        p = p->csat = malloc(sizeof(cella_t));
        p->adat = rhs->adat;
    }
    p->csat = NULL;
}

Láncok bejárására írhatunk olyan függvényt amelynek paramétere az elvégzendő művelet:

1
2
3
4
5
6
7
8
typedef void (*muvelettip)(elemtip*);

void bejar(lista l, muvelettip muv) {
   for(; l != NULL; l = l->csat) {
      /* művelet a sorozat elemén */
      muv(&(l->adat));
   }
}

Ezzel a módszerrel a megvalósítás egyes technikai részleteit jobban elkülöníthetjük, érthetőbbé, átláthatóbbá, könnyen módosíthatóbbá válik a kódunk. Ha például adatszerkezetet cserélünk, a bejárását elegendő abejar() függvényben egyetlen helyen átírni, hogy a program továbbra is jól működjön.

Utolsó frissítés: 2022-11-25 15:25:14