C - Strukturbaum sortieren

[max .. (vbc2011)]

Hallo,

ich möchte einen Strukturbaum sortieren. D.h. die einzelen 
Unterstrukturen nach bestimmten kritrien ordnen. Das funktioniert 
einwandfrei mit einer Quicksortfunktion.

Nun mein Problem:
Ich gebe den originalen Strukturbaum in meine Sortierfunktion und 
bekomme einen neuen sortierten Strukturbaum zurück - dieser neue Baum 
bestitz jedoch Speicherabhänigkeiten zu dem originalen baum (das ganze 
kann man sich vorstellen wie eine verkettete Struktur - mit Pointern zum 
nächsten Element).
Wenn ich also jetzt den Speicher des originalen Baums freigebe hat das 
auch Auswirkungen auf den Sortierten (kopierten) Baum -> das ist 
schlecht.

Ich dachte ich könnte mit memcpy() sozusagen eine Kopie des orignalen 
Baums erstellen und diese Kopie dann ohne Auswirkungen auf das original 
verändern (und umgekehrt). Das geht leider nicht - oder ich mache es 
falsch!

So sieht die Struktur aus:
typedef struct xmlnodestruct
{
  struct xmlnodestruct  *parentnode;
  struct xmlnodestruct **childnodes; // Array of xmlnodes
  }
XMLNODE;

typedef XMLNODE  *XMLNODEPTR;

Danke schonmal...

[Rolf Magnus (Gast)]

max .. schrieb:
> Ich dachte ich könnte mit memcpy() sozusagen eine Kopie des orignalen
> Baums erstellen und diese Kopie dann ohne Auswirkungen auf das original
> verändern (und umgekehrt). Das geht leider nicht - oder ich mache es
> falsch!

Du mußt in der Kopie natürlich auch die Zeiger anpassen. Die zeigen ja 
schließlich immer noch auf die Originale.

[max .. (vbc2011)]

ja - das habe ich eben auch herausgefunden - das einzige problem sind 
die Abhängigkeiten der einzelen Element - ich darf nur die Inhalte 
kopieren und muss mir einen "leeren" neuen Baum erstellen mit eigenen 
Abhängigkeiten.

Ich setze das gerade um - wenns klappt gibts die Lösung!

[max .. (vbc2011)]

also es funktioniert.

man muss sich eben einen "leeren" Baum erstellen und dann die Inhalte 
des originals rüberkopieren und die Abhängigkeiten der einzelene 
Elemente neu nachbilden - d.h. die Zeiger anpassen!

[Karl H. (kbuchegg)]

max .. schrieb:
> also es funktioniert.
>
> man muss sich eben einen "leeren" Baum erstellen und dann die Inhalte
> des originals rüberkopieren

dann machst du das aber kompliziert.
Eine rekursive Funktion kann von einem gegebenen Baum eine Kopie während 
des Durchmarsches durch den Baum erzeugen.

Dem Prinzip nach:

XMLNODEPTR copyTree( XMLNODEPTR root )
{
  int i;
  XMLNODEPTR newRoot;

  if( root == NULL )
    return NULL;

  newRoot = malloc( sizeof( *root ) );
  newRoot->parentnode = NULL;

  // alle Nutzdaten dieses Knotens kopieren
  copyData( newRoot, root );

  // und Duplikate von den Kindern anlegen,
  // falls es überhaupt welche gibt
  newRoot->nrChilds = root->nrChilds;
  if( newRoot->nrChilds == 0 )
    newRoot->childnodes = NULL;
  else {
    newRoot->childnodes = malloc( newRoot->nrChilds * sizeof( XMLNODEPTR  ) );
    for( i = 0; i < newRoot->nrChilds; ++i ) {
      newRoot->childnodes[i] = copyTree( root->childnodes[i] );
      if( newRoot->childnodes[i] )
        newRoot->childnodes[i]->parentnode = newRoot;
    }
  }

  return newRoot;
}

Das hier

typedef struct xmlnodestruct
{
  struct xmlnodestruct  *parentnode;
  struct xmlnodestruct **childnodes; // Array of xmlnodes
  }
XMLNODE;

typedef XMLNODE  *XMLNODEPTR;

kann nicht dein Knoten sein. Da fehlt noch die Information, wie gross 
das Array der Childknoten ist. Ich hab mal noch einen Member 'nrChilds' 
angenommen.

[max .. (vbc2011)]

dann haben wir uns falsch verstanden - denn exakt so mache ich es 
letztendlich auch.
ich nehme an in der Funktion copyData() kopierst du die Inhalte (wie 
Kontennamen, KnotenWert,....) in den neuen Node!

und ja klar - die Struktur beinhaltet nat. noch mehr infos (parentnode, 
childcount,....).

Aber du hast wohl mehr mit dem Thema zu tun - da du das gut umgesetzt 
hast!!

[max .. (vbc2011)]

...wenn man Strukturbäumen arbeitet braucht man eig. immer eine 
rekursive Funktion! Das ist hier bei dem Thema der Knackpunkt!

[Karl H. (kbuchegg)]

max .. schrieb:

> Aber du hast wohl mehr mit dem Thema zu tun - da du das gut umgesetzt
> hast!!

:-)
Mit XML hab ich nicht viel am Hut.
Aber ich hab schon 'öfter' mit Bäumen zu tun und vor allen Dingen: Ich 
hab keine Angst vor rekursiven Funktionen :-)