4. Problem mit Bubble Sort in C

Problem mit Bubble Sort in C

  • Mod

    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.

    0
  • ?

    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.

    0
  • Mod

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

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

    0
  • ?

    @ 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.

    0
  • Mod

    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.

    0
  • ?

    @ 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?

    0
  • ?

    @ 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;
 }
}
}
    0
  • Mod

    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).

    0

  • Das hast du jetzt davon :p

    0
  • Mod

    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);
}
    0
Anmelden zum Antworten