Abstrakcyjne typy danych – kolejki



Pobieranie 196,16 Kb.
Strona2/2
Data23.10.2017
Rozmiar196,16 Kb.
1   2

Kolejka zawiera trzy elementy: Poczatek=3, Koniec=5 (usunięto: 0(a), 1(b), 2(c) i dodano: 3(d), 4(e)))


Poczatek Koniec

0

1

2

3

4

5

6

7









d

e










  1. Kolejka zawiera pięć elementów: Koniec=2, Poczatek=5 (usunięto 3(d), 4(e)) i wstawiono: 5(a), 6(b), 7(c), 0(d), 1(e) )

Koniec Poczatek

0

1

2

3

4

5

6

7

d

e










a

b

c

  1. Kolejka pełna: Koniec=5, Poczatek=5 (po wstawieniu na koniec następujących elementów: 2(f), 3(g), 4(h))

Poczatek

Koniec


0

1

2

3

4

5

6

7

d

e

f

g

h

a

b

c

  1. Kolejka pusta, stan nieokreślony: Koniec=5, Poczatek=5 (po usunięciu elementów: 5(a), 6(b), 7(c), 0(d), 1(e), 2(f), 3(g), 4(h)). Należy więc po usunięciu ostatniego elementu zainicjować kolejkę tak, aby Poczatek =N, Koniec=0, czyli wprowadzić kolejkę w stan A)

Poczatek

Koniec


0

1

2

3

4

5

6

7

























#include

#include

#include

#include


//1. interfejs ADT kolejki

typedef int dane; // dane umieszczone stosie

const long N=5;

struct kolejka //elementy typu kolejki

{ int Poczatek;



int Koniec;

dane tab[N];

};

//funkcje interfejsu mają ten sam nagłówek jak dla listy wiązanej

void Inicjalizacja(kolejka& Kolejka);

inline int Pusty(kolejka Kolejka);

int Wstaw(kolejka& Kolejka, dane Dana);

dane Usun(kolejka& Kolejka);


//Funkcje we/wy, ogólnego przeznaczenia, klienckie oraz program są //identyczne dla obu implementacji

//2. funkcje we/wy dla danych umieszczonych w kolejce

void Pokaz_dane (dane Dana);

dane Dane();


//3. funkcje ogolnego przeznaczenia

void Komunikat(char*);

char Menu(const int ile, char *Polecenia[]);
//4. elementy programu

const int Esc=27;

const int POZ=4;

char * Tab_menu[POZ] = { "1 : Wstawianie do kolejki- na koniec",

"2 : Usuwanie z kolejki-na poczatku",

"3 : Wydruk kolejki wraz z jej usuwaniem",

" >Esc Koniec programu"};

//funkcje klienta korzystajace z kolejki

void Wstaw_do_kolejki(kolejka& Kolejka);

void Wyswietl_usun_z_kolejki(kolejka& Kolejka);
void main(void)

{ kolejka Kolejka;



char Wybor;
clrscr();

Inicjalizacja( Kolejka);



do

{ Wybor= Menu(POZ, Tab_menu);



switch (Wybor)

{ case '1' : Wstaw_do_kolejki(Kolejka); break;



case '2' : if (Pusty(Kolejka)) Komunikat("\nStos pusty\n");

else (Usun(Kolejka));

break;


case '3' : if (Pusty(Kolejka)) Komunikat("\nStos pusty\n") ;

else Wyswietl_usun_z_kolejki(Kolejka);

break;


}

} while (Wybor !=Esc );

}

//*********funkcje interfejsu ADT kolejki************



void Inicjalizacja(kolejka& Kolejka)

{ Kolejka.Poczatek = N;

Kolejka.Koniec=0; }
inline int Pusty(kolejka Kolejka)

{ return Kolejka.Poczatek==N && Kolejka.Koniec==0; }


int Wstaw(kolejka& Kolejka, dane Dana)

{ if (Kolejka.Poczatek != Kolejka.Koniec)

{ Kolejka.tab[Kolejka.Koniec++] = Dana;

Kolejka.Koniec %= N;



if (Kolejka.Poczatek==N) Kolejka.Poczatek=0;

return 1; }

else return 0;

}
dane Usun(kolejka& Kolejka)

{ dane d;

Kolejka.Poczatek %= N;

d= Kolejka.tab[Kolejka.Poczatek++];

if (Kolejka.Poczatek%N==Kolejka.Koniec)

Inicjalizacja(Kolejka);



return d; }


1   2


©operacji.org 2017
wyślij wiadomość

    Strona główna