Problem mit Bubble Sort in C

[Crossader]

Hallo, ich sitze nun seit Stunden vor meinem Programmcode und finde einfach den Fehler nicht. Bei manchen Eingaben gehen Elemente der verketteten Liste verloren. Vielleicht kann mir ja jemand von euch helfen.

unsigned int i, j; //Deklaration Zählvariablen
	struct buch *zgr_Save = NULL; //Deklaration eines Zeigers, um andere Zeiger zwischenzuspeichern

	for (j = 0; j <= ID_B; j++)

	{
		zgr = zgr_Anfang; //Der Zählzeiger soll zu Beginn auf das erste Element zeigen

		while (zgr->zgr_Next != NULL)//Solange das nachfolgende Element nicht NULL ist soll sortiert werden
	{
		zgr_Save = zgr->zgr_Next; 

		if (zgr->bewertung < zgr_Save->bewertung) //Falls das Element Bewertung der ersten Struktur kleiner ist als das Element Bewertung der zweiten Struktur soll getauscht werden
		{
			if(zgr == zgr_Anfang) //Falls die Struktur, die getauscht werden soll, das erste Element ist...
			{
				zgr_Anfang = zgr->zgr_Next; //...Soll der Anfang auf das zu tauschende Element zeigen
			}

			zgr->zgr_Next = zgr_Save->zgr_Next;
			zgr_Save->zgr_Next = zgr; //Tauschen der Zeiger der Elemente
		}
		else {
			zgr = zgr->zgr_Next; //Falls nicht getauscht werden soll 
		}
	}

	}

Ich habe versucht meinen Programmcode verständlich auszukommentieren. Ich hoffe ihr kommt damit zurecht. Vielen Dank für alle Antworten.

[SeppJ]

Wenn du zwei Elemente tauscht, wohin zeigt dann das Element, welches in der Liste vor diesen beiden steht?

[Wutz]

Nimm statt deiner verketteten Liste ein einfaches Array, damit kannst du deine Sortierübungen weitaus einfacher realisieren.

[Crossader]

@ SeppJ:

Vielen Dank für deine Antwort. Ich habe jetzt versucht das entsprechend anzupassen. Jetzt stürzt mir das Programm aber beim Sortieren ab. Könnt ihr mal nachsehen, wo jetzt der Fehler liegen könnte?

unsigned int i, j; //Deklaration Zählvariablen
	struct buch *zgr_Save = NULL; //Deklaration eines Zeigers, um andere Zeiger zwischenzuspeichern

	for (j = 0; j <= ID_B; j++)

	{
		zgr = zgr_Anfang; //Der Zählzeiger soll zu Beginn auf das erste Element zeigen

		while (zgr->zgr_Next != NULL)//Solange das nachfolgende Element nicht NULL ist soll sortiert werden
	{
		if (zgr->bewertung < zgr->zgr_Next->bewertung) //Falls das Element Bewertung der ersten Struktur kleiner ist als das Element Bewertung der zweiten Struktur soll getauscht werden
		{
			if(zgr_B == zgr_Anfang) //Falls die Struktur, die getauscht werden soll, das erste Element ist...
			{
				zgr_Anfang = zgr->zgr_Next; //...Soll der Anfang auf das zu tauschende Element zeigen
				zgr_Save = zgr->zgr_Next;

				zgr->zgr_Next = zgr_Save->zgr_Next;
				zgr_Save->zgr_Next = zgr; //Tauschen der Zeiger der Elemente
			}
			else
			{
				zgr->zgr_Next = zgr->zgr_Next->zgr_Next;
				zgr->zgr_Next->zgr_Next = zgr_Save;
				zgr_Save->zgr_Next = zgr;
			}

		}

		zgr_Save = zgr;
		zgr = zgr->zgr_Next;

	}

[SeppJ]

Da kann ja schon mindestens mal im ersten Durchlauf eine NULL-Dereferenzierung stattfinden (über zgr_Save).

Mach das lieber so: Du hast zwei Elemente und es gibt einen Zeiger, der auf das erste dieser beiden Elemente zeigt. Das kann der Anfangszeiger sein oder der next-Zeiger des vorherigen Elementes. Du merkst dir einfach nur einen Zeiger auf diesen Zeiger, nicht einen Zeiger auf das Element in dem dieser Zeiger steht (denn es kann ja auch der Anfangszeiger sein). Im Vertauschungsfall kannst du über diesen Zeiger auf den Zeiger den Zeiger gegebenenfalls umbiegen.

So brauchst du auch keine Sonderbehandlung für den Anfangszeiger mehr.

Klingt wahrscheinlich etwas kompliziert, aber versuch das mal so durchzudenken. Falls du es nicht versteht, frag nach! Dann versuche ich ein Bildchen zu malen.

[Crossader]

Hallo SeppJ,

nochmal vielen Dank für deine Antwort.
Ich habe es gerade versucht durchzudenken, bin aber kläglich daran gescheitert. Auf welchen Zeiger willst du einen Zeiger zeigen lassen?
Wäre evtl. wirklich hilfreich, wenn du ein Bild dazu zeichnen könntest.

[SeppJ]

So meine ich das:
http://postimage.org/image/6t5vov4wj/

P.S.: Beim Umbiegen natürlich auf die Reihenfolge aufpassen!

[Crossader]

@ SeppJ:

Danke für die schnelle Antwort und die gute Darstellung. Nur habe ich immer noch ein Problem Wie kann ich einen Zeiger auf einen Zeiger zeigen lassen, ohne dass ich das Element davor kenne, denn davon hängt dieser doch ab? Es kann ja eben auch der Anfangszeiger sein oder eben ein Next-Zeiger eines Elements davor?
Danke vielmals.

[SeppJ]

Am Anfang ist es eben der Anfangszeiger und später merkst du dir beim Weitergehen den entsprechenden Zeiger aus dem vorherigen Durchgang (Vorsicht, dass du dir beim Vertauschen auch den richtigen Zeiger merkst). Dir ist bekannt, dass man auch einen Zeiger auf einen Zeiger (das ist dann mit zwei Sternchen) haben kann?

Pseudocode (ohne Prüfungen auf NULL an ein paar Stellen an denen es nötig wäre und mit nur einem Bubble-Durchgang):

// Mit den Bezeichnungen aus dem Bild:
Element **zeiger1 = &anfangszeiger;
Element *zeiger2 = anfangszeiger;  // Zeiger auf das "linke" Element
Element *zeiger3 = anfangszeiger->next;  // Zeiger auf das "rechte" Element

while(zeiger3 != NULL)
{
 if (vergleiche_elemente(zeiger2, zeiger3)  // wenn getauscht werden soll
 {
   // Erst einmal tauschen:
   *zeiger1 = zeiger3;   // 1 auf 3 umbiegen
   zeiger2->next = zeiger3->next;  // 2->next auf 3->next umbiegen
   zeiger3->next = zeiger2;        // 3->next auf 2 umbiegen
   // Nun weitergehen:
   zeiger1 = &zeiger3->next;
   zeiger2 = zeiger3;
   zeiger3 = zeiger2->next->next;  // Also das ehemalige zeiger3->next
 }
 else  // Normales weitergehen
 {
  zeiger1 = &zeiger2->next;
  zeiger2 = zeiger3;
  zeiger3 = zeiger3->next;
 }
}

Ich habe es hoffentlich selber richtig gemacht. Du merkst schon, da sind ein paar Hirnverrenkungen nötig.

[Crossader]

@ SeppJ:

Juhu danke er tauscht jetzt immerhin schon mal die ersten beiden Elemente. Aber wenn ich etz einfach mal die gleiche for-Schleife wie am Anfang verwende und eben die zeiger1, zeiger2, zeiger3 erst in der Schleife auf Anfang setze und nur davor definiere gibt er bei 2 Elementen die sorierte Liste aus aber wenn ich 3 Elemente eingebe, gibt er nur noch das 2. Element aus?

[Crossader]

@ SeppJ:
Hier noch mal der Quelltext:

Element **zeiger1;
Element *zeiger2;  // Zeiger auf das "linke" Element
Element *zeiger3;  // Zeiger auf das "rechte" Element

for(i = 1; i < ID; i++)
{
zeiger1 = &anfangszeiger;
zeiger2 = anfangszeiger;
zeiger3 = anfangszeiger->next;

while(zeiger3 != NULL)
{
 if (vergleiche_elemente(zeiger2, zeiger3)  // wenn getauscht werden soll
 {
   // Erst einmal tauschen:
   *zeiger1 = zeiger3;   // 1 auf 3 umbiegen
   zeiger2->next = zeiger3->next;  // 2->next auf 3->next umbiegen
   zeiger3->next = zeiger2;        // 3->next auf 2 umbiegen
   // Nun weitergehen:
   zeiger1 = &zeiger3->next;
   zeiger2 = zeiger3;
   zeiger3 = zeiger2->next->next;  // Also das ehemalige zeiger3->next
 }
 else  // Normales weitergehen
 {
  zeiger1 = &zeiger2->next;
  zeiger2 = zeiger3;
  zeiger3 = zeiger3->next;
 }
}
}

[SeppJ]

Hmm, dann habe ich wohl selber irgendwas falsch gemacht . Das ist aber zu viel Knotenbildung, um das im Kopf zu lösen, da muss ich morgen mal mit dem Debugger dran. Dafür wäre es sehr hilfreich, wenn du den Code deines gesamten Programms zeigen würdest. Dann muss ich nämlich nicht das ganze Drumherum schreiben und ich kann ausschließen, dass in deinem Drumherum ein Fehler ist (oder ich kann ihn gegebenenfalls finden).

[Wutz]

Das hast du jetzt davon :p

[SeppJ]

In meiner Weitersetzelogik im Vertauschungsfall war ein Fehler. Es muss lauten:

zeiger1 = &zeiger3->next;
              // zeiger2 bleibt unverändert
              zeiger3 = zeiger2->next;

Insgesamt (mir ist klar, dass ich dir dadurch deine Hausaugfgabe gemacht habe):
http://ideone.com/FGsUuK

#include <stdlib.h>

typedef struct Element
{
  int data;
  struct Element* next;
} Element;

typedef Element* List;

int compare_elements_greater(const Element *lhs, const Element *rhs)
{
  return lhs->data > rhs->data;
}

void bubble_sort(List *root, int (*comparison)(const Element*, const Element*))
{
  // If the list has 0 or 1 element, it is already sorted:
  if (! *root || !(*root)->next)
    return;

  // Otherwise use extra stupid sort:
  int num_changes;
  do
    {
      num_changes = 0;
      Element **p1 = root;
      Element *p2 = *root;
      Element *p3 = (*root)->next;

      while (p3)
        {
          if (comparison(p2, p3))
            {
              ++num_changes;

              *p1 = p3; 
              p2->next = p3->next; 
              p3->next = p2;        

              p1 = &p3->next;
              p3 = p2->next;  
            }
          else
            {
              p1 = &p2->next;
              p2 = p3;
              p3 = p3->next; 
            }
        }
    }
  while (num_changes);
}

List create_list()
{
  return NULL;
}

int insert_list(int value, List *list)
{
  List old_list = *list;
  *list = malloc(sizeof(Element));
  if (*list)
    {
      (*list)->data = value;
      (*list)->next = old_list;
      return 1;
    }
  else
    {
      *list = old_list;
      return 0;
    }
}

void delete_list(List* list)
{
  while (*list)
    {
      List next = (*list)->next;
      free(*list);
      *list = next;
    }
}

List iterate_list(List *list)
{
  *list = (*list)->next;
  return *list;
}

int get_list_data(List list)
{
  return list->data;
}

#include <time.h>
#include <stdio.h>

int main()
{
  List list = create_list();

  srand(time(0));
  for(int i = 0; i < 25; ++i)
    {
      if (!insert_list(rand() % 42, &list))
        {
          fputs("Fehler beim Einfügen!\n", stderr);
          goto Exception;
        }
    }

  bubble_sort(&list, &compare_elements_greater);

  for(List iterator = list; iterator; iterate_list(&iterator))
    {
      printf("%d\n", get_list_data(iterator));
    }

 Exception:
  delete_list(&list);
}