Wydział Elektrotechniki, Informatyki i Telekomunikacji
Instytut Informatyki i Elektroniki
Instrukcja do zajęć laboratoryjnych
Język ANSI C (w systemie LINUX)
wersja: 3.0
Nr ćwiczenia: dodatkowe
Temat: Stos i drzewo w języku ANSI C
Cel ćwiczenia: Celem ćwiczenia jest zapoznanie studenta z organizacją stosu oraz drzewa w języku
ANSI C oraz praktyczne wykorzystanie tych informacji do napisania kalkulatora
liczącego w odwrotnej notacji polskiej.
Wymagane Informacje dotyczące organizacji stosu i drzewa oraz zapoznanie się z odwrotną
przygotowanie notacją polską.
teoretyczne:
Sposób zaliczenia: Sprawozdanie w formie pisemnej. [x]
Pozytywna ocena ćwiczenia przez prowadzącego pod koniec zajęć. [ ]
1. Wstęp
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.
2. Implementacja stosu i drzewa w języku ANSI C
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 1
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 2
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.
3. Notacje: infiksowa, prefiksowa, postfiksowa
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. A
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.
4. Algorytmy obliczania wyrażenia w postaci postfixowej
4.1. Przykład z wykorzystaniem stosu
Dla kolejnych zapisów wyrażenia:
opracowała: mgr inż. Izabela Skorupska 3
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
4.2. Przykład z wykorzystaniem drzewa
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 4
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+3=5 5*4=20 5-1=4 4+20=24
2 5
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 5
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 6
Język ANSI C (w systemie LINUX)
 5. Opis zadania:
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.
6. Przykład działania
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
7. Sprawozdanie:
Sprawozdanie powinno zawierać następujące elementy:
" schemat blokowy działania programu,
" skomentowany plik z
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 7
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.
7. Literatura:
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
opracowała: mgr inż. Izabela Skorupska 8
Język ANSI C (w systemie LINUX)