Suchbaum will nicht funktionieren...
-
meine Aufgabe ist es ein Programm zu schreiben, in das man Zahlen einlesen kann, suchen kann und löschen kann, wobei die Zahlen in einem Art Baum gespeichert werden sollen.
Die genaue Aufgabenstellung findet ihr sonst hier:
http://www.inf.ethz.ch/personal/fcellier/Lect/InfI/Ex/Inf1_ex9_Aufgabe.pdf
Nun habe ich bereits eine Such- sowie eine Einfüg-Funktion entworfen, doch keine der beiden funktioniert wie sie sollte. Auf den Aufruf der Suchfunktion kommt immer eine Windows-Fehlerbericht-Senden Meldung. Der Aufruf der Einfügfunktion klappt zwar, allerdings funktioniert auch diese nicht richtig, da man zweimal denselben Wert eingeben kann, ohne dass das Programm meckert.
Wäre froh, wenn sich jemand meinen Code mal ansehen könnte, komme allein nicht weiter bez. sehe den/die Fehler nicht.
#include <iostream> using namespace std; struct Node{ int key; Node *nextleft; Node *nextright; }; Node *firstnode=NULL; bool search(int number, Node *node){ if(node->key==number){ return true; } if(node==NULL){ return false; } if(node->key>number && node->nextleft!=NULL){ return search(number,node->nextleft); } if(node->key<number && node->nextright!=NULL){ return search(number,node->nextright); } return false; } bool insert(int number, Node *node){ if(node==NULL){ node=new Node; node->key=number; node->nextleft=NULL; node->nextright=NULL; return true; } if(node->key>number){ return insert(number,node->nextleft); } if(node->key<number){ return insert(number,node->nextright); } return false; } int main() { int pseudo=0; do{ cout << "tell if you want to insert[i], delete[d] or search[s] a key: " << endl; char cmd; cin >> cmd; if(cmd=='s'){ cout << "enter key to search: " << endl; int key; cin >> key; search(key,firstnode); if(search(key,firstnode)){ cout << "key found" << endl; } else{ cout << "key not found, key doesnt exist" << endl; } } if(cmd=='i'){ cout << "enter key you wanna insert: " << endl; int key; cin >> key; insert(key,firstnode); if(insert(key,firstnode)){ cout << "key inserted" << endl; } else{ cout << "key already exists" << endl; } } }while(pseudo==0); system("PAUSE"); return 0; }
-
Dein Insert verursacht den Fehler. Du übergibst der Methode einen Pointer, bzw eine Kopie eines Pointers. Wenn diese 0 ist, erstellst du ein neues Objekt und übrschreibst den Wert der Kopie des Pointers. Der eigentliche Pointer bleibt dabei unberührt.
Eine Möglichkeit wäre eine Referenz auf einen Pointer zu übergeben.
-
ok, vielen Dank für den Hinweis, habe nun das Funktionsargument von Insert zu einer Referenz auf den Pointer umgeändert:
#include <iostream> using namespace std; struct Node{ int key; Node *nextleft; Node *nextright; }; Node *firstnode=NULL; bool search(int number, Node *node){ if(node->key==number){ return true; } if(node==NULL){ return false; } if(node->key>number && node->nextleft!=NULL){ return search(number,node->nextleft); } if(node->key<number && node->nextright!=NULL){ return search(number,node->nextright); } return false; } bool insert(int number, Node *&node){ if(node==NULL){ node=new Node; node->key=number; node->nextleft=NULL; node->nextright=NULL; return true; } if(node->key>number){ return insert(number,node->nextleft); } if(node->key<number){ return insert(number,node->nextright); } return false; } int main() { int pseudo=0; do{ cout << "tell if you want to insert[i], delete[d] or search[s] a key: " << endl; char cmd; cin >> cmd; if(cmd=='s'){ cout << "enter key to search: " << endl; int key; cin >> key; search(key,firstnode); if(search(key,firstnode)){ cout << "key found" << endl; } else{ cout << "key not found, key doesnt exist" << endl; } } if(cmd=='i'){ cout << "enter key you wanna insert: " << endl; int key; cin >> key; insert(key,firstnode); if(insert(key,firstnode)){ cout << "key inserted" << endl; } else{ cout << "key already exists" << endl; } } }while(pseudo==0); system("PAUSE"); return 0; }nun funktioniert das suchen, sofern ich zuvor einen wert eingefügt habe. wenn ich allerdings den leeren (nicht vorhandenen) baum durchsuchen möchte, also als erstes search auswähle, kommt noch immer ne windows-fehlerbericht-senden meldung... dabei ist der leere baum doch klar als NULL definiert... weshalb funktioniert das nicht?
zudem kommt nach dem einfügen immer die meldung "key already exists", auch wenn der key noch nicht vorhanden ist. der key wird auch tatsächlich eingefügt und lässt sich nachher über search ausfindig machen, aber wieso behauptet das programm "key already exists"?
-
if(node==NULL){ return false; }muss die erste Abfrage in der Suche sein. Ansonsten prüfst du auf den Wert des ersten Knotens wenn dieser nicht existiert.
-
danke, ja ist eigentlich logisch nur sehe ich solche Dinge nicht immer^^
nun an einem problem verzweifle ich noch, und zwar
bool insert(int number, Node *&node){ if(node==NULL){ node=new Node; node->key=number; node->nextleft=NULL; node->nextright=NULL; return true; } if(node->key>number){ return insert(number,node->nextleft); } if(node->key<number){ return insert(number,node->nextright); } return false; }wieso gibt diese funktion immer, auch wenn das eingefügte element noch nicht existiert, false zurück?? komischerweise wird der key ja korrekt eingefügt, es funktioniert alles, doch die funktion gibt false zurück und somit erscheint nach der eingabe auf der konsole "key already exists"
-
Deswegen:
insert(key,firstnode); if(insert(key,firstnode)){. Du führst insert immer zweimal aus. Nimm das erste weg.
-
danke dir, bin echt halb verzweifelt daran obwohl ich eigentlich wusste, dass das zeugs in der if-bedingung auch immer ausgeführt wird...
so jetzt bin ich an der löschfunktion, das wir dein spass
