verkettete Liste

AJ

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.

mady

http://www.ts-networld.de/?page=prog/article/sort-linked-list

TheTester

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]    |___ H

Der 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

maconey

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 1

gruss,

matthias

rgHorus

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;
}

rgHorus

Kann mir keiner helfen? Ich weiß, es ist nicht so das Problem aber ich hänge echt fest!

c.rackwitz

vertausche doch einfach zeiger->name und zeiger1->name, wenn in der struct sonst nichts anderes steht

rgHorus

Der struct sieht folgendermaßen aus:

struct ware
{
char name[20];
char herstller[20];
float preis;
struct ware *next;
}

c.rackwitz

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.

PAD

Mach doch den klassischen ringtausch

a,b vertauchen:
a -> tmp
b -> a
tmp->b

d.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;
  }

ZuK

@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

rgHorus

Ja, und genau das ist mein Problem!!!

PAD

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.

ZuK

Und dann wäre da noch das problem das der next-pointer beim element vor den zu tauschenden elementen neu gesetzt werden muss. Dann sollte es aber funktionieren.
Kurt

rgHorus

Kannst du mir da bitte mal schreiben, wie das da aussehen müsste? Danke.