Kurz jazyka C - 7. dílPavel Čížek
Opět je zde pokračování našeho seriálu o programování v jazyce C. Dnes se
připravíme na velké změny, které naši Kalkulačku čekají. V této části se podíváme na některé programovací techniky a postupy, které
nám umožní pokračovat v efektivním vývoji našeho programu. Náš prográmek je
zatím sice velmi malý a téměř nic neumí, ale zajisté jste si všimli jedné věci.
Ačkoli jsme se omezili pouze na sčítání a odčítání, nejednalo se při stávajícím
postupu (= mechanické procházení zadaného řetězce s výrazem) o triviální úlohu,
bylo třeba vynaložit jisté úsilí, aby vše pracovalo dle běžných zvyklostí.
Dovedete si jistě představit, jakym způsobem by se situace zkomplikovala, kdyby
bylo nutné uvažovat i násobení a dělení (včetně jejich přednosti před sčítáním),
nebo kdyby dokonce měl program umět zpracovávat závorky a další funkce, jako
například sinus, mocniny apod.
V takovémto případě by se program nejenom velice komplikoval (stal by se patrně
téměř nečitelným), ale ani rychlost vyhodnocení výrazu by nebyla příliš velká
(uvážíte-li potřebné množství operací). Pokud by docházelo
k vyhodnocení výrazu pouze jednou, tak by to tak velká závada nebyla, ovšem
například při kreslení grafu funkce, kdy je nutno určit velké množství funkčních
hodnot, by zpomalení bylo značné. Závěr: výraz je třeba před vlastním
vyhodnocením předzpracovat nejlépe do takové podoby, ve které už budou zahrnuty
priority jednotlivých operací a v níž budou čísla, názvy funkcí a další elementy
převedeny do nějaké vnitřní formy, kterou jsme schopni rychle dekódovat. Rekurze
První, s čím se dnes seznámíme, je postup (metoda) zvaná rekurze. Význam
slova rekurentní je "vracející se, opakující se", což velmi dobře vystihuje
podstatu rekurze. Princip spočívá v tom, že nějaká funkce volá (používá) ve svém
těle mimo jiné také sama sebe. Jednoduchým příkladem na ilustraci je výpočet
faktoriálu: n! = 1.2.3 ... n. Samozřejmě, že nejjednodušší a nejrychlejší
metodou je použití for cyklu, například takto (předpokládáme, že v proměnné n
je přirozené číslo): for(fakt = l ; n > 1; n--) fakt *= n; Rychlé a jednoduché. Pro výpočet faktoriálu lze využít i rekurzi (v praxi to
nedělejte - zde je to jen na ukázku): pokud máme totiž funkci Faktorial(n),
která spočte n!, pak víme, že Faktorial (n) = n * Faktorial(n-1). A zde se právě
nabízí možnost použití rekurze, neboť hodnota n! se dá spočítat pomocí téže
funkce s argumentem (n-1), tj. (n-1)!. Funkce pro výpočet faktoriálu může tedy
vypadat následovně (0! = 1): long Faktorial(int n)
{
/* pokud hodnotu známe (n = 0, 1), rovnou ji vrátíme */
if(n<= 1)
return( 1 );
/* v opačném případě využijeme rekurentního volání téže funkce pro parametr n-1
*/
else
return( n * Faktorial(n-1));
} Zde je princip rekurze jasně patrný funkce volá samu sebe. Všimněte si jedné
důležité věci: funkce Faktorial sice rekurentně volá samu sebe, ale ne VŽDY!
Kdyby vždy zavolala samu sebe, vznikl by nekonečný cyklus. Zde se opětovné
(rekurentní) volání zastaví, je-li parametr n menší nebo roven 1.
Rekurze však nemusí být takto jednoduchá a průhledná. Rekurentní postup se může
skládat v podstatě z libovolného množství funkcí, které se navzájem cyklicky
volají. Složitější rekurze může např. vypadat následovně: /* deklarace funkcí */
int a(char x, char y);
int b(int t);
/* definice funkcí */
int a(char x, char y)
{
/* začátek funkce... */
b(parametr);
/* konec funkce... */
}
int b(int t)
{
/* začátek funkce... */
if (podmínka)
a(x1, x2);
/* konec funkce... */
} Ve složitější situaci může být mezi rekurentními voláními téže funkce
proveden různý počet jiných funkcí atd. Možností je mnoho. Rekurze může často
být jedinym prostředkem k řešení nějakého problému. Pokud je to ovšem možné,
neužívejte i zbytečně a zvláště opatrně užívejte return, v níž funkce volá sama
sebe vícekrát (pak roste časová náročnost algoritmu třeba exponenciálně). Proč?
Podívejme se na jednoduchý příklad s výpočtem Faktoriálu, kde existuje i
jednoduché nerekurentní řešení. Při výpočtu faktoriálu pomocí for-cyklu
potřebujete pouze dvě proměnné - n (přirozené číslo - int) a proměnnou
obsahující výsledek. Při rekurentním postupu sice na první pohled nepotřebujeme
žádnou proměnnou, ale provádíme opakovaně (n krát) volání funkce. Při volání
funkce je nutno ovšem uložit na zásobník návratovou (zpáteční) adresu i
parametry pro volanou funkci. Proto při řešení pomocí rekurentní funkce bude
nutno uložit do paměti n přirozených čísel (int)! A to nepočítáme prostor na ony
návratové adresy apod. Obecně je většinou pravda, že když existuje k danému
problému nepříliš komplikovaný nerekurentní postup, je často rychlejší a méně
náročný na paměť než odpovídající postup rekurentní.
Proč si tedy o rekurzi povídáme? To proto, že často jiné rozumné (= dostatečně
jednoduché) řešení neexistuje - a to je náš případ. Představte si, že máme
výraz, v němž se vyskytuje sčítání a násobení. Pokud se tam najednou objeví
závorky nebo další funkce (sinus), tak na ně lze pohlížet jako na sčítance,
jejichž parametrem je opět výraz skládající se ze sčítání a násobení - a ten už
umíme rozebrat, tj. zavoláme z naší "rozebírací" funkce znovu tuto rozebírací
funkci pro tento podvýraz (např.2+3*(4-6) .. (4-6) bude ten podvýraz, na nějž
budeme rekurentně aplikovat naši funkci). Dynamická alokace paměti
Často je vhodné reprezentovat data pomocí nějaké struktury - tu si totiž
můžeme nadefinovat tak, aby obsahovala vše potřebné, a zároveň s ní můžeme
manipulovat jako s celkem. Jak víme, definice struktury je uvozena klíčovým
slovem struct, za nímž následuje jméno struktury a po té ve složených
závorkách (zakončených středníkem) seznam položek, například: struct Osoba
{
char jmeno(32);
int vek;
}; Připomínám, že k položkám struktur se přistupuje pomocí operátoru . (pokud
máte ukazatel na strukturu, tak pomocí ->). Mějme například následující
deklarace: struct Osoba soused, *clovek; Pak jméno souseda máme přístupné pomocí zápisu soused.jmeno a pokud ukazatel
clovek ukazuje na nějakou strukturu, pak věk dané osoby zjistíme pomocí zápisu clovek->vek. Pokud máte struktury použité jako typy nějakých lokálních či globálních
proměnných máte jich pevný počet, což je obvykle nevýhodné. Máme-li strukturu
Osoba (výše definovanou) a budeme-li ji chtít využít pro udržování jmen a věků
různých osob (např. zaměstnanců firmy), bude se tento počet různě měnit a nebude
znám předem (ani jeho horní odhad). V takovém případě je třeba využít dynamicky
vytvářených struktur. Jde o to, že se nemusíme spolehnout na možnost vytváření
místa pro data na zásobníku (lokální proměnné), ale můžeme požádat o přidělení
další paměti. To je u velkých struktur nutno použít vždy, neboť zásobník není
neomezený (standardní zásobník přiřazený programu má 4 kB).
Jak na to? Je to velice jednoduché. Pokud chcete požádat operační systém o
přidělení paměti pro svoje data, stačí zavolat standardní funkci jazyka C
malloc, jejíž deklarace se nachází v souboru <stdlib.h>. Tato funkce má jediný
parametr - počet bytů, které chcete získat pro svoji potřebu (alokovat).
Výsledkem je adresa v paměti (tj. ukazatel), která ukazuje na počátek získaného
bloku paměti. Tento ukazatel si stačí uložit do nějaké vlastní proměnné a můžeme
pracovat. Samozřejmě může nastat situace, kdy není dostatek volné paměti pro
naše potřeby. V tom případě vrátí tato funkce NULL. POZOR! Před použitím
alokované paměti je nutno vždy zkontrolovat, zda paměť byla skutečně alokována,
tj. že funkce malloc() nevrátila NULL (jinak pravděpodobně dojde ke spadnutí
vašeho programu, případně pádu celého počítače).
Pokud bychom tedy potřebovali dynamicky získat (alokovat) místo pro strukturu
Osoba , můžeme to provést následujícím způsobem (nezapomeňte, že velikost
jakéhokoliv objektu v bytech lze v Céčku zjistit pomocí standardního operátoru
sizeof): /* ukazatel na strukturu Osoba */
struct Osoba *clovek;
/* získáme paměť pro 1 osobu */
clovek = malloc( sizeof(struct Osoba) );
if (clovek == NULL)
Chyba(); /* = ohlášení chyby */
else clovek->vek = 20; Jak vidíte, můžeme s takto získanou pamětí (ihned po ujištění se, že nám
operační systém skutečně paměť vyhradil) pracovat jako s ostatními běžně
užívanými proměnnými - rozdíl je pouze v tom, že zde k dané struktuře
přistupujeme vždy pomocí ukazatele. Poznamenejme, že obvykle bývá zvykem v
případě nedostatku paměti toto ohlásit uživateli (nějakou Funkcí Chyba()). Je
třeba si dále uvědomit jednu věc - funkce malloc(J vám pouze hradí paměť, ale
nečistí ji, tj. pokud chcete, aby bylo vše na počátku vynulováno musíte to
udělat ručně. Zmíním se tedy o ještě jedné podobné funkci - calloc(). Ta se
liší ve dvou bodech od funkcemalloc() - jednak vám přidělenou paměť vynuluje
(vyčistí) a navíc má dva argumenty. Ten první parametr má opět význam počtu bytů
potřebných pro alokovaný objekt (zjistíte pomocí sizeof()) a druhý parametr
udává počet objektů, pro něž chcete paměť alokovat. Pokud budeme potřebovat
paměť pro 3 osoby, tak ji lze získat pomocí malloc() lide = malloc(3 * sizeof(struct Osoba));
nebo pomocí funkce calloc()
lide = calloc( sizeof(struct Osoba), 3 );
přičemž v druhém případě bude paměť navíc vynulována. Zatím jsme si pověděli jak paměť získat - to vlastně znamená zabrat si úsek
paměti pro svoje potřeby. Tím, že kus paměti zabereme, ovšem bráníme ostatním
programům v používání příslušného kusu paměti - když máme paměť alokovánu nikdo
jiný ji nemůže používat. Pokud bychom pouze alokovali paměť a nikdy ji
neuvolnili, byla za chvíli všechna operační paměť vyčerpána. Proto jakmile už
pro nás nějaký námi alokovaný blok paměti nemá význam, nepotřebujeme ho, by měla
být příslušná část uvolněna. To zajišťuje funkce free() (opět deklarována v
<stdlib.h>) - má jediný parametr - adresu paměti, kterou chcete uvolnit, tj.
právě tu adresu, kterou nám při alokaci vrátila funkce malloc() nebo
calloc(). Správně by ke každé alokaci těmito funkcemi mělo existovat v
programu volání funkce free(), viz následující příklad: /* získáme paměť pro 1 osobu */
clovek = malloc( sizeof(struct Osoba) );
if (clovek -= NULL)
{ /* ohlášení chyby a konec funkce */
Chyba();
return(FALSE);
}
/* ...použití struktury Osoba, na niž ukazuje clovek... */
clovek->vek = 20; /* ... */
/* uvolnění použité paměti */
free(clovek); Je to důležité, neboť (jak již jednou bylo řečeno) jinak zabíráte zbytečně
paměť ostatním programům a snadno může dojít k jejímu vyčerpání. Seznamy
Tak co, zdá se vám dynamická alokace paměti dobrá věc? Ano? Má to ale háček,
jak si možná někteří z vás uvědomili. Po alokaci paměti si musím zapamatovat
ukazatel na alokovanou strukturu - a kde mám brát ty ukazatele, když nevím kolik
jich bude třeba? Například seznam osob ve třídě - nikdo neví, kolik budu
potřebovat záznamů.
Řešení není nijak složité. Lze například použít tzv. seznamy. Princip je
následující - budu si pamatovat pouze ukazatel na první (popř. i poslední)
strukturu; každá struktura (datový objekt) bude obsahovat ukazatel na
následující (popř. předchozí) strukturu, přesněji její adresu. Pokud budeme
potřebovat získat data o osobě jejíž záznam je uprostřed seznamu, pak si
jednoduše vezmeme první strukturu (o té víme, kde je), v ní je ukazatel na další
(druhou) strukturu seznamu, tam je zase ukazatel na další (třetí) atd. Tak je
možno (pouze na základě znalosti adresy jedné položky seznamu) získat obsah
kterékoliv položky v seznamu.
A jak by to vypadalo případě seznamu osob? Například takto: struct Osoba
{
struct Osoba *dalsi;
char jmeno(32);
int vek;
};
struct Osoba *Prvni = NULL; V definici struktury Osoba přibyla pouze jedna položka - ukazatel na
následující Osobu. Proměnná Prvni pak může obsahovat ukazatel na první záznam
- první osobu. Je třeba ještě vyřešit některé drobnosti: je-li seznam prázdný,
pak obvykle ukazatel na první položku obsahuje NULL (ukazuje "nikam"). Podobně
je vyřešeno rozpoznání poslední struktury v seznamu. Pokud něco následuje, je v
položce dalsi ukazatel na tu následující strukturu; pokud se jedná o poslední
strukturu v seznamu, obsahuje položka dalsi opět hodnotu NULL. Takovémuto
seznamu říkáme jednosměrný. Pokud se chceme pohybovat v seznamu oběma směry, obsahuje každá struktura
nejenom ukazatel na následující, ale také na předchozí strukturu seznamu. V
tomto případě si zpravidla pamatujeme také ukazatel na poslední strukturu
seznamu. Podobně jako u jednosměrného seznamu, lze i zde rozlišit poslední
strukturu podle NULL v dalsi první strukturu seznamu lze rozlišit dle toho, v
položce ukazující na předcházející strukturu je NULL. Takovémuto seznamu se říká
obousměrný. Vše si můžete prohlédnout na obrázku.
Pokud chceme seznam (například osob) rozšiřovat, pak je třeba vždy alokovat
paměť pro novou strukturu, dosadit hodnoty a zařadit do seznamu. Pokud bychom
chtěli třeba přidat na konec seznamu osob někoho nového (pana Nováka starého 45
let), pak to můžeme udělat následujícím způsobem. Předpokládám, že máme výše
definovanou proměnnou Prvni, která ukazuje na první osobu v seznamu (seznam je
neprázdný) a dva ukazatele struct Osoba *novy, *osoba; Nejprve získáme paměť pro popis pana Nováka: novy = malloc( sizeof(struct Osoba) );
if (no == NULL)
{
Chyba();
return(FALSE);
} Pokud se to povedlo, dosadíme si údaje, které o něm máme (strcpy() je
funkce, která kopíruje řetězce): strcpy(novy->jmeno, "Karel Novák);
novy->vek = 45; Nu, a nyní zbývá zařazení na konec k tomu ovšem potřebujeme znát ukazatel na
poslední strukturu... jak ho najít jsme si již řekli - stačí vyjít od první osob
a postupovat v seznamu dál a dál, víme, že poslední prvek poznáme tak, že
ukazatel na následníka v seznamu je NULL. for( osoba = Prvni;
osoba->dalsi != NULL;)
osoba = osoba->dalsi; Vlastní zařazení na konec pak spočívá v tom, že doposud poslední struktura
bude ukazovat na námi nově vytvořenou a nový záznam o panu Novákovi bude mít
ukazatel na následníka nastaven na NULL: /* v proměnné osoba je ukazatel na poslední osobu seznamu */
osoba->dalsi = novy;
novy->dalsi = NULL; Stejným způsobem, jak jsme si nyní ukázali lze zařazovat prvky i dovnitř
seznamu (rozmyslete). Většinou však bývá pohodlnější i praktičtější pracovat se
seznamy obousměrnými. V případě zařazování do obousměrných seznamů je však třeba
správně nastavit ukazatele na následníka i předchůdce. Než uplyne měsíc do
dalšího pokračování, můžete přemýšlet nad tím, jak se struktura ze seznamu
vypustí. Vytlačiť článok
Pozn.: články boli naskenované ako text a preto obsahujú aj zopár chýb. Taktiež neručíme za zdrojové kódy (Asm, C, Arexx, AmigaGuide, Html) a odkazy na web. Dúfame, že napriek tomu vám táto databáza dobre poslúži.
Žiadna časť nesmie byť reprodukovaná alebo inak šírená bez písomného povolenia vydavatela © ATLANTIDA Publishing
none
|