Časová náročnost: 25 minut

Programovou podporu pro přidělování paměti z haldy a její navracení zpět, definuje ISO norma jazyka C pomocí několika funkcí. Jejich deklarace jsou umístěny v stdlib.h.

void *malloc(size_t size); Funkce malloc() vrací ukazatel na první byte v oblasti paměti o velikost size, která byla alokována z haldy. Pokud pro uspokojení požadavku není v haldě dostatek paměti, vrací malloc() nulový ukazatel. Před použití vráceného ukazatele je důležité prověřit, zda není nulový. Použití nulového ukazatele obvykle způsobí havárii systému. void *calloc(size_t num, size_t size); Funkce calloc() vrací ukazatel na alokovanou paměť. Velikost alokované paměti se rovná num * size. Funkce calloc() může tedy například alokovat dostatek paměti pro pole, které má num prvků o velikost size. Funkce calloc() vrací ukazatel na první byte alokované oblasti. Pokud pro uspokojení požadavku není dostatek paměti, vrací se nulový ukazatel.Před použití vráceného ukazatele je důležité prověřit, zda není nulový. void free(void *ptr); Funkce free() dealokuje (uvolňuje) paměť, na kterou ukazuje ptr. Tím je paměť k dispozici pro příští alokaci. Je nutné, aby byla funkce free() volána jen s ukazatelem, který byl předtím nastaven pomocí některé z funkcí systému dynamické alokace, například calloc() nebo malloc(). Použití nevhodného ukazatele při volání pravděpodobně naruší mechanismus správy paměti a způsobí havárii systému. void *realloc(void *ptr, size_t size); Funkce realloc() mění velikost alokované paměti, na kterou ukazuje ptr, na velikost určenou argumentem size. Hodnota size může být větší, nebo menší než původní velikost. Vrací se ukazatel na blok paměti, jelikož funkce realloc() musí někdy původní blok paměti přemístit, aby jej mohla zvětšit. Pokud se to stane, je obsah starého bloku překopírován do nového, takže nedojde k žádné ztrátě informací. Pokud v haldě není dostatek paměti pro alokaci size bytů, vrací se nulový ukazatel. To znamená, že je důležité si ověřit úspěšnost volání realloc().

Tato funkce alokuje paměť potřebnou pro uložení struktury typu adr.

	Příklad:
	#include <stdio.h> #include <stdlib.h> struct adr { char jmeno[40]; char ulice[40]; char mesto[40]; char stat[40]; }; . . . struct adr *get_struct(void) { struct adr *p; if((p = malloc(sizeof(struct adr))) == NULL) { printf("Chyba pri alokaci pameti"); exit(1); } return p; }

Následující funkce vrací ukazatel na dynamicky alokované pole 100 čísel typu float.

	Příklad:
	#include <stdio.h> #include <stdlib.h> float *get_mem(void) { float *p; p = calloc(100, sizeof(float)); if(!p) { printf("Chyba pri alokaci pameti"); exit(1); } return p; }

Následující program nejprve alokuje místo pro 10 uživatelem zadaných řetězců a pak je uvolní.

Příklad 12.1.

/****************************** * malloc_1.c * 19.03.2002 ******************************/ #include <stdio.h> #include <stdlib.h> int main(void) { char *str[10]; int i; printf("Zadej 10 retezcu:\n"); for(i=0; i<10; i++) { if((str[i] = malloc(128)) == NULL) { printf("Chyba pri alokaci"); exit(1); } gets(str[i]); } /* uvolneni pameti */ for(i=0; i<10; i++) free(str[i]); printf("Alokace i uvolneni pameti probehlo uspesne"); return 0; }

Poslední příklad nejprve alokuje 17 znaků, zkopíruje do tohoto místa řetězec "toto je 16 znaku" a pak použije realloc() pro zvětšení velikosti na 18, aby se dala na konec řetězce vložit tečka.

Příklad 12.2.

/****************************** * malloc_2.c * 19.03.2002 ******************************/ #include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { char *p; p = malloc(17); if(!p) { printf("Chyba pri alokaci pameti"); exit(1); } strcpy(p, "toto je 16 znaku"); p = realloc(p, 18); if(!p) { printf("Chyba pri realokaci pameti"); exit(1); } strcat(p, "."); printf(p); free(p); return 0; }

Časová náročnost: 25 minut

Seznam je dynamická datová struktura, která mezi svými členy obsahuje kromě datové části i vazebný člen, který ukazuje na následující prvek seznamu, nebo NULL, je-li posledním prvkem. Minimum statických dat, které pro správu takového seznamu potřebujeme, je ukazatel na jeho první prvek. Dále přirozeně potřebujeme podpůrné funkce. Popsaný seznam se rovněž nazývá jednosměrný seznam. Postupně totiž můžeme projít od začátku seznamu až k jeho konci, nikoliv však naopak. Existuje ještě jedna varianta seznamu, mající vazebné členy dva. Jeden ukazuje opět na následníka, druhý na předchůdce.

Správné pochopení práce se seznamem si ukážeme na příkladu. Mějme za úkol spočítat četnost výskytu všech slov ve vstupním textu. Na závěr vytiskneme tabulku, v níž bude uvedena četnost výskytu a řetězec, představující slovo. Jména funkcí i proměnných v programu jsou volena s ohledem na jejich maximální popisnost. Vstupem může být soubor, je-li zadán jako první argument příkazového řádku. Jinak je vstupem standardní vstup.

Příklad 12.3.

/****************************** * list.c * 15.04.2002 ******************************/ #include <stdio.h> #include <string.h> #include <stdlib.h> #include <ctype.h> #define DELKA_RADKU 80 #define PAGE 24 typedef struct struct_info { int pocet; char *slovo; struct struct_info *dalsi; } info; void pridej_slovo(info **prvni, char *s) { info *prvek; prvek = *prvni; /* dokud neni na konci, porovnava nove s ulozenym */ while (prvek != NULL) { /* shoda nalezena, pocet se zvetsil */ if (strcmp(s, prvek->slovo) == 0) { (prvek->pocet)++; return; } prvek = prvek->dalsi; /* prejdi na naslednika */ } /* shoda nenalezena je nutno vytvorit novy prvek */ prvek = malloc(sizeof(info)); /* naalokovat i misto pro kopii slova */ prvek->slovo = malloc(strlen(s) + 1); strcpy(prvek->slovo, s); /* nastavi pocet vyskytu na jedna,prida prvek na zacatek seznamu */ prvek->pocet = 1; prvek->dalsi = *prvni; *prvni = prvek; } void tiskni(info *prvni) { int vytisknuto = 0; while (prvni != NULL) /* dokud nejsme na konci seznamu */ { printf("%4d..%s\n", prvni->pocet, prvni->slovo); prvni = prvni->dalsi; vytisknuto++; /* tiskne stukturu prvek a pocita, kolikrat kontroluje totoz vystup na obrazovku kvuli pozastaveni vypisu */ if ((vytisknuto % PAGE) == 0) { printf("pro pokracovani stiskni enter"); getchar(); printf("\n"); } } } int main(int argc, char **argv) { info *prvni = NULL; char radek[DELKA_RADKU + 1], *slovo; /* retezec obsahuje mezeru TAB NL a CR */ char oddelovace[] = " \t\\n\\r"; FILE *f; if (argc != 1) f = fopen(argv[1], "rt"); /* otevreni textoveho streamu */ else f = stdin; /* pouzije standardni vstup */ if (f == NULL) return(1); /* dokud neni konec vstupu cte radek za radkem a vybira z nej slova */ while (fgets(radek, DELKA_RADKU, f) != NULL) { /* nastaveni funkce,navrat prvniho slova z radku */ slovo = strtok(radek, oddelovace); while (slovo != NULL) { pridej_slovo(&prvni, slovo); /* slovo do seznamu */ slovo = strtok(NULL, oddelovace); /* ziskani dalsiho slova z radku */ } } tiskni(prvni); return 0; }

Za slova považuje program řetězce oddělené specifikovanými znaky. Tuto skutečnost můžeme ovšem měnit úpravou řetězce oddelovace, který obsahuje mezeru a escape sekvence oddělovačů. V cyklu while je funkcí gets() načítán řádek za řádkem, dokud gets() nevrátí NULL a program postupuje dál. Načtený řádek je na slova rozdělen pomocí funkce strtok. Pro ni je prohledávanou oblastí řetězec radek a oddělovači slov jsou znaky z řetězce oddelovace. Poprvé je nutno načíst další slovo hned po načtení řádku a nastavit tak prohledávanou oblast. Další čtení až do konce řádku probíhají tak dlouho, dokud není slovo ukazatel na NULL. Vnitřní cyklus zpracování řádku je ukončen a probíhá načítání dalšího řádku.

Pro každé načtené slovo je zavolána funkce pridej_slovo s argumenty prvni a slovo. Proměnná prvni představuje ukazatel na seznam, přesněji na strukturu námi vytvořeného typu struct_info.

Při prvním volání funkce pridej_slovo je seznam prázdný, funkce obdrží hodnotu NULL, proto je prohledávání seznamu přeskočeno a pomocí funkce malloc je alokována paměť pro položku velikosti sizeof(struct_info). Jakmile je tato dynamická položka vytvořena, je v ní naalokován řetězec délky odpovídající slovu s a řetězcové zarážce, konkrétně malloc(strlen(s)+1). Do vytvořeného prostoru je slovo s nakopírováno pomocí strcpy. Dosud jsme se stále odkazovali na slovo umístěné ve zpracovávaném řádku. Bez vytvoření kopie bychom jej načtením dalšího řádku ztratili. Kromě kopie řetězce musíme nastavit v nové položce seznamu počet výskytů na jedna.

Pak přichází klíčové místo. Připojení položky do seznamu. V našem případě připojíme stávající seznam přes vazební člen prvek->dalsi k nově vytvořenému prvku a ten se následně stává novým prvním prvkem seznamu, *prvni = prvek.

Když je v seznamu nejméně jeden prvek, musí být při přidávání slova nejprve prohlédnut stávající seznam. Provádíme to prvek za prvkem, kdy posouváme pomocný ukazatel prvek na další položku seznamu pomocí prvek = prvek->dalsi, dokud se nedostaneme na konec seznamu, indikovaný hodnotou NULL ve vazebním členu dalsi. Pokud při průchodu narazíme na výskyt stejného řetězce, jako je přidávané slovo, tedy je splněna podmínka strcmp(s, prvek->slovo), zvýšíme počet výskytů slova v položce a opustíme funkci pridej_slovo.

Zkrácený výpis:

   1..POSLEDNI
   1..PRIDAT
   1..JESTE
   1..UMIM!
   1..SOUBOR
pro pokracovani stiskni enter
   1..JE
   1..TOTO
   1..WUER
   1..OIEWR
   2..83945
   2..EWIRIWR

Časová náročnost: 5 minut

Velmi pohodlnou dynamickou datovou strukturou je dynamické pole ukazatelů. Princip je jednoduchý. Požádáme o paměť pro dostatečně veliké pole ukazatelů. Dále již pracujeme stejně, jako by pole bylo statické (až na ten ukazatel na pole navíc). K jednotlivým prvkům můžeme přistupovat pomocí indexu. Nesmíme zapomenout, že prvky jsou ukazatele, a že tedy musíme paměť, na kterou ukazují, také alokovat. Díky funkci realloc() máme možnost snadno měnit počet prvků našeho pole ukazatelů. Navíc s tím, že naše dynamická data svou adresu nemění a funkce realloc() přenese správné (stále platné) adresy do nového (většího) bloku ukazatelů. My k nim přistupujeme pomocí stejné proměnné, indexy všech prvků zůstávají stejné, jen jich přibylo.