[C++] Priority_queue: come si inizializzano?

**tulkas85** · 24-01-2006, 01:49

ho abbozzato questa classe....
la logica dovrebbe essere questa, devo verificare se funzionano le connessioni tra gli elementi della lista...

codice:

class coda_p
{
private:
	
	int key;
	coda_p *next;
	
public:
	grafo *nodo;
	coda_p()
	{
		//coda_p *testa=new coda_p;
		next=NULL;
		nodo=NULL;
		key=INT_MAX;

	}
	//grafo * getnodo(){return nodo;}

	void push(grafo *E,int chiave)
	{
		coda_p *insert=new coda_p;
		insert->key=chiave;
		insert->nodo=E;
		if (this->next==NULL)  //this contiene la testa della coda
			this->next=insert;
		else
		{

			coda_p *app=this->next;
			coda_p *app2;
			while(app->key<chiave && app!=NULL)
			{
				app2=app;
				app=app->next;
			}
			if(app!=NULL)
			{
				app2->next=insert;
				insert->next=app;
			}
		}

	}
	void pop()
	{

	}

};

per quanto dicevi qui :

Qquindi o ti sei premunito e per ogni nodo hai memorizzato anche il puntatore al precedente durante la scansione della lista, (ma questo richiede di distinguere il caso speciale della testa) o usi i doppi puntatori

per doppi puntatori intendi :
puntatore al successivo Q->next
puntatore al precedente Q->prec
oppure parli di doppio puntatore ** ?
in quest'ultimo caso in che modo posso evitare di memorizzare il puntatore prima di incrementarlo ??

**unomichisiada** · 24-01-2006, 01:56

Due cose:
1) Non credo ti convenga confondere la classe Nodo con la classe coda (che di nodi è composta), direi che è il caso di dichiarare una classe a parte per i nodi come classe interna a coda.Questo sinifica che in coda non te ne fai nulla di un puntatore a next.
2)Ovviamnete intendo i doppi puntatori "**". Prima fai la modifica di cui al punto sopra poi ne riparliamo,se non non si capisce nulla.

**tulkas85** · 24-01-2006, 02:03

parli di questo grafo *nodo; ??
questo è il dato che devo memorizzare nella coda....
diciamo che è come se memorizzassi una coda di struct, il mio dato è composto da nodo(di tipo grafo*) e key che mi serve per l'ordinamento...

**unomichisiada** · 24-01-2006, 02:15

Originariamente inviato da tulkas85
parli di questo grafo *nodo; ??
questo è il dato che devo memorizzare nella coda....
diciamo che è come se memorizzassi una coda di struct, il mio dato è composto da nodo(di tipo grafo*) e key che mi serve per l'ordinamento...

No non parlo di quello, se avessi notato che anche tu usi la parola nodo avrei evitato proprio per non ingenerare confusione di usarla pure io.
No parlo degli elementi della lista concatenata, la classe che li rappresenta non andrebbe confusa con al classe che rappresenta la lista stessa come hai fatto tu.

**tulkas85** · 24-01-2006, 15:35

ok cambio il nome....
ho cambiato anche un pò il codice, sembra funzionare...
per l'eliminazione posso fare un delete dello spazio allocato ??

codice:

class coda_p
{
private:
	
	int key;
	coda_p *next;
	
public:
	grafo *elem;
	coda_p()
	{
		//coda_p *testa=new coda_p;
		next=NULL;
		elem=NULL;
		key=INT_MAX;

	}
	//grafo * getnodo(){return nodo;}

	void push(grafo *E,int chiave)
	{
		coda_p *insert=new coda_p;
		insert->key=chiave;
		insert->elem=E;
		if (this->next==NULL)  //this contiene la testa della coda
			this->next=insert;
		else
		{

			coda_p *app=this->next;
			//coda_p *app2;
			bool trovato=false;
			while(app->next!=NULL && trovato==false)
			{
				
				if(app->key>chiave)
				{
					app->next=insert;
				    insert->next=app;
					trovato=true;
				}

				app=app->next;
			}
			if(app==NULL)
			{
				app->next=insert;
				insert->next=app;
			}
		}

	}
	void pop()
	{

	}

};

**unomichisiada** · 24-01-2006, 16:11

Ah volte ho l'impressione di parlare arabo

.
Scusa ma hai letto i miei post precedenti?Non ho affatto detto che il problema era il nome di quella variabile, ti ho detto che è sbagliato identificare la classe coda (che deve rappresentare l'intera struttura dati), con la classe elemnto_della_coda (o chimala come vuoi) che deve rappresentare i singoli elementi della coda.All'esterno non deve nemmeno vedersi che tu hai implementato la coda con una lista concatenata,la classe deve solo fornire dei metodi push e pop che ne rimangano assolutamente indipendenti.Grafo è solo il tipo dell'informazione in ognuno di quegli elementi.Non so non mi sembra di essermi spiegato così male.In ogni caso invito chiunque legga questa discussione a spiegare meglio la cosa se effettivamnete l'ho fatto.

**tulkas85** · 25-01-2006, 00:41

si mi pare di aver capito,
ma la mia struttura dati all'interno del programma è un array di puntatori a grafo....
per farti capire, ti faccio un esempio di inserimento nella mia coda:

codice:

int i;
		
		coda_p *Q=new coda_p;

		for(i=0;i<m;i++)
			Q->push(G[i],m-i);
		Q->stampa();

il push sembra funzionare, ora non riesco ad eliminare il nodo di testa tramite il pop....mi dice che :
error C2106: '=' : left operand must be l-value
ecco il metodo responsabile di tutto ciò:

codice:

void pop()
	{
		this=this->next;
	}

se può essere d'aiuto ecco la mia classe coda, this contiene la testa della coda :

codice:

class coda_p
{
private:
	
	int key;
	coda_p *next;
	grafo *elem;
public:
	
	coda_p()
	{
		
		next=NULL;
		elem=NULL;
		key=INT_MAX;

	}


	void push(grafo *E,int chiave)
	{
		coda_p *insert=new coda_p;
		insert->key=chiave;
		insert->elem=E;
		coda_p *app=this;//this rappresenta la testa della coda

		bool trovato=false;
		while(app->next!=NULL && trovato==false)
		{
			if(app->next->key>chiave)
			{
				insert->next=app->next;
				app->next=insert;
		  
				trovato=true;
			}
		
			app=app->next;
		}
		if(app->next==NULL)
			app->next=insert;
	}

	void pop()
	{
		

		this=this->next;

	}

	void stampa ()
	{
		coda_p *p=this->next;
		while(p!=NULL )
		{
			cout<<p->key<<"  "<<endl;
			p=p->next;
		}
	}
};

**unomichisiada** · 25-01-2006, 01:21

Come volevasi dimostrare...questo errore scaturisce anche dal fatto che non mi dai retta continui a fare l'errore di cui ti ho già detto due volte e ciò ti porta a confonderti.this non può essere assegnato! Si tratta di una parola chiave del linguaggio che individua un puntatore all'istanza corrente della classe, è per ovvie ragioni un puntatore COSTANTE,non modificabile e quindi non assegnabile.Come mai ti ostini a non seguire il mio consiglio proprio non lo capisco.La cosa diventerà molto più logica se lo farai,ed anche per me sarà possibile dare dei consigli basandomi sul del codice corretto.Ciao

**tulkas85** · 25-01-2006, 02:00

scusa non è che mi ostino... solo così riesco ad implementarla sta benedetta coda....
ahhh se potessi usare le priority queue del c++

**unomichisiada** · 25-01-2006, 02:23

Originariamente inviato da tulkas85

scusa non è che mi ostino... solo così riesco ad implementarla sta benedetta coda....
ahhh se potessi usare le priority queue del c++

Scusami è lineare: ti scrivi una classe coda in cui hai,un puntatore alla testa della lista come campo privato, e tre metodi pubblici più un costruttore:un metodo push() che prende come parametro l'informazione da inserirenella coda,un metodo pop() o top() o quello che è che ritorna l'INFORMAZIONE (bada bene quella,non l' elemento della lista) legata al più "grande" degli elementi nella coda e lo elimina, un metodo isEmpty() che ritorna un booleano e dice all'eseterno se la coda è vuota o no.

Fatto questo all'interno della classe definisci una struttura, o una classe interna (non ricordo se in c++ si possono usare le classi interne ma non è un problema) che rappresenti il SINGOLO elemento della lista con cui internamente implementi la lista.(Per intenderci se la lista la implemnetassi con uno heap,non avresti bisogno del campo privato puntatore alla testa e avresti bisogno di una array, inoltre i metodi avrebbero un'implementazione diversa ma LA STESSA INTERFACCIA VERSO l'ESTERNO cioè lo stesso prototipo.)
A questo punto puoi usare il campo puntatore alla testa (che è un puntatore di tipo elemento_lista non un puntatore di tipo coda) come useresti una variabile globale in un programma C.Ti faccio un esempio col metodo Top

codice:

class coda
{
  private:
     ElemLista* head;
  public:
      data Top(); //data nel tuo caso sarà grafo o quello che è 
}

class coda
{
   data coda::Top()
   {
   if (head == NULL)
      return //un valore di errore compatibile col valore di ritorno

    ElemLista* top = head;
    data retValue = top->key; //key è di tipo data
    head = head->next;
    delete top;
    return retValue;
   }
}

manca la definizione della struttura /classe ElemLista ma spero di essere stato chiaro

Discussione: [C++] Priority_queue: come si inizializzano?

Strumenti discussione

Ricerca discussione

Visualizza

Permessi di invio