opracowała: mgr in . Izabela Skorupska
1
J zyk ANSI C (w systemie LINUX)
!
"
!
"
#
$
%
&
'() #
$
$
& %
$
!
#
$
%
$
&
%
$
&
&$
&!
% &'
"
)$
$
!
*
$
$
& % $
!
+
,-
+-
.!
$
Celem wiczenia jest zapoznanie studenta ze strukturami: lista, stos, drzewo oraz ich implementacja
w j zyku ANSI C. Zrozumienie działania tych struktur pozwoli na napisanie programu kalkulatora
licz cego w odwrotnej notacji polskiej.
/!
$
'() #
Lista to uporz dkowany ci g elementów. Przykładami list s wektory lub tablice jednowymiarowe.
W wektorach mamy dost p do dowolnego elementu, poprzez podanie indeksu tego elementu.
Stos jest list z trzema operacjami:
• dodawanie elementów na wierzch stosu,
• zdejmowanie elementu z wierzchu stosu,
• sprawdzanie czy stos jest pusty.
Na stosie dodajemy i odejmujemy elementy z samego ko ca. Taka organizacja obsługi listy
okre lana jest LIFO (ang. last in first out – ostatni wszedł, pierwszy wyjdzie)
.
opracowała: mgr in . Izabela Skorupska
2
J zyk ANSI C (w systemie LINUX)
Struktura reprezentuj ca element stosu:
struct stos
{
char element;
struct stos *wskaznik;
struct stos *wskaznik;
};
Deklaracja elementów stosu:
struct stos *nowy, *stary;
Procedura realizuj ca dodawanie elementów na stos:
void na_stos(char znak)
{stary=nowy;
nowy= malloc (sizeof(struct stos));
nowy->element=znak;
nowy->wskaznik=stary;
}
Procedura realizuj ca zdejmowanie elementów ze stosu:
void ze_stosu(struct stos *wskaz_element)
{
if (wskaz_element!=NULL)
{
stary=wskaz_element->wskaznik;
//printf("Usunieto %c ", wskaz_element->element);
free(wskaz_element);
nowy=stary;
}
}
Procedura usuwaj ca wszystkie elementy ze stosu:
void oczysc_stos(void)
{
stary=nowy;
while (stary!=NULL)
ze_stosu(stary);
printf("\nStos oczyszczony.");
}
Procedura drukuj ca zawarto stosu:
void pokaz_stos(void)
{
printf("Zawartosc stosu \n");
stary=nowy;
while (stary!=NULL)
{
printf(" %c ", stary->element);
stary=stary->wskaznik;
}
}
Drzewo jest hierarchiczn struktur danych. Pierwszy element drzewa, zwany korzeniem jest
wyró niony. Inne elementy s jego potomstwem lub potomstwem jego potomstwa itd. Elementy
opracowała: mgr in . Izabela Skorupska
3
J zyk ANSI C (w systemie LINUX)
drzewa nazywa si wierzchołkami lub w złami. Li cie to wierzchołki nie maj ce potomstwa.
Drzewa cz sto przedstawia si w formie grafu, gdzie ka dy wierzchołek jest poł czony kraw dzi
ze swoim ojcem i ze swoimi dzie mi (swoim potomstwem). Dla ka dego elementu w drzewie
istnieje dokładnie jedna cie ka prowadz ca od korzenia do tego wierzchołka. Drzewa binarne to
takie drzewa, w których ka dy wierzchołek ma co najwy ej dwóch potomków.
Struktura reprezentuj ca drzewo binarne:
struct drzewo
{
char element;
struct drzewo *prawy;
struct drzewo *lewy;
};
Drzewa mog by zrównowa one i niezrównowa one. Drzewo jest zrównowa one, gdy ró nica
wysoko ci obu poddrzew ka dego w zła w drzewie wynosi 0 lub 1. Szczególnym przypadkiem
drzewa niezrównowa onego jest stos.
!
(
$
$
Obliczenia arytmetyczne mo emy zapisywa w notacji infiksowej, prefiksowej (notacja polska) lub
postfiksowej (odwrotna notacja polska). Je li dodawanie dwóch liczb a i b zapiszemy w postaci:
a + b
to mamy do czynienia z notacj infiksow , gdy nazwa funkcji została umieszczona pomi dzy
argumentami. W notacji prefiksowej działanie przybiera posta :
+ a b
natomiast odwrotna notacja polska zostala przedstawiona przez polskiego logika J. Łukasiewicza i
działanie opisujemy ci giem:
a b +
Odwrotna notacja polska jest stosowana w nowoczesnych kalkulatorach naukowych, gdy nie
trzeba w niej u ywa nawiasów i nie sprawia kłopotów przy wprowadzaniu wielu argumentów.
Konwersja bardziej skomplikowanych wyra e przedstawionych w notacji infiksowej do postaci
postfiksowej jest kłopotliwa zwłaszcza wtedy, gdy wyra enie oryginalne zawiera wiele
zagnie d onych nawiasów.
0!
'%
1
$
$
,
()
*)+
,
!
Dla kolejnych zapisów wyra enia:
opracowała: mgr in . Izabela Skorupska
4
J zyk ANSI C (w systemie LINUX)
• je eli element jest stał lub zmienn , to wkładamy jego warto na stos,
• je eli element jest znakiem operacji, to:
o
zdejmujemy dwie warto ci z wierzchu stosu,
o
wykonujemy operacj na tych warto ciach,
o
obliczon warto wkładamy na wierzch stosu,
• po przej ciu całego wyra enia jego warto znajduje si na stosie.
Przykład 1: Dany jest ci g w notacji postfiksowej: a b c + * d e / + nale y zamieni go w ci g
zapisany w notacji infiksowej:
Krok 1. Kładziemy elementy a b c na stos
Krok 2. Wykonujemy działanie
+
Krok 3. Wykonujemy działanie *
Krok 4. Kładziemy elementy d e na stos
Krok 5. Wykonujemy działanie /
Krok 6. Wykonujemy działanie +
Krok 1
Krok 2
Krok 3
Krok 4
Krok 5
Krok 6
c
c
+b
(c+b)
*a
e
e
/d
e/d
+(c+b)*a
b
a
d
(c+d)*a
a
(c+d)*a
W wyniku działania algorytmu otrzymamy wyra enie:
e/d+(c+b)*a
()
-)+
,
Dla kolejnych zapisów wyra enia, czytaj c
od ko ca wyra enia:
• pierwszy element stanowi wierzchołek drzewa,
• kolejny element stanowi jego prawego potomka,
• je eli wstawiany element jest:
o
znakiem nale y powtórzy operacj 2,
o
cyfr lub liter , nale y wróci do najbli szego wierzchołka i sprawdzi czy ma on
ju lewego potomka:
je li nie ma nale y go utworzy i powtórzy operacje: 2 i 3,
je li ma wróci do najbli szego wierzchołka nie posiadaj cego dwóch
potomków i powtórzy operacje: 2 i 3.
opracowała: mgr in . Izabela Skorupska
5
J zyk ANSI C (w systemie LINUX)
Wszystkie operacje wykonujemy do momentu wyczerpania elementów.
Przykład 2: Obliczy warto wyra enia:
4 2 3 + * 1 5 - +
(metod stosu)
Post pujemy zgodnie z opisanym algorytmem:
Krok 1
Krok 2
Krok 3
Krok 4
Krok 5
Krok 6
2
2+3=
5
5*4=
20
5
5-1=
4
4+20=
24
3
4
1
20
4
20
Przykład 3: Ci g:
a b c + * d e / +
za pomoc drzewa nale y zamieni w ci g zapisany w
notacji infiksowej:
Krok 1. Operator „+” stanowi korze drzewa, „/” jego prawego potomka. Poniewa „/” nie jest
cyfr ani liter , staje si wierzchołkiem nowej gał zi. Jego prawym li ciem b dzie „e”, które jest
liter i nie mo e mie swojego potomka. Nale y wróci do najbli szego wierzchołka („/”) i
sprawdzi , czy ma on lewego potomka. W realizowanym przykładzie: „/” go nie ma, wi c b dzie
nim „d”. Ten element nie mo e by wierzchołkiem nowej gał zi, dlatego szukamy najbli szego
wierzchołka, który nie posiada jeszcze dwóch potomków. Warunek ten spełnia korze drzewa.
Krok 2. Tworzymy lewego potomka wierzchołka „+”. Kolejny element ci gu stanowi znak
opeacji„*”, zatem mo e by on nowym wierzchołkiem.
Krok 3. Post pujemy analogicznie jak w kroku 1. Elementy: „+”, „c”, „b” b d stanowiły jego
poddrzewo.
opracowała: mgr in . Izabela Skorupska
6
J zyk ANSI C (w systemie LINUX)
Krok 4. Analogicznie jak w kroku 2. Tak zbudowane drzewo b dzie miało posta :
Odczytywanie i obliczanie warto ci wyra enia rozpoczynamy od najni szego poziomu (poddrzewa)
lewego potomka (od strony prawej do lewej) i w drujemy ku górze a do wierzchołka, nast pnie
powtarzamy operacj dla prawego potomka. Odczytane wyra enie b dzie miało posta :
(c+b)*a+(e/d)
Przykład 4: Obliczy warto wyra enia:
4 2 3 + * 1 5 - +
(metod drzewa)
Tworzymy drzewo:
Odczytujemy poszczególne składowe wyniku:
opracowała: mgr in . Izabela Skorupska
7
J zyk ANSI C (w systemie LINUX)
2!
3$
Zadanie polega na napisaniu: programu
kalkulator.c licz cego warto wyra enia podanego w
odwrotnej notacji polskiej (notacji postfiksowej).
Zało enia programu kalkulator:
• program przyjmuje tylko cyfry:
0..9
oraz symbole operacji:
* / + -
• próba wprowadzenia innej warto ci oraz dzielenia przez zero powinna spowodowa
wy wietlenie odpowiedniego komunikatu i przerwanie operacji liczenia.
•
q
oznacza wyj cie z programu
• dozwolone s dwa sposoby wykonywania oblicze :
o
za pomoc stosu,
o
za pomoc drzewa.
4!
*
Przykładowe uruchomienie programu kalkulator:
Wprowadz liczby:
1 2 3 + -
Wynik operacji: 4
Wprowadz liczby
1 a +
„a” nie jest cyfra ani znakiem operacji.
Wprowadz liczby:
0 1 2 + /
Dzielenie przez 0.
Wprowadz liczby:
q
Wyjscie z programu
5!
)$
Sprawozdanie powinno zawiera nast puj ce elementy:
•
schemat blokowy działania programu,
•
skomentowany
plik ródłowy,
•
plik makefile do kompilacji programu,
•
w przypadku wykonywania oblicze na drzewie dokładny opis utworzonej struktury oraz
funkcji,
•
wnioski i uwagi.
opracowała: mgr in . Izabela Skorupska
8
J zyk ANSI C (w systemie LINUX)
UWAGA:
Program licz cy oparty o operacje wykonywane na drzewie b dzie wy ej punktowany ni
program wykorzystuj cy obliczenia na stosie.
5!
6
1.
A. Drozdek, D. L. Simon „Struktury danych w j zyku C”, WNT 1996.
2.
http://julia.univ.gda.pl/~matszp/book/Md8.pdf
3.
http://galaxy.uci.agh.edu.pl/~chwastek/lectures/C/spis.html