Bubblesort bei einfach verlinkter Liste in C

[DrOhm]

Hallo!

Könnt mir jemand dabei helfen, wie ich bei einer einfach verlinkten Liste die Listeneinträge nach deren id (unsigned int) in aufsteigender Reihenfolge sortieren kann.

Hab mich mal mit dem sogenannten BubbleSort beschäftigt, aber mein Programm klappt überhaupt nicht.

Hier wichtige Ausschnitte, und zwar die Structs

typedef struct _Header_
{
  unsigned int id_;
  double latitude_;
  unsigned int content_length_;
}Header;

typedef struct _Content_
{
  char *name_;
}Content;

typedef struct _Data_
{
  Header header_;
  Content content_;  
}Data;

typedef struct _List_
{
  struct _List_ *next_;
  Data data_;
}List;

und die Funktion selbst

List *bubbleSort(List *list)
{  

 List* list1;
 List* list2;
 List* temp;

 for(list1 = list; list1->next_ != NULL; list1 = list1->next_) 
 {
   for(list2 = list1->next_; list2 != NULL; list2 = list2->next_) 
   {
     if(list2->data_.header_.id_ > list1->data_.header_.id_) 
     {
         temp = list2; 
         list2 = list1;
         list1 = temp;
     }
   }
 }
 return list;
}

Bitte um Hilfe, ich verzweifel da schon richtig

[SeppJ]

DrOhm schrieb:

Hab mich mal mit dem sogenannten BubbleSort beschäftigt,

Ist das für Lernzwecke? Bubblesort ist denkbar schlecht. Es ist sogar absichtlich schlechter als alles was ein Kindergartenkind bei klarem Verstand sich beim ersten Versuch ausdenken würde. Es ist ein Verfahren aus dem Informatikunterricht, bei dem es darum geht, zu zeigen, wie man es besser machen kann.

aber mein Programm klappt überhaupt nicht.

Ist ja toll. Und meinst du, diese Fehlerbeschreibung nützt uns, wenn wir dir helfen möchten?

[Listen]

Ist list ein Pointer auf das erste Element?

[DrOhm]

Na klar ist das aus dem Informatikunterricht, ich lese bei meinem Programm aus einer Binärdatei Daten für xml Dateien, die alle nach einer ID, die sich im Header der eingelesenen Datei befindet, geordnet werden sollen. Anschließend muss ich das ganze in eine html-Datei speichern. Ich habe schon alles geschafft, nur das Sortieren klappt leider nicht.
Ich brauch keinen effizienten Algorithmus, nur einer, der überhaupt geht.
Ich hab das Programm nochmals erweitert und zwar um error, mit welchem ich überprüfe, ob nicht 2 gleiche id's existieren.

Es ist aber leider so, dass ich die genau die gleiche Liste retourniert bekomme, die ich hineingebe.

List *bubbleSort(List *list, int *error)
{  
 List* list1;
 List* list2;
 List* temp;

 for(list1 = list; list1->next_ != NULL; list1 = list1->next_) 
 {
   for(list2 = list1->next_; list2 != NULL; list2 = list2->next_) 
   {
     if(list2->data_.header_.identifier_ > list1->data_.header_.identifier_) 
     {
       temp = list2; 
       list2 = list1;
       list1 = temp;
     }
     if(list2->data_.header_.identifier_ > list1->data_.header_.identifier_)
     {
       *error = -6;
       return list;
     }
   }
 }
 return list;
}

Ist list ein Pointer auf das erste Element?

Ja ist es. Die Daten habe ich da schon drinnen, halt nur unsortiert.

[ghfgh]

Du musst die Operationen auch auf der Liste durchführen, die später zurückgegeben wird. Außerdem ist Bubblesort nicht zwangsläufig beim ersten Durchlauf fertig. Du musst unter Umständen den Algorithmus so oft wiederholen bis nichts mehr getauscht werden konnte.

Mal ein Beispiel.

#include <stdlib.h>
#include <stdio.h>

#define MAX 100

int main()
{
	int list[MAX];
	int i, done;

	for (i = 0; i < MAX; ++i)
	{
		list[i] = rand();
	}

	do
	{
		done = 1;

		for (i = 0; i < MAX - 1; ++i)
		{
			if (list[i] > list[i + 1])
			{
				int tmp = list[i];
				list[i] = list[i + 1];
				list[i + 1] = tmp;

				done = 0;
			}
		}
	} while (!done);

	for (i = 0; i < MAX; ++i)
	{
		printf("%d\n", list[i]);
	}
}

Dieses Prinzip musst du nun noch auf deine Liste umsetzen.

Aus eigenem Interesse: Wo gibt es die Binärdatei die du zum Testen verwendest? Oder muss man sich diese selber erzeugen?

[DrOhm]

Danke, ich werd das mal versuchen!

Diese Binärdatei haben wir selbst erzeugen müssen, und diese lesen wir dann mit Kommandozeilenparametern ein.

[Binggi]

Wieso sortierst du eigendlich nicht die Einträge wenn du die Liste erzeugst?
D.H Bei jedem neuen Element schauen wo du es einfügen musst.
Dann sparst du dir auch die Mühe die Liste noch zu sortieren...

[DrOhm]

Ich weiß einfach nicht weiter, ich bekomme immer einen Segmentation Fault, sowie ich das jetzt mache.

List *bubbleSort(List *list, int *error_code, int *number_of_entries)
{  
  List* list1 = list;
  List* list2 = list1->next_;
  List* temp;
  int entries = *number_of_entries;

  int i, done;

  do
  {
    done = 1;
    for (i = 0; i <= entries; i++)
    {
      if(list1 > list2)
      {
        temp = list1;
        list1 = list2;
        list2 = temp;
        done = 0;
      }

      if(list1 == list2)
      {
        *error_code = BINARY_FILE_CORRUPT_ERROR;
      }
    }
  }while(!done);
  return list1;
}

Ich weiß eben einfach nicht, wie man das auf eine Liste ummünzt.

Binggi schrieb:

Wieso sortierst du eigendlich nicht die Einträge wenn du die Liste erzeugst?
D.H Bei jedem neuen Element schauen wo du es einfügen musst.
Dann sparst du dir auch die Mühe die Liste noch zu sortieren...

Ich kann mir nicht richtig vorstellen, wie mir das das Leben leichter malen soll und außerdem habe ich jetzt alles schon anders implementiert und da stecken mehr als ein paar Stunden Arbeit dahinter.
Ich glaube zum jetzigen Zeitpunkt bleib ich doch wohl lieber bei der Lösung durch Sortierung danach.

[SeppJ]

Darf ich für effizientes Sortieren vorschlagen, den Listeninhalt in ein Array zu kopieren, dann quicksort aus der Standardbibliothek drauf loszulassen und dann das Ergebnis wieder in eine Liste zu packen? Oder lass die Liste ganz weg und nimm gleich ein Array oder eine andere geeignete Datenstruktur. Die Liste ist fast nie die Antwort auf die Frage nach der besten Datenstruktur.

Dann solltest du auch viele deiner Speicherzugriffsfehler vermeiden können, da andere Datenstrukturen meistens sehr viel unkomplizierter sind.

[SeppJ]

DrOhm schrieb:

Ich weiß einfach nicht weiter, ich bekomme immer einen Segmentation Fault, sowie ich das jetzt mache.

List *bubbleSort(List *list, int *error_code, int *number_of_entries)
{  
  List* list1 = list;
  List* list2 = list1->next_;
  List* temp;
  int entries = *number_of_entries;
  
  int i, done;
 
  do
  {
    done = 1;
    for (i = 0; i <= entries; i++)
    {
      if(list1 > list2)
      {
        temp = list1;
        list1 = list2;
        list2 = temp;
        done = 0;
      }
      
      if(list1 == list2)
      {
        *error_code = BINARY_FILE_CORRUPT_ERROR;
      }
    }
  }while(!done);
  return list1;
}

Ich weiß eben einfach nicht, wie man das auf eine Liste ummünzt.

Das solltest du gar nicht auf deine Liste ummünzen, dieser Code ist Mist.

[DrOhm]

SeppJ schrieb:

Darf ich für effizientes Sortieren vorschlagen, den Listeninhalt in ein Array zu kopieren, dann quicksort aus der Standardbibliothek drauf loszulassen und dann das Ergebnis wieder in eine Liste zu packen? Oder lass die Liste ganz weg und nimm gleich ein Array oder eine andere geeignete Datenstruktur. Die Liste ist fast nie die Antwort auf die Frage nach der besten Datenstruktur.

Dann solltest du auch viele deiner Speicherzugriffsfehler vermeiden können, da andere Datenstrukturen meistens sehr viel unkomplizierter sind.

Das Problem ist, ich MUSS das ganze mit einer einfach verketteten Liste machen

[Bashar]

Ein paar Tips.

Implementiere Bubble-Sort (oder welchen Algorithmus auch immer) mit Arrays, falls dir die grundsätzliche Funktionsweise nicht klar ist.

Zeichne dir die komplizierteren Aktionen (z.B. Vertauschen) bei deiner Liste mit Papier und Bleistift auf.

Überlege dir die Reihenfolge, in der die Zeiger umgehängt werden müssen, damit du keine verlierst.

Berücksichtige alle Spezialfälle: Anfang der Liste, Ende der Liste, Liste ist leer, Liste hat nur 1 Element, evtl noch mehr.

[Wutz]

DrOhm schrieb:

Das Problem ist, ich MUSS das ganze mit einer einfach verketteten Liste machen

Das Problem ist dein Lehrer.

[DrOhm]

Bashar schrieb:

Ein paar Tips.
Implementiere Bubble-Sort (oder welchen Algorithmus auch immer) mit Arrays, falls dir die grundsätzliche Funktionsweise nicht klar ist.
Zeichne dir die komplizierteren Aktionen (z.B. Vertauschen) bei deiner Liste mit Papier und Bleistift auf.
Überlege dir die Reihenfolge, in der die Zeiger umgehängt werden müssen, damit du keine verlierst.

Ja mit Arrays sehe ich kein Problem, das schaffe ich ja ohne was.
Ja mit diesen Pointern in der Liste, da bin ich überfordert, aber ich kann's ja mal versuchen.

Bashar schrieb:

Berücksichtige alle Spezialfälle: Anfang der Liste, Ende der Liste, Liste ist leer, Liste hat nur 1 Element, evtl noch mehr.

Spezialfälle sind alle schon vorher durch diverse Fehlerüberprüfungen beim Einlesen abgedeckt, beim Sortieren kann maximal der Fehler auftreten, dass ich 2 mal die gleiche ID bekommen.

Wutz schrieb:

DrOhm schrieb:

Das Problem ist, ich MUSS das ganze mit einer einfach verketteten Liste machen

Das Problem ist dein Lehrer.

Der Herr. DDr. hat halt etwas mehr zu reden als ich, da kann nur ich die Probleme machen.

[kjjhkjhkhjk]

Hier mal eine quick and dirty Lösung. Normalerweise könnte man einfach die Zeiger umbiegen, aber da war ich mir gerade selber nicht mehr so sicher... Daher hab ich die Daten umkopiert:

#include <stdlib.h>
#include <stdio.h>

typedef struct _Header_
{
  unsigned int id_;
  double latitude_;
  unsigned int content_length_;
}Header;

typedef struct _Content_
{
  char *name_;
}Content;

typedef struct _Data_
{
  Header header_;
  Content content_;  
}Data;

typedef struct _List_
{
  struct _List_ *next_;
  Data data_;
}List; 

List *bubbleSort(List *list, int *error_code)
{
	List *it = list;

	while (it->next_ != NULL)
	{
		List *next = it->next_;

		if (it->data_.header_.id_ > next->data_.header_.id_)
		{
			Header hTmp = it->data_.header_;
			char *sTmp = it->data_.content_.name_;

			it->data_.header_ = next->data_.header_;
			it->data_.content_.name_ = next->data_.content_.name_;

			next->data_.header_ = hTmp;
			next->data_.content_.name_ = sTmp;

			it = list;
		}
		else
		{
			it = next;
		}
	}

	return list;
}

int main()
{
	List *list;
	List *it;
	int i;
	int error;

	list = malloc(sizeof(List));

	it = list;

	for (i = 0; i <= 15; ++i)
	{
		it->data_.header_.id_ = rand();
		it->next_ = malloc(sizeof(List));

		it->data_.content_.name_ = malloc(sizeof(char) * 100);
		sprintf(it->data_.content_.name_, "%d", i);

		it = it->next_;
	}

	it->next_ = NULL;

	it = list;

	while (it->next_ != NULL)
	{
		printf("%d\n", it->data_.header_.id_);
		printf("%s\n\n", it->data_.content_.name_);

		it = it->next_;
	}

	printf("\nSort:\n");

	list = bubbleSort(list, &error);

	it = list;

	while (it->next_ != NULL)
	{
		printf("%d\n", it->data_.header_.id_);
		printf("%s\n\n", it->data_.content_.name_);

		it = it->next_;
	}
}

Müsste sich gut einfügen lassen, da die deine Codeschnipsel verwendet habe.

[DrOhm]

http://www.fachinformatiker.de/c-c/134135-einfach-verkettet-listen.html
Also eine sortierte Liste ist nicht schwer, du musst einfach die Elemente von Anfang an sortiert einfügen
z.B: Aufsteigend sortierte Liste:

1. Erstes Element immer einfügen (head auf neu)
neu->NULL
2. Falls das neue Element kleiner als das erste, dann lasse neu auf erste zeigen und das neue das erste werden (head auf neu)
neu->alt_neu->NULL
3. Ansonsten gehe durch die Liste bis man NULL erreicht und prüfe jeweils ob das neue Element < nächste Element, wenn ja, dann tu das neue element auf das nächste zeigen und das derzeitige element auf das neue.
derzeitig->neu->next
4. Man muss es ganz hinten anfügen
letzte->neu->NULL

Falls Probleme kann ich auch dafür ein Code-schnippsel schreiben, oder am besten frag erst

hab ich in einem Forum gefunden, vielleicht mach ichs echt so.

[Wutz]

Deine Unterstriche in den Variablennamen sind schrecklich anzuschauen.

typedef struct List List;

struct List {
int i;
List *next;
} c={1},b={2,&c},a={3,&b};

void bubbleSort(List *list)
{
 List *list1,*list2;

 for(list1 = list; list1->next != NULL; list1 = list1->next)
   for(list2 = list1->next; list2 != NULL; list2 = list2->next)
     if(list2->i < list1->i)
     {
         int temp = list2->i;
         list2->i = list1->i;
         list1->i = temp;
     }
}

void Ausgabe(List *a)
{
  while( a )
    printf("%d",a->i),a=a->next;
}

int main()
{
  Ausgabe(&a);
  bubbleSort(&a);
  Ausgabe(&a);
  return 0;
}

[DrOhm]

WOW! Danke, dass werd ich mal so probiern.

Das mit den Unterstrichen, dass ist bei uns leider im Codingstandard so, ich muss das machen

Dein Programm vertauscht ja nur die IDs alleine, ich muss ja einen ganzen Eintrag, also
unsigned int id
double latitude
double longitude
unsigned int content_length
char *place_name
char *description
in einem vertauschen. Kann ich hier als temp eine List *temp nehmen?

[Bashar]

DrOhm schrieb:

Das mit den Unterstrichen, dass ist bei uns leider im Codingstandard so, ich muss das machen

Dann merk dir fürs echte Leben, dass die meisten dieser Unterstriche nicht nur unschön, sondern schlicht falsch sind, jedenfalls die am Anfang.

__bezeichner oder _Grossbuchstabe (u.a.) sind verboten bzw. für die Implementation reserviert. Wenn das ein Codingstandard ist, bekommst du damit früher oder später große Probleme, weil deine Bezeichner mit internen Bezeichnern des Compilers oder der Library kollidieren.

[hjghjghj]

DrOhm schrieb:

WOW! Danke, dass werd ich mal so probiern.

Das mit den Unterstrichen, dass ist bei uns leider im Codingstandard so, ich muss das machen

Dein Programm vertauscht ja nur die IDs alleine, ich muss ja einen ganzen Eintrag, also
unsigned int id
double latitude
double longitude
unsigned int content_length
char *place_name
char *description
in einem vertauschen. Kann ich hier als temp eine List *temp nehmen?

Ich glaube nicht, dass dich eine temporäre Liste da weiterbringt.

Das Programm sollte eigentlich alles im Header korrekt tauschen. Nur die Zeiger in Content musst du manuell umtauschen.