Spojový seznam
V programování rozlišujeme statické a dynamické datové struktury. Statické datové struktury mají po celou dobu trvání programu stejnou velikost. Dynamické datové struktury přizpůsobují svou velikost počtu uložených informací. Jejich principem je dynamické přidělování a uvolňování paměti za běhu programu. Jsou to například spojové seznamy nebo stromové struktury
Obousměrný spojový seznam
Spojový seznam patří mezi dynamické datové struktury. Jedná se o lineárně uspořádané prvky, které jsou propojeny ukazateli. Pokud ukazatel neukazuje na žádný prvek, má hodnotu NULL. Seznam může být jednosměrný (každý prvek má ukazatel na následující prvek) nebo obousměrný (každý prvek má ukazatel na předchozí i následující prvek).
V obousměrném seznamu platí, že první prvek seznamu nemá předchůdce a poslední prvek nemá následovníka. Jednotlivé odpovídající ukazatele ukazují do "prázdna", mají hodnotu NULL.
Vstupním bodem do spojového seznamu je ukazatel na jeho první prvek, který se také nazývá hlavička (head). Prázdný spojový seznam poznáme tak, že do prázdna ukazuje už přímo jeho hlavička. Pro zefektivnění práce se seznamem můžeme ještě používat další ukazatel, a to na poslední prvek v seznamu.
Každý prvek v sobě nese datovou hodnotu (například číslo, znak, datovou strukturu nebo objekt) a ukazatel. Při vysvětlení principu práce se seznamem (přidávání, procházení, odstraňování...) se však konkrétním obsahem dat nemusíme zabývat. Je ale zřejmé, že bez datových hodnot samotný seznam nemá vůbec smysl.
Definice datového typu pro prvek seznamu:
typedef struct data {
int cislo;
//další datové položky různých typů
struct data *nasl, *pred; //ukazatel na následující a předchozí prvek seznamu
}Tdata;
Vkládání informací do spojového seznamu
Na začátku práce se spojovým seznamem je seznam prázdný:
Tdata *prvni = NULL; //inicializace spojového seznamu
Pokud vkládáme nový prvek do spojového seznamu, postupujeme následovně:
- alokování místa pro nový prvek
- naplnění datových položek - načtení potřebných informací z klávesnice nebo ze souboru
- zařazení nového prvku do obousměrného spojového seznamu
Nové prvky můžeme přidávat na začátek nebo na konec seznamu, případně je můžeme vkládat na určené místo uprostřed spojového seznamu. V následujícím kódu je prvek umístěn na začátek seznamu, hodnoty zadáváme z klávesnice.
Tdata *novy;
int id;
/* alokování místa pro nový prvek */
novy = (Tdata*) malloc(sizeof(Tdata));
if(novy == NULL)
{
printf("Nedostatek pameti !\n");
system("pause");
exit (1);
}
novy->pred = NULL;
novy->nasl = NULL;
/* naplnění datových položek */
printf("cislo :");
scanf("%d",&id);
novy->cislo = id;
//zadání hodnot pro další datové položky
/* zařazení nového prvku na začátek seznamu */
if (prvni != NULL)
{
prvni->pred = novy;
novy->nasl = prvni;
prvni = novy;
}
else
{
prvni = novy;
}
Procházení spojového seznamu
Tdata *p;
for( p = prvni; p != NULL; p = p->nasl)
{
//zpracování hodnot prvku, na který ukazuje ukazatel p
}
Práce se souborem
Pro ukládání hodnot ze spojového seznamu je vhodnější použít binární soubor než textový. Do binárního souboru ukládáme celou strukturu najednou. Pokud uložíme celou strukturu včetně ukazatelů, musíme si uvědomit, že při načítání hodnot ze souboru ukazatele znovu nastavujeme podle aktuálně přiděleného místa v paměti.
//ulozeni informaci z dynamickeho seznamu do binarniho souboru
FILE *f;
Tdata *p;
f=fopen("udaje.dat","wb") ;
if(f == NULL)
{
//printf("\nSoubor se nepovedlo otevrit\n");
return -1;
}
for( p = prvni; p != NULL; p = p->nasl)
{
fwrite(p, sizeof(Tdata), 1, f);
}
if (fclose(f)==EOF)
{
//printf("Soubor se nepodarilo zavrit");
return -1;
}
Použití vnořených struktur
Ve spojovém seznamu je vhodné oddělit ukazatele od samotných informací. Použijeme vnořené struktury tzn. strukturu ve struktuře.
typedef struct {
int cislo;
char jmeno[20];
//další datové položky různých typů
}Tinfo;
typedef struct data {
Tinfo inf;//"balíček informací"
struct data *nasl, *pred; //ukazatel na následující a předchozí prvek seznamu
}Tdata;
Ukázka přístupu k položkám vnořené struktury z výše uvedeného příkladu:
Tdata *x;
x->inf.cislo = 7;
strcpy(x->inf.jmeno, "Alois");
Výhody použití vnořené struktury:
- se všemi informacemi, které do seznamu chceme uložit (např. číslo, jméno, příjmení, věk, ...), můžeme pracovat jako s celkem - jedna proměnná inf. Hodně nám to usnadní např. záměnu informací ve dvou uzlech seznamu při řazení.
- při použití binárního souboru: ukládáme jenom informace, ne ukazatele. Je zbytečné ukládat ukazatele na následující a předchozí prvek. Jejich platnost je omezená na umístění spojového seznamu v operační paměti. Při vytváření seznamu se tyto ukazatele nastavují podle aktuálně přidělené paměti.