Verkettet Liste - Elemente sortieren

Sund0se

Hi Leute

Ich hätt eine Frage bzgl. Verkettete Listen.
Ich habe eine verwaltung von DVD´s gemacht, das heißt: Eingabe, Ausgabe, suchen, gesuchtes Element löschen, gesuchtes Element aendern, gesuchte Element ausgeben...
Alles ja ganz einfach, doch wie sortiere ich jetzt zB. den Namen der ganzen DVD´s alphabetisch, um sie nachher alphabetisch ausgeben zu können?
Wie schon gesagt mache ich alles mit einfach Verketteten Listen (doppelt habe ich mir noch nicht angesehen).
Es muss jetzt kein spezifischer C-Code sein, mir genügt auch wenn ihr mir eine Idee vorschlagen würdet.

lg Sund0se

Für listen ist Mergesort ganz nett. Wikipedia ist dein weiterer Freund.

Sund0se

okay, aber ich verstehe das prinzip noch nicht, habe bisher nur mit arrays zB. zahlen sortiert!

wie stellt man das an wennman eine verkettete liste hat?

lg

MergeSort(Liste l)
  if (l besteht mehr als aus einem Element) //1
    l1 = erste hälfte von l                 //2
    l2 = zweite hälfte von l                //3
    MergeSort(l1)                           //4
    MergeSort(l2)                           //5
    l = Merge(l1, l2)                       //6

einfach checken ob l->next == NULL

tricksen. eigentlich brauchst du keine hälften sondern nur 2 gleich große teillisten. wie erstellen? durch die große liste steppen und abwechselnd an l1 und l2 ein element dranklatschen

klar

ist jetzt auch nicht mehr schwer

nwp2

Beim Vergleichen der Listenelemente in merge(l1, l2) musst du nur darauf achten dass du auch liste->wert miteinander vergleichst und nicht etwa liste. Du willst schließlich die Liste nach ihren werten sortieren und nicht nach ihrer Speicheradresse.

Edit: Du solltest mit Funktionen wie add(wert, liste) und wert pop(liste) anfangen, dann geht das alles viel einfacher.

Sund0se

Okay, danke, das Prinzip ist mir klar!

Doch ich verstehe noch nicht ganz wie man die Liste in zwei Teillisten teilt...

Habt ihr dazu vilt. ein kleines Codebeispiel?

mfg

nwp2

while (liste nicht leer){ //teilt liste in 2 listen liste1 und liste2 auf
    addelement(liste1, popelement(liste))
    addelement(liste2, popelement(liste))
}

Sund0se schrieb:

Es muss jetzt kein spezifischer C-Code sein, mir genügt auch wenn ihr mir eine Idee vorschlagen würdet.

lg Sund0se

Probier es doch erst mit dem Verfahren Sortieren durch Einfügen. Mergesort baut darauf auf und ohne Arrays ist es um einiges schwieriger.

Sund0se

hey leute

naja nun hab ichs mir ganz einfach gemacht, warscheinlich ziemlich schlecht, aber es geht...

ich habe von jedem element in der liste den anfangsbuchstaben genommen und in ein array hintereinander gespeichert.
dann habe ich das array mit bubble sort sortiert und dann habe ich jedes element im array wieder mit jedem anfangsbuchstaben verglichen und ausgegeben wenn gleich...

lg

http://www.c-plusplus.net/forum/viewtopic-var-t-is-246539-and-highlight-is-merge+sort.html

Sund0se

hi leute

ich habs jetzt mal mit bubble sort versucht, es endet aber mit programm musste geschlossen werden und ich komme auf kein ergebnis!

hier der code:

void bubbleSort( void )
{
   struct DVD* zeiger = anfang, *hilf, *hilf2;
   char temp[MAX];
   int i = 0, j = 0;

   while ( zeiger->next != NULL ) {
	   i++;
	   zeiger = zeiger->next;
   }
   hilf = ende;
   hilf2 = anfang;
   for ( i = i - 1; i >= 0; hilf = hilf->prev )
   {
     for ( j = 1; j <= i; hilf2 = hilf2->next )
     {
       if (hilf2->prev->titel > hilf->titel)
       {
         strcpy(temp,hilf2->prev->titel);
         strcpy(hilf2->prev->titel,hilf->titel);
         strcpy(hilf->titel,temp);
       }
	   j++;
	 }
	 i--;
   }
   output();
}

bitte um hilfe