Speicherzugriffsfehler C++

[Max F. (mexxe)]

Hallo Gemeinde,
Ich habe ein Problem beim Tausch von Werten eines Structs innerhalb 
einer Liste. Beim ersten Mal tausche ich die Werte ohne Probleme. Da ich 
sie aber nun zurück tauschen will, tritt ein Speicherzugriffsfehler auf 
und ich kann mir nicht erklären, wo dieser liegen soll.
Das Programm soll eine Liste von Dominosteinen so in einem Kreis 
anornden, dass dieser geschlossen ist. Beispielsweise soll, wenn die 
rechte Hälfte des Dominosteins eine 11 ist, der passende Dominostein 
gefunden werden und so gedreht werden, dass die 11 links, also dazu 
passend, ist. Hier der Quelltext auszugsweise:

struct node {
  int zahl_l;
  int zahl_r;
  node* next;
};

void sortieren (node* head, int anzahl) {
  node *new_head, *start, *pos, *aktuell, *temp, *tausch;
  int swap;
  int i = 0;
  int j = 0;
  int k = 0;
  int stelle = 0;
  node *feld[anzahl];
  bool getauscht = false;

  aktuell = head;
  while (aktuell != 0) {
    aktuell->markiert = false;
    aktuell = aktuell->next;
  }

  new_head = new node;
  new_head->zahl_l = head->zahl_l;
  new_head->zahl_r = head->zahl_r;
  new_head->next = 0;
  pos = head->next;
  aktuell = head->next;


start = head;
    while (start != NULL) {  
      aktuell = head;
      while (aktuell != 0) {
        aktuell->markiert = false;
        aktuell = aktuell->next;
      }

      new_head = new node;
      new_head->zahl_l = head->zahl_l;
      new_head->zahl_r = head->zahl_r;
      new_head->next = 0;
      pos = head->next;
      aktuell = head->next;
        
      tausch->zahl_l = new_head->zahl_l;
      tausch->zahl_r = new_head->zahl_r;

      new_head->zahl_l = start->zahl_l;
      new_head->zahl_r = start->zahl_r;

      start->zahl_l = tausch->zahl_l;
      start->zahl_r = tausch->zahl_r;


      while (aktuell->zahl_r != new_head->zahl_l) {
        pos = head->next;  
    //    if (pos == 0)
    //      return;
        if (i == 0) 
          aktuell = new_head;
        
  
        while (pos->zahl_r == aktuell->zahl_r && pos->zahl_l == aktuell->zahl_l) {
          pos = pos->next;
          j++;

          if (pos == 0)
            pos = head->next;
          if (pos->markiert == true)
            pos = pos->next;
          if (pos == 0)
            pos = head->next;
        
          while (pos->zahl_r != aktuell->zahl_r && pos->zahl_l != aktuell->zahl_r) {
            pos = pos->next;
            if (pos == 0)
              pos = head->next;
            if (pos->markiert == true)
              pos = pos->next;
            if (pos == 0)
              pos = head->next;
          }
  
          if (pos == 0)
            pos = head->next;
        }

        pos->markiert = true;

        if (j == 0) {
          while (pos->zahl_r != aktuell->zahl_r && pos->zahl_l != aktuell->zahl_r) {
            pos = pos->next;
            if (pos->markiert == true)
              pos = pos->next;
            if (pos == 0)
              pos = head->next;
          }
        }  
        j = 0;
        pos->markiert = true;

        if (pos->zahl_l != aktuell->zahl_r) {
          swap = pos->zahl_l;
          pos->zahl_l = pos->zahl_r;
          pos->zahl_r = swap;
          getauscht = true;
        }
        temp = new node;
        temp->zahl_l = pos->zahl_l;
        temp->zahl_r = pos->zahl_r;
        aktuell->next = temp;
        aktuell = temp;
        aktuell->next = 0;
      /*  if (getauscht == true) {     Hier kommt der Fehler
          swap = pos->zahl_l;
          pos->zahl_l = pos->zahl_r;
          pos->zahl_r = swap;
        }
  */      pos->getauscht = false;
        i++;
        k++;
        getauscht = false;
      }        // beendet while-Schleife
      i = 0;
      j = 0;
      k = 0;
      start->zahl_l = new_head->zahl_l;
      start->zahl_r = new_head->zahl_r;
      feld[stelle] = new_head;
      while (feld[stelle] != NULL) {
        printf("[%d;%d]", feld[stelle]->zahl_l, feld[stelle]->zahl_r);
        feld[stelle] = feld[stelle]->next;
      }
      printf("\n");
      stelle++;
      start = start->next;
    }

Ich übergebe der Funktion den head einer Liste, so viel zur Erläuterung.
Mein zweites Problem dann ist, dass ich ja grundsätzlich die Liste mit 
jedem Listenelement am Anfang ausgeben will, sodass die oben genannte 
Bedingung erfüllt ist. Nun ist es so, dass bei gewissen Datein das 
Programm sich in einer Endlosschleife aufhängt und bei manchen Datein 
macht er das bis zum letzten Element, gibt da allerdings nur den 
Listenkopf aus. Wie oben aufgezeigt, vertausche ich nicht die ganzen 
Elemente, sondern lediglich die gespeicherten Zahlenwerte. Woran liegt 
das Problem hier?

[Sven B. (scummos)]

valgrind --track-origins=yes ./main

[Max F. (mexxe)]

Sven B. schrieb:
>

valgrind --track-origins=yes ./main

Was bringt das, um mal dumm zu fragen?

[Sven B. (scummos)]

valgrind (bzw. memcheck, das Default-Tool) ist ein "memory error 
detector", der dir genau sagen kannst, wann und von wo du zum Beispiel 
uninitialisierten Speicher liest, außerhalb von Array-Grenzen schreibst, 
auf gelöschte Objekte zugreifst etc. Die meisten komischen 
C++-Speicherfehler hat man damit sehr schnell gefunden.

[Max F. (mexxe)]

Sven B. schrieb:
> valgrind (bzw. memcheck, das Default-Tool) ist ein "memory error
> detector", der dir genau sagen kannst, wann und von wo du zum Beispiel
> uninitialisierten Speicher liest, außerhalb von Array-Grenzen schreibst,
> auf gelöschte Objekte zugreifst etc. Die meisten komischen
> C++-Speicherfehler hat man damit sehr schnell gefunden.

Und wie genau implementiere ich ihn innerhalb meines Cods?

[user (Gast)]

gar nicht, du musst nur valgrind mit deinem Programm als parameter 
starten, das Ergebniss bekommt du nach Beendigung deinen Programms

[Carl D. (jcw2)]

Was daran ist eigentlich C++?
Wenn es C++ wäre, dann gäbe es da std::list<> (besser std::vector<>) und 
kein Speicherproblem.

[Max F. (mexxe)]

Carl D. schrieb:
> Was daran ist eigentlich C++?
> Wenn es C++ wäre, dann gäbe es da std::list<> (besser std::vector<>) und
> kein Speicherproblem.

Speicherplatz anfordern mit new.
Darf ich nicht nutzen.

[The D. (thedaz)]

Max F. schrieb:
> Carl D. schrieb:
>> Was daran ist eigentlich C++?
>> Wenn es C++ wäre, dann gäbe es da std::list<> (besser std::vector<>) und
>> kein Speicherproblem.
>
> Speicherplatz anfordern mit new.
> Darf ich nicht nutzen.

Der STL kannst du deine eigene allocator Klasse in die Hand drücken, die 
dann statt der Standard-Heap Implementierung benutzt wird.

[Max F. (mexxe)]

The D. schrieb:
> Max F. schrieb:
>> Carl D. schrieb:
>>> Was daran ist eigentlich C++?
>>> Wenn es C++ wäre, dann gäbe es da std::list<> (besser std::vector<>) und
>>> kein Speicherproblem.
>>
>> Speicherplatz anfordern mit new.
>> Darf ich nicht nutzen.
>
> Der STL kannst du deine eigene allocator Klasse in die Hand drücken, die
> dann statt der Standard-Heap Implementierung benutzt wird.

Das Problem ist, ich darf die Aufgabe nur mit den im Programm genutzen 
Werkzeug lösen. Das macht die Sache erheblich schwerer.

[Carl D. (jcw2)]

The D. schrieb:
> Max F. schrieb:
>> Carl D. schrieb:
>>> Was daran ist eigentlich C++?
>>> Wenn es C++ wäre, dann gäbe es da std::list<> (besser std::vector<>) und
>>> kein Speicherproblem.
>>
>> Speicherplatz anfordern mit new.
>> Darf ich nicht nutzen.
>
> Der STL kannst du deine eigene allocator Klasse in die Hand drücken, die
> dann statt der Standard-Heap Implementierung benutzt wird.

Ich glaube er meinte, er darf die STL nicht benutzen, new aber schon, da 
es ja ein Sprachelement von C++ ist.
Klingt nach Schule oder untere Semester. Ich hoffe nach der Übung sagt 
der Lehrer/Prof. "so und jetzt das ganze mal mit STL, ganz knapp und 
stabil".
(man darf ja hoffen, oder? Auch wenn's sicher vergeblich ist ;-)

[Max F. (mexxe)]

Carl D. schrieb:
> The D. schrieb:
>> Max F. schrieb:
>>> Carl D. schrieb:
>>>> Was daran ist eigentlich C++?
>>>> Wenn es C++ wäre, dann gäbe es da std::list<> (besser std::vector<>) und
>>>> kein Speicherproblem.
>>>
>>> Speicherplatz anfordern mit new.
>>> Darf ich nicht nutzen.
>>
>> Der STL kannst du deine eigene allocator Klasse in die Hand drücken, die
>> dann statt der Standard-Heap Implementierung benutzt wird.
>
> Ich glaube er meinte, er darf die STL nicht benutzen, new aber schon, da
> es ja ein Sprachelement von C++ ist.
> Klingt nach Schule oder untere Semester. Ich hoffe nach der Übung sagt
> der Lehrer/Prof. "so und jetzt das ganze mal mit STL, ganz knapp und
> stabil".
> (man darf ja hoffen, oder? Auch wenn's sicher vergeblich ist ;-)

2. Semester ;)
Den Speicherzugriffsfehler habe ich gelöst, danke an dieser Stelle für 
die Hilfe.
Allerdings besteht das 2. Problem immernoch, keine Ahnung, ob es hier 
passend ist.
Die eine Datei liest er zweifelsfrei, bei der anderen gerät er nach der 
Ausgabe des 2. neuen Heads in eine Endlosschleife. Ich muss erstmal 
gucken, in welcher.

[Sven B. (scummos)]

Hier wäre ein Debugger empfehlenswert.

[Carl D. (jcw2)]

Vielleicht solltest du das ganze in die Komponenten Swap, Sort und 
Compare zerlegen. Diese sind dann jeweils kleiner und überschaubarer.
Das was du hier machst, ist nämlich die Aufgabe des Compilers(/Linkers): 
aus der strukturierten Lösungsbeschreibung per Optimierung möglichst 
Branchfreien, auch Spagetti-Code genannten, Maschinen-Code zu 
produzieren. Jeder halbwegs vernünftige Compiler wird auf ein Resultat 
kommen, das bei dir schon im Sourcecode vorhanden ist und leicht 
unübersichtlich wirkt.
Da es a C++ sein soll, darf die struct auch diese Methoden besitzen: 
Sort(), Swap() und Compare() oder auch operator<(), oder?

[Max F. (mexxe)]

Carl D. schrieb:
> Vielleicht solltest du das ganze in die Komponenten Swap, Sort und
> Compare zerlegen. Diese sind dann jeweils kleiner und überschaubarer.
> Das was du hier machst, ist nämlich die Aufgabe des Compilers(/Linkers):
> aus der strukturierten Lösungsbeschreibung per Optimierung möglichst
> Branchfreien, auch Spagetti-Code genannten, Maschinen-Code zu
> produzieren. Jeder halbwegs vernünftige Compiler wird auf ein Resultat
> kommen, das bei dir schon im Sourcecode vorhanden ist und leicht
> unübersichtlich wirkt.
> Da es a C++ sein soll, darf die struct auch diese Methoden besitzen:
> Sort(), Swap() und Compare() oder auch operator<(), oder?

Das wäre dann aber ein abstrakter Datentyp (=Class) und kein Struct mehr 
;)
Das mit den in Unterfunktionen zu untergliedern, ist sicher richtig,das 
ist auch zugegebenermaßen meine Schwäche :D
Ich habe es aber jetz einmal bis hier hin, das würde ich ungern über den 
Haufen werfen.
Die fehlerhafte Schleife habe ich zwar gefunden, den Fehler da drin aber 
noch nicht.
Das ist der aktuelle Stand der Dinge:

void sortieren (node* head, int anzahl) {
  node *new_head, *start, *pos, *aktuell, *temp, *tausch;
  int swap;
  int i = 0;
  int j = 0;
  int k = 0;
  int stelle = 0;
  int zahl_links, zahl_rechts;
  node *feld[anzahl];

  aktuell = head;
  while (aktuell != 0) {
    aktuell->markiert = false;
    aktuell->getauscht = false;
    aktuell = aktuell->next;
  }

  new_head = new node;
  new_head->zahl_l = head->zahl_l;
  new_head->zahl_r = head->zahl_r;
  new_head->next = 0;
  pos = head->next;
  aktuell = head->next;

start = head;
    while (start != NULL) {  
      aktuell = head;
      while (aktuell != 0) {
        aktuell->markiert = false;
        aktuell = aktuell->next;
      }
      tausch = new node;
      new_head = new node;
      new_head->zahl_l = head->zahl_l;
      new_head->zahl_r = head->zahl_r;
      new_head->next = 0;
      pos = head->next;
      aktuell = head->next;
        
      tausch->zahl_l = new_head->zahl_l;
      tausch->zahl_r = new_head->zahl_r;
      if (start->getauscht != true) {            // löst den Speicherzugriffsfehler übrigens
        new_head->zahl_l = start->zahl_l;
        new_head->zahl_r = start->zahl_r;
      }
      else {
        new_head->zahl_l = start->zahl_r;
        new_head->zahl_r = start->zahl_l;
      }
      start->getauscht = false;
      start->zahl_l = tausch->zahl_l;
      start->zahl_r = tausch->zahl_r;

      while (aktuell->zahl_r != new_head->zahl_l && i < 7) {
  //      printf("[%d;%d]\n", aktuell->zahl_l, aktuell->zahl_r);
        pos = head->next;  
        head->markiert = true;
        if (pos == 0)
          return;
        if (i == 0) 
          aktuell = new_head;
        
  
        while (pos->zahl_r == aktuell->zahl_r && pos->zahl_l == aktuell->zahl_l) {
          pos = pos->next;
          j++;

          if (pos == 0)
            pos = head->next;
          if (pos->markiert == true)
            pos = pos->next;
          if (pos == 0)
            pos = head->next;
        
          while (pos->zahl_r != aktuell->zahl_r && pos->zahl_l != aktuell->zahl_r) {
            pos = pos->next;
            if (pos == 0)
              pos = head->next;
            if (pos->markiert == true)
              pos = pos->next;
            if (pos == 0)
              pos = head->next;
          }
  
          if (pos == 0)
            pos = head->next;
        }

        pos->markiert = true;

        if (j == 0) {
          while (pos->zahl_r != aktuell->zahl_r && pos->zahl_l != aktuell->zahl_r) {
            pos = pos->next;
            if (pos->markiert == true)
              pos = pos->next;
            if (pos == 0)
              pos = head->next;
          }
        }  
        j = 0;
        pos->markiert = true;

        zahl_links = pos->zahl_l;
        zahl_rechts = pos->zahl_r;
        if (pos->zahl_l != aktuell->zahl_r) {
          swap = pos->zahl_l;
          pos->zahl_l = pos->zahl_r;
          pos->zahl_r = swap;
          pos->getauscht = true;
        }
        temp = new node;
        temp->zahl_l = pos->zahl_l;
        temp->zahl_r = pos->zahl_r;
  
    /*    if (getauscht == true) {
          tausch->zahl_l = temp->zahl_l;
          tausch->zahl_r = temp->zahl_r;
          pos->zahl_l = tausch->zahl_r;
          pos->zahl_r = tausch->zahl_l;
          printf("[%d;%d]", pos->zahl_l, pos->zahl_r);
          printf("drin\n");
        }
        else {
          printf("draußen\n");
        } */
        aktuell->next = temp;
        aktuell = temp;
        aktuell->next = 0;
        i++;
        k++;
      }        // beendet while-Schleife
      i = 0;
      j = 0;
      k = 0;
      start->zahl_l = new_head->zahl_l;
      start->zahl_r = new_head->zahl_r;
      feld[stelle] = new_head;
      while (feld[stelle] != NULL) {
        printf("[%d;%d]", feld[stelle]->zahl_l, feld[stelle]->zahl_r);
        feld[stelle] = feld[stelle]->next;
      }
      printf("\n");
      stelle++;
      start = start->next;
    }

Der Fehler muss in der Schleife sein:

while (aktuell->zahl_r != new_head->zahl_l) {  
...
}

Die Liste
1 3 (= Dominostein mit links 1 und rechts 3)
3 5
2 6
6 23
23 42
2 42
1 5
liefert nach Abbruch folgendes, fehlerhaftes Ergebnis:
[1;3][3;5][5;1] (richtig)
[3;5] (falsch, keine Ahnung was er hier macht)
[2;6][6;23][23;42][42;23][23;42][42;23][23;42][42;23] (falsch)
[6;23][23;42][42;2][2;6] (richtig)
[42;23][23;6][6;2][2;42] (falsch, da er eigentlich mit [23;42] beginnen 
muss)
[42;2][2;6][6;23][23;6][6;23][23;6][6;23][23;6] (falsch)
[1;5][5;3][3;1] (richtig)

Wenn ich die Sache nicht nach 7 Durchläufen abbrechen würde, würde er 
sich irgendwann in der Dauerschleife verlieren und nur noch [23;42] und 
[42;23] jeweils im Wechsel ausgeben. Woran könnte das liegen?

[Carl D. (jcw2)]

In C++ unterscheidet sich eine struct von der class nur durch den 
Defaultwert für die Komponentensichbarkeit. Bei class ist diese private, 
bei einer struct ist sie public.

[Max F. (mexxe)]

Carl D. schrieb:
> In C++ unterscheidet sich eine struct von der class nur durch den
> Defaultwert für die Komponentensichbarkeit. Bei class ist diese private,
> bei einer struct ist sie public.

Stimmt, im Struct sind alle Methoden grundsätzlich Public.

Nichtsdestotrotz hilft mir das im Moment nicht weiter und mir ist es 
leider auch nicht gelungen die Fehlerquelle weiter einzugrenzen.

[Sven B. (scummos)]

Max F. schrieb:
> Nichtsdestotrotz hilft mir das im Moment nicht weiter und mir ist es
> leider auch nicht gelungen die Fehlerquelle weiter einzugrenzen.
Hast du denn mal einen Debugger benutzt? Sorry, ich habe keine Lust mich 
in diesen Code einzulesen, das musst du im Detail schon selber tun ...

[Carl D. (jcw2)]

Max F. schrieb:
> Carl D. schrieb:
>> In C++ unterscheidet sich eine struct von der class nur durch den
>> Defaultwert für die Komponentensichbarkeit. Bei class ist diese private,
>> bei einer struct ist sie public.
>
> Stimmt, im Struct sind alle Methoden grundsätzlich Public.
>
> Nichtsdestotrotz hilft mir das im Moment nicht weiter und mir ist es
> leider auch nicht gelungen die Fehlerquelle weiter einzugrenzen.

Meine Idee (am Anfang) war ja auch eher dich zu Gedanken über dein 
Nudelprogramm anzuregen. Eine seiner Nachteil erlebst du ja gerade.