Hallo,
Ich habe die Aufgabe einen Baum in C abzubilden.
Um zu verdeutlichen wie die Struktur eingelesen wird hier ein Beispiel:
dies soll folgende Grafik erzeugen:
Dabei gilt folgendes: Jeder Knoten hat einen Namen von A-Z (Großbuchstaben) und dazu eine eindeutige ID von 1 bis 10000.
Jeder Knoten wird durch den Datentyp graph abgebildet. Da jeder Knoten n Kinder haben kann enthält der Datentyp eine Liste, die auf die Kinder verweisen soll.
Um eine Verknüpfung aus dem String zu erstellen werden graph-Elemente erzeugt und in eine Liste gepackt (tmpls). Dann wird bei einer Zuweisung auf die liste zurückgegriffen und die Verknüpfung geschaffen.
Leider läuft da irgendwas schief und ich kann den Fehler nicht finden. Ich vermute den Fehler in der addChildToNode aber kann ihn nicht entdecken.
Bei mir wird immer folgende Struktur erzeugt: Knoten A mit den Kindern E und F (ohne weitere Kinder)
Hier mein bisheriger Code:
Ich freue mich über jede Anregung, Kritik und Hilfe! Danke im Voraus!
Ich habe die Aufgabe einen Baum in C abzubilden.
Um zu verdeutlichen wie die Struktur eingelesen wird hier ein Beispiel:
Code:
1:A;
2:B;
3:C;
4:E;
5:F;
6:D;
7:E;
8:F;
9:D;
1->2;
1->3;
1->4;
1->5;
2->6;
2->7;
3->8;
3->9;Dabei gilt folgendes: Jeder Knoten hat einen Namen von A-Z (Großbuchstaben) und dazu eine eindeutige ID von 1 bis 10000.
Jeder Knoten wird durch den Datentyp graph abgebildet. Da jeder Knoten n Kinder haben kann enthält der Datentyp eine Liste, die auf die Kinder verweisen soll.
Um eine Verknüpfung aus dem String zu erstellen werden graph-Elemente erzeugt und in eine Liste gepackt (tmpls). Dann wird bei einer Zuweisung auf die liste zurückgegriffen und die Verknüpfung geschaffen.
Leider läuft da irgendwas schief und ich kann den Fehler nicht finden. Ich vermute den Fehler in der addChildToNode aber kann ihn nicht entdecken.
Bei mir wird immer folgende Struktur erzeugt: Knoten A mit den Kindern E und F (ohne weitere Kinder)
Hier mein bisheriger Code:
C++:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> //C99-Standard
#include <strings.h> //strtok()
#define DELIMITER ";" //Trennzeichen für Operationen
typedef struct nextelement{ //Linkls: Kind-Liste innerhalb eines Knotens
struct node *child; // - child: Zeiger auf Kindelement des Knotens
struct nextelement *next; // - nextelement: Zeiger auf nächstes Listenelement
}linkls;
typedef struct node{ //graph: Ein Knotenpunkt des Graphs
char label; // - label: Name des Knotens, doppeltes Vorkommen möglich
int id; // - id: eindeutige Nummer des Knotens
linkls *link; // - link: Startpunkt der Liste der Kinder-Elemente
}graph;
typedef struct lsele{ //tmpls: Temporäre Liste zum Erzeugen der Verknüpfungen der Struktur
graph *ele; // - ele: Knotenpunkt, der nach Erstellen festgehalten wird
struct lsele *nxt; // - nxt: Nächstes Listenelement
}tmpls;
/** Funktion getAddressFromList
* Durchläuft temporäre Liste für das Verknüpfen der erzeugten Elemente.
* Nach dem Auffinden einer gesuchten ID wird das Element zurückgegeben.
* IN: - list: Zeiger auf das Anfangselement der Liste
* - id: Gesuchte ID des zu verknüpfenden Elements
* RETURN: Pointer auf gesuchtes Graphenelement
*/
graph *getAddressFromList(tmpls *list, int id){
tmpls *runner=list;
if(!runner) //Wenn Liste leer->NULL
return NULL;
//Ein Element weitergehen so lange es ein nächstes Element gibt und die gesuchte ID nicht gefunden wurde
while((id!=runner->ele->id) && (runner->nxt))
runner=runner->nxt;
if(id==runner->ele->id) //Wenn aktuelles Element die ID hat -> zurückgeben
return runner->ele;
else
return NULL; //Andernfalls nicht in Liste gefunden
}
/** Funktion appendToList
* Läuft bis ans Ende der temporären Liste und hängt neues Element an
* IN: - element: Knoten der ans Ende der Liste gespeichert werden soll
* - list: Pointer auf Pointer auf Liste (Änderbarkeit bei leerer Liste)
*/
void appendToList(graph *element, tmpls **list){
tmpls *runner=*list,
*newelement=(tmpls *) malloc (sizeof(tmpls));
if(newelement){ //Wenn Speicher reserviert werden konnte
newelement->ele=element; //Übergebenen Knoten dem Listenelement zuordnen
newelement->nxt=NULL;
if(!(*list)) //Wenn Liste leer -> Element ist Liste
*list=newelement;
else{
while (runner->nxt) //Andernfalls ans Ende der Liste gehen
runner=runner->nxt;
runner->nxt=newelement; //und dann Listenelement anhängen
}
}
else
printf("Es konnte kein Speicher freigegeben werden!\n");
}
/** Funktion removeList
* Gibt den reservierten Speicher für die temporäre Liste frei
* IN: - element: Knoten der ans Ende der Liste gespeichert werden soll
* - list: Pointer auf Pointer auf Liste (Änderbarkeit bei leerer Liste)
*/
void removeList(tmpls *start){
tmpls *deleter, *tmp;
if(start){ //Wenn Liste nicht leer
deleter=start->nxt; //Setze deleter an 2. Position
while(deleter){ //So lange noch ab der zweiten Position Elemente in der Liste bestehen
tmp=start->nxt->nxt; //Gehe mit tmp auf 3. Position
start->nxt=tmp; //Startelement zeigt auf 3.Position (Ausgliederung des 2. Elements)
free(deleter); //Zweites Element wird gelöscht
deleter=tmp; //deleter wird wieder auf 2.Position gesetzt
}
free(start->nxt); //Zweites Element wird gelöscht
free(start); //Startelement wird gelöscht
start=NULL;
}
}
/** Funktion createNewNode
* Reserviert Speicherplatz für ein neues Element und ordnet ihm Werte zu
* IN: - id: Eindeutige Nummer des Knotens
* - label: Großbuchstabe, der den Namen des Knotens darstellt
* RETURN: Neu erzeugter Knotenpunkt
*/
graph *createNewNode(int id, char label){
graph *newelement=(graph*) malloc (sizeof(graph));
if(!newelement) //Bei Fehlschlagen->NULL
return NULL;
newelement->id=id;
newelement->label=label;
newelement->visited=false;
newelement->link=NULL;
printf("Nummer %i mit Label %c wurde auf Adresse %p definiert\n", id, label, newelement);
return newelement;
}
/** Funktion addChildToNode
* Ordnet einem Knoten einen anderen Knoten als Kind zu
* IN: - node: Eltern-Knoten der auf etwas zeigen soll
* - newchild: Kind-Knoten den es zu verknüpfen gilt
*/
void addChildToNode(graph *node, graph *newchild){
linkls *linkele=(linkls *) malloc (sizeof(linkls));
if(!linkele)
printf("Erstellen des Elements fehlgeschlagen: Kein freier Speicher verfügbar!\n");
linkele->next=NULL;
linkele->child=newchild;
if(node->link){ // Wenn bereits eins oder mehrere Kind-Elemente bestehen
while(node->link->next)
node->link=node->link->next;
node->link->next=linkele;
}
else{ // Fall, dass noch keine Kind-Liste zugewiesen wurde
node->link=linkele;
}
}
/** Funktion createStructure
* Erzeugt Datenstruktur aus String
* IN: - input: Konstrukt der eingelesenen Graphendatei
* RETURN: gibt Wurzelknoten des erzeugten Graphs zurück
*/
graph *createStructure(char *input){
graph *root=NULL;
tmpls *list=NULL;
int i=-1,o1=-1,o2=-1;
char c='0',
*tmp=strtok(input, DELIMITER); //erstes "Teilen" des Strings
//Definition des ersten Punktes, der den Startpunkt (Wurzel) darstellt
if ((sscanf(tmp, "%i:%c", &i, &c) == 2) && (c>=65) && (c<=90) && (i>0) && (i<10000)){
root=createNewNode(i,c); //Startpunkt des Graph erzeugen, festhalten
appendToList(root, &list); // und dann in Liste packen
tmp=strtok(NULL, DELIMITER); //String erneut teilen
}
else
printf("Fehlerhafte Definition des Wurzelelements! Einlesen wird abgebrochen.\n");
while(tmp){ //So lange String noch nicht abgearbeitet ist
// Definitionsoperation: GANZZAHL:GROßBUCHSTABE //
if ((sscanf(tmp, "%i:%c", &i, &c) == 2) && (c>=65) && (c<=90) && (i>0) && (i<10000)){
appendToList(createNewNode(i,c), &list); //neu erzeugten Knoten in Liste hängen
}
// Zuweisungsoperation: GROßBUCHSTABE->GROßBUCHSTABE//
else if((sscanf(tmp, "%i->%i", &o1, &o2) == 2) && (o1>0) && (o1<10000) && (o2>0) && (o2<10000)){
addChildToNode(getAddressFromList(list,o1),getAddressFromList(list,o2)); //Beide Knoten aus Liste holen und einander zuordnen
printf("%i zeigt auf %i (%p->%p)\n", o1,o2,getAddressFromList(list,o1),getAddressFromList(list,o2));
}
else{ // Fehlerhafte Syntax->Abbruch
printf("Fehlerhafter Dateiinhalt: Syntaxfehler! Das Einlesen wird abgebrochen.\n");
return NULL;
}
tmp = strtok(NULL, DELIMITER); //fortführendes Teilen des Strings
}
removeList(list); //Am Ende: Temporäre Liste auflösen
return root; // und Wurzelelement zurückgeben
}
void main(void){
graph *gstructure=NULL;
char graphdata[]="1:A;2:B;3:C;4:E;5:F;6:D;7:E;8:F;9:D;1->2;1->3;1->4;1->5;2->6;2->7;3->8;3->9;";
gstructure=createStructure(graphdata);
}
