verkettete Liste
-
Sicher das man dazu nicht doppelt verkettete Listen benötigt?
-
Zwanghaft benötigen nicht. Man muss aber trotzdem eine 'gibt mir das vorhergehende Element'-Funktionalität einbauen. Und das ist bei binfach verkettete Listen ähnlich nützlich wie Eisfischen im Mittelmeer, richtig.
-
Also sagen wir es mal so. Eine einfach verkettete Liste und eine Form des Quicksort passen nur sehr, sehr bedingt zusammen.
-
Ok, das hab ich jetzt kapiert, dass ich keinen qsort verwenden kann.
Aber wie bekomme ich meine Liste jetzt trotzdem sortiert?
-
Wie sortierst du denn Karten die du auf der Hand hast? Überleg dir doch was!
-
Versuch doch Bubble-Sort.
Langsam aber kommt auch zum Ziel.
-
Dann doch lieber den Insertsort (Kartenbeispiel).
Aber ein Quicksort manuell programmiert sollte doch auch gehen. Man muss, wie oben schon erwähnt nur die Funktionalität "Element vorher - Element nachher" eingebaut werden. Also anstatt das Element selbst zu tauschen, werden nur die Zeiger auf die Elemente davor und danach getauscht.
-
-
mergesort mag auch listen
-
Wie wärs wenn man in die verkettete Liste einfach sortiert einfügt
Beispiel:
[Neue Eingabe] H [Liste] A -> C -> D -> | -> P -> V -> Z | [Einfügung] |___ HDer Algo muss dann in etwa so aussehen:
- Mit dem ersten Element prüfen. Falls kleiner: Eingabe vor erstem Element einfügen. Ende-
- Mit dem letzten Element prüfen. Falls größer: letztes Element an die Liste anhängen. Ende-
- Liste solange durchgehen bis Element gefunden wurde, das größer ist als Eingabe. Vor diesem Element einfügen. Ende-
Noch eine Möglichkeit wäre es einen Array mit Pointern auf Listenelementen paralell zur Liste zu verwalten. Und diesen dan mit Quicksort (natürlich mit den Dereferenzierten Daten) zu sortieren und dieses Array weiterhin zu benutzen. Aber das macht ja dann eigentlich die verkettete Liste überflüssig
Dave
-
warum nicht bubblesort?
ist vielleicht nicht so schnell, aber von der implementierung her sicher einfacher.das ganze mal in worten:
1: aktuelles element=anfang der liste
wenn aktuelles element grösser als nachfolger, verschiebe aktuelles element hinter den nachfolger
aktuelles element = nachfolgendes element
wenn kein element mehr getauscht worden ist gehe zu 1gruss,
matthias
-
Ich benötige bubble sort als Sortiermethode, ich hab jedoch probleme, die Listenelemente zu vertauschen.
struct ware * bubblesort_name(struct ware *anfang) { struct ware *zeiger, *zeiger1, *tmp; int abbruch; abbruch=1; while(abbruch != 0) { abbruch=0; zeiger=anfang; zeiger1=anfang->next; while(zeiger1 != NULL) { if((strcmp(zeiger->name,zeiger1->name))<0) { //hier die beiden Listenelemente vertauschen - aber wie? abbruch=1; } zeiger=zeiger->next; zeiger1=zeiger1->next; } } return anfang; }
-
Kann mir keiner helfen? Ich weiß, es ist nicht so das Problem aber ich hänge echt fest!
-
vertausche doch einfach zeiger->name und zeiger1->name, wenn in der struct sonst nichts anderes steht
-
Der struct sieht folgendermaßen aus:
struct ware { char name[20]; char herstller[20]; float preis; struct ware *next; }
-
na dann tauschste halt alle members der struct. das wäre aber ziemlicher unsinn, obwohl es geht.
besser ist, wenn du in der liste die pointer austauschst.
-
Mach doch den klassischen ringtausch
a,b vertauchen:
a -> tmp
b -> a
tmp->bd.h
if((strcmp(zeiger->name,zeiger1->name))<0) { // d.h.zeiger->name ist < zeiger1->name somit tauschen tmp=zeiger1->next; zeiger1->next=zeiger->next; zeiger->next=tmp; //hier die beiden Listenelemente vertauschen - aber wie? abbruch=1; }
-
@PAD: das genügt bei einer verketteten liste nicht.
Nehmen wir einmal an wir vertauschen das 1. mit dem 2. element.
nach dem tausch zeigt anfang nicht mehr auf das erste element der liste.
Kurt
-
Ja, und genau das ist mein Problem!!!
-
Mach die doch einen zusätzlichen Pointer der auf den Anfang der Liste zeigt. Wenn sich jetzt das erste uns das zweite Element
vertauschen. Merke dir den neuen Anfang in diesem BasisPointer.