Vaje 12

Tatjana Ahčin

22.12.1997

Uvod v pogodbo:

Želimo imeti podatkovno strukturo sklad z naslednjimi operacijami:

0.1 Začetek in konec

ustvari: (create, new, instantiate), Ustvari spremenljivko tipa sklad.

uniči: (destruct, despose, delete), uniči spremenljivko tipa sklad.

Operaciji ustvari in uniči sta obvezni za vsako podatkovno strukturo. Primer operacije ustvari:

{ int i= 0;   /* ustvari spremenljivko i, ki ima vrednost 0 */
  printf("%d\n", i);
}

Spremenljivka i ima pomen samo v okviru bloka (v zavitih oklepajih). Kako naredimo polje 10-ih celih števil?

{ int v[10];    /* rezerviramo 10 mest za cela stevila */
  ...
}

0.2 Operacije nad skladom

naloži - push: Naloži nekaj na sklad (na vrh sklada).

zloži - pop: Zloži nekaj s sklada (spet seveda z vrha sklada).

0.3 Poizvedovanja

prazen - empty: Pogleda, ali je sklad prazen ali ne. Če je prazen, potem ne moremo z njega nič zloziti.

poln - full: Pogleda, ali je še kaj prostora na skladu, torej če nanj še lahko kaj naloži.

Primer pogodbe:

typedef SKL_tSklad;
SKL_tSklad SKL_Ustvari();
/*  Desc:   Ustvari prazen sklad.
Parms:  /
Result: sklad
Pre:    /
Post:   SKL_Prazen(sklad)
*/
void SKL_Unici(SKL_tSklad * sklad);
/*  Desc:   Unici sklad.
Parms:  sklad - sklad, ki ga unicimo (po referenci)
Result: /
Pre:    sklad je bil ustvarjen
Po:     sklad ne moremo vec uporabiti
*/
void SKL_Nalozi(SKL_tSklad * sklad,
            int element);
/*  Desc:   Na sklad nalozi element.
Parms:  sklad - sklad, na katerega nalozimo element (po referenci)
        element - na sklad nalozen element (po vrednosti)
Result: /
Pre:    NOT (SKL_Poln(sklad))
Post:   sklad' = [element | sklad]
int SKL_Zlozi(SKL_tSklad * sklad);
/*  Desc:   S sklada zlozi element.
Parms:  sklad - sklad, s katerega zlozimo element (po referenci)
Result: element

Pre:    (NOT SKL_Prazen(sklad)) AND (sklad = [element | ostalo])
Post:   sklad' = ostalo
*/
bool SKL_Prazen(SKL_tSklad sklad);  /* ...(const SKL_tSklad *sklad) */
/*  Desc:   Preveri, ali je sklad prazen in tedaj vrne vrednost TRUE, sicer
        FALSE.
Parms:  sklad - sklad, za katerega poizvedujemo
Result: {if sklad = [] then TRUE else FALSE }
Pre:    sklad ustvarjen
Post:   /
*/
/* Potrebujemo se funkcijo bool SKL_Prazen(SKL_tSklad * sklad) */