Štruktúry

Záznam z prednášky

Úvod

• (slide) Na predmete Základy algoritmizácie a programovania ste sa venovali najmä tzv. jednoduchým alebo ináč nazývaným aj primitívnym údajovým typom. Výlučne s nimi si však do konca života nevystačíme, pretože svet a problémy, ktoré budete riešiť, nebudú vždy také jednoduché. A dnes si ukážeme prečo.

• Predstavte si napríklad, že vo svojom programe potrebujete opísať vlastnosti nejakého auta alebo osoby. Čo všetko by vás zaujímalo? (nechať študentov menovať jednotlivé vlastnosti a zapisovať si ich do súboru)

• Ak by sme tieto vlastnosti mali reprezentovať v jazyku C, aké údajové typy by mali? (k vymenovaným vlastnostiam začať písať údajové typy)

• Máme k dispozícii niekoľko vlastností, pomocou ktorých vieme opísať nejakú osobu. Čo ak by sme však potrebovali opísať viac ako jednu osobu? Čo ak by sme potrebovali vytvoriť informačný systém, ktorý bude pracovať s tisíckami takýchto osôb? Čo ak budeme potrebovať funkciu, ktorá spracuje informácie o konkrétnej osobe?

• (slide) Jazyk C umožňuje pracovať s tzv. štruktúrovanými typmi údajov, resp. štruktúrami. Význam je podobný ako tomu bolo v jazyku Pascal, kde sa na tento účel používal údajový typ record.

• Podobný prístup je možné vidieť napr. aj v relačných databázach, kde entita (tabuľka) reprezentuje štruktúrovaný údajový typ a konkrétny riadok v tabuľke hovorí o konkrétnom objekte, resp. zázname.

Vytvorenie štruktúrovaného údajového typu

• (slide) Na vytvorenie štruktúrovaného údajového typu (štruktúry) sa používa kľúčové slovo struct nasledovne:

  struct person {
      char name[10];
      char surname[20];
      char sex; // M, F
      int age;
  };

• Tým sme vytvorili štruktúru s názvom person. Ak chceme vytvoriť premennú, ktorá bude daného údajového typu, zadeklarujeme ju v tvare:

  struct person john;

Kľúčové slovo typedef

• (slide) V jazyku C sa môžete stretnúť s kľúčovým slovom typedef, pomocou ktorého je možné zadefinovať nové meno pre niektorý už existujúci údajový typ.

• (slide) Jeho použitie si môžeme ilustrovať na nasledujúcom príklade:

  typedef unsigned char BYTE;

• Následne v kóde viem zadeklarovať premennú byte tak, že bude typu BYTE:

  BYTE byte;

• Tento zápis je ekvivalentný so zápisom:

  unsigned char byte;

• Ak by sme teda chceli vytvoriť nový údajový typ na základe práve vytvorenej štruktúry Person, mohol by vyzerať nasledovne:

  typedef struct {
      char name[10];
      char surname[20];
      char sex; // M, F
      int age;
  } PERSON;

• Následne je možné zadeklarovať novú premennú, ktorá bude typu PERSON:

  PERSON john;

Typ size_t

• (slide) S niektorými údajovými typmi, ktoré boli vytvorené pomocou kľúčového slova typedef, sa je možné stretnúť bežne v knižniciach jazyka. Ak sa pozriete napr. na typ návratovej hodnoty funkcie strlen() z knižnice string.h (napr. pomocou man strlen), tak zistíte, že sa jedná o typ size_t a nie o typ int, ako sme si doteraz mysleli a aj používali. Čo za typ je teda size_t?

• Tento údajový typ je zadefinovaný v hlavičkovom súbore stddef.h (man stddef.h). A je pri ňom uvedené, že:

  Unsigned integer type of the result of the sizeof operator.

• Takže sa jedná o kladné celé číslo a jeho použitie je vhodné všade tam, kde sa pracuje s dĺžkou alebo indexom, napr. pri iterovaní pomocou cyklu for.

• Použitie tohto údajového typu si ilustrujeme v rámci dnešných príkladov. A hneď ho viem použiť aj pri reprezentácii roku osoby v štruktúre struct person, ktorý je rozhodne celým kladným číslom:

  struct person {
      char name[10];
      char surname[20];
      char sex; // M, F
      size_t age;
  };

Veľkosť štruktúrovaného údajového typu

• (slide) Ako je to s množstvom pamäti, ktoré štruktúrované údajové typy zaberajú v pamäti? Koľko miesta v pamati teda bude zaberať premenná, ktorá bude typu struct person?

• (slide) Množstvo bytov, ktoré zaberá štruktúra v pamäti, je možné zistiť ako súčet veľkostí jednotlivých jej členov. Ak teda chcem zistiť, koľko bytov v pamäti zaberá štruktúra person, vložíme do programu tieto riadky:

  printf("%ld + %ld + %ld + %zu = %ld\n",
      sizeof john.name,
      sizeof john.surname,
      sizeof john.sex,
      sizeof john.age,
      sizeof john.name + sizeof john.surname + sizeof john.sex
          + sizeof john.age
  );
  // 10 + 20 + 1 + 8 = 39

• Operátor sizeof() samozrejme môžeme použiť na celú štruktúru, čím získame veľkosť štruktúry v pamäti použitím jedného operátora sizeof():

  printf("Size is: %zu\n", sizeof(struct person));
  // Size is: 40

• Po spustení programu sa však na obrazovku vypíše hodnota 40 miesto očakávanej hodnoty 39. Ako je to možné?

• Obsah štruktúry je totiž v pamäti zarovnaný na veľkosť deliteľnú číslom 4. Ak chceme toto správanie potlačiť, pridáme k štruktúre atribút packed:

  struct person {
      char name[10];
      char surname[20];
      char sex; // M, F
      size_t age;
  } __attribute__((packed));

• Tentokrát sa po spustení a použití operátora sizeof() nad celou štruktúrou struct person naozaj zobrazí hodnota 39.

Inicializácia štruktúry

• (slide) Inicializovať premennú typu štruktúra je možné podobne ako jednorozmerné pole - vymenovaním hodnôt pre konkrétnych členov štruktúry v rovnakom poradí, ako je štruktúra definovaná:

  struct person sherlock = { "sherlock", "holmes", 'M', 33 };

• Môžeme však použiť aj tzv. Designated initialisers, kde je možné podobne ako v poli selektívne inicializovať konkrétne prvky. Na poradí v tomto prípade nezáleží:

  struct person john = {
      .sex = 'M',
      .age = 42,
      .surname = "smith",
      .name = "john"
  };

Prístup k položkám štruktúry

• Pre prístup ku konkrétnym položkám štruktúry budeme používať operátor “.”. Ak teda chceme nastaviť premennej john typu struct person pohlavie, zabezpečíme to zápisom:

  john.sex = 'M';

• Podobne môžeme pristupovať aj ku ostatným položkám štruktúry. Vytvoríme teda novú premennú typu struct person a miesto jej priamej inicializácie naplníme jej položky hodnotami postupne. Nakoniec ich vypíšeme na obrazovku:

  struct person bruce;
  
  bruce.sex = 'M';
  strcpy(bruce.name,"bruce");
  sprintf(bruce.surname, "wayne");
  
  printf("%s %s is %c\n",
      bruce.name, bruce.surname, bruce.sex);

Štruktúra ako parameter funkcie

• Keďže však chceme vypisovať obsah aj iných premenných, ktoré sú typu struct person, pripravíme si za týmto účelom funkciu s menom print_person(). Táto funkcia dostane jeden parameter typu tejto štruktúry a vypíše na obrazovku jej hodnoty:

  void print_person(struct person person){
      printf("%s %s (%c) is %zu years old.\n",
          person.name, person.surname, person.sex, person.age
      );
  }

• V kóde ju potom môžeme použiť nasledovne:

  print_person(john);

• Ako je možné vidieť zo zápisu, štruktúrované údajové typy sa odovzdávajú funkcii adresou podobne, ako tomu bolo v prípade polí.

Zoznam osôb

• Vráťme sa však k pôvodnému zámeru - chceme uchovávať informácie o viacerých ľuďoch - nie len o jednom človeku. Ak by sme teda chceli naraz uchovať informácie o viacerých ľuďoch, čo by sme za tým účelom vedeli s výhodou použiť?

• Pre vytvorenie zoznamu osôb použijeme jednorozmerné pole typu struct person:

  #include <stdio.h>
  #include <string.h>
  
  // structure representing a person
  struct person {
      char name[10];
      char surname[20];
      char sex;
      size_t age;
  };
  
  void print_person(struct person person){
      printf("%s %s (%c) is %zu years old.\n",
          person.name, person.surname, person.sex, person.age
      );
  }
  
  int main(){
      // read the nr of persons
      printf("Enter the number of persons: ");
      size_t size;
      scanf("%zu", &size);
  
      // declare list of persons
      struct person list[size];
  
      // populate list
      for(size_t i = 0; i < size; i++){
          printf("Enter %zu person: ", i);
          scanf("%s %s %c %zu",
              list[i].name, list[i].surname, &list[i].sex,
              &list[i].age
          );
      }
  
      // traverse the list
      for(size_t i = 0; i < size; i++){
          printf("%zu: ", i);
          print_person(list[i]);
      }
  }

• Aby sme nemuseli stále dookola pridávať osoby znova a znova, môžeme si zoznam pripraviť bokom do súboru (list.txt) a následne presmerovať vstup do nášho programu:

  $ ./person < list.txt

Perzistencia dát

• (slide) Teraz sa pozrime na to, ako zabezpečiť trvácnosť našich údajov. Našim cieľom bude zabezpečiť, aby sa údaje nestratili a nepoškodili ani po vypnutí a opätovnom zapnutí aplikácie. Budeme ich teda ukladať a následne načítavať zo súboru.

• Základnú prácu so súbormi už ovládate zo zimného semestra. Viete načítavať a ukladať textové súbory. My sa teraz naučíme pracovať s binárnymi.

• Ak by sme mali tieto údaje ukladať ako textové súbory, pravdepodobne by sme došli ku niektorej schéme, ako napr.

  • (slide) každý údaj by sme uložili na samostatný riadok, alebo
  • (slide) každý jeden záznam by sme uložili na jeden riadok, pričom by sme jeho jednotlivé položky oddeľovali napr. bodkočiarkou. Tento spôsob reprezentácie sa volá CSV súbor (Comma Separated Values súbor).

• (slide) My však nebudeme ukladať údaje textovo, ale binárne

• (slide) Na čítanie a zápis budeme používať dve funkcie: fread() a fwrite().

• Obe funkcie vrátia počet prečítaných alebo zapísaných údajov. Pozor - nie je to počet prečítaných/zapísaných bytov, ale počet prvkov.

• To, či bol počas čítania dosiahnutý koniec súboru, je možné zistiť z tohto počtu (je rovný 0) alebo pomocou funkcie feof().

• Poďme sa teda pozrieť na to, ako uložiť najprv jednu osobu a potom aj všetky osoby na disk.

Uloženie binárnych údajov na disk

Uloženie jedného prvku

• Najprv sa pokúsme uložiť na disk len jednu osobu, napr. prvú v zozname:

  FILE* fp = fopen("person.bin", "wb");
  fwrite(&list[0], sizeof list[0], 1, fp);
  // fwrite(&list[0], sizeof(struct person), 1, fp);
  fclose(fp);

• Keď sa pozrieme na disk, uvidíme tam súbor s názvom person.bin. Keď sa do neho pozrieme, síce budeme viacmenej schopní dešifrovať uložené údaje (tie textové), ale okrem nich tam bude kopec ďalších nezobraziteľných znakov.

  Poznámka

  Pre prezeranie binárnych súborov je možné s výhodou použiť hexa editory. Jeden z nich je priamo integrovaný napr. aj v správcovi súborov Midnight Commander, ktorý viete spustiť priamo z príkazového riadku príkazom mcview. Hexa režim následne zapnete klávesom F4.

• Pozrime sa však aj na výslednú veľkosť uloženého súboru. Prečo je tá veľkosť taká aká je? Na disku uložené údaje zaberajú presne toľko miesta, koľko zaberá štruktúra struct person v pamäti.

Uloženie celého zoznamu

• Teraz sa však pokúsme uložiť celý zoznam. Uložíme ho pomocou nasledujúceho fragmentu kódu:

  FILE* fp = fopen("list.bin", "wb");
  for(size_t i = 0; i < size; i++){
      fwrite(&list[i], sizeof list[i], 1, fp);
  }
  fclose(fp);

• V tomto prípade sme ukladali obsah zoznamu položku po položke. V princípe by bolo možné uložiť aj obsah celého poľa naraz týmto volaním:

  fwrite(list, sizeof list[0], size, fp);

• To však nemusí byť vždy praktické, nakoľko ukladanie prebieha po blokoch. A my sme povedali, že uloženie prebehne jedenkrát v bloku veľkom sizeof(struct person) * size.

• Pozrime sa opäť na veľkosť súboru - je možné ju aspoň odhadnúť pred samotným uložením? (veľkosť 1 štruktúry * počet položiek)

Funkcia pre uloženie celého zoznamu

• Fragment kódu na uloženie zoznamu do súboru môžeme osamostatniť a vytvoriť z neho funkciu. Nazveme ju save_list() a môže vyzerať nasledovne:

  void save_list(struct person list[], const size_t size, const char* path){
      // open file for writing
      FILE* fp = fopen(path, "wb");
  
      // write size first
      fwrite(&size, sizeof size, 1, fp);
  
      // write list
      for(size_t i = 0; i < size; i++){
          fwrite(&list[i], sizeof list[i], 1, fp);
      }
  
      // close file
      fclose(fp);
  }

Serializácia

• (slide) Procesu ukladania dát na disk sa zvykne hovoriť aj serializácia. Serializáciu môžeme voľne definovať ako

  proces prekladu údajov (objektov) do formátu, v ktorom môžeme tento údaj uložiť (napr. do pamäte alebo na disk alebo ich môžeme preniesť po sieti).

Načítanie binárnych údajov z disku

• Teraz sa pozrime na to, ako tieto uložené údaje prečítať z disku a uložiť ich do premennej typu struct person ako aj do poľa tohto typu.

Načítanie jedného prvku

• Začneme nahratím jednej osoby z disku - zo súboru person.bin a následne necháme tieto údaje vypísať na obrazovku:

  struct person person;
  
  FILE* fp = fopen("person.bin", "rb");
  fread(&person, sizeof person, 1, fp);
  fclose(fp);
  
  print_person(person);

• Ak by sme ako súbor, z ktorého budeme osobu načítavať, použili list.bin, výsledok sa nezmení - aj zo súboru, kde sa nachádza viac osôb dôjde k prečítaniu práve jednej osoby z jeho začiatku.

Načítanie celého zoznamu

• Teraz sa však pokúsme načítať celý uložený zoznam osôb. Postup bude vyzerať dosť podobne, ako tomu bolo v prípade jeho ukladania - bude prebiehať kus po kuse alebo osoba po osobe:

  // load
  struct person list[10];
  FILE* fp = fopen("list.bin", "rb");
  for(size_t i = 0; i < 10; i++){
      fread(&list[i], sizeof list[0], 1, fp);
  }
  fclose(fp);
  
  // traverse the list
  for(size_t i = 0; i < 10; i++){
      printf("%zu: ", i);
      print_person(list[i]);
  }

• To je síce pekné, ale celé to má jeden vážny nedostatok - čo ak potrebujeme načítať iný počet dát, ako je 10? Ak chceme tento problém vyriešiť, musíme tento údaj o počte položiek uložiť do výsledného súboru tiež. A to ešte predtým, ako začneme ukladať samotné údaje.

• Najprv teda upravíme kód, ktorý ukladá zoznam osôb. V rámci úpravy ešte pred samotnými osobami uložíme informáciu o tom, koľko osôb je v súbore uložených:

  FILE* fp = fopen("list.bin", "wb");
  fwrite(&size, sizeof size, 1, fp);
  for(size_t i = 0; i < size; i++){
      fwrite(&list[i], sizeof list[i], 1, fp);
  }
  fclose(fp);

• Následne upravíme aj kód deserializácie, v ktorom najprv načítame počet položiek a následne načítame potrebný počet položiek:

  // open file for reading
  FILE* fp = fopen("list.bin", "rb");
  
  // read the size
  int size;
  fread(&size, sizeof size, 1, fp);
  
  // create the array of size elements
  struct person list[size];
  
  // read the elements
  for(size_t i = 0; i < size; i++){
      fread(&list[i], sizeof list[i], 1, fp);
  }
  fclose(fp);
  
  // traverse the list
  for(size_t i = 0; i < size; i++){
      printf("%zu: ", i);
      print_person(list[i]);
  }

Funkcia pre načítanie celého zoznamu

• Takúto funkciu aktuálne nevieme spraviť efektívne, ak chceme vytvoriť zoznam len s takým množstvom prvkov, ktorý je uložený. Musíme dynamicky alokovať.

Deserializácia

• (slide) Procesu extrakcie údajov z disku sa hovorí aj deserializácia.

Záver

• Dnes sme sa teda pozreli na štruktúry a štruktúrované údajové typy v jazyku C. Ukázali sme si ich základné použitie, vytvorili sme zoznam, ktorý obsahoval položky typu štruktúra a ukázali sme si aj proces serializácie a deserializácie takýchto údajov.

• Nabudúce budeme v téme pokračovať a pozrieme sa, ako triediť a vyhľadávať v zoznamoch, ktoré obsahujú štruktúrované údaje.