Zwei Fragen zu verketteten Listen

[Kanone (Gast)]

Hallo,

ich spiele gerade mit verschiedenen Datenstrukturen in C, um was zu 
lernen. Dabei kommen gerade zwei Fragen auf, die ich mit 
Suchmaschinen-Hilfe nicht klären konnte.

1. Frage: Wenn ich eine verkettete Liste als struct deklarieren möchte, 
wie bekomme ich dann den Verweis auf das nächste Elemente innerhalb der 
struct definiert? Zu dem Zeitpunkt kennt der Compiler das ja noch nicht 
und spuckt eine Fehlermeldung aus:

typedef struct{
  int variable_1;
  int variable_2:
  liste_t *next;
} liste_t;

Ich könnte einfach eine Variable definieren, so wie es in den meisten 
Beispielen im Netz gemacht wird, dann geht es:

struct liste
{
  int variable_1;
  int variable_2;
  liste *next;
}

Ich brauche aber eine saubere Typdefinition, möchte die Algorithmen 
auslagern.

2. Frage: Wenn ich neue Elemente zufüge, mache ich dann jedes Mal ein 
malloc() für ein paar Bytes? Wie ist das mit der Speicherverwaltung, ist 
das nicht furchtbar ineffizient? Ich habe gelesen, dass bei vielen 
Betriebssystemen die kleinst allozierbare Einheit schon ein paar kb groß 
ist, das heißt bei vielen Elementen in der Liste verbrauche ich doch ein 
vielfaches des eigentlich nötigen Speicherplatzes, oder?

Wie lösen Profis das Problem?

Danke und Gruß,
Martin

[Franz H. (dl7avf)]

Martin,
die übliche Deklaration einer einfach verketteten Liste in Standard-C 
ist wie folgt:

// in Header-Datei list.h

// Struktur eines Listenelements.
struct listen_element
  {
  int idata; // oder was auch immer als Datenobjekt benötigt wird.
  struct listen_element *pnext;  
  };

// Typ eines Listenelements. 
typedef struct listen_element listen_t;  

// in main.c z.B.

// Beispiel für statische Listenelemente:
listen_t listen_element1;
listen_t listen_element2;

zu 2.
Die Speicherverwaltung bei malloc() usw. macht üblicherweise die 
C-Laufzeitbibliothek und ist dabei auf den im Heap angelegten 
Speicherbereich beschränkt. Was darüber hinausgeht ist 
betriebssystemabhängig (falls bei Microcontrollern überhaupt ein 
Betriebssystem vorhanden ist).

Schöne Grüsse,
Franz

[Klaus W. (mfgkw)]

Das ist richtig, aber vielleicht etwas näher an der ersten Frage:

// der Trick ist, der struct hier bereits einen Namen zu geben:
typedef struct s_liste{
// dadurch kann man die struct entweder als 'struct s_liste'
// oder als 'liste_t' verwenden, beides ist eigentlich gleichwertig.
// Der einzige Unterschied ist, daß 'struct s_liste' bereits
// hier bekannt ist, 'liste_t' erst später.
  int variable_1;
  int variable_2:
  struct s_liste *next; // das geht
} liste_t; // ab hier erst gibt es 'liste_t'

[(prx) A. K. (prx)]

Man kann auch den gleichen Namen verwenden:

typedef struct liste_t {
  ...
  struct liste_t *next;
} liste_t;

[Klaus W. (mfgkw)]

Zur 2. Frage:
"effizient" und "ineffizient" sind dehnbare Begriffe.
Ein Allokieren und wieder Freigeben vieler Elemente auf dem Stack wird 
sicher langsamer sein, als dieselben Elemente nebeneinander auf dem 
Stack zu haben.

Aber so schlecht ist es dann in der Regel auch nicht implementiert, und 
wenn doch muß man die C-Lib wechseln.

Im allgemeinen Fall ohne Nebenbedingungen wird es nicht viel effizienter 
gehen.
Weiß man dagegen Randbedingungen, kann man evtl. etwas Schnelleres 
finden.

Beispielsweise müssen Obstacks (GNU-libc, kein Standard: 
http://www.gnu.org/software/libc/manual/html_node/Obstacks.html#Obstacks 
) in der umgekehrten Reihenfolge freigegeben wie allokiert werden, sind 
dann aber effizienter.
Oder man hat eine (nicht zu hohe) Obergrenze der Anzahl allokierter 
Elemente, dann kann man die Elemente in einem Feld halten.

[Klaus W. (mfgkw)]

A. K. schrieb:
> Man kann auch den gleichen Namen verwenden:

ja, aber es ist eine Stilfrage, ob man das möchte :-)

Wenn du zwei Kinder hast, kann das Standesamt wahrscheinlich nichts 
dagegen machen, wenn du beiden denselben Namen gibst.
Empfehlen würde ich es trotzdem nicht, auch nicht bei Zwillingen.

[(prx) A. K. (prx)]

Klaus Wachtler schrieb:

> ja, aber es ist eine Stilfrage, ob man das möchte :-)

Selbst bei deinen Zwillingen handelt es trotz aller Ähnlichkeit um 
getrennte Individuen. Hier aber bezeichnet es exakt die selbe Sache. 
Daher habe ich damit kein Problem.

Etwas ungünstig wäre das jedoch bei

typedef struct listeA {
   ...
} listeB;

typedef struct listeB {
   ...
} listeA;

[Klaus W. (mfgkw)]

naja, ist halt Geschmackssache.

Wenn das irgendwas in struct irgendwas Teil von struct irgendwas ist und 
nur damit zusammen zu einem Typ wird, dann ist das irgendwas, das ohne 
struct ein Typname ist, für mich nicht dasselbe.
Wenn man z.B. jeden Typ mit angehängtem _t kennzeichnet, was macht man 
dann mit dem Ding nach struct?
Es ist kein eigenständiger Typ, trotzdem ein _t anhängen?
Aber egal...

In C++ hat es sich eh erledigt, weil man das struct bei der Verwendung 
des Typs weglassen kann und damit auch das typedef in diesem Fall 
obsolet wird:

struct liste_t
{
  int      i;
  liste_t *next;  // geht ohne struct davor nicht in C, nur C++
};

liste_t  *knurzel = NULL; // geht ohne struct davor nicht in C, nur C++

[Klaus W. (mfgkw)]

PS: ich weiß natürlich, daß das Korinthenkackerei ist ist und bestehe 
jetzt nicht auf eine endgültigen Lösung der Frage :-)

[(prx) A. K. (prx)]

Aber selbst in C++ ist es zulässig, was bei eine C/C++ Mix eine gewisse 
Rolle spielt.

[Klaus W. (mfgkw)]

Zulässig ja, was aber die Frage nach dem Stil nicht beantwortet :-)

[(prx) A. K. (prx)]

Klaus Wachtler schrieb:

> PS: ich weiß natürlich, daß das Korinthenkackerei ist ist und bestehe
> jetzt nicht auf eine endgültigen Lösung der Frage :-)

Hehe... Es ist ausser uns eh noch niemand wach, wir stören also 
niemanden mit der Korinthenkackerei. ;-)

[Klaus W. (mfgkw)]

A. K. schrieb:
> typedef struct listeA {
>    ...
> } listeB;
>
> typedef struct listeB {
>    ...
> } listeA;

Das geht übrigens bei C noch durch, bei C++ nicht mehr.

[(prx) A. K. (prx)]

Klaus Wachtler schrieb:

> Zulässig ja, was aber die Frage nach dem Stil nicht beantwortet :-)

Gewissermassen schon. In C++ musste man nämlich für genau diese 
Möglichkeit eigens eine Extrawurst braten, da es sich anders als in C 
formal um eine doppelte Definition des gleichen Namens im gleichen 
Namespace handelt. Das hätte Stroustrup nicht gemacht, wenn bloss ein 
einzelner Spassvogel in mikrocontroller.net das elegant gefunden hätte.

[Klaus W. (mfgkw)]

A. K. schrieb:
> Es ist ausser uns eh noch niemand wach,

Vielleicht mal ein neues Feature bei den Betreibern einfordern:
Eine Option, tagsüber den Unsinn ausblenden zu können, der nachts so 
entsteht?

[Klaus W. (mfgkw)]

A. K. schrieb:
> einzelner Spassvogel

Wer?

[Klaus W. (mfgkw)]

Aber im Ernst: daß man in C++ das Geeier abgeschafft hat mit dem 
unvollständigen Typnamen und deshalb immer struct irgendwas... schreiben 
muß, ist doch nett. Dadurch entfällt ja auch gleich das typedef und es 
wird schon etwas übersichtlicher.
Es stören sich doch nur die Leute daran, die unbedingt seit '45 alles 
mit typedef machen wollen.

[(prx) A. K. (prx)]

Klaus Wachtler schrieb:

> A. K. schrieb:
>> einzelner Spassvogel
>
> Wer?

Uns Uhu erkennt Spass meist nichtmal dann, wenn er mit dem Holzhammer 
daherkommt, also dieser Vogel kanns nicht sein.

[(prx) A. K. (prx)]

Klaus Wachtler schrieb:

> Aber im Ernst: daß man in C++ das Geeier abgeschafft hat mit dem
> unvollständigen Typnamen und deshalb immer struct irgendwas... schreiben
> muß, ist doch nett.

Keine Frage. Das war sinnvoll.

Allerdings hatte Stroustrup an anderer Stelle dafür eigens ein paar neue 
faule Eier ins Nest gelegt. Meine Begeisterung über seinen Sinn für 
Syntax hält sich daher in Grenzen.

[Klaus W. (mfgkw)]

Da wiederum gebe ich dir Recht.

Wenn gar nichts mehr hilft, muß man irgendwo ein typename hinschreiben, 
weil der Compiler selber nicht mehr weiter weiß. In solchen Fällen 
zweifle ich auch manchmal etwas.

Demnächst kommt für den entgegengesetzten Fall vielleicht ein 
nottypename (bzw. um wie gewohnt Schlüsselwörter einzusparen ein 
¨typename oder !typename oder mal wieder auto) zur Klärung, wenn etwas 
eben kein Typ ist.

[Nico S. (nico22)]

Klaus Wachtler schrieb:
> Wenn gar nichts mehr hilft, muß man irgendwo ein typename hinschreiben,
> weil der Compiler selber nicht mehr weiter weiß.

Das hat nicht unbedingt damit etwas zu tun, dass der Compiler das nicht 
mehr weiß, sondern dass in diesen Fällen das "typename" vom Standard 
gefordert ist, selbst wenn der Compiler es besser wüsste:

http://pages.cs.wisc.edu/~driscoll/typename.html

> This rule even holds if it doesn't make sense even if it doesn't make sense to
> refer to a non-type.