\documentclass[a4paper,12pt]{article}

% Tatjana Ahcin PRAKTICNA MATEMATIKA - 2.LETNIK

\usepackage[latin2]{inputenc}

\title{Vaje 21}
\author{Tatjana Ahčin}
\date{06.04. in 07.04.}

\begin{document}

\maketitle
\section*{Rekurzivne podatkovne strukture (RPS)}

Ukvarjali se bomo s problemom slovarja.

Najprej bomo definirali problem, ki ga hočemo rešiti, nato si bomo
ogledali rekurzivno podatkovne strukture, s katerimi bomo le-tega
rešili.

\subsection*{Problem slovarja}

\begin{center}
      {\it J}
      {\it jabolko} ~apple(a:pel) .....
\end{center}
%
\textbf{Prva beseda je ključna, nato sledijo pojasnila, podatki}.
Poznamo tri operacije nad slovarji (\textit{dictionary}), 4.\ bomo
omenili malo kasneje:
%
\begin{itemize}
\item Poišči ključ $\longrightarrow$ podatki
\item Vnesi geslo
\item Zbriši ključ (podatki so vezani na ključ)
\item Obstaja(podatki) $\longrightarrow$ \texttt{true} ali
  \texttt{false}
\end{itemize}
%
Ključ je bistvena stvar, s katero pridemo do podatkov. če želimo
geslo kaj popraviti, moramo ključ najprej zbrisati, potem ga spet
vnesemo (z vsemi npr.\ dopoljnjenimi pojasnili).
%
Vnašamo lahko le ključ, ki v slovarju še ne obstaja. Izbrišemo pa
lahko le tistega, ki obstaja v slovarju.

\subsection*{Kaj pa, če ključ ne obstaja?}

Rezervirali bomo npr.\ podatek \emph{NAPAKA}, ki pove, da ključa ni v
slovarju.
%
Obstaja več možnosti:
%
\begin{itemize}
\item v primeru neobstajanja ključa vrnemo posebne podatke
\item definiramo še neko novo funkcijo \texttt{Obstaja}
\end{itemize}
%
Napake ne bi radi povedali. To pa zato, ker smo v tem primeru omejeni
pri vpisu, ki ima lahko napake v podatkih.  Razred naj se sam odloči,
kaj je najbolj primerno oz. kaj je zanj napaka.

\noindent
\textbf{Vprašanje:}
Ali obstaja podatek, ki bi opisoval ključ in vsa pojasnila?

\noindent
\textbf{Odgovor:}
Da, \emph{slovarsko geslo}!

\subsection*{Definicija gesla}

Geslo sestoji iz:
%
\begin{center}
\begin{itemize}
\item {\it ključ}
\item {\it podatki}
\end{itemize}
\end{center}
%
Definiramo razred gesel, ki jih veže skupna lastnost:
%
{\tt
\begin{verbatim}
class Geslo {
public:
  char * ključ[32]
  char * podatki[256]

  Geslo();        // kreator
  ~Geslo();       // destruktor
}
\end{verbatim}
}
%
Našli boste na
%
\[
  \texttt{Z:}
     \backslash\texttt{PREDAVANJA}
     \backslash\texttt{POLDE}
     \backslash\texttt{code}
     \backslash\texttt{Geslo}
     \backslash\texttt{Geslo.h}
\]

\subsection*{Sklad celih števil}

Sklad:
%
\begin{quote}
  Funkcija Ustvari že določi velikost sklada na začetku. Poleg
  osnovnega kreatorja ustvarimo še en kreator, ki nam bo že na začetku
  nudil željeno velik sklad.
\end{quote}
%
{\tt
\begin{verbatim}
private:                     // to nam manjka v prevatnem delu
  int min_sklad              // najmanjsa velikost skladisca

  Sklad(int min_velsklad){
/* Desc:   Ustvari prazen sklad, za katerega velikost skladisca
           ni nikoli manjsa od min_velsklad.
   Parm:   /
   Result: sklad
   Pre:    min_vel_sklad>0
   Post:   Prazen()
*/

// NOV KREATOR:

  Sklad:: Sklad(int min_velikost) {
    ptr_skladisce = new int[min_vel_sklad];
    velikost = min_vel_sklad;
    zadnji = 0;
    min_velikost = 0;
    ...
} // Sklad
\end{verbatim}
}
%
Ta program si lahko ogledate na:
%
\[
  \texttt{Z:}
     \backslash\texttt{PREDAVANJA}
     \backslash\texttt{POLDE}
     \backslash\texttt{code}
     \backslash\texttt{Sklad}
     \backslash\texttt{Sklad-int.cpp}
\]

\subsection*{Nazaj k slovarju}

{\tt
\begin{verbatim}
class Geslo {
public:
  char * m_kljuc;  /* m pomeni member-clan */
  char * m_podatki;
  Geslo();          /* manjka pogodba */
  ~Geslo();
  Geslo(char *kljuc, char *podatki);
}; // Geslo
\end{verbatim}
}
%
{\tt
\begin{verbatim}
class Slovar {
public:
/*----------------------USTVARJANJE
  Slovar();
/* ...
   Post: this = {} (Slovar ustvari prazno mnozico.)
*/
/*----------------------SPREMINJANJA
  Vnesi(const Geslo geslo);
/* ...
   Pre: ne obstaja geslo.m_kljuc: (m_kljuc, karkoli) je
        element this
        (Kar ze obstaja, ne smemo se enkrat vnesti.)
   Post: this'= this U geslo
         (Vrstni red ni pomemben.)
*/
/*----------------------POIZVEDOVANJA
char * Poisci(char *kljuc);    /* referenca na podatek */
/* ...
   Result: result *
   Post:   IF ((kljuc, podatki) niso elementi this) THEN
             result = NULL
           ELSE
             result = & podatki
*/
\end{verbatim}
%
Popolno izvedbo definicijskega modula si oglejte na področju
%
\[
  \texttt{Z:}
     \backslash\texttt{PREDAVANJA}
     \backslash\texttt{POLDE}
     \backslash\texttt{code}
     \backslash\texttt{Geslo}
     \backslash\texttt{Geslo.h}
\]

Dodatna popogoja pri operaciji \texttt{Poišči} sta:
%
\begin{itemize}
\item uporabnik ne sme spreminjati podatkov
\item rezultat je veljaven do naslednjega posega v slovar (operacije
  nad slovarjem)
\end{itemize}
%
Nadaljevanje definicijskega modula:
{\tt
\begin{verbatim}
/*--------------------------SPREMINJANJA
void Zbrisi(char *kljuc);
/* ...
   Pre: (kljuc,----) je element this = Poisci(kljuc)!=NULL
   Post: this' = this \ (kljuc)
*/
\end{verbatim}
}

\section*{Različni razredi skladov}

\subsection*{Sklad števil s plavajočo vejico}

Definicijski, izvedbeni in testni modul si lahko ogledate na področjih
%
\[
  \texttt{Z:}
     \backslash\texttt{PREDAVANJA}
     \backslash\texttt{POLDE}
     \backslash\texttt{code}
     \backslash\texttt{Sklad}
     \backslash\texttt{Sklad-tip.h}
\]
\[
  \texttt{Z:}
     \backslash\texttt{PREDAVANJA}
     \backslash\texttt{POLDE}
     \backslash\texttt{code}
     \backslash\texttt{Sklad}
     \backslash\texttt{Sklad-tip.cpp}
\]
\[
  \texttt{Z:}
     \backslash\texttt{PREDAVANJA}
     \backslash\texttt{POLDE}
     \backslash\texttt{test}
     \backslash\texttt{Skald}
     \backslash\texttt{Sklad-tip.h}
\]
%
Definirati smo morali novo tip \texttt{tSklElt} in ga v primeru
opearcij nad realnimi števili definirali kot \texttt{float}. S tem
tipom smo nato potem lahko operirali.

\subsection*{Sklad s nizi (\textit{string})}

Sklada s črkami ni težko narediti. Spremembe so podobne, kot pri
skladu z realnimi števili glede na sklad s celimi števili.
%
Tudi tukaj definiramo tip tSklElt kot niz \texttt{char *}, s katerim
operiramo. Vemo, da je niz vedno prenešen po naslovu.  Pomagati si
moramo s funkcijo \texttt{strcpy}, s katero prepisujemo nize.
%
Definicijski, izvedbeni in testni modul si lahko ogledate na področjih
%
\[
  \texttt{Z:}
     \backslash\texttt{PREDAVANJA}
     \backslash\texttt{POLDE}
     \backslash\texttt{code}
     \backslash\texttt{Sklad}
     \backslash\texttt{Sklad-str.h}
\]
\[
  \texttt{Z:}
     \backslash\texttt{PREDAVANJA}
     \backslash\texttt{POLDE}
     \backslash\texttt{code}
     \backslash\texttt{Sklad}
     \backslash\texttt{Sklad-str.cpp}
\]
\[
  \texttt{Z:}
     \backslash\texttt{PREDAVANJA}
     \backslash\texttt{POLDE}
     \backslash\texttt{test}
     \backslash\texttt{Skald}
     \backslash\texttt{Sklad-str.h}
\]

\end{document}
