Listen in C

[wing354]

Moin moin,

ich bräuchte mal eure Hilfe, und zwar bin ich gerade dabei meine Klausur vorzubereiten für die Programmiersprache C und bin nun dabei angekommen Listen richtig verstehen zu wollen, allerdings bin ich gleich am Anfang ziemlich hängen geblieben, weil ich einfache Ausdrücke nicht verstehe. Es wäre super, wenn ihr mir ein bisschen unter die Arme greifen könntet damit ich das folgende verstehe:

Code: Alles auswählen

void list_append_end ( linked_list *l , node * n) {
node * tmp ;
// invalid pointer
if (! l || !n) {
return ;
}
// list is empty
if (!l - > head ) {
l -> head = n ;
return ;
}
tmp = l -> head ;
// iterate to the end
while ( tmp -> next ) {
tmp = tmp -> next ;
}
// append n
tmp -> next = n;
return ;
}

Das Programm soll dazu dienen ein Element am Ende einer Liste einzufügen. Allerdings fängt es gleich am Anfang bei mir schon an, dass ich etwas nicht verstehe. Beim Ausdruck "node *tmp" bin ich mir schon unsicher was dieser bewirken soll, bzw. wozu der Pointer *tmp dient, da dieser auch in anderen Beispielen auftaucht gehe ich davon aus, dass dieser eine höhere Bedeutung hat. Die zweite Sache bei der ich im Verständnis nicht weiterkomme befindet sich bei der Zeile "if (!l - > head)", was bewirkt der Pfeil "->" ?
Sagt der einfach aus, wenn "l" einen Wert hat, also wahr ist, wird dieser als falsch angenommen und in "head" gespeichert? Damit die Liste als leer angenommen wird?
Ich hoffe ihr könnt mir weiterhelfen, damit ich auch die verketteten Listen endlich kapiere.
Mit freundlich Gruß
wing354

[Xin]

Ich bin gerade unterwegs, daher heute Abend eher was konkretes.

Übergangsweise schau mal hier: Listen

[cloidnerux]

Beim Ausdruck "node *tmp" bin ich mir schon unsicher was dieser bewirken soll, bzw. wozu der Pointer *tmp dient, da dieser auch in anderen Beispielen auftaucht gehe ich davon aus, dass dieser eine höhere Bedeutung hat

Grundsätzlich tut jede Variable(auch Pointer) das Gleiche: Werte speichern. Den Sinn einer Variable kannst du also nicht daraus schließen, dass sie Angelegt wurde, sondern was damit gemacht wird.
Effektiv musst du nur deinen Code anschauen, um zu verstehen wofür tmp dient.

Die zweite Sache bei der ich im Verständnis nicht weiterkomme befindet sich bei der Zeile "if (!l - > head)", was bewirkt der Pfeil "->" ?

Dereferenzierung von struct-Elementen. Um auf ein Element eine Structs zu zugreifen nutzt du normalerweise den Punkt "."

Code: Alles auswählen

struct myStruct
{
    int a;
    int b;
}
[...]
myStruct s;
s.a = 5;

Wenn du aber statt einem Objekt des Structs einen Pointer auf eben ein solches Struct hast, müsstest du immer erst dereferenzieren und dann zugreifen:

Code: Alles auswählen

myStruct * pS = &s;
(*pS).a = 5;

Um das eleganter zu machen, hat man den "->" Operator eingeführt, der eben das macht:

Code: Alles auswählen

pS->a = 5;

[wing354]

Code: Alles auswählen

tmp = l -> head ;
// iterate to the end
while ( tmp -> next ) {
tmp = tmp -> next ;

Ich verstehe das jetzt so, dass der Pointer "tmp" zunächst auf den Anfang der list also den "head" zeigen soll, anschließend zeigt "tmp" immer auf das nächste Element bis keines mehr da ist, oder wie ist dieser Ausdruck zu verstehen?

Code: Alles auswählen

tmp -> next = n;
return ;

Dieser Codeabschnitt ist dafür da, wenn "tmp" am Ende angekommen ist, dann wird nun ein zusätzliches Element angefügt, quasi zeigt "tmp" durch das next ins leere, in das aber gleichzeitig ein Element eingefügt wird, ist das so richtig oder wie habe ich das zu verstehen?

[Xin]

Prinzipiell sieht das aus, als hättest Du das soweit verstanden.

tmp wird solange auf den Nachfolger gesetzt, bis es keinen Nachfolger mehr gibt. Das Element, dass keinen Nachfolger hat, ist logischerweise das letzte. Am Ende der Schleife zeigt tmp also auf das letzte Element. Um das neue Element hinten anzufügen, erklärt man das neue Element zum Nachfolger des letzten Elementes.

[wing354]

Wenn ich nun ein Programm schreiben möchte das die Elemente einer Liste zählt, kann man das wie folgt gestalten?

Code: Alles auswählen

int list_count( linked_list *l , node * n){
int i;
node *tmp
tmp = l->head;
while{tmp->next){
tmp=tmp -> next;
i++;
}
return i;
}

Gibt es auch einen Befehl in C, welcher eine Liste komplett löscht?

Und dann hab ich noch ein Programm gefunden, dass die Elemente einer Liste alle um eins nach rechts verschieben soll, welches wie folgt aussieht:

Code: Alles auswählen

void list_rotate(linked_list *l){
l->tail->prev->next=NULL;
l->tail->next=l->head;
l->head->prev=l->tail;
l->head = l -> tail;
l-tail = l->tail->prev;
l->head->prev=NULL;
return;
}

Allerdings hakt es nun beim Verständnis mal wieder, zum Beispiel bei der Zeile "l->tail->prev->next=NULL;", ich würde das so interpretieren wie: l greift auf das Ende der Liste zu, dieses Ende auf das Element davor, welches wiederum auf das Element danach zugreift und diesen gleichzeitig Null setzt, wobei das ja wieder das Ende wäre. Allerdings bezweifel ich, dass das so richtig ist.

[Xin]

Wenn ich nun ein Programm schreiben möchte das die Elemente einer Liste zählt, kann man das wie folgt gestalten?

Code: Alles auswählen

int list_count( linked_list *l , node * n){
int i;
node *tmp
tmp = l->head;
while{tmp->next){
tmp=tmp -> next;
i++;
}
return i;
}

Bitte rücke ein!

Ansonsten ist das Programm theoretisch richtig... probiere es doch aus!?

Du wirst feststellen, dass es nicht funktioniert, es wird immer wieder ein anderes Ergebnis herauskommen.

Gibt es auch einen Befehl in C, welcher eine Liste komplett löscht?

Es gibt in C keine Listen, also auch keine Befehle dafür. Du musst das schon selbst schreiben.

Und dann hab ich noch ein Programm gefunden, dass die Elemente einer Liste alle um eins nach rechts verschieben soll, welches wie folgt aussieht:

Vielleicht schreibst Du solche Programme selbst, dann verstehst Du auch, was Du da tust?

Allerdings hakt es nun beim Verständnis mal wieder, zum Beispiel bei der Zeile "l->tail->prev->next=NULL;", ich würde das so interpretieren wie: l greift auf das Ende der Liste zu, dieses Ende auf das Element davor, welches wiederum auf das Element danach zugreift und diesen gleichzeitig Null setzt, wobei das ja wieder das Ende wäre. Allerdings bezweifel ich, dass das so richtig ist.

Weshalb?
Der Zeiger auf den Nachfolger des Vorgängers des letzten Elementes der Liste wird auf Null gesetzt.

[wing354]

Was meinst du mit "rücke ein" ?

Ich versuche schon möglichst viel selbst zu schreiben, aber trotzdem möchte ich so viele Programme durchdringen und Ideen für mögliche Klausuraufgaben sammeln wie möglich.

Also war meine Interpretation der Zeile richtig? Ich verstehe nämlich nicht, warum vorher auf das Vorgängerelement gezeigt wird, damit danach wieder auf das Nachfolgerelement gezeigt wird. Kann man das nicht abkürzen mit: "l->tail=NULL;" ? Weil ich ja quasi schon am Ende bin, warum muss ich dann einen Schritt zurück, um wieder einen Schritt vorwärts zukommen?

[Xin]

Was meinst du mit "rücke ein" ?

Den Code so zu formatieren, dass man ihn lesen kann:

Code: Alles auswählen

int list_count( linked_list *l , node * n){
  int i;
  node *tmp

  tmp = l->head;
  while{tmp->next){
    tmp=tmp -> next;
    i++;
  }
  return i;
}

Also war meine Interpretation der Zeile richtig? Ich verstehe nämlich nicht, warum vorher auf das Vorgängerelement gezeigt wird, damit danach wieder auf das Nachfolgerelement gezeigt wird.

Es wird nicht auf das Nachfolge-Element gezeigt. Der -> Operator greift auf ein Zeiger-Element zu. Mit dem -> zeigt man also nicht mehr, sondern geht zu dem Element. Schauen wir uns die Unterschiede an:

Kann man das nicht abkürzen mit: "l->tail=NULL;" ?

Nein. l ist die Liste, mit -> greifen wir auf tail zu. Wir arbeiten jetzt also mit dem Wert "tail", der in "l" steht und überschreiben ihn mit NULL.

Schauen wir uns nun "l->tail->prev->next=NULL;" an:
Wir haben den Zeiger l und greifen auf tail zu. Nun haben wir den Zeiger tail und greifen auf das Element zu (->). Damit haben nun den letzten Node der Liste in der Hand und nehmen daraus "prev", was ein Zeiger auf Node ist. Auf den Zeiger wird jetzt zugegriffen (->) und haben jetzt gewissermaßen den Node-Datensatz der letzten Node in der Liste in der Hand und nehmen uns "next" aus dieser letzten Node vor. Das ist wieder ein Zeiger und diesen Zeiger setzen wir auf Null.

Im ersten Fall wird der Zeiger "tail" im Datensatz "l" überschrieben, hier wird der Zeiger "next" im letzten Element der Liste überschrieben.

Weil ich ja quasi schon am Ende bin, warum muss ich dann einen Schritt zurück, um wieder einen Schritt vorwärts zukommen?

Du macht keinen Schritt vorwärts. Du überschreibst den Zeiger, der sagt, wo der nächste Schritt hinführen würde.

[wing354]

Okay, in Zukunft werde ich das mit dem formatieren beachten!

Ich denke ich habe es jetzt kapiert, danke für deine Hilfe!