IB111 Programování a algoritmizace Datové struktury I Zřetězené seznamy Opakování ­ struktura (záznam) struct student { int vek; float studijni_prumer; char jmeno[30]; } st, *uk_st; st.vek=22; st.studijni_prumer=1.12; strcpy (st.jmeno, "Jan Kos"); uk_st = &st; uk_st ->vek=23; Opakování - pole struct student prvaci[100]; prvaci[0].vek=25; prvaci[0].studijni_prumer=2.8; 0 1 2 3 4 5 ... ... ... 99 Věk: int Průměr: float Jméno: Pole Výhody Jednoduchý přístup přes indexy Nevýhody Náročné přesouvání prvků Fixní počet prvků Přidávání a mazaní prvků Např. v setříděné podobě Zřetězený seznam Datová struktura spolu s ukazatelem na další prvek Ukazatel ukazuje na příští nebo předchozí prvek struct item { int data; struct item *next; }; data next Jednosměrně zřetězený seznam Obousměrně zřetězený seznam Kruhový seznam Jednosměrný nebo obousměrný Typy zřetězených seznamů data next data next data next data prev next data prev next data prev next data next data next data next Obousměrně zřetězený seznam Příklad Praktický příklad v C struct student { int vek; float studijni_prumer; char jmeno[30]; struct student *next; } *head; data next data next data next head data next 0x101 0x204 0x2a0 0x84b Data nejsou uložena v paměti kontinuálně, ale na různých adresách podle toho jak jsme prvky přidávali/alokovali. Konec seznamu Jak zakončit zřetězený seznam Ukazatel na další prvek nastavit na NULL Přidat speciální prvek, který nebude obsahovat žádnou hodnotu Kruhový seznam data next 0x84b data next 0x2a0 0x000 (NULL) Př. Prázdný seznam struct student *head; head = NULL; head 0x000 (NULL) Př: Seznam s jedním prvkem struct student *n = (struct student*) malloc(sizeof(struct student)); if (n==NULL) exit(1); n->vek = 20; n->studijni_prumer=1.0; strcpy(n->jmeno,"Jan Kos"); n->next=NULL; struct student *head = n; Př: přidáme druhý prvek n = (struct student*) malloc(sizeof(struct student)); if (n==NULL) exit(1); n->vek = 21; n->studijni_prumer=1.1; strcpy(n->jmeno,"Jarek Klaus"); n->next=NULL; head->next = n; Procházení seznamu Úkol: projít (např. vypsat) všechny prvky seznamu Začneme u prvku, na který ukazuje head Opakujeme dokud další prvek není NULL Zpracuj prvek (např. vypiš hodnotu data) běž na další prvek data next data next data next Hledání v nesetříděném seznamu Podobné jako procházení, ale porovnávám hodnotu s klíčem data next data next data next Přidávání prvku Alokujeme paměť pro další prvek, naplníme jeho datovou část a zařadíme do seznamu Na začátek Na konec Časová náročnost data next data next data nextdata next Odebrání prvku Musíme odpojit prvek ze seznamu, dále můžeme uvolnit paměť použitou pro prvek data next data next data next data next data next Oboustranně zřetězené seznamy Máme ukazatel na začátek a konec seznamu Lehce můžeme přistoupit k prvnímu i poslednímu prvku Ale musíme vždy aktualizovat oba směry Přidávání prvků Mazání prvků data prev next data prev next data prev next Využití spojených seznamů Seznam prvků Přidání, mazání, vyhledávání, výpis prvků Zásobník (LIFO) Přidání (na vrchol zásobníku), odebrání (z vrcholu zásobníku), je zásobník prázdný? Fronta (FIFO) Přidání prvku, odebrání prvku, je fronta prázdná Zásobník (LIFO) Stačí jednosměrně zřetězený seznam Přidáváme na začátek seznamu Odebíráme ze začátku seznamu Pokud je seznam neprázdný Obě operace v konstantním čase data next data next data nextdata next Fronta (FIFO) Můžeme použít jednosměrně i obousměrně zřetězený seznam Přidáváme na začátek a odebíráme z konce Nebo obráceně U oboustranně zřetězeného seznamu umíme udělat obě operace v konst. čase data prev next data prev next data prev next Fronta (FIFO) U jednostranně zřetězeného seznamu umíme buď konstantní přidání nebo konstantní odebrání Druhá operace vyžaduje lineární procházení všech záznamů data next data next data nextdata next Příští přednáška Následuje cvičení v B311 v 14:00 Příští přednáška 13.10.2009 v B410 od 12:00