AIwiki

To jest stara wersja strony!

Termin zajęć: 12/13.04.2011

Do przygotowania:

1. Znajomość zasad działania podstawowych struktur danych:
   • stos
   • kolejka FIFO, cykliczna
2. Odwrotna Notacja Polska:
   • co to jest notacja postfixowa, prefixowa i infixowa?
   • algorytmy zamiany notacji infixowej na ONP przy pomocy stosu
   • obliczanie wartości wyrażania w notacji ONP
3. Proszę zaimplementować następujące klasy wraz z odpowiednimi metodami:
   1. Stos implementujemy jako tablice i wskaźnik na szczyt stosu (wskazuje na ostatni wstawiony element)

class STOS
  TAB[MAX] #MAX - maksymalna liczba elementów
  top := 0
end class

funkcje:

func isEmpty()
   if ( top == 0 ) return true;
   else return false;
   end if
end func

func isFull()
  if ( top == MAX ) return true;
  else return false;
end func

func push( element )
  top := top + 1;
  TAB[top] := element;
end func

func pop()
  top := top - 1;
  return TAB[top + 1];
end func

func peek()
  return TAB[top];
end func

1. kolejka FIFO

implementowana tak, że po wyciągnięciu elementu z kolejki wszystkie pozostałe są przesuwane na początek, czyli usuwany jest zawsze pierwszy element kolejki

 class KOLEJKA
    TAB[MAX]
    rear := 0 #wskazuje na ostatni element
 end class

 func isEmpty()
    if ( rear == 0 ) return true;
    else return false;
 end func

 func isFull()
    if ( rear == MAX ) return true;
    else return false;
 end func

 func insert( element )
    rear := rear + 1;
    TAB[rear] := element;
 end func

 func remove()
    tmp := TAB[1];
    for i in 2 .. rear step 1
       TAB[i-1] := TAB[i];
    end for
    rear := rear - 1;
    return tmp;
 end func;

 func peek()
    return TAB[1]
 end func;
  -  kolejka cykliczna

 class KOLEJKA
    TAB[MAX]
    front := 1 #wskazuje na pierwszy element 
    rear := 0 #wskazuje na ostatni element
    n := 0; #liczba elementów
 end class

 func isEmpty()
    if ( n == 0 ) return true;
    else return false;
 end func

 func isFull()
    if ( n == MAX ) return true;
    else retirm false;
 end func

 func insert( element )
    rear := ( rear + 1 )  mod MAX;
    TAB[rear] := element;
    n := n + 1;
 end func

 func remove()
    tmp := TAB[front];
    #if ( front == MAX ) front := 1;
    #else front := front + 1;
    front := ( front + 1 ) mod MAX;
    n := n - 1;
    return tmp;
 end func;

 func peek()
    return TAB[front]
 end func;