Lekcja 6
stosy, kolejki

Zmienne obiektowe w pseudokodzie, notacja nawiasowa.

Niech X będzie zmienną obiektową reprezentującą obiekt z atrybutami (lub inaczej polami):
    a, b, c
do atrybutów obiektu X odwołujemy się używając notacji nawiasowej:
    a[X], b[X], c[X]

Także tablice traktujemy jako zmienne obiektowe, które mogą posiadać dodatkowe atrybuty,
przykładowo tablica A[1..n] może posiadać atrybuty:
    pocz[A], kon[A]
które - przykładowo - mogą oznaczać początek i koniec pewnego "zakresu" tablicy.

Przyjmujemy że zmienne obiektowe to w rzeczywistości tzw wskazania na obiekt.

Struktury danych: stos i kolejka.

Stos to tablica S[1..n] z dodatkowym atrybutem p[S] wskazującym wierzchołek stosu.
Na stosie można wykonywać następujące operacje:

• Inicjuj(S)
      inicjuje stos S
• Pisz(S, element)
      zapisywane elementy są kładzione na wierzchołku stosu
• Czytaj(S) // to jest funkcja zwracająca odczytany element
      odczytywane elementy są zdejmowane z wierzchołka stosu

Kolejka to tablica K[1..n], z dodatkowymi atrybutami c[K], p[K] wskazującymi na element do odczytu oraz na wolny element do zapisu.
Na kolejce można wykonywać następujące operacje:

• Inicjuj(K)
      inicjuje kolejkę K
• Pisz(K, element)
      zapisywane elementy są kładzione na koniec kolejki
• Czytaj(K) // to jest funkcja zwracająca odczytany element
      odczytywane elementy są pobierane z początku kolejki
• Pusta(K), Pełna(K), LiczElem(K)
      stwierdza czy kolejka jest pusta, pełna oraz podaje liczbę elementów

Uwaga: indeksy c[K] i p[K] mogą się "przewinąć" na początek tabeli!

.........................................................................................

Zadanie 100
Zaimplementuj operacje na stosie S i kolejce K.
Jeśli operacja powoduje błąd (np odczyt z pustego stosu) to użyj procedury
    error "opis błędu"
Wskazówka: zwróć uwagę że w przypadku kolejki, gdy c[K]=p[K] to nie wiadomo czy kolejka jest pusta czy pełna!

Zadanie 101
Mamy dwie kolejki K1 i K2, które zawierają posortowane elementy (tj gdybyśmy odczytywali elementy kolejek procedurą Czytaj(K) otrzymalibyśmy posortowany ciąg elementów). Scal kolejki, K1 i K2 a wynik umieść w kolejce K3. Czas działania powinien być =O(LiczElem(K1)+LiczElem(K2)).

Zadanie 102
Tablica W[1..n] z atrybutem ost[W], której elementami są napisy, zawiera wyrażenie arytmetyczne w tzw
        Odwrotnej Notacji Polskiej (= ONP)
Wyrażenia te składają się z następujących elementów:
        liczba, +, -, *, /
Przykład wyrażenia w ONP:
        1 100 + 15 33 - *
co w zwykłej notacji wyrażeń oznacza
        (1+100)*(15-33)
Napisz algorytm obliczający wartość wyrażenia zapisanego w tablicy W.

Uwaga 1: powyższe wyrażenie ONP jest pamiętane w W w następujący sposób:

W[1]="1"
W[2]="100"
W[3]="+"
W[4]="15"
W[5]="33"
W[6]="-"
W[7]="*"
ost[W]=7

Uwaga 2: dysponujemy funkcją wartość(), która zamienia napis reprezentujący liczbę na liczbę.

.......................................................................

inne zadania ...

Zadanie 103
Zapisz procedurę sortowania przez wstawianie tablicy A[1..n] wykorzystując tzw wyszukiwanie binarne (patrz zadanie 45). Oszacuj czas działania tej procedury sortowania gdy za operację dominującą przyjmujemy:

1. porównywanie elementów tablicy
2. przypisywanie elementów tablicy

.......................................................................

Zadanie domowe 104
Napisz procedurę wygrywającą (o ile to możliwe ?) w grze w "kółko i krzyżyk" 3x3.
Procedura ta powinna mieć następujący nagłówek:

procedura Ruch(var plansza, gracz)

Zadanie domowe 105
Dana jest macierz M[1..n, 1..n] reprezentująca obraz. W tablicy tej za pomocą 1 jest reprezentowany kontur, pozostałe elementy zawierają 0. Napisz algorytm wypełniający kontur wartością 2.
Założenie upraszczające: elementy o wartości 1 stykają się bokami (a nie narożnikami).

Uwaga: na powyższym rysunku 0 nie są zapisane.