verkettete Liste

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.