Priority Queue

Hallo miteinander!

Ich sollte in einer Priority Queue (d.h. linked list) eine insert-Methode implementieren, die "node" als Argument hat. Als private Variable sollte man lediglich _root (ich hoffe, die Namen sind selbsterklärend ) verwenden.
Meine Frage: Aus was muss ich hier besonders achten, bzw. wie ist diese Methode zu implementieren? (evtl. Schritt-"Anleitung")

Liebe Grüsse,
Max

SeppJ

Sag doch erst einmal, wie du es machen würdest. Dann kann man kommentieren, ob das gut oder schlecht ist.

volkard

MaxC++ schrieb:

Hallo miteinander!
Ich sollte in einer Priority Queue (d.h. linked list)

Ungewöhnlich, weil insert O(n) Zeit kostet.
Ich sehme mal an single linked list, also nur Nachfolgerzeiger.

Erste Idee:

void insert(Node* newNode){
   for(Node* n=root;n!=nullptr;n=n->next)//läuft über alle bisherigen Nodes
      if(n->key>=newNode->key)
          //füge newNode VOR n ein. 
}

EDIT: Glaube, <= war gemeint, ist dann auch im Folgenden überall falsch.

Mist. Wie kann ich denn VOR n was einfügen?
Dazu müßte ich einen Zeiger auf den Node VOR n haben.
Ok, den merke ich mir halt auch.

void insert(Node* newNode){
   Node* vorher;
   for(Node* n=root;n!=nullptr;n=n->next){
      if(n->key>=newNode->key)
          //füge newNode VOR n ein. Also NACH vorher. 
      vorher=n;
   }
}

Ja, riecht gut.

void insert(Node* newNode){
   Node* vorher;
   for(Node* n=root;n!=nullptr;n=n->next){
      if(n->key>=newNode->key){
          vorher->next=newNode;
          newNode->next=n;
      }
      vorher=n;
   }
}

Ok, jetzt noch die Ränder checken.
Klappt das auch ganz am Ende?
Nee. Das müßte nach der Schleife passieren.

void insert(Node* newNode){
   Node* vorher;
   for(Node* n=root;n!=nullptr;n=n->next){
      if(n->key>=newNode->key){
          vorher->next=newNode;
          newNode->next=n;
          return;
      }
      vorher=n;
   }
   //falls kein Einfügen passierte
   vorher->next=newNode;
   newNode->next=nullptr;
}

Riecht schon nicht mehr schön. Aber scheint zu laufen.
Noch den Sonderfasll abfangen, daß am Anfang eingefügt wird, weil dann gibt es noch kein vorher.

void insert(Node* newNode){
   Node* vorher=nullptr;
   for(Node* n=root;n!=nullptr;n=n->next){
      if(n->key>=newNode->key){
          if(vorher==nullptr){
             newNode->next=root;
             root=newNode;
          }
          else{
             vorher->next=newNode;
             newNode->next=n;
          }
          return;
      }
      vorher=n;
   }
   //falls kein Einfügen passierte
   vorher->next=newNode;
   newNode->next=nullptr;
}

Und den Sonderfall, daß die Liste ganz leer war.

void insert(Node* newNode){
   if(root==nullptr){
      root=newNode;
      newNode->next=nullptr;
   }
   Node* vorher=nullptr;
   for(Node* n=root;n!=nullptr;n=n->next){
      if(n->key>=newNode->key){
          if(vorher==nullptr){
             newNode->next=root;
             root=newNode;
          }
          else{
             vorher->next=newNode;
             newNode->next=n;
          }
          return;
      }
      vorher=n;
   }
   //falls kein Einfügen passierte
   vorher->next=newNode;
   newNode->next=nullptr;
}

So, Phase I abgeschlossen. Falls es klappt, habe nichts getestet.
Phase II ist dann, gleichartigen Code zusammenzurassen, falls möglich.

Skym0sh0

lol volkard

n1, einfach mal so aus dem stegreif...

*respekt hab*

WOW! Vielen Dank für den Vorschlag!
Den werde ich mir zu Hause gleich mal anschauen.
Ich habs inzwischen so gemacht - allerdings hat es noch bugs drinnen, denn die Ausgabe ist nicht korrekt. Zudem ist vorgegeben, dass man nur die private Variable _root verwenden darf, und ich teilw. einige "temporäre" erstellt habe.
Was meint ihr dazu? (..oder ist es völliger bullshit?)

#include "priority_queue.hpp"

priority_queue::priority_queue() : _root(NULL) {}

void priority_queue::insert(node* node_)
{
    /* Insert your code here. */
	node* prev = NULL;
	node* current = _root;
	while (current != NULL && current->get_priority() >= node_->get_priority()) {
		prev = current;
		current = current->get_next();
	}
	node* temp;
	if (prev = NULL) {
		temp->get_next() == _root;
		_root = temp;
	}
	else {
		temp->get_next() == current;
		prev->get_next() == temp;
	}

}

node* priority_queue::pop()
{
	/* Insert your code here. */
	node* temp = _root;
	_root = _root->get_next();
	return temp;
}

size_t priority_queue::size() const
{
	/* Insert your code here. */
	*_root = priority_queue().size();
	_root->get_next() == NULL;
	return 0;
}

volkard

MaxC++ schrieb:

node* temp;//und zeigt wohin?
	if (prev = NULL) {
		temp->get_next() == _root;
		_root = temp;
	}
	else {
		temp->get_next() == current;
		prev->get_next() == temp;
	}

}

War damit nicht eher gemeint

//node* temp; //weg
	if (prev = NULL) {
		node_->get_next() == _root;
		_root = node_;
	}
	else {
		node_->get_next() == current;
		prev->get_next() == node_;
	}

}

Dein insert verlangt, daß jemand außerhalb schon den neuen Node genastelt hat.

node* newNode=new Node;//hier
newNode->priority=17;
theQueue.insert(newNode);

Deswegen mußt Du keinen selber anlegen.

Um symmetrisch zu sein, sollte pop auch nur den kleinsten Node ausketten und den ausgeketteten Node zurückliefern.

node* poppedNode=theQueue.pop();
cout<<poppedNode->priority<<'\n';
delete poppedNode;

Oh, das klappt ja schon.

Besten Dank für die Antworten!

Mein Code funktioniert soweit.
In einer diesen beiden Methoden muss es aber irgendwo noch einen (logischen) Fehler haben, denn der Compiler kompiliert, aber bei der Ausführung bricht das Programm ab. Doch was ist falsch, oder noch nicht vollständig?

node* priority_queue::pop()
{
	/* Insert your code here. */
	node* temp = _root;
	_root = _root->get_next();
	delete temp;
	return _root;
}

size_t priority_queue::size() const
{
	/* Insert your code here. */
	*_root = priority_queue().size();
	_root->get_next() == NULL;
	return 0;
}

Liebe Grüsse,
Max

inter2k3

MaxC++ schrieb:

// schnipp
void priority_queue::insert(node* node_)
{
    /* Insert your code here. */
	node* prev = NULL;
	node* current = _root;
	while (current != NULL && current->get_priority() >= node_->get_priority()) {
		prev = current;
		current = current->get_next();
	}
	node* temp;
	if (prev = NULL) {                 // <- eine Zuweisung
		temp->get_next() == _root;     // <- keine Zuweisung + temp nicht initialisiert
		_root = temp;
	}
	else {
		temp->get_next() == current;    // <- keine Zuweisung
		prev->get_next() == temp;       // <- keine Zuweisung
	}

}
// schnapp

Du willst wahrscheinlich (unter der Annahme, dass get_next eine Referenz eines nichtkonstanten Zeiger zurückgibt):

if (prev == NULL) {
    node->get_next() = _root;
    _root = node_;
}
else {
    node_->get_next() = current;
    prev->get_next() = node_;
}

Was du dir beim programmieren der size-Fkt. gedacht hast kann ich leider garnicht nachvollziehen

P.S.: zwei mal editieren müssen - es wird wohl Zeit ins Bett zu gehen

CStoll

MaxC++ schrieb:

node* priority_queue::pop()
{
	/* Insert your code here. */
	node* temp = _root;
	_root = _root->get_next();
	delete temp;
	return _root;
}

Das löscht das bisherige Kopf-Element und gibt das neue Kopf-Element zurück. Du solltest da vermutlich temp zurückgeben anstatt es zu vernichten.

size_t priority_queue::size() const
{
	/* Insert your code here. */
	*_root = priority_queue().size();
	_root->get_next() == NULL;
	return 0;
}

Ich hab' echt keine Ahnung, was dieser Code macht. Die erste Zeile sieht nach einem rekursiven Aufruf der Methode aus, die zweite Zeile kappt die Verbindung zwischen dem Kopf und der restlichen Kette (was dir zumindest ein Speicherleck beschert).
Wenn du die Größe/Länge deiner Queue zurückgeben willst, hast du zwei Möglichkeiten: Entweder du merkst dir die Größe und aktualisierst sie bei jedem insert() und pop() oder du läufst einmal durch die Struktur und zählst die Elemente.

//Variante 1:
void priority_queue::insert(node* node_)
{
  //dein Code
  ++_size;
}

node* priority_queue::pop()
{
  node* tmp = _root;
  _root = _root->get_next();
  --_size;
  return tmp;
}

size_t priority_queue::size() const
{
  return _size;
}

//Variante 2
size_t priority_queue::size() const
{
  node* tmp = root;
  size_t sz=0;
  for( ; tmp!=NULL ; tmp=tmp->ge_next(),++sz ) ;
  return sz;
}