[C/C++] Einfach verkettete Liste mittels Bubblesort sortieren!

jiggolo · 27. Mai 2011

Einfach verkettete Liste mittels Bubblesort sortieren!

Hey Leute,

ich hab die Aufgabe eine Liste mit dem Bubblesort Algorithmus zu sortieren. Leider funktioniert mein Programm nicht ganz. Er lässt zum Beispiel einige Elemente Komplett weg und sortiert sie erst gar nicht und andere Elemente sortiert er ganz normal. Ich kann denn Fehler einfach nicht finden.
Ich hoff einer von euch kann mir helfen.

Mein Quellcode für die Bubblesort - Funktion lautet:

Code:

#include <cstdio>
#include <cstdlib>
#include "bubblesort.h"


int bubblesort(LinkedList *l) {
 Node *a; 
 Node *b; 
 Node *c; 
 Node *e=l->head; 
 Node *tmp; 
 int i=0;

 if(!l) 
 return ERR_LIST_INVALID; 

 while(e->next!=NULL) { 
 e=e->next; 
 i++; 
 }

 while(i != 0) { 
 c = a = l->head;
 b = a->next;
 
 while(a->next != NULL) { 
 if(a->data > b->data) { 
 if(l->head == a) { 
 tmp = b -> next; 
 b->next = a; 
 a->next = tmp; 
 l->head = b; 
 } else { 
 tmp = b->next; 
 b->next = a; 
 a->next = tmp;
 }
 } else { 
 a = a->next; 
 }

 b = a->next; 
 }

 i--;
 }
 
 return LIST_SUCCESS;
}

Vielen Dank schon mal im Voraus und BW ist für jede Hilfe drin

MFG

jiggolo

Anzeige

terraNova · 27. Mai 2011

AW: Einfach verkettete Liste mittels Bubblesort sortieren!

Hey.

Beim nächsten mal bitte den richtigen Präfix wählen, den Code formatieren und alle nötigen
Quelldateien angeben (bubblesort.h fehlt komplett)!

Was mir direkt auffällt ist, dass Du ´l´ schon vor der Prüfung (l == nullptr) verwendest. Das gäbe 'nen Segfault. Auch die Namen könnte man etwas lesbarer formulieren.

Da ich jetzt absolut keine Ahnung hab wie deine Liste aussieht, hier mal ein Beispiel:

Code:

#include <iostream>
#include <cstdlib>

using namespace std;

typedef struct bla {
 struct bla* head;
 struct bla* next;
 unsigned data;

 bla() {
 head = next = nullptr;
 data = 0;
 }
} LinkedList, Node;


int bubblesort(LinkedList *root) {
 Node *left, *right, *left_tmp, *tmp;
 unsigned i=1;

 if(root == nullptr) {
 return 1;
 }

 tmp = root->head;
 while(tmp->next != nullptr) {
 tmp = tmp->next;
 i++;
 }

 while(i > 0) {
 left = root->head;
 right = left->next;

 while(left->next != nullptr) {
 if(left->data > right->data) {
 if(left == root->head) {
 /* root
 left -> r1 -> r2

 root
 r1 -> left -> r2
 */
 root->head = right;
 tmp = right->next;
 right->next = left;
 left->next = tmp;
 } else {
 tmp = root->head;

 while(tmp->next != left) {
 tmp = tmp->next;
 }

 left_tmp = tmp;
 tmp = right->next;

 /* left_tmp -> left -> r1 -> r2 

 left_tmp -> r1 -> left -> r2
 */
 left_tmp->next = right;
 right->next = left;
 left->next = tmp;
 }
 } else {
 left = left->next;
 }
 
 right = right->next;
 }

 i--;
 }

 return 0;
}

int main( void ) {
 LinkedList r, t[5], *tmp;

 r.data = 5;
 r.head = &r;
 r.next = &t[0];

 t[0].data = 8;
 t[0].next = &t[1];

 t[1].data = 4;
 t[1].next = &t[2];

 t[2].data = 0;
 t[2].next = &t[3];

 t[3].data = 10;
 t[3].next = &t[4];

 t[4].data = 9;

 bubblesort(&r);

 tmp = r.head;
 while(tmp != nullptr) {
 cout << tmp->data << endl;
 tmp = tmp->next;
 }

 return 0;
}

jiggolo · 27. Mai 2011

AW: Einfach verkettete Liste mittels Bubblesort sortieren!

Hey,

vielen dank für die Antwort. Ich hab den Code mal bei mir implementiert und jetzt zeigt er zwar alle Elemente an, aber er Sortiert sie nicht alle.
Natürlich haste recht und ich hätte alle nötigen Dateien einreichen sollen, deshalb hier sind nochmal die anderen Dateien.

bubblesort.h :

Code:


#ifndef BUBBLESORT_H_
#define BUBBLESORT_H_

#define LIST_SUCCESS 0
#define ERR_LIST_INVALID 1
#define ERR_NODE_INVALID 2
# include "linkedlist.h"

int bubblesort(LinkedList *l);

#endif

Hier ist auch meine main_buublesort.cpp, vielleicht ist ja dort ein Fehler (ich glaube aber eher nicht) :

Code:

#include <cstdio>
#include "bubblesort.h"
#include "linkedlist.h"

int main() {

 LinkedList *l = createEmptyList();
 Node *n0 = createNode(4);
 Node *n1 = createNode(8);
 Node *n2 = createNode(-8);
 Node *n3 = createNode(10);
 Node *n4 = createNode(76);
 Node *n5 = createNode(2);
 Node *n6 = createNode(0);
 Node *n7 = createNode(9);
 Node *n8 = createNode(32);
 Node *n9 = createNode(500);

 appendNode(l, n0);
 appendNode(l, n1);
 appendNode(l, n2);
 appendNode(l, n3);
 appendNode(l, n4);
 appendNode(l, n5);
 appendNode(l, n6);
 appendNode(l, n7);
 appendNode(l, n8);
 appendNode(l, n9);

 bubblesort(l);
 printList(l);

 deleteList(l);
 return 0;
}

Ich hoffe du kannst mir helfen.

MFG

jiggolo

PS: Die linkedlist.h bzw. linkedlist.cpp beinhaltet nur die Funktionen für "appendNode", welche mit Sicherheit fehlerfrei funktioniert, aber falls diese Dateien auch gewünscht sind, kann ich sie ja nochmal hochladen.

Nützliche Suchen

[C/C++] Einfach verkettete Liste mittels Bubblesort sortieren!

Videos zum Themenbereich