Warum hier Doppel-Pointer?



  • Hallo zusammen,

    ich soll eine einfach-verkettete Liste erstellen. Über ein Menü soll man wählen können, int-Werte sortiert zu speichern, zu löschen oder auszugeben. Hätten wir dazu keine Vorgaben bekommen, hätte ich kein Problem damit, diese Aufgabe zu lösen, aber leider sollen wir vorgegebene Funktionen verwenden. Ich zitiere:

    Programmieren Sie in C eine sortierte einfach verkettete Liste für int-Werte mit folgenden Operationen:

    struct Knoten
    {int key; struct Knoten *next;};
    
    struct Knoten * linit()
    

    : Erzeugen einer leeren Liste. Sie besteht nur aus dem Endelement.

    void linsert (struct Knoten ** schlange, int key)
    

    : Sortiertes Einfügen eines Elementes in die Liste

    int ldelete (struct Knoten ** schlange, int key)
    

    : Entfernen des
    Elementes mit Schlüssel key aus der Liste. Ist ein Element mit key nicht enthalten, soll natürlich eine Meldung kommen.

    int isempty (struct Knoten * schlange)
    

    : Rückgabe von 1, falls die Liste leer ist, 0 sonst.

    void printList (struct Knoten * schlange)
    

    : Ausgabe der in der Liste gespeicherten Elemente.

    Benutzen Sie diese Listenimplementierung, um in einem Programm den Benutzer menügeführt eine Liste füllen, entleeren und ausgeben zu lassen.

    Das Menü sollte dabei ungefähr so aussehen:

    Menue zur Warteschlangenverwaltung:
    1. Sortiertes Einfuegen eines Elementes
    2. Loeschen und Ausgeben des Elementes mit Schluessel key
    3. Ausgeben der Liste
    4. Beenden des Programms
    Bitte geben Sie die Ziffer der gewuenschten Funktion ein:

    Mal davon abgesehen, dass ich das Wort "Warteschlangenverwaltung" und die entsprechende Pointer-Bezeichnung "schlange" etwas unglücklich finde, weil ich das eher mit einer Queue als mit einer sortierten Liste assoziere, frage ich mich, wofür in den Funktionen

    void linsert (struct Knoten ** schlange, int key)
    

    und

    int ldelete (struct Knoten ** schlange, int key)
    

    die Doppel-Pointer gut sind. Hätte ich freie Hand, würde ich einen einfachen Pointer auf den Listenanfang übergeben. Ich habe mal im Netz nach Funktionen mit Doppel-Pointern gesucht, um zu sehen, wie die benutzt werden. Gefunden habe ich zweidimensionale Arrays, um die es hier ja nicht geht, aber auch Funktionen zu verketteten Listen, die ich aber nicht verstanden habe. Was die meisten gemeinsam hatten, war, dass der Doppel-Pointer in der Funktion wieder dereferenziert wird. Ein Beispiel:

    void addNode(ListNode ** head, ListNode * new){
    
    if(*head == NULL){
      *head = new;
    [...]
    

    Ich verstehe nicht, was das bringt, einen Doppel-Pointer zu übergeben und ihn dann durch Dereferenzierung direkt wieder zu einem einfachen Pointer zu machen. Warum nimmt man dann nicht gleich einen einfachen, den man dann nicht dereferenziert? Das Beispiel sähe dann so aus:

    void addNode(ListNode * head, ListNode * new){
    
    if(head == NULL){
      head = new;
    [...]
    

    Ich wäre sehr dankbar, wenn mir das jemand zeitnah (Dienstag früh ist Abgabe) erklären könnte, vielen Dank!

    EDIT: Ich habe übrigens eher rudimentäre C-Kenntnisse, das bitte ich in der Formulierung eurer Antworten zu berücksichtigen, vielen Dank!


  • Mod

    Offtopic: Wenn du Doopelzeiger im Zusammenhang mit 2D-Arrays gefunden hast, dann hast du nur Code von irgendwelchen Anfängern gefunden. Ist falsch.

    Ontopic:
    Der von dir zitierte Code zeigt es doch:

    void addNode(ListNode ** head, ListNode * new){
    
    if(*head == NULL){
      *head = new;
    

    *head = new ! Das ist der ganz entscheidende Unterschied. Nicht innerhalb der Funktion, sondern bezüglich dessen, was der Aufrufer später sieht.

    Vielleicht hast du ja Angst vor vielen Sternchen, dabei ist da gar nichts magisches dran. Zeiger auf X ist ein ganz normaler Datentyp wie jeder andere. Und entsprechend kann man auch Zeiger auf Zeiger auf X haben. Wenn ich mal ListNode* durch int ersetze, vielleicht wird es dir dann klarer:

    void addNode(int * head, int new){
    
    if(*head == 0){
      *head = new;
    

    vs.

    void addNode(int head, int new){
    
    if(head == 0){
      head = new;
    

    Siehst du jetzt den großen Unterschied?



  • Zeiger werden bei Funktionen oftmals verwendet, wenn innerhalb der Funktion der Wert/Inhalt der Variable verändert wird und dieser geänderte Wert nach Funktionsaufruf weiterverwendet werden soll.

    Anfänger, Lehrer, Fachbuchautoren und andere Laien verwenden hierfür fälschlicherweise auch den Begriff call by reference.

    void increment(int i)
    {
      i = i + 1;
    }
    ...
    int i = 0;
    increment(i);
    printf("%d",i); /* 0 => nicht gewünscht */
    

    Da es in C ausschließlich call by value gibt müssen Zeiger verwendet werden, um Änderungen an Daten aus dem Innern der Funktion nach außen zu geben. (Es gäbe noch die Variante, die geänderte Variable als return zurückzugeben, das ist hier aber nicht das Thema)

    void increment(int *i)
    {
      *i = *i + 1;
    }
    ...
    int i = 0;
    increment(&i);
    printf("%d",i); /* 1 => gewünscht */
    

    Allgemeines Schema für dein Problem ist somit:

    void funktion(TYP var)
    {
    var = foo;
    }
    /* wird nicht funktionieren, nach Funktionsaufruf enthält var nicht foo */
    
    void funktion(TYP *var)
    {
    *var = foo;
    }
    /* funktioniert in dem Sinne, dass var nach Funktionsaufruf foo enthält */
    

    Dein "Doppelzeiger"-Verständnisproblem ist also gar kein solches, sondern liegt daran, dass du o.g. Schema nicht verstanden hast, denn:
    für deinen Fall ist TYP :=

    typedef struct Knoten {int key; struct Knoten *next;} * ZeigeraufKnoten;
    

    d.h. der Ausgangstyp ist bereits ein Zeigertyp. (da du innerhalb der Funktion mit Zeigern auf struct operierst und nicht direkt mit struct).

    Folglich ist gemäß o.g. Schema als Funktionsparameter TYP* zu verwenden (und nicht TYP); und TYP* resultiert dann eben in einen "Doppel"Zeiger. (weil TYP selbst ja schon ein Zeigertyp ist (und bereits ein Sternchen hat))

    TYP := struct {...} * MeinTyp
    TYP* := struct {...} ***** * MeinTyp



  • Vielen Dank für eure Antworten, ich glaube, ich habe verstanden, warum ich irritiert war. Ich hatte nicht an das call by reference (O.k., Wutz, ich habe gelesen, dass du das für eine Fehlbezeichnung hältst, aber so habe ich es gelernt) gedacht, was mir natürlich hätte auffallen müssen, da die vorgegebenen Funktionen ja void, also nichts, zurückgeben.

    In meiner funktionierenden(!) verketteten Liste, die ich in der Vergangenheit mal programmiert hatte, hatte ich mit call by value und return gearbeitet. Das sah dann so aus (Ausschnitte; entscheidendes fett hervorgehoben):

    typedef struct vokabelliste vokList;

    struct vokabelliste
    {
    char deuVok_ary [MAX];
    char engVok_ary [MAX];
    vokList * pre_structPtr;
    vokList * next_structPtr;
    };

    /------------------------------------------------/

    **vokList *** neuesListenelement (vokList * position_structPtr)
    {
    while (position_structPtr->next_structPtr != NULL)
    {
    position_structPtr = position_structPtr->next_structPtr;
    }

    position_structPtr->next_structPtr = calloc (1, sizeof(vokList));
    if (position_structPtr == NULL)
    {
    puts ("Fehler! Es konnte kein Speicher reserviert werden! Das Programm wird nun beendet ...");
    beenden ();
    }

    position_structPtr->next_structPtr->pre_structPtr = position_structPtr;
    position_structPtr->next_structPtr->next_structPtr = NULL;
    position_structPtr = position_structPtr->next_structPtr;

    return (position_structPtr);
    }

    /------------------------------------------------/

    **vokList *** vokabelEingeben (vokList * position_structPtr)
    {
    char engVokEingabe_ary [MAX] ={0};
    char deuVokEingabe_ary [MAX] ={0};

    position_structPtr = neuesListenelement (position_structPtr);

    puts ("Bitte die englische Vokabel eingeben:");
    fgets (engVokEingabe_ary, MAX, stdin);
    fcuts (engVokEingabe_ary);
    strncpy (position_structPtr->engVok_ary, engVokEingabe_ary, sizeof (position_structPtr->engVok_ary));

    puts ("Bitte die deutsche Übersetzung eingeben:");
    fgets (deuVokEingabe_ary, MAX, stdin);
    fcuts (deuVokEingabe_ary);
    strncpy (position_structPtr->deuVok_ary, deuVokEingabe_ary, sizeof (position_structPtr->deuVok_ary));

    return (position_structPtr);
    }

    /------------------------------------------------/

    int main ()
    {
    char auswahl_charAry [4] = {0};
    vokList * position_structPtr = NULL;
    vokList * listenAnfang_structPtr = NULL;

    position_structPtr = calloc (1, sizeof(vokList)); /* Dummy-Listenelement als Einstiegsanker, damit nicht immer überprüft werden muss, ob bereits ein Element vorhanden ist */
    if (position_structPtr == NULL)
    {
    puts ("Fehler! Es konnte kein Speicher reserviert werden! Das Programm wird nun beendet ...");
    beenden ();
    }

    position_structPtr->pre_structPtr = NULL;
    position_structPtr->next_structPtr = NULL;

    listenAnfang_structPtr = position_structPtr;

    while (1)
    {
    puts ("\nWas wollen Sie tun?\n(s) die Vokabelliste speichern\n(d) Vokabeln aus einer Datei einlesen\n(e) eine neue Vokabel eingeben\n(l) eine Vokabel loeschen\n(f) eine Vokabel finden\n(a) Vokabeln abfragen\n(b) Programm beenden");

    fgets (auswahl_charAry, 4, stdin);

    switch (auswahl_charAry [0])
    {
    [...]
    case 'e':
    position_structPtr = vokabelEingeben (position_structPtr);
    break;
    [...]
    }
    }
    return (EXIT_SUCCESS);
    }

    Wie ihr seht, habe ich per Übergabe des einfachen(!) Pointers auf die Listenposition und return-Statements diesen Positions-Pointer durch das ganze Programm durchgereicht, so dass ich in der main den - durch eine Funktion verschobenen - Positions-Pointer an die nächste Funktion weitergeben konnte. Das ganze lief also immer call by value.

    Was der Proff nun mit dem Doppel-Pointer und dem void-return (also ohne return) vorgegeben hat, ist, dass wir call by reference verwenden sollen, was gegenüber meinem call by value natürlich auch besser ist, weil ich dann nicht per returns den Positionspointer durch das Programm schleifen muss.

    Habe ich das richtig verstanden?



  • Dein Enthusiasmus ist verständlich aber unpassend;
    die Aufgabenstellung war klar eine andere, außerdem habe ich wohlweislich deine Variante als Alternattive genannt.
    In der Programmierpraxis - insbesondere bei der Unzahl der C-Libs und Module -
    wirst du häufig genau diese Aufgabenstellung vorfinden: eine exakte Beschreibung der Prototypen(Funktionssignatur), die verlangt wird; dass es auch anders gehen würde interessiert dabei niemanden.



  • Verstehe ich dich richtig, dass du glaubst, ich sei der Meinung, dass der in meinem letzten Postig gezeigte Code die Lösung der gestellten Aufgabe sei? Dann hast du mich komplett missverstanden.

    Wie geschrieben, handelt es sich um einen Ausschnitt aus einem Programm, welches ich früher (nicht zu der aktuellen Aufgabe!) einmal geschrieben habe. Ich habe ihn nicht gepostet, weil ich ihn für die aktuell gestellte Aufgabe verwenden möchte, sondern um zu zeigen, dass ich damals mit call by value gearbeitet habe und deswegen beim Betrachten der aktuell gestellten Aufgabe nicht an das "call by referense"-Prinzip gedacht hatte und deswegen wegen der Doppel-Pointer verwirrt war.

    Meine nur zur Sicherheit (weil man aus dem Seminar fliegt, wenn man die Aufgabe nicht korrekt löst) an dich gestellte Frage war, ob ich es richtig verstanden habe, dass in der aktuellen Aufgabenstellung mittels der Doppel-Pointer und der fehlenden Rückgabe (void) gezeigt wird, dass wir mit call by reference arbeiten sollen. Das tut mein alter Code, wie geschrieben, natürlich nicht, das ist mir klar.


  • Mod

    EXIT_SUCCESS schrieb:

    Meine nur zur Sicherheit (weil man aus dem Seminar fliegt, wenn man die Aufgabe nicht korrekt löst) an dich gestellte Frage war, ob ich es richtig verstanden habe, dass in der aktuellen Aufgabenstellung mittels der Doppel-Pointer und der fehlenden Rückgabe (void) gezeigt wird, dass wir mit call by reference arbeiten sollen. Das tut mein alter Code, wie geschrieben, natürlich nicht, das ist mir klar.

    Ja, aus der Aufgabenstellung ergibt sich unzweifelhaft, dass dies hier die gesuchte Lösung ist.



  • Alles klar, danke, jetzt kann ich mir zu 100% sicher sein anstatt nur zu 90%. Angesichts der Wichtigkeit des Bestehens der Aufgabe waren mir die 10% Restunsicherheit zu brisant. Einen schönen Abend wünsch ich.



  • EXIT_SUCCESS schrieb:

    Vielen Dank für eure Antworten, ich glaube, ich habe verstanden, warum ich irritiert war. Ich hatte nicht an das call by reference (O.k., Wutz, ich habe gelesen, dass du das für eine Fehlbezeichnung hältst, aber so habe ich es gelernt)

    Kleiner Tipp: in Prüfungen auf gar keinen Fall die von Wutz behauptete (richtige) Bezeichnung verwenden.

    Ich habe mich in meiner Prüfung (Java) ebenfalls mit dem Prof. angelegt, indem ich behauptet habe, dass Java kein Call by Reference kenne. Der Prof. wollte aber hören, dass Objekte als "Call by Reference" übergeben werden und Dinge wie "int" nicht. Wutz würde meiner Argumentation sicher folgen, der Prof. fand es nicht so lustig, insbesondere da er ein "Definitionsherumreiter" war und nur seine Definitionen hören wollte. (Prüfungsfragen wie "Was ist ein Objekt" am besten wörtlich aus dem Script zitieren!) -> somit ist "Einführung in Java", wo ich gar nichts gelernt habe, meine allerschlechteste Prüfung geworden.
    Mein Beispiel, dass sowas wie public void foo(List l){l=null;} die übergebene Liste nicht ändert, wurde nicht akzeptiert, es sei trotzdem Call by Reference, wenn Objekte im Spiel seien.



  • naja werden bei java nicht immer referenzen auf objekte übergeben, um sich den kopieraufwand zu sparen und dem programmierer ein minimales maß an freiheit zu gönnen, während man bei atomaren datentypen auch gleich den wert übergeben kann, weils da keinen unterschied macht?

    daher hat der prof da wohl nicht ganz unrecht. 🙄



  • Wade1234 schrieb:

    naja werden bei java nicht immer referenzen auf objekte übergeben, um sich den kopieraufwand zu sparen und dem programmierer ein minimales maß an freiheit zu gönnen, während man bei atomaren datentypen auch gleich den wert übergeben kann, weils da keinen unterschied macht?

    daher hat der prof da wohl nicht ganz unrecht. 🙄

    Offensichtlich nicht, denn dann könnte man die ja auf null setzten, wie in meinem Beispiel foo() gezeigt. Der Code ist gültig, aber l wird nur innerhalb der Funktion auf null gesetzt, das hat keine Auswirkungen auf den Caller. Wir haben also ein Call by Value, denn bei Call by Reference wäre ja auch im aufrufenden Code der Wert auf null gesetzt worden. Nur dass bei Objekten eben ein Pointer auf das Objekt übergeben wird und der "." implizit dereferenziert.

    auch sowas geht nicht:

    public static void createMe(List<int> l) { l = new ArrayList<int>(); }
    public static void xxx() { List<int> l = null; createMe(l); l.whatever(); /* throws npe */ }
    


  • void MyFunc(struct MyStruct *ms)
    {
         ms = NULL;
    }
    

    hier wird ms auch nur innerhalb der funktion auf NULL gesetzt, und sowas funktioniert auch nicht:

    void MyFunc(struct MyStruct *ms)
    {
         ms = malloc(sizeof(struct MyStruct));
    }
    

    das ist das gleiche, nur dass du bei java keine sternchen schreiben musst.



  • Genau, das sag ich doch die ganze Zeit!

    Und mein Prof. hätte das "Call by Reference" genannt. Und ich halte es da wie Wutz und nenne es "Call by Value".



  • aber du übergibst da doch eine adresse und das nennt man dann call by reference.



  • call by value wäre das hier:

    void MyFunc(struct MyStruct ms)
    {
         //mach was
    }
    

    aber das hat man bei java meine ich entfernt, weil es inbesondere bei größeren objekten/strukturen zu unnötigem kopieraufwand führen würde.



  • Wade1234 schrieb:

    aber du übergibst da doch eine adresse und das nennt man dann call by reference.

    Ok, da gehen unsere Meinungen aber auseinander.

    Wie sieht es mit

    void foo(uintptr_t i);
    

    aus? Da übergebe ich auch eine Adresse. Ist es deswegen Call by reference? Nein! Aber ich caste es doch in foo in einen Pointer und dann kann ich da Daten ändern! Na und?

    Und in C++

    void foo(int *i);
    void bar(int * &i)
    

    sind die für dich beide Call by Reference?

    Was Java macht, ist doch eher "Pass a refecence by value"!


  • Mod

    Also ich als Prof würde euch alle durchfallen lassen, wenn ihr mir damit kämt, dass das nicht call by reference wäre. Ihr habt ganz klar nicht verstanden (oder eher: Ihr stellt euch extra dumm, um vermeintlich gebildet auszusehen), was der konzeptionelle Unterschied zwischen call by value und call by reference ist. Das sind Programmierkonzepte, und keine Frage der genauen technischen Umsetzung. Wenn der Programmierer einer C-Funktion einen Zeiger auf einen Wert anstatt dem Wert selbst erwartet und den Wert über diesen Zeiger ändert, dann hat er den Zeigerparameter ganz klar als Referenz auf diesen Wert benutzt und es ist vollkommen egal, dass der Zeiger selber kopiert wurde oder nicht. C ist bloß eben sehr explizit in seiner Syntax und man sieht die nackten Zeiger, die vor einem in anderen Sprachen versteckt werden. Trotzdem ist es in C möglich, dass man Funktionen programmieren kann, die das Konzept 'call by reference' umsetzen, um mit der Außenwelt zu kommunizieren. Ob sie das manuell über value-kopierte Pointer simulieren oder ob die Sprache extra Syntaxzucker dafür anbietet, ändert nichts da dran.

    Das ist vergleichbar damit, wenn Leute behaupten, in C könne man nicht objektorientiert programmieren, weil es keine direkte Unterstützung in der Sprache dafür gibt. Dabei sind die Leute, die sich hier so sehr an dem Begriff 'Referenz' aufhängen, normalerweise die ersten, die angesprungen kommen, wenn mal wieder ein Anfänger behauptet, objektorientiert ginge nicht in C.



  • wob schrieb:

    Wie sieht es mit

    void foo(uintptr_t i);
    

    aus? Da übergebe ich auch eine Adresse. Ist es deswegen Call by reference? Nein! Aber ich caste es doch in foo in einen Pointer und dann kann ich da Daten ändern! Na und?

    kommt drauf an: wenn du mit dem wert des zeigers rechnen willst, z.b. um die anzahl bytes zwischen zwei zeigern festzustellen, ist es call by value, wenn du auf den wert in der adresse zugreifen bzw. den zeiger dereferenzieren und die variable, auf die er zeigt, verändern willst, ist es call by reference. 🙄

    Und in C++

    void foo(int *i);
    void bar(int * &i)
    

    sind die für dich beide Call by Reference?

    das erste ist wohl klar call by reference, das zweite kenne ich nicht.



  • Wutz schrieb:

    Anfänger, Lehrer, Fachbuchautoren und andere Laien verwenden hierfür fälschlicherweise auch den Begriff call by reference.
    ...
    Da es in C ausschließlich call by value gibt ...

    Physikalisch wird der Wert eine Zeigers übergeben, aber semantisch gesehen ist ein Zeiger eine Referenz.

    Btw, deine persönlichen Probleme mit Anfängern, Lehrern, Fachbuchautoren sind hier nicht relevant. 🙂



  • Call-by-reference bedeutet nicht, dass eine Referenz übergeben wird, sondern dass das Argument per Referenz übergeben wird. Wenn das Argument zufällig eine Art von Referenz ist, wird aus Call-by-value nicht auf magische Weise Call-by-reference.


Anmelden zum Antworten