verkettete Liste

Hi,

Kann mir vielleicht jemand sagen, ob ich bei einer verketteten Liste auch den qsort verwenden kann?

Bei einem Array geht das ja.

Danke, Gruß Sabrina

tobidope

Nein, der allgemeine qsort aus der stdlib.h arbeitet nur auf Feldern und gute Sortiermethoden für verkettete Listen sind mir im Moment nicht bekannt, aber Google hilft bestimmt.

Gruß Tobias

Daniel E.

Wenn Du mit qsort die C-Funktion meinst, dann geht das nicht.

Quicksort im allgemeinen ist aber durchaus auf Listen anwendbar.

tobidope

Sicher das man dazu nicht doppelt verkettete Listen benötigt?

Daniel E.

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.

tobidope

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?

tobidope

Wie sortierst du denn Karten die du auf der Hand hast? Überleg dir doch was!

Geo

Versuch doch Bubble-Sort.
Langsam aber kommt auch zum Ziel.

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