headerphoto

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 základem je dynamické přidělování paměti. 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).

seznam.png, 497B

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 id;
    //další datové položky různých typů
    struct data *nasl, *pred; //ukazatel na následující a předchozí prvek seznamu
    }Tdata;

Poznámka: všechny datové položky můžeme taky definovat jako vnořenou strukturu. Je to výhodnější pro oddělení datové části prvků seznamu od ukazatelů.


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 hned za hlavičku seznamu, hodnoty zadáváme z klávesnice.

  TDATA *novy, *p;  
  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 do 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. Ideálně ukládáme jenom datové položky, ukládat ukazatele nemá smysl. Jejich platnost je omezená na umístění spojového seznamu v operační paměti. 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.


Design downloaded from Free Templates - your source for free web templates