Podstawy Programowania - Ćwiczenia 5

Zasady, Ćw1, Ćw2, Ćw3, Ćw4, Ćw5, Ćw6, Ćw7, Ćw8, Ćw9, Ćw10, Ćw11, Ćw12, Ćw13

Prowadzący: Rafał Witkowski
Temat: Stos i kolejka, ONP

Procedury i funkcje

Procedury i funkcje to takie kawałki programów, które mogą być wywoływane z innych miejsc w programie dowolną liczbę razy. Czasem są nazywane po prostu podprogramami.
Kształt ich zostanie omówiony dokładnie na zajęciach

Definicje

W języku C/C++ można na początku programu definiować dowolnie pewne stałe, ale też wyrażenia, które następnie można wykorzystywać w programie. Robi się to przy pomocy polecenia #define w nagłówku programu.
Przykład deklaracji i użycia stałych:

#define PI 3.14
#define ogr 1000

int main()
{
  int tablica[ogr]; // Powstanie tablica ograniczona przez 1000
  int r = 4;
  double pole_kola; // Zadeklarowanie zmiennej zmiennoprzecinkowej (ułamkowej)
  pole_kola = r*r*PI; // Pod PI zostanie podstawione 3,14 i obliczone zostanie pole koła o promieniu r
  return 0;
}

Przykład deklaracji wyrażenia i jego użycia:

#define FOR(i,n) for(int i=0; i<n; i++)
// powyżej zdefiniowana została inna struktura pętli for, którą będzie można wykorzystać w kodzie
// Np. szkielet pisanych przez nas programów mógłby wyglądać następująco:

int main()
{
  int d;		// deklaracja zmiennej oznaczającej liczbę zestawów danych
  scanf("%d",&d);	// sczytwanie liczby zestawów danych
  FOR(i,d)              // pętla sterująca programem - wykonywana tyle razy, ile jest zestawów
  {			// Powyższa pętla zostanie podmienione przez preprocesor na dokładnie to samo,
			//   co znajdowało się tu wcześniej w kodzie
  //---------------------------------------------------------------------------------------------
  // Tu powinien znajdować się właściwy kod programu rozwiązujący zadanie dla pojedynczego testu
  //---------------------------------------------------------------------------------------------
  }
  return 0;
}

Stos

Stos jest podstawową strukturą danych wykorzystywaną w informatyce. Zasada jego działania jest bardzo prosta: im coś później na stos zostało odłożone, tym wcześniej z niego zostanie zdjęte. Jak w każdym stosie znanym nie tylko z informatyki, ale także z życia - żeby zdjąć coś co jest pod spodem (trafiło na stos wcześniej) trzeba najpierw zdjąć to, co jest na jego wierzchu (trafiło na stos później). Angielski skrót na stos to LIFO (last in first out).

Dwoma operacjami, które są na stosie dopuszczalne są:
push(x) - dodanie elementu x do stosu
pop() - sczytanie elementu ze stosu

Implementacja

Stos można zaimplementować przy pomocy tablicy, której długość będzie maksymalnym rozmiarem stosu. Oprócz tablicy musimy mieć zmienną s która będzie pamiętała ile na stosie jest danych elementów.

Deklaracja zmiennych (tylko tych niezbędnych do wyrzystywania stosu) oraz procedury push i pop wyglądałyby w pascalu następująco:

int stos[1001], s;

void push(int x)
{
  stos[s] = x;
  s++;
}

int pop()
{
  if (s==0) 
  {
    printf("BŁĄD");
    return 0;
  }
  s--;
  return stos[s];
}

Zadanie 1

Zadanie 309 - treść jest tutaj.

Kolejka

Kolejka jest również jedną z podstawowych strukturą danych wykorzystywanych w informatyce. Zasada jej działania jest bardzo prosta: im coś później na kolejke zostało odłożone, tym później z niej zostanie zdjęte. Jak w każdej kolejce znanej nie tylko z informatyki, ale także z życia - każdy musi poczekać na swoją kolej i przepuścić wszystkich, którzy przyszli przed nim. Angielski skrót na kolejkę to FIFO (first in first out).
Dwoma operacjami, które są na kolejce dopuszczalne są:
push(x) - dodanie elementu x do kolejki
pop() - sczytanie elementu z kolejki

Implementacja

Kolejkę można zaimplementować przy pomocy tablicy, której długość będzie maksymalnym rozmiarem kolejki (największą liczbą elementów mogących się znajdować naraz w kolejce). Oprócz tablicy musimy mieć zmienne pk i kk oznaczające odpowiednio początek i koniec kolejki.
Deklaracja zmiennych (tylko tych niezbędnych do wyrzystywania kolejki) oraz procedury push i pop wyglądałyby w pascalu następująco:

#define rozmiar_kolejki 1000

int kolejka[rozmiar_kolejki];
int pk, kk;

void push(int x)
{
  kolejka[kk] = x;
  kk = (kk + 1) % rozmiar_kolejki; // % - dzielenie modulo
}

int pop()
{
  if (pk==kk) 
  {
    printf("BŁĄD");
    return 0;
  }
  int pom;
  pom = kolejka[pk];
  pk = (pk + 1) % rozmiar_kolejki;
  return pom;
}

Zadanie 2

Rowziąż zadanie ppr6. Treść jest tutaj.