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