AMIGA REVIEW online
  Uvodná stránka     Software     Hry     Obaly     Download     Amiga na PC     Amiga Forever  

Kurz jazyka C - 7. díl

Pavel Číž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


© ATLANTIDA Publishing Všechna práva vyhrazena.
Žádna část nesmí být reprodukována nebo jinak šířena bez písemného svolení vydavatele.



Amiga na Vašem PC rychle, snadno a zdarma!


none

AMIGA REVIEW

57 ( 11-12 / 2000 )
56 ( 9-10 / 2000 )
55 ( 7-8 / 2000 )
54 ( 5-6 / 2000 )
53 ( 3-4 / 2000 )
52 ( 1-2 / 2000 )
 
51 ( 12 / 1999 )
50 ( 11 / 1999 )
49 ( 10 / 1999 )
48 ( 9 / 1999 )
46-47 ( 7-8 / 1999 )
45 ( 6 / 1999 )
44 ( 5 / 1999 )
43 ( 4 / 1999 )
42 ( 3 / 1999 )
41 ( 2 / 1999 )
40 ( 1 / 1999 )
 
39 ( 12 / 1998 )
38 ( 11 / 1998 )
37 ( 10 / 1998 )
36 ( 9 / 1998 )
35 ( x / 1998 )
34 ( x / 1998 )
33 ( 1-2 / 1998 )
 
32 ( 11-12 / 1997 )
31 ( 9-10 / 1997 )
30 ( 7-8 / 1997 )
29 ( 6 / 1997 )
28 ( 5 / 1997 )
27 ( 4 / 1997 )
26 ( 3 / 1997 )
25 ( 2 / 1997 )
24 ( 1 / 1997 )
 
23 ( 12 / 1996 )
22 ( 11 / 1996 )
21 ( 10 / 1996 )
20 ( 9 / 1996 )
18-19 ( 7-8 / 1996 )
17 ( 6 / 1996 )
16 ( 5 / 1996 )
15 ( 4 / 1996 )
14 ( 3 / 1996 )
13 ( 2 / 1996 )
12 ( 1 / 1996 )
 
11 ( 12 / 1995 )
10 ( 11 / 1995 )
9 ( 10 / 1995 )
8 ( 9 / 1995 )
7 ( 7 / 1995 )
6 ( 5 / 1995 )

ATLANTIDA NEWS

5 ( 3 / 1995 )
4 ( 1 / 1995 )
 
3 ( 11 / 1994 )
2 ( 9 / 1994 )
1 ( 7 / 1994 )
0 ( 5 / 1994 )