1.1.1
Struktúrák és mutatók
A korábbiakban már volt szó a strutúrákról. Pointerekkel
hivatkozhatunk a struktúrk egyes elemeire is, mint azt a következő példában
láthatjuk.
struct datum
{ int ev,ho,nap};
struct datum *map;
Az így létrehozott mutatónak értéket adhatunk, illetve értékét
lekérdezhetjük.
(*map).ev=2001; (*map).ho=2; (*map).nap=14;
Mivel a C-ben elég gyakori a strutúrák és a pointerek
használata, a fenti hivatkozásoknak van egy másik alakja is.
map->ev=2001;map->ho=2;map->14;
A két hivatkozás egymással teljesen egyenértékű, de a C
programokban és a szakirodalomban a második lényegesen elterjedtebb.
1.1.2
Dinamikus lista
A lista olyan adtaszerkezet, melynek minden egyes eleme két jól
elkülöníthető részből áll, az adatrészből és egy mutatóból, mely a lista
következő elemére mutat. A lista első elemére a listafejjel hivatkozhatunk. A
lista utolsó elemének mutató mezője pedig NULL értékű.
A fenti ábrán a szürke az adatrész a fekete pedig a mutató
rész.
A lista szerkezetnek sok előny van egy vektorhoz képest. Egy
listában tnyleg mindig csak annyi elem van, amennyire éppen szükségünk van. A
szerkezet módosítása is nagyon egyszerű. Ha egy új adatot akarunk felvenni,
akkor
1.
megkeressük az új elem helyét
2.
az aktuális adat mutaóját átmásoljuk az új elem
mutatójába
3.
az aktuális elem mutatóját az új elemre irányítjuk
Ha egy listából egy elemet törölni akarunk, akkor a
következőképpen járhatunk el:
1.
megkeressük a törlendő elemet
2.
a mutatóját bemásoljuk az előtte lévő elem mutatójába
Nézzük ezt először egy egyszerű programon keresztül. Először
létrehozunk egy struktúrát, a struktúra mutató mezője egy ugyanilyen típusú
struktúrára hivatkozik, ezt nevezzük önhivatkozó struktúrának.
#include <stdio.h>
struct lista {
int value;
struct lista *next;
};
main()
{
struct lista n1,
n2, n3, n4;
struct lista
*lista_pointer = &n1;
n1.value = 100;
n1.next = &n2;
n2.value = 200;
n2.next = &n3;
n3.value = 300;
n3.next = &n4;
n4.value = 400;
n4.next = 0;
while(
lista_pointer != 0 ) {
printf("%d\n", lista_pointer->value);
lista_pointer = lista_pointer->next;
}
}
Ez még így egyáltalán nem dinamikus, csak a lista használatát
figyelhetjük meg rajta. Vegyük észre, hogy az a sok értékadás a listázás előtt,
ciklikus folyamat, nyilván nem érdemes ilyen sokszor leírni.
n1.next = n2.next;
n2_3.next =
n2.next;
n2.next = &n2_3;
Mi történik a listával a fenti értékadások hatására?
A következő program már egy dinamikus lista megvalósítására
mutat példát.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct data
{
int value;
struct data *nxt;
};
struct data *head=NULL,
*prev, *akt, *next;
void list()
{
akt=head;
while (akt!=NULL)
{
printf("%5d",akt->value);
akt=akt->nxt;
}
}
main()
{
char c;
int i=0,sv;
clrscr();
randomize();
printf("Következő szám ");
scanf("%d",&sv);
while (sv>0)
{
akt=(struct
data *) malloc(sizeof(struct data));
if
(!akt)
{
printf("Nincs elég memória!");
return -1;
}
akt->value=sv;
akt->nxt=NULL;
if
(i==0)
head=prev=akt;
else
{
prev->nxt=akt;
prev=akt;
}
printf("Következő szám ");
scanf("%d",&sv);
i++;
}
printf("\n");
list();
while ((c=getch()) !=13);
}
A főprogramban lévő while ciklussal pozitív számokat olvasunk
be, és ezeket fűzzük föl egy dinamikus listába. Látszik, hogy a listában mindig
csak a következő elem számára foglalunk helyet a
malloc függvénnyel. A lista feltöltése után meghívott
list() függvény a fölvett elemeket listázza ki.