Pomoce:

Biblioteka procedur obsługi konsoli znakowej - newconio


Kolejka

Kolejka (ang. queue) jest strukturą danych przechowującą elementy w kolejności ich wprowadzenia.

Elementy wprowadzane do kolejki są dopisywane do jej końca - długość kolejki rośnie.

Elementy pobierane są z kolejki z jej początku - długość kolejki maleje.

 

Kolejkę możemy traktować jak bufor, w którym przechowywane są wprowadzone do niej dane. Naturalną strukturą danych do realizacji takiej kolejki jest lista, jednakże list jeszcze nie omawialiśmy na kole, zatem zrealizujemy kolejkę w znanej nam strukturze danych - tablicy. Oprócz samej tablicy będziemy potrzebowali dodatkowo dwóch zmiennych:

wp - wskaźnik początku kolejki, zawiera indeks elementu, który jest początkiem kolejki
wk - wskaźnik końca kolejki, zawiera indeks elementu, który leży tuż za ostatnim elementem kolejki

 

Dane zawsze wpisujemy do elementu tablicy, którego indeks zawiera wskaźnik końca kolejki wk. Po tej operacji wk jest zwiększane o 1. Jeśli wk wyjdzie poza ostatni element tablicy, to jest zerowane. Dane odczytujemy z elementu tablicy o indeksie wp. Po odczycie wp jest zwiększane o 1. Jeśli wyjdzie poza ostatni element tablicy, to, podobnie jak wk, jest zerowane.

Długość kolejki to liczba oczekujących w niej elementów. W pierwszym przypadku, gdy wk > wp, długość obliczamy ze wzoru:

 

d = wk - wp

 

Jednakże zastosowanie tego wzoru do przypadku drugiego, gdy wk < wp daje wynik ujemny. W takim razie wystarczy do tego wyniku dodać długość tablicy, aby otrzymać wynik poprawny.

Algorytm wstawiania danej do kolejki

Dane wejściowe:

e  -  wprowadzany element
K[ ]  - tablica, w której realizowana jest kolejka
wk  - wskaźnik końca kolejki

Dane wyjściowe:

K[ ]  -  tablica z wstawionym do kolejki elementem e
wk  - zmodyfikowany wskaźnik końca kolejki

Lista kroków

K01: K[wk] ← e
K02: wkwk + 1
K03: Jeśli wk = długość K[ ], to wk ← 0
K04: Zakończ

 

Algorytm pobierania danej z kolejki

Dane wejściowe:

K[ ]  -  tablica, w której realizowana jest kolejka
wp  - wskaźnik początku kolejki

Dane wyjściowe:

e  -  element pobrany z początku kolejki
K[ ]  - tablica z usuniętym z początku kolejki elementem e
wp  - zmodyfikowany wskaźnik początku kolejki

Lista kroków

K01: e ← K[wp]
K02: wpwp + 1
K03: Jeśli wp = długość K[ ], to wp ← 0
K04: Zakończ
 

Gra Wąż

Gra toczy się na planszy obejmującej cały ekran. Po planszy przesuwa się wąż w kierunku, który określa gracz za pomocą klawiszy kursora. W trakcie gry na planszy pojawiają się w przypadkowych miejscach losowe cyferki od 1 do 9 oraz przeszkody. Wąż zjada cyferki i zwiększa swoją długość o wartość cyfry. Gra kończy się, gdy wąż uderzy w cokolwiek innego niż cyfra.

Wąż zrealizowany jest w formie kolejki, w której zapamiętujemy współrzędne segmentów węża. Głowa węża w trakcie ruchu dopisuje nowe współrzędne kolejki. Ogon węża pobiera współrzędne z kolejki i wypisuje na nich spację - dzięki temu ostatni segment znika, co daje wrażenie ruchu węża. Zjedzenie cyferki powoduje wstrzymanie pobierania ostatnich segmentów z kolejki, dzięki czemu długość węża przyrasta.

 

// Zastosowanie kolejki - gra WĄŻ
// (C)2010 ILO w Tarnowie
// KOŁO INFORMATYCZNE
//-----------------------

#include <iostream>
#include <time.h>
#include <cstdlib>
#include "newconio.h"

using namespace std;

// ************************
// *** Zmienne globalne ***
// ************************

int K[2][4000];   // przechowuje współrzędne segmentów węża
int wp,wk;        // wskaźniki początku i końca kolejki
int jedzenie;     // jedzonko węża
int trawi;        // połknięty pokarm
int co_zjadl;     // znak zjedzony przez węża
int kierunek;     // w którą stronę sunie wąż
int w_x,w_y;      // współrzędne głowy węża

// Zapisuje współrzędne do kolejki
//--------------------------------

void k_wstaw(int x,int y)
{
    K[0][wk] = x;
    K[1][wk] = y;

    wk++; if(wk == 4000) wk = 0;
}

// Odczytuje współrzędne z kolejki
//--------------------------------

void k_pobierz(int & x, int & y)
{
    x = K[0][wp];
    y = K[1][wp];

    wp++; if(wp == 4000) wp = 0;
}

// Wyświetla planszę gry, czeka na klawisz i wraca
//------------------------------------------------

void start()
{
    fullscreen(true);

    cursoroff();

    frame(FRAME_SINGLE,0x1f,0,0,79,48);
    fillrect(' ',0x10,1,1,78,47);
    fillrect(' ',0x0,16,20,62,26);
    textattr(0xe);
    center(21,_pl("GRA WĄŻ"));
    center(23,_pl("(C)2010 I LO w Tarnowie"));
    textattr(0xc);
    center(25,_pl("Naciśnij dowolny klawisz, aby rozpocząć grę."));

    while(!getch());

    fillrect(' ',0x10,1,1,78,47);
}

// Wyświetla napis, czeka na klawisz, czyści ekran
//------------------------------------------------

void koniec()
{
    while(wp != wk)
    {
        int x,y;

        wk--;  if(wk < 0) wk = 3999;

        x = K[0][wk];
        y = K[1][wk];

        putxy('+',0x1f,x,y);

        delay(15);
    }

    if(kbhit()) while(!getch()); // likwidujemy ewentualny klawisz

    textattr(0x4e);
    center(23,_pl(" KONIEC GRY. Naciśnij dowolny klawisz. "));

    while(!getch());      // czekamy na klawisz

    textattr(7); clrscr(); cursoron(); fullscreen(false);
}

// Losuje cyfrę od 1 do 9 i umieszcza ją w wolnym miejscu ekranu
//--------------------------------------------------------------

void pokarm()
{
  int x,y;

  if(!jedzenie)
  {
      jedzenie = 1 + rand() % 9;

      do
      {
          x = 1 + rand() % 78;
          y = 1 + rand() % 47;
      } while(getchxy(x,y) != ' ');

      textattr(0x1e); gotoxy(x,y); cout << jedzenie;
  }
}

// Czyta klawisze i ustawia odpowiednio kierunek głowy węża
//---------------------------------------------------------

void klawisze()
{
    int c;

    if(kbhit())
    {
      while(!(c = getch()));

      switch(c)
      {
          case 72: kierunek = 0; break;
          case 77: kierunek = 1; break;
          case 80: kierunek = 2; break;
          case 75: kierunek = 3; break;
      }
    }
}

// Rysuje głowę węża, maże ogon
//-----------------------------

void ruch()
{
    switch(kierunek)
    {
        case 0: w_y--; break;
        case 1: w_x++; break;
        case 2: w_y++; break;
        case 3: w_x--; break;
    }

    co_zjadl = getchxy(w_x,w_y);
    putxy('@',0x4e,w_x,w_y);
    k_wstaw(w_x,w_y);

    if(trawi) trawi--;
    else
    {
        int x,y;

        k_pobierz(x,y); putxy(' ',0x10,x,y);
    }
}

int main()
{
    int licznik,dlugosc;

    _cinit();

    srand((unsigned)time(NULL));

    start();

    kierunek = 1;
    w_x = 39;
    w_y = 23;
    trawi = 10;
    licznik = wp = wk = jedzenie = 0;

    while(true)
    {
        delay(1);

        pokarm();

        klawisze();

        if(!licznik)
        {
            dlugosc = wk - wp; if(dlugosc < 0) dlugosc += 4000;
            textattr(10); gotoxy(38,49); cout << dlugosc;

            ruch();

            if(co_zjadl >= '1' && co_zjadl <= '9')
            {
                trawi += jedzenie;
                jedzenie = 0;
            }
            else if(co_zjadl != ' ') break;

            licznik = 30;

            if(dlugosc >  40) licznik = 25;
            if(dlugosc >  60) licznik = 20;
            if(dlugosc >  80) licznik = 15;
            if(dlugosc > 100) licznik = 10;
            if(dlugosc > 120) licznik =  7;
            if(dlugosc > 150) licznik =  5;
        }

        licznik--;
    }

    koniec();

    return 0;
}

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.