7 - Spojové struktury, práce se soubory
Procvičovaná témata
Dynamická alokace
Rekurze
Valgrind
Spojový seznam
Zásobník vs. fronta
Práce se soubory
Úkoly na cvičení
Implementujte frontu, která bude obsahovat celá čísla, která bude uživatel zadávat z klávesnice.
Společně s cvičícím navrhněte vhodnou datovou stukturu, na které bude fronta založena.
Společně s cvičícím navrhněte prototypy funkcí, které umožní vkládání dat do fronty (PUSH), odebírání z fronty (POP), dotaz na poslední prvek.
Vytvořte funkci, která vypíše na konzoli obsah celé fronty.
Nezapomeňte implementovat i funkci, která uvolní všechna data spojená s implementovanou frontou.
Kontrolujte správnost dynamické alokace paměti pomocí Valgrindu.
Upravte vhodně kód tak, abyste naimplementovali zásobník.
S cvičícím diskutujte změny, které jste v kódu provedli.
Další úkoly na procvičení
Implementujte spojový seznam, který v sobě bude obsahovat vždy dvojici dat - dvě celá čísla - první bude datová složka a druhé bude představovat prioritu.
Upravte předchozí seznam tak, aby implementoval prioritní frontu tak, aby funkce PUSH od začátku vytvářela vnitřní stukturu seznamu seřazenou podle priority.
Práce se soubory
FILE *fopen(const char *path, const char *mode);
size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream);
size_t fwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream);
Úkoly
Načtěte ze vstupu seznam čísel a uložte je do binárního souboru. Poté soubor načtěte a vypište seznam čísel. Prohlédněte si uložený soubor programem xxd
nebo hexdump -C
.
Naplňte strukturu test
, uložte ji do binárního souboru, binární soubor načtěte do struktury a její obsah vypište.
struct test {
int ival;
char cval;
};
typedef struct test test_t;
Totéž udělejte se strukturou test2
, do které uložíte i pointer na řetězec. Zamyslete se, jak správně uložit řetězec v položce .str
, jak ho správně načíst a jak rozlišit, zda .str
obsahuje NULL nebo odkaz na prázdný řetězec.
struct test2 {
int ival;
char cval;
char *str;
};
typedef struct test2 test2_t;
Udělejte totéž s polem struktur test
a test2
.
Jak to bude, pokud použijete atribute packed
? Jak se změní velikost struktury a proč? Musíte něco změnit ve vašem kódu? Jak ukládání a načítání naprogramovat, aby byl nezávislý na tomto atributu?
__attribute__((packed))
uint32_t le_to_be(uint32_t v);
Načítejte čísla ze stdin a postupně je ukládejte do BST. Nakonec vyhledejte některá čísla a vypište, kolik kroků bylo potřeba k vyhledání.
Výsledný BST pravděpodobně není vyvážený. Jak upravíte načítání, aby byl strom vyvážený?
Pokud jste použili strukturu z přednášky, napadá vás, jak tuto úlohu vyřešit úsporněji bez pointerů .left
a .right
?