Implementacja Listy -kolejki W C++

[wragler]

Witam

Musze napisac program ktory bedzie symulowal kolejke (liste) tzn. Mam zaaplikowac polecenia typu add i del ktore beda wkladac cos do listy i z niej cos zdejmowac. Np jezlei zdejme wszsytkie elementy to porgram napisze ze kolejka jest pussta. Jak takie cos zrobic bo nie ma kompletnie poamyslu na to . Mysle ze trzeba uzyc do tego wskaznikow ale jak?

Prosze o pomoc.

[MeHow]

moj drogi... zaimplementuj to sobie na vectorze. Jesli to ma byc priority queuee czy jak to sie pisze, to operuj na danym typie wzgledem danego operatora < . Poczytaj o czyms takim jak sterta/kopiec/heap .

 

pozdrawiam

[ULLISSES]

Nie do końca jestem pewien, czy chodzi o kopiec czy o listę. Dodaje się i ściąga z kopca (stosu), a Ty tu o liście mówisz.

 

Kopiec, to jest sprawa dość prosta: przypypomina układanie talerzy jeden na drugim - aby dostać się do tego niżej, musisz najpierw ściągnąć ten wyżej.

 

List natomiast są 2 rodzaje: jednokierunkowa i dwukierunkowa.

AFAIK pierwsza z nich posiada głowę i ogon (head i tail - druga chyba też), i można poruszać się w po niej tylko w jednym kierunku przez wskaźnik *next. Po drugiej można poruszać się w obie strony - wskaźniki *prev i *next;

 

Deklaracja klasy powinna wygladać mniej wiecej tak (dla Pascala):

type  pLista=^Tlista;  Tlista=record	imie, nazwisko :string;	rok_urodzenia :integer;	next :pLista;	prev :pLista;	end;

Wyjaśnienie:

1. Definiujemy nowy typ, który jest wskaźnikiem do rekordu (w C będzie to klasa).

2. Definiujemy rekord (klasę).

[__max]

Spróbuj poszukać przez google 'queue c++'

[vtg]

Ja bym proponował stworzyć sobie jakiś ładny wektor, zawsze to lepsze niż lista.

Mozna użyć też szablonów (template), aby nie martwic sie o typ danych.

[__max]

Drobna uwaga: w STL-u obok klasy vector jest chyba też szablonik klasy queue......

Ale tu chyba nie chodzi o gotowca tylko o własną implementację?

Edytowane 21 Stycznia 2006 przez __max

[wragler]

No niestey nic ni emoge napisac. Znalazlem w necie sporo informacji ale te programy sa trudne i nie moge ich za bardzo zrozumiec. Chodzi mi o program ktory dzieki funckja pop i push bedzie dokladal i zdjemowal rzeczy do kolejki. A jak kolejka bedzie pusta to sie wyswieli komunika .tyle. Czy kots moze mi konkretnie pomoc???

Znalazlem takie cos:

TYlko ja chcialby zrobic tak zeby samodzielnie wprowadzac te wyrazy do kolejki. Np w ten sposob: Wprowdza 1 elemet listy i ja wprowadzam. A pozniej wyswietlal po kolieji zadejmuje 4 elemet listy "Basia" i zdjemuje 4 elemet "Krzysiek" itd.

template <class TypPodst>  class FIFO{  TypPodst *t;  int glowa,ogon,MaxElt;public:  FIFO(int n)	 {	 MaxElt=n;	 glowa=ogon=0;	 t=new TypPodst[MaxElt+1];	 }	void wstaw(TypPodst x)	 {	 t[ogon++]=x;	 if(ogon>MaxElt) ogon=0;	 }  int obsluz(TypPodst &w)	 {	 if (glowa==ogon) return -1; // informacja o błędzie operacji	 w=t[glowa++];	 if(glowa>MaxElt) glowa=0;	 return 1;	 }  int pusta()							// czy kolejka jest pusta?	 {	 if (glowa==ogon)		return 1; // kolejka pusta	 else	 return	0;	 }};#include <iostream.h>#include "kolejka.h"static char *tab[]={"Kowalska","Fronczak","Becki","Pigwa"};int main(){FIFO<char*> kolejka(5); // kolejka 5-osobowafor(int i=0; i<4;i++)  kolejka.wstaw(tab[i]);  char *s;  for(i=0; i<5;i++)  {  int res=kolejka.obsluz(s);  if (res==1)		cout <<  "Obsluzony zostal klient: "<<s<<endl;  else		cout <<  "Kolejka pusta!\n";  }  /* wersja 2:  while(!kolejka.pusta())	 {	 int res=kolejka.obsluz(s);	 cout <<  "Obsłużony został klient:"<<s<<endl;	 }	 --- */}

Edytowane 21 Stycznia 2006 przez wragler

[__max]

Hmmm...

Poświęcę się i dam gotowca (a co! ;P)

 

1. Plik kolejka.h zawierający interfejs i implementację składowych klasy Kolejka

#ifndef KOLEJKA_H#define KOLEJKA_Htemplate <typename TYP>class Kolejka;template <typename TYP>class Wezel{   friend class Kolejka<TYP>;public:   Wezel(const TYP& a);private:   Wezel<TYP> *nastepny;   TYP wartosc;};template <typename TYP>class Kolejka{public:   Kolejka();   ~Kolejka();   void poloz(const TYP& a);   TYP zdejmij();   bool pusty() const   {	  if(glowa) return false;	  else return true;   }private:   Wezel<TYP> *glowa;   Wezel<TYP> *ogon;};template <typename TYP>Wezel<TYP>::Wezel(const TYP& a) : wartosc(a), nastepny(0){}template <typename TYP>Kolejka<TYP>::Kolejka() : glowa(0), ogon(0){}template <typename TYP>Kolejka<TYP>::~Kolejka(){   while(!pusty()) zdejmij();}template <typename TYP>void Kolejka<TYP>::poloz(const TYP& a){   if(pusty())   {	  ogon = new Wezel<TYP>(a);	  glowa = ogon;   }   else    {	  ogon->nastepny = new Wezel<TYP>(a);	  ogon = ogon->nastepny;   }}template <typename TYP>TYP Kolejka<TYP>::zdejmij(){   if(!pusty())   {	  TYP rob = glowa->wartosc;	  	  if(glowa == ogon)	  {		 delete glowa;		 glowa = ogon = 0;	  }	  else	  {		 Wezel<TYP> *wsk = glowa;		 glowa = glowa->nastepny;		 delete wsk;	  }	  	  return rob;   }}#endif

2. Plik źródłowy przykładowego programu testującego klasę Kolejka:

#include <iostream>#include "kolejka.h"using namespace std;int main(){   int ileElementow, jakisElement;   Kolejka<int> jakasKolejka;      cout << "Podaj ile elementow kolejki chcesz wprowadzic" << endl;   cin >> ileElementow;      for(int k = 1; k <= ileElementow; k++)   {	  cout << "Podaj " << k <<" element kolejki" << endl;	  cin >> jakisElement;	  jakasKolejka.poloz(jakisElement);   }   cout << endl;   for(int k = 1; k <= ileElementow; k++)   {	  cout << jakasKolejka.zdejmij() << endl;   }   system("pause");   return 0;}

Mam nadzieję, że o coś takiego chodziło;)

[wragler]

Dzieki bardzo!!!!!!Troch e go poprzerabiam i bedzie cacy:)

POzdrawiam i dziekuje bardzo za ten program.

Edytowane 22 Stycznia 2006 przez wragler

[__max]

A na zdrowie ;P