LinkedList.push - nil-Zeiger zuweisen - seltsames Verhalten

Symbroson · Verfasst: Mo 18.12.17 18:07

Hallo EE,
wir haben in Info kürzlich mit Zeigern und verlinkten Listen in Delphi angefangen. Deswegen habe ich begonnen mir eine LinkedList-Klasse mit typischen Funktionen wie zB auch das essenzielle push() zu basteln. An sich ist das ja eigentlich kein Problem. Dabei bin ich über folgenden seltsamen Sachverhalt gestolpert:

Ich suche ja in der push-Funktion erst einmal das letzte Element, also den nil-Zeiger, um diesen dann mit new() erstellen und zuweisen zu können.
Wenn ich aber meinen temporären such-Zeiger habe, wird mit dem nicht das Element der Liste erstellt, sondern nur das meines temp-Zeigers (obwohl ja beide dieselbe Speicheradresse enthalten).

Meine Lösung bisher war, meinen temp-Zeiger als einen Zeiger auf den Zeiger auf ein Listenelement zu definieren - das funktioniert dann auch.
Mich wundert nur, warum die erste Variante das nicht tut.

Der Quelltext bringt vielleicht etwas Licht in die verwirrede Beschreibung:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

//1st variant: doesn't work
procedure lList.push(v:integer);
var cur: pNode;
begin
  cur := head;
  while cur <> nil
  do cur := cur^.next;
  new(cur);
  cur^.value := v;
  cur^.next := nil;
end;

// 2nd variant: works
procedure lList.push(v:integer);
var cur: ^pNode;
begin
  cur := @head;
  while cur^ <> nil
  do cur^ := @cur^^.next;
  new(cur^);
  cur^^.value := v;
  cur^^.next := nil;
end;

(vollständiger Code im Anhang)

Anmerkung: Ich weiß dass das Programm einen Memory-Leak enthält, weil ich die Nodes und Zeiger noch nicht zerstöre - das kommt noch...

LG,
Symbroson

Einloggen, um Attachments anzusehen!

_________________
most good programmers do programming not because they expect to get paid or get adulation by the public, but because it's fun to program. (Linus Torvalds)

Ehemaliges Mitglied Erhaltene Danke: 1

- Nachträglich durch die Entwickler-Ecke gelöscht -

Symbroson · Verfasst: Di 19.12.17 07:40

Zitat:

zumal ich auch nicht weiss, wie push() an sich funktioniert

das ist angelehnt an javascript listen - push soll ein Element der liste hinten hinzufügen. In c++ wird das meistens push_back() genannt, in python append.

Zitat:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

procedure lList.push(v:integer);
var cur: pNode;
begin
  cur := @head;
  while cur <> nil 
  do cur := cur^.next;
  New(cur);
  cur^.value := v;
  cur^.next := nil;
  Dispose(cur);
end;

So wird das leider nichts, da der Listenkopf (das erste Element in der Liste) schon ein Zeiger ist (deswegen pNode - p für pointer)
meine Funktionierebde Variante arbeitet dann wie gesagt mit Zeigern auf Zeiger auf Nodes.

Zitat:

Benutz' bitte den Prefix T für Klassen und I für Schnittstellen

Ich mag diese Präfixe nicht besonders - Delphi scheint damit auch die einzige Sprache zu sein die sowas macht (vllt noch einige verwandte Sprachen wie Lazarus)
Ja vielleicht macht es den Code minimal verständlicher...

_________________
most good programmers do programming not because they expect to get paid or get adulation by the public, but because it's fun to program. (Linus Torvalds)

Ehemaliges Mitglied Erhaltene Danke: 1

- Nachträglich durch die Entwickler-Ecke gelöscht -

Symbroson · Verfasst: Di 19.12.17 21:12

Zitat:

Push() bzw. push_back() fügt also das neue Element (PNode) immer am Listenende hinzu?
Das muss ich selber mal probieren.

ja, das sollte es theoretisch - wobei pNode eben immer ein Zeiger auf das Listenelement selbst ist - Node ist das echte Element

Zitat:

Die vector-Klasse in VC++ ruft darin die Methode insert() auf, und diese wiederum replace(), unter bestimmten Bedingungen.

vermutlich, um an quelltextlänge einzusparen - obwohl es schon so ewig dauert wenn man solche Komponenten ohne vorkompilation importiert.

Zitat:

Das zu übernehmen wäre mühsamer als dein Beispiel.

ich empfehle einfach mit meinen qt aus dem Anhang herumzuexperimentieren. mir geht es eigentlich nur darum, warum ich mit einer Kopie eines Zeiger das Objekt an der Stelle des ursprünglichen Zeigers nicht erstellen kann, sondern mit einem Zeiger auf diesen Zeiger arbeiten muss.

_________________
most good programmers do programming not because they expect to get paid or get adulation by the public, but because it's fun to program. (Linus Torvalds)

bole · Beiträge: 107 Erhaltene Danke: 15 win 10

Hallo

Es ist zwar schon lange her das ich so was in Delphi programmiert habe aber ich glaube nicht das die eine oder andere Version funktioniert... Für mich fehlt da etwas wesentliches.

Du generierst zwar mit new(cur) ein neues Element Adresse auf dem Pointer cur. Jedoch speicherst Du diesen Pointer nicht im aktuellen Element sondern wirfst ihn einfach in die Tonne :shock:

So hast Du nie eine Verknüpfung. Du benötigst noch einen 2. Pointer der auf das letzte Element zeigt in dem Du den Pointer cur als next speichern musst.

Gruss

Bole

_________________
ein programm macht nicht das was du willst sondern was du schreibst!

Symbroson · Verfasst: Di 19.12.17 23:06

Nunja das liefe dann in etwa auf die zweite Variante mit dem Pointer-Pointer hinaus...

Zitat:

ich glaube nicht das die eine oder andere Version funktioniert...

doch, die zweite Variante funktioniert wie gesagt (zwangsläufig)

Ich dachte eigentlich dass new() das Objekt an der Stelle erzeugt auf den mein Pointer zeigt, aber anscheinend ist dem irgendwie nicht so.

_________________
most good programmers do programming not because they expect to get paid or get adulation by the public, but because it's fun to program. (Linus Torvalds)

Symbroson · Verfasst: Di 19.12.17 23:16

Ah doch vielleicht ist genau das der Grund - cur ist ja nach der Suche ein nil-Zeiger, genauso wie das Element selber. demnach wird der Zeiger cur erst mit new() erstellt, aber das Listenelement selber bleibt logischerweise ein nil-Pointer.
Das wird es sein

Danke

Ach ja ich muss mich entschuldigen - ich rede die ganze Zeit von 'erster und zweiter Variante' - dabei waren die beiden im Ausgangspost genau anders herum notiert. Tut mir leid falls das verwirrung gestiftet hat ^^
Jetzt ist es jedenfalls richtig herum

_________________
most good programmers do programming not because they expect to get paid or get adulation by the public, but because it's fun to program. (Linus Torvalds)

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme