✔ Sortierfunktion für doppelt verkettet Liste will einfach nicht ....

W

Wallnussfolie

Grünschnabel
Hallo liebe Programmier-Freunde,

ich habe eine doppelt verkettete Liste programmiert. Es funktioniert auch alles wunderbar, nur die Sortierfunktion bereitet mir seit mehreren Stunden Kopfschmerzen und ich weiß einfach nicht mehr weiter, deswegen wäre ich sehr froh, wenn ihr mir helfen könntet.
Die Sortierung an sich funktioniert nicht richtig und manchmal bekomme ich Speicherzugriffsfehler ...

Hier meine Funktion (es handelt sich um ein Wörterbuch, deswgen sort_german() )
-reset_current() setzt LIST.current auf LIST.head
-count ist eine Variable, die die Anzahl der Datensätze speichert

Vielen Dank im Voraus für eure Hilfe !
C++: 
void sort_german(void)
{
 int x,i,j,change_current2;
 item_content *content1;
 item_content *content2;
 item_content *tmp_content;
 item *help;
 item *current2;
 if (LIST.head->next == NULL)               // keine Sortierung notwendig bei nur einem Datensatz
 {
  return;
 }
 reset_current();
for (i=0; i<count; i++)
{
 if(LIST.current->next == NULL)
 {
  break;
 }
 current2=LIST.current->next;
 for (j=0; j<(count-1); j++)  
 {
  if((j != 0) && (change_current2==1) )
  {
  current2=LIST.current->next;
  }
  content1=LIST.current->pdata;
  content2=current2->pdata;
  printf("Vergleiche nun %s und %s\n",content1->Deutsch,content2->Deutsch);
  if (strcmp(content1->Deutsch,content2->Deutsch) > 0)
  {
  printf("Änderung erforderlich");
  tmp_content=content1;
  content1=content2;
  content2=tmp_content;
  LIST.current->pdata=content1;
  LIST.current=current2;
  LIST.current->pdata=content2;
  change_current2=1;
   
  }
  else
  {
  printf("Keine Änderung erforderlich");
  if (current2->next == NULL)
  break;
  current2=current2->next;
  change_current2=0;
  }
 }
 if (LIST.current->next == NULL)
  break;
 LIST.current=LIST.current->next;
}
}
 
ENDLICH, es funktioniert, ich habe es endlich gelöst :D Bevor ihr euch also die Mühe macht, euch in meinen Code einzuarbeiten, hier meine Lösung, vieleicht interessiert es ja jemanden irgendwann. Es geht wahrscheinlich alles viel einfacher und Bubblesort ist wahrscheinlich auch nicht die beste Methode, aber es ist meine eigene Arbeit und es funktioniert :D

C++: 
void sort_german(void)
{
 int x,i,j,change_current2;
 item_content *content1;
 item_content *content2;
 item_content *tmp_content;
 item *help;
 item *current2;
 if (LIST.head->next == NULL)             // keine Sortierung notwendig bei nur einem Datensatz
 {
  return;
 }
 reset_current();
 for (i=0; i<count; i++)               // 1. Schleife: für jeden Datensatz eine eigene Schleife
 {
 if (LIST.current->next == NULL)             // wenn es kein nächstes Element mehr gibt: fertig
 {
  break;
 }
 current2=LIST.current->next;             // current2 ist der Vergleichspartner, vor dem ersten Durchlauf ist er das next von current
 for (j=0; j<(count-1); j++)              // Start 2. Schleife
 {
  if ((j != 0) && (change_current2==1) )         // current 2 nur dann weiterschalten, wenn nicht schon vorher und auch nicht im 1. Durchlauf
  {
  current2=LIST.current->next;
  }
  content1=LIST.current->pdata;             // Inhalt auslesen
  content2=current2->pdata;
  //printf("Vergleiche nun %s und %s\n",content1->Deutsch,content2->Deutsch);
  if (strcasecmp(content1->Deutsch,content2->Deutsch) > 0)     // Vergleich, keine Beachtung von Groß- und Kleinschreibung
  {
  //printf("Änderung erforderlich");
  help=LIST.current;               // Daten der Knoten austauschen und Stand von List.current speichern   
  tmp_content=content1;
  content1=content2;
  content2=tmp_content;
  LIST.current->pdata=content1;
  LIST.current=current2;
  LIST.current->pdata=content2;
  change_current2=1;               // current2 muss nun geändert werden  
  }
  else                   // bei keiner Änderung der Daten:
  {
  //printf("Keine Änderung erforderlich");
  if (current2->next == NULL)
  break;
  current2=current2->next;             // Änderung von current2
  change_current2=0;
  }
  if (LIST.current->next==NULL)             // LIST.current auf alten Stand zurücksetzen, falls es nun das letzte Element sein sollte
  LIST.current=help;
 }
 if (LIST.current->next == NULL)
  break;
 LIST.current=LIST.current->next;           // LIST.current weiterschalten nach jedem Ende der 2. Schleife
}
}
 
Zuletzt bearbeitet:
Hab heute früher schon vergeblich gesucht, wo das Problem ist, und dann aufgegeben :D bzw. wegmüssen

Paar Bemerkungen:

Bubblesort ist nicht das Beste, ja. Viele sinnvollere Algorithmen sind (nur) auf Arrays ausgerichtet statt auf Listen,
aber zB. Mergesort wäre eine mögliche Verbesserung. Siehe auch http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html (inkl. Beispielcode)


Globale Variablen sind schlecht. Eine sinnvolle sort-Funktion funktioniert für mehr Listen als das deutsche Wörterbuch :)

Am Anfang prüfst du, ob nur ein Element da ist, weil dann kein Sort nötig ist. Aber was ist, wenn sogar gar kein Element da ist? Bzw. wirklich möglich ist das in deiner FUnktion nicht, auf LIST wird ohne Pointer etc. zugegriffen also kanns gar nicht NULL sein. Unabhängig vom Sortieren, wie soll die Liste bei 0 Elementen ausschauen?

Die Variablen help und x werden nie verwendet.
 
Zuletzt bearbeitet:
Vielen Dank für deine Bemühungen und deine Bemerkungen!

Also LIST.head ist auch ein Pointer, deswegen könnte ich noch eine Prüfung einbauen, ob LIST.head == NULL ist. Wenn das der Fall ist, ist die List leer, also es sind keine Elemente vorhanden. LIST.head zeigt bzw. ist dann einfach ein Null-Pointer. Die Variable help verwende ich 1x, um den Zustand von LIST.current zu speichern, aber die Variable x verwende ich nicht, das stimmt :D
 
@sheel : Was heißt nur auf Arrays ausgerichtet? Ist das nicht egal? Der Algorithmus bleibt ja der gleiche, die Implementierung ist mit Listen nur etwas aufwändiger. Deshalb wird bei den Erklärungen häufig von einem Array ausgegangen. Aber prinzipiell müsste jeder Sortieralgorithmus auch auf Listen anwendbar sein, oder irre ich da?
 
A ja... muss ich samt meinem Editor übersehen haben :D

@alxy Ich sag ja nicht, dass irgendein Algo mit einer Liste nicht funktionieren würde, aber dass man bei der Liste nicht in konstanter Zeit zu einem beliebigen Index springen kann macht einige Algos oder zumindest Implementierungsarten ineffizienter als bei Arrays. (Und umgekehrt werden einige Algos besser, wenn sie ohne viel Verschieben an beliebigen Stellen Werte einfügen/löschen können)
 
Zuletzt bearbeitet:
und @Wallnussfolie : Du kannst deinen Code lesbarer gestalten, indem du ihn auf mehrere Funktionen aufteilst. Die Listenimplementierung und die Sortieralgo-Implementierung kannst du getrennt behandeln. Auch wäre eine eigene Funktion zum Austauschen sicher sinnvoll und würde die Lesbarkeit enorm erhöhen.
 
Danke Alxy, ich werd mal schauen was sich machen lässt :)

Ich hätte noch eine andere Frage: Ich möchte mein Programm nun in mehrere Module aufteilen. Meine Bibliothek mit den Funktionsprototypen, typedefs für die Structs usw. ist auch schon fertig und funktioniert, nur die Moduldatei für die Funktionen (hat den Namen func.c) funktioniert nicht. Ich möchte in diese Datei alle Funktionsdefinitionen unterbringen. Problem ist, dass die Funktionen auf die globalen Variablen LIST.head, LIST.current und LIST.tail zurückgreifen müssen. LIST ist dabei eine Instanz von einem Strukturtyp. Wo muss ich diese 3 Variablen deklarieren bzw, initialisieren, denn egal wo ich sie reinschreibe, jedes mal kennen meine Funktionen in func.c die Variablen nicht mehr ...
 
Du solltest wirklich Parameter statt globalen Variablen verwenden... wenns unbedingt sein muss kannst du die Variablen in der c-Datei wieder deklarieren, aber diesmal mit "extern" dabei.
 
Danke sheel, ich weiß das die Methode nicht gerade schön ist, aber es ist im Moment einfacher zu programmieren und mein Projekt muss am Samstag um 23:59 spätestens fertig sein. Das Programm beherrscht nun alle Funktionen, nun fehlt nur noch das fertige GUI, wovon ich auch schon die Hälfte fertig habe. Kennst du (oder jemand anders) zufällig ein gutes (deutsches) Tutorial für die Verwendung treeview von gtk+ ?

PS: Ist es möglich meinen Beitrag mit der finalen Sortier-Funktion nochmal zu bearbeiten ? Habe da noch einen Fehler entdeckt, den ich gerne korrigieren würde.
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück