Typdeklaration von Verbundtypen und Lineare Listen

Hallo zusammen,

ich bin mal wieder im Rahmen meines Programmierkurses an der Fernuni an ein Problem gestossen, das ich zum einen in Pascal nicht ganz kapiert habe und von dem ich zweitens nicht weiß wie ich das in C umsetzen kann.

Also zunächst würde mich interessieren wie ich einen Verbundtyp für Lineare Listen erstelle? Unter Pascal sieht das etwa so aus:

type

tRefListe : ^tListe;
tListe = record
info : integer;
next : ^tRefListe
end;

var

Zahl : integer;
Zeiger : ^tListe;

Ich hoffe ich habs auch richtig wiedergegeben (sorry aber das Skript liegt zu Hause).

Wenn man nun eine Lineare Liste aufbauen will kann man sich doch dann innerhalb einer Funktion oder einer Prozedur durch die Liste hangeln. Hierzu benutzt man Zeiger. Ich kapiere nicht ganz wie das funktioniert und wie man das realisiert.

Kann mir das jemand mal anhand eines Beispiels erklären.

Danke

Stefan

[thommy]

Zunächst gestatte mir die Anmerkung, dass Dein Problem wesentlich eleganter in C++ gelöst werden könnte.

Aber nun zum "reinen C".

Mit der Struktur hast Du hoffentlich alles verstanden, "next" verweist auf ein weiteres Element vom selben Typ (struct Liste). Um nicht immer "struct Liste" schreiben zu müssen, definiere ich mir dafür den Typ "TListe".

Das "Herzstück" ist die Funktion "Insert". Sie bekommt einen Zeiger auf ein Element der Liste und fügt ein neues Element an dessen Ende an.

Zwei Fälle müssen unterschieden werden:

1. Der Zeiger, der übergeben wird ist NULL (also es gibt noch gar kein Element in der Liste).
Also erzeuge ich Speicherplatz für das neue Element, belege den Wert (im Beispiel "number") und setze den Zeiger auf das folgende Element auf NULL (es gibt ja vorerst kein weiteres Element). Den Zeiger auf das soeben erzeugte Element gebe ich zurück.

2. Der Zeiger "zeigt" bereits auf ein Element. Jetzt muss das letzte Element der Liste gesucht werden ("while ...").
Habe ich den Zeiger darauf gefunden, muss ein neues Element erzeugt werden und an dessen "next"-Zeiger angehangen werden. Ich bevorzuge, dan Zeiger auf dieses neue Element zurück zu geben...

Alles klar?

Thomas

[Dieser Beitrag wurde von thommy am 13. November 2000 editiert.]

Danke Thomas,

ich muß mir das jetzt nochmal ein wenig verinnerlichen und am Wochenende dann mal ein wenig rumtesten, aber ich denke das ich es jetzt kapiert habe.

Gruß

Stefan

[thommy]

Nicht die eleganteste Lösung, aber ich habe derzeit keinen Compiler zur Verfügung, um das Beispiel zu testen:

<pre>
#include &lt;stdio.h&gt

struct Liste {
int number;
struct Liste* next;
};

typedef struct Liste TListe;

TListe* Insert ( TListe* element, int value ) {
if ( element == NULL ){
element = (TListe*) malloc (sizeof(TListe));
element-&gt;next = NULL;
element-&gt;number = value;

return element;
}

while ( element-&gt;next )
element = element-&gt;next;

element-&gt;next = (TListe*) malloc (sizeof(TListe));
element-&gt;next-&gt;next = NULL;
element-&gt;next-&gt;number = value;

return element-&gt;next;
}

int main() {
TListe* mListe=NULL;
int i;

mListe = Insert (mListe, 1000 );
// Zur Demonstration werden 5 weitere Elemente eingefügt
for ( i=0; i &lt; 5; i++ )
Insert (mListe, i );

# Ausgabe aler Elemente
while ( mListe ) {
printf("%d\n", mListe-&gt;number);
mListe = mListe-&gt;next;
}
}
</pre>

Thomas

Schon mal vielen Dank, aber ich glaube ich habe noch nicht ganz verstanden wie das mit den Zeigern von Element.Next wieder auf den Anfang der Liste bzw. von der Variable auf den Typ funktionukkelt. Ich meine vom Ablauf stelle ich mir das etwa wie folgt vor:

I.)

++++++++++++++++
+ Element.info + -----> zeigt auf Null oder
++++++++++++++++ eine Initalisierung

++++++++++++++++
+ Element.next + \ Next zeigt auf den
++++++++++++++++ \ nächsten Anfangswert
\
II.) /
/
++++++++++++++++ <
+ Element.info +
++++++++++++++++

Wie muß ich mir das nun mit den Zeigern und Typen in der Theorie und in der Realisierung vorstellen. Vielleicht könntest Du mal kurz erläutern welche Variable/Zeiger zu welchem Zeitpunkt wohin zeigt.

Stefan