Anfägerfrage: Baum dynamisch bauen

mr_sol

Hallo

Vielleich hat jemand von euch eine Idee oder Hinweis.

Ich arbeite gerade auf einen ATMEL in C und müsste dynamische Bäume einlegen.

Das Beispiel dient zu meinem Verständnis.

Es gibt einen Raum in welchen 1..n Objecte abgelegt werden. Die Anzahl ist von Anfang an nicht feststellbar und wird mit der Zeit ergänzt (Im Orginal sind es Sensoren welche sich erst alle 10 Minuten melden). Leider gibts kein new für den Compiler.

Hier mein Ansatz

typedef struct{        
            char name[];
          } object;

typedef struct{            
            int id;
            char name[];
            object *link;
          } room;                  

room myroom={};          

void setup()
{ 

??

}

void loop()
{ 
}

Vielen Dank im voraus.

DaRe

Hi,
sowas wie malloc, calloc geht nicht?

"new" als Schlüsselwort, kenn ich auch nur von objektorientierten Programmiersprachen.

mr_sol

Versuch klappt leider nicht: invalid conversion from 'void*' to 'room*'

typedef struct{        
            char name[];
          } object;

typedef struct{            
            int id;
            char name[];
            object *link;
          } room;                  

int *rooms;

void setup()
{  
  //**** Versuch einen Raum dynamisch zu erzeugen
  rooms = malloc(sizeof(room));
}

void loop()
{ 
}

Belli

Was ist mit:
rooms = (room*) malloc(sizeof(room));
?

Die Fehlermeldung passt nicht zu deinm Code.
rooms sollte schon ein Zeiger auf die room sein.

Und dann kannst du auch casten.
Benutzt du C++ ?

DaRe

was ist mit

int *rooms;

mr_sol

Erstmals vielen Dank für eure Unterstützung

Ich benutze C nicht C++

Fehlermeldung: invalid conversion from 'void*' to 'int*'

typedef struct{        
            char name[];
          } object;

typedef struct{            
            int id;
            char name[];
            object *link;
          } room;                  

void setup()
{  
  int *rooms;
  rooms = malloc(sizeof(room));
}

void loop()
{ 
}

bzw

Fehler:cannot convert 'room*' to 'int*' in

typedef struct{        
            char name[];
          } object;

typedef struct{            
            int id;
            char name[];
            object *link;
          } room;                  

int *rooms;

void setup()
{  
  rooms = (room*) malloc(sizeof(room)); 
}

void loop()
{ 
}

mr_sol schrieb:

Erstmals vielen Dank für eure Unterstützung

Ich benutze C nicht C++

Fehlermeldung: invalid conversion from 'void*' to 'int*'

Dann stell deinen Compiler auch in den C Modus.

Schau mal hier unter Punkt 1:http://www.c-plusplus.net/forum/292950

C++ verlangt den Cast an der Stelle.

mr_sol

Es ist ein reiner C Compiler (für Microcontroller)

Mein erster Versuch oben war ein Ansatz, welcher sicher Fehler beinhaltet. Mein Ziel einen dynamischen Baum zu bauen.

Hat jemand ein Beispiel zum Nachvollziehen?

Rab-Bit

Wieso möchtest du denn einen Baum erstellen und welche Eigenschaften soll er haben (z.B. binärer Suchbaum)? Wenn du nur eine dynamische Anzahl von Objekten verwalten musst, würde sich eine verkettete Liste oder ein Vektor empfehlen (ersteres, wenn Objekte häufig entfernt werden).
Ansonsten solltest du dich vielleicht noch mal ein bisschen mit den Grundlagen von C beschäftigen (Zeiger usw.), bevor du dich an dynamischen Datenstrukturen versuchst. Sowas wie

int *rooms;
// ...
rooms = (room*) malloc(sizeof(room));

sollte dich eigentlich selbst zum Stutzen bringen. Wieso definierst du rooms als int-Zeiger, wenn er auf eine room-Struktur zeigen soll. Sinnvoller wäre (und wurde hier ja schon mehrfach angedeutet):

room *rooms = (room*) malloc(sizeof(room))

baum? warum so etwas unhandliches? tuts nicht ne liste oder ein array?
welchen compiler benutzt du?

char name[];

so etwas in einer struct, das sieht mir nach c99 syntax aus.
rückgabewerte von malloc sollte man nicht casten, das ist oft ne typische c++ compiler meldung.

mr_sol

Danke für euere Rückmeldungen

zu juppi++

Compiler:avr-gcc (für ATML MCs)
2 dynamische Array (rooms,object) wobei die rooms auf objecte verweisen würde (noch nicht probiert)

typedef struct{        
            char *name;
          } object;

typedef struct{            
            int id;
            char *name;
            object link[];
          } room;                  

void setup()
{  
  //**** 
  room *rooms = (room*) malloc(sizeof(room)); //OK
  rooms->id=12;                               //OK
  rooms->name="Test";                         //OK

  rooms->link[0]->name="A";                   // rooms->link[0] klappt ->name="A" nicht mehr
  rooms->link[1]->name="B";                   

}

void loop()
{ 
}

Langsam verstehe ich:
Ein Zeiger auf room zeigt auf Speicheradresse welche durch malloc frei gegeben wird. OK?

Was ich noch nicht verstehe:
Um mehrer Objecte "innerhalb" von rooms zu bekommen klappt es mit rooms->link[0],usw jedoch wie spreche ich diese an?

Der Hacken malloc() schluckt 450Bytes

Wutz

mr_sol schrieb:

Ich arbeite gerade auf einen ATMEL in C und müsste dynamische Bäume einlegen.
...
Leider gibts kein new für den Compiler.

Köstlich.

Gehe davon aus, dass ein gcc alles richtig macht, und wenn du Fehler erhälst, liegt es an dir und nicht am Compiler.
Gehe davon aus, dass du nicht weißt, was "dynamische Bäume" und "dynamische Arrays" sind oder gar die Unterschiede.
Gehe davon aus, dass dein genannter Code unkompilierbar ist und dass du die o.g. Hinweise zum laienhaften malloc Cast und sinnfreier Verwendung von verketteten Listen aufgrund deiner eigenen Unkenntnis ignorierst und diese auch durch mehrfache Wiederholungen nicht richtig werden.

CStoll

Der Index-Zugriff hat die Dereferenzierung schon gratis enthalten, da mußt du den Zeiger nicht nochmal extra dereferenzieren. D.h. das heißt korrekterweise rooms->link[0].name="A"; .

(btw, diese Konstruktion mit den größenlosen Arrays (object link[];) funktioniert echt in C?)

mr_sol

Gehe davon aus, dass ein gcc alles richtig macht, und wenn du Fehler erhälst, liegt es an dir und nicht am Compiler....usw

Ich bin C-Anfänger und bin hier etwas zu lernen. Deine Ansage bringt mich keinen Schritt weiter, ich finde sie ziemlich unhöflich.

Vielen Dank an alle anderen.

mr_sol schrieb:

Der Hacken malloc() schluckt 450Bytes

Du willst "dynamische Bäume" machen. Dynamsiche Speicherverwaltung läuft in C über malloc() . Das von dir vermisste new() braucht sicher mehr Speicher.

mr_sol schrieb:

rooms->name="Test";                         //OK

Ist nicht OK. Es funktioniert. Aber nicht so wie du denkst.
Strings werden in C anders behandelt als integrale Typen (int, double).

mr_sol schrieb:

...
  rooms->link[0]->name="A";                   // rooms->link[0] klappt ->name="A" nicht mehr
  rooms->link[1]->name="B";

Wo hast du denn link[0] bzw link[1] Werte zugewiesen?
Zudem macht ->name="A"; nicht das was du denkst.

mr_sol schrieb:

Ich bin C-Anfänger

Mit welchen Programmiersprachen hast du dich denn bis jetzt vergnügt?

mr_sol

Bisher: OOP-PHP, SQL, VB, JS, XSLT also nix systemnahes.

Im Hintergrund meiner Frage steht ein Projekt bei welchen Sensordaten im MC gepuffert werden. Leider können es zwischen 1....n sein. Würde ich zb 150 Datensätze in einem Array reservieren und nur 3 wirklich empfangen, schmerzt der verlorene Speicherplatz. 32 kByte sind ja nicht allzuviel.

Daher der Versuch einer Lösung mit dynamischen Arrays oder Variablen (ich hoffe es richtig Ausgedrückt zu haben)

Malloc kostet fast 450 Bytes. Vielleicht ist mein Lösungsansatz vollkommen falsch und es gibt eine bessere einfachere Lösung.

Wenn deine 150 Datensätze in den Speicher (RAM) passen ist doch gut.
Der MC macht doch sonst nichts weiter. Mit dem freiem Speicher kannst du doch sonst nichts anfangen.
Und deine Baumverwaltung ist viel teuerer als die 450 Byte.

Nimm Arrays.

Und lies die Kapitel über Arrays, Zeiger und Strings gründlich und mehrmals durch.

Wutz

mr_sol schrieb:

Ich bin C-Anfänger und bin hier etwas zu lernen. Deine Ansage bringt mich keinen Schritt weiter, ich finde sie ziemlich unhöflich.

Unhöflich ist, dass du die dir mehrfach gezeigten Fehler ignorierst und anschließend diesen uncompilierbaren, falschen und sinnfreien Code wiederholst und damit zum Ausdruck bringst, dass du eben nicht lernen willst.
Das Problem mit euch Anfängern ist auch, dass diese (wie du in deinem Beitragstitel offenbarst) keine Ahnung von C haben, aber schon ganz genau wissen, mit welchen Mitteln (von denen sie auch nur nebulöse Vorstellungen haben, in deinem Fall "dyn. Bäume") sie ihre Aufgabenstellung umsetzen wollen.

Haken schreibt man in diesem Zusammenhang richtig Haken und nicht Hacken.

DaRe

Statt dynamisch zu arbeiten, könntest du auch eine ungefähre Schätzung für den maximal nötigen Puffer bestimmen und deinen Puffer dennoch statisch anlegen.
=> Nachteil wäre dann natürlich notfalls Daten "wegschmeißen" zu müssen, was bei kritischeren Systemen wohl unverzeihlich wäre.

Keine Ahnung, vllt. kannst du die Schätzung zum Puffer mit ner Gauß-Verteilung co. und weiteren Werten noch iwie optimieren.