Sortiertes Einfügen in eine bereits sortierte doppelt verkettete Liste

EJason

Hallo. Ich habe ein Problem bei meinem Code. Bei Ausführung des Codes (wenn i eingegeben wird), wird letztlich nichts ausgegeben. Es soll aber eine Liste ausgegeben werden, in die ein neues Element sortiert eingefügt wird. Die Liste wurde vorher schon (durch Eingabe von s) sortiert. Kann mir jemand sagen, woran das liegt und mir gegebenfalls helfen, das Problem zu lösen? Danke schonmal im Voraus! (Ich habe nachfolgend nur den problematischen Code eingefügt, da der Rest schon funktioniert).

#include <iostream>
#include <stdlib.h>

using namespace std;

struct Node {
   int item;
   struct Node* next;
   struct Node* prev;
};
// Funktion zur Ausgabe der Liste
void displayList(struct Node* node) {
   struct Node* tail;

   while (node != NULL) {
      cout << node->item <<" ";
      tail = node;
      node = node->next;
   }

}

void InsertSorted(Node** head, int new_data) {

	Node* new_node = new Node;

	Node* tail = NULL;

	Node *temp1, *temp2;

	(*head)->item = new_data;

	temp1 = (*head);
	bool ist_groesser = true;
	while(ist_groesser) {
		if(new_node->item > temp1->item) {
			if((*head) != tail) {
				temp1 = temp1->next;
			} else {
				temp1 = NULL;
				ist_groesser = false;
			}
		}
		if(temp1 == (*head)) {
			new_node->next = (*head);
			new_node->prev =NULL;
			(*head)->prev = new_node;
			(*head) = new_node;
		}else if (temp1 == NULL) {
			new_node->prev = tail;
			new_node->next = NULL;
			tail->next = new_node;
			tail = new_node;
		} else {
			new_node->next = temp1;
			temp2 = temp1;
			temp1 = temp1->prev;
			temp2->prev = new_node;
			new_node->prev = temp1;
			temp1->next = new_node;
		}
	}
	(*head) = new_node;
	displayList(*head);

}
int main() {
    struct Node* head = NULL;


  char choice;
  int data;
  int b=1;
  while(b==1){

  	cout<<endl<<"a"<<endl<<"e"<<endl<<"s"<<endl<<"i"<<endl<<"r"<<endl<<"q"<<endl<<"Bitte Auswahl eingeben"<<endl;
  	cin>>choice;
  	switch(choice){
  			case 'a':
  				 data = rand() % 1001;
  				InsertAtBegin(&head,data);
  			break;
  			case 'e':
  				 data = rand() % 1001;
  				InsertAtEnd(&head,data);
  			break;
  			case 's':
  				Sort(&head);
  			break;
  			case 'i':
  				 data = rand() % 1001;
  				//insertSorted(&head,data);
  			break;
  			case 'q':
  				b=2;
  			break;
  			case 'r':
  				PrintList_Reverse(&head);
  			break;

	  }


  }
}

Jockelx

@EJason sagte in Sortiertes Einfügen in eine bereits sortierte doppelt verkettete Liste:

Bei Ausführung des Codes (wenn i eingegeben wird), wird letztlich nichts ausgegeben.

Was nicht überrascht bei

case 'i':
  				 data = rand() % 1001;
  				//insertSorted(&head,data);
  			break;

Th69

case 'i':
	 data = rand() % 1001;
	//insertSorted(&head,data);
break;

Du solltest schon den Code wieder einkommentieren und dann debugge ihn, um zu sehen, ob die Liste richtig angelegt wird.

Belli

Zeile 63 kommt mir auch seltsam vor, der Listenkopf wird ohne weitere Bedingung auf den neuen Knoten gesetzt?
Macht das nicht nur Sinn, wenn immer am Listenanfang eingefügt wird?

EJason

@Jockelx ach ja. Bin ich bescheuert Aber leider funktioniert es trotzdem nicht. Es wird einfach gar nichts gemacht. Offensichtlich kommt es nicht mal zum Aufruf der Funktion displayList ...

wob

Ich habe noch eine ganz allgemeine Anmerkung:
Welche Sprache willst du lernen, C oder C++?

Das Problem, dass Anfänger hier mit einem Mischmasch vorbeikommen, ist hier sehr häufig anzutreffen (das ist nicht dein Fehler, @EJason, sondern vermutlich der deines Lehrers/Profs). Einerseits verwendest du cin/cout, die nur in C++ funktionieren. Andererseits sieht der Rest eher nach C aus.

struct Node {
   int item;
   struct Node* next;
   struct Node* prev;
};

In C++ gibt es die Notwendigkeit nicht, das struct zu wiederholen. Es kann einfach heißen:

struct Node {
   int item;
   Node* next;
   Node* prev;
};

Genauso hier:
void displayList(struct Node* node) { ... }
dies würde zu:
void displayList(Node* node) { ... }

Außerdem nennt sich NULL in C++ nullptr. Wichtig: der Typ ist unterschiedlich, d.h. während du int i = NULL schreiben kannst (NULL ist einfach nur eine fancy Schreibweise für die Zahl 0 + ein bisschen Spezialbehandlung vom Compiler, um Warnungen anzuzeigen), während int i = nullptr nicht kompiliert (ich habe hier int und nicht int * gewählt). Daher sollte man in C++ immer nullptr bevorzugen (bei Vergleichen mit nullptr/NULL lässt man das nullptr/NULL aber häufig eh weg, also statt if (pointer != nullptr) schreibst du if (pointer) - ist das gleiche).

Das sind erstmal die offensichtlichen Dinge.

Außerdem würde man in C++ den "int"-Datentyp für "item" als Parameter der Klasse übergeben, was sich dann template nennt - somit könntest du deine Node dann für beliebige Datentypen verwenden.

Dann können structs in C++ auch Funktionen enthalten. Das heißt, du könntest eine Klasse "struct LinkedList" erstellen und dieser dann Funktionen zum Einfügen geben (so wie in der Standardbibliothek std::list das macht, zum Beispiel).

Wenn du viel mit * oder gar mit ** von Hand rumhantierst, ist das oft ein Zeichen für schlechtes C++ (sofern es denn C++ sein soll), wärend das in C schon häufiger vorkommen kann.

Eine andere Sache ist noch die Ressourcenverwaltung. Hierfür nutzt man in C++ ein Konzept namens RAII - und damit man mit new/delete keine Fehler macht, lagert man die Ressourcenverwaltung anderswohin aus, wo sich jemand ausschließlich mit Ressourcenverwaltung beschäftigt. Ich sehe in deinem Code ein "new", aber kein "delete".

(Ende Rant)

PS: Es ist übrigens völlig OK, solche Dinge mit C zu machen, weil du dich dann vielleicht besser/stärker auf die eigentliche Datenstruktur konzentrieren kannst - Templates usw. lenken vermutlich am Anfang nur ab. Nur denke nicht, dass dein Code auch nur annähernd idiomatisches C++ ist.