Was ist der Zweck der Verwendung von NIL zur Darstellung von Nullknoten?
17
In meinem Kurs über Algorithmen und Datenstrukturen haben Professoren, Folien und das Buch ( Einführung in Algorithmen, 3. Auflage ) das Wort verwendet NIL, um beispielsweise ein Kind eines Knotens (in einem Baum) zu bezeichnen, der nicht existiert.
Einmal sagte NILmein Klassenkamerad während eines Vortrags, anstatt zu sagen , nullund der Professor korrigierte ihn, und ich verstehe nicht, warum Professoren dieses Wort betonen.
Gibt es einen Grund, warum Menschen das Wort NILanstelle von nulloder noneoder einem anderen Wort verwenden? Hat NILdas eine besondere Bedeutung, die die anderen nicht haben? Gibt es einen historischen Grund?
Beachten Sie, dass ich auch einige Stellen im Internet gesehen habe, an denen z. B. das Wort nullanstelle von verwendet wurde NIL, aber normalerweise wird dieses letzte Wort verwendet.
Soweit ich betroffen bin, null, nil, noneund nothingsind allgemeine Namen für das gleiche Konzept: ein Wert, der die „Abwesenheit von einem Wert“ darstellt und die in vielen verschiedenen Arten vorhanden ist ( so genannte Nullable Types ). Dieser Wert wird normalerweise verwendet, wenn normalerweise ein Wert vorhanden ist, er kann jedoch weggelassen werden, beispielsweise ein optionaler Parameter. Verschiedene Programmiersprachen implementieren dies unterschiedlich, und einige Sprachen haben möglicherweise kein solches Konzept. In Sprachen mit Zeigern ist es ein Nullzeiger . In vielen objektorientierten Sprachen ist null kein Objekt: Das Aufrufen einer Methode ist ein Fehler. Um einige Beispiele zu nennen:
In Lisp nilwird häufig verwendet, um für das Fehlen eines Werts zu stehen. Im Gegensatz zu den meisten anderen Sprachen nilhat Struktur - es ist ein Symbol, dessen Name ist "NIL". Es ist auch die leere Liste (weil eine Liste eine Nachteile-Zelle sein sollte, aber manchmal gibt es keine Nachteile-Zelle, weil die Liste leer ist). Ob es durch einen Nullzeiger unter der Haube oder als Symbol wie jedes andere implementiert wird, hängt von der Implementierung ab.
Ist in Pascal nilein Zeigerwert (gültig in jedem Zeigertyp), der möglicherweise nicht dereferenziert wird.
In C und C ++ enthält jeder Zeigertyp einen NULLWert, der sich von jedem Zeiger auf ein gültiges Objekt unterscheidet.
Ist in Smalltalk nilein Objekt ohne definierte Methode.
Ist in Java und in C # nullein Wert eines beliebigen Objekttyps. Jeder Versuch, auf ein Feld oder eine Methode von zuzugreifen, nulllöst eine Ausnahme aus.
undefUnterscheidet sich in Perl von jedem anderen Skalarwert und wird in der gesamten Sprache und Bibliothek verwendet, um das Fehlen eines „echten“ Werts anzuzeigen.
NoneUnterscheidet sich in Python von jedem anderen Wert und wird in der gesamten Sprache und Bibliothek verwendet, um das Fehlen eines „echten“ Werts anzuzeigen.
In ML (SML, OCaml) Noneist ein Wert eines beliebigen Typs im Typschema 'a option, der Noneund Some xfür einen beliebigen xTyp enthält 'a.
In Haskell verwendet das ähnliche Konzept die Namen Nothingund Just xfür die Werte und Maybe afür den Typ.
In Algorithmus-Präsentationen stammt der verwendete Name in der Regel aus dem Hintergrund des Präsentators oder der Sprache, die in Codebeispielen verwendet wird.
NULLn ich l
Möglicherweise möchte Ihr Dozent das Wort nullfür eine Nullzeiger-Konstante in der im Kurs verwendeten Programmiersprache (Java oder C #?) Verwenden und NILdas Fehlen eines Knotens in einigen Datenstrukturen angeben, die möglicherweise implementiert sind oder nicht als Nullzeiger-Konstante (wird beispielsweise, wie oben in Lisp zu sehen, NILhäufig nicht als Nullzeiger implementiert). Diese Unterscheidung wäre relevant, wenn Implementierungstechniken für Datenstrukturen diskutiert werden. Bei der Erörterung der Datenstrukturen selbst ist das Nullzeiger-Konstanten-Konzept irrelevant, nur das Ungleichwertigkeitskonzept ist von Bedeutung.
Es gibt kein Standardbenennungsschema. Ein anderer Dozent oder Lehrbuch könnte andere Namen verwenden.
Noch zwei Beispiele. Ziel C hat sowohl NULL(für C-Kompatibilität) als auch nil; Aufrufen von Methoden nilist ein No-Op. JavaScript hat sowohl null(ein Wert, der nichts darstellt) als auch undefined(der Wert ist nicht einmal festgelegt).
200_success
1
"In objektorientierten Sprachen ist null kein Objekt: Das Aufrufen einer Methode ist ein Fehler." - Dies gilt nicht für alle Sprachen, einschließlich einiger der von Ihnen aufgelisteten Sprachen. In Ruby und Smalltalk nilist ein Objekt wie jedes andere, es ist eine Instanz von NilClass, es gibt kein anderes Konzept von "Null-Ness", und insbesondere gibt es keinen Null-Zeiger. In Scala unterscheidet Niles sich stark von einem Nullzeiger null, nullist ein bisschen wie ein Nullzeiger, hat jedoch tatsächlich ein type ( Null), Nilist ein reguläres altes Objekt, die Singleton-Instanz der EmptyListKlasse, wenn man so will, und es gibt auch ...
Jörg W Mittag
1
… NothingWelches der unterste Typ ist und keine Instanz hat, und Unitwelches der Typ von Subroutinen ist, die keinen Wert zurückgeben und die Singleton-Instanz haben (). nullIrgendwie wird der Begriff "Nullzeiger" oder "Nullreferenz" verwendet, nicht weil dies dem Begriff inhärent ist, sondern einfach weil Sprachen wie C, C ++, D, Java, C #, die ihn verwenden, allgegenwärtig sind Weise. NILträgt diese Konnotation nicht, obwohl sie tatsächlich so verwendet wird, z. B. in Pascal, Modula-2 und Oberon. In Ruby nilhat viele nützliche Methoden: nil.to_i # => 0, nil.to_s # => '', ...
Jörg W Mittag
1
... nil.to_a # => [], nil.to_h # => {}, nil.to_f # => 0.0, nil.inspect # => 'nil', und so weiter. Die vollständige Liste finden Sie hier .
Jörg W Mittag
3
Ich glaube, der Grund für die Verwendung von Null und Null ist, dass ersteres in erster Linie ein Substantiv und letzteres in erster Linie ein Adjektiv ist (ich habe es im Internet und in meinem Tagebuch nachgeschlagen: American Heritage 1992).
In Bezug auf Bedeutung und Geschichte ist NIL eine Kontraktion aus dem Lateinischen "nihil", was "nichts" bedeutet.
Meines Wissens wurde die Verwendung des Namens nilzur Bezeichnung eines Nullzeigers mit der Programmiersprache Lisp (1958) eingeführt.
Ein Nullzeiger ist ein Zeigerwert, der auf nichts zeigen soll und daher nicht dereferenziert werden sollte. In den meisten Fällen sind Zeiger einfach Speicheradressen. Jede Variable (dh jeder Ort), der einen solchen Zeiger enthalten soll, enthält immer eine Konfiguration von Bits, und jede solche Konfiguration kann als Speicheradresse gelesen werden. Daher ist es häufig der Fall, dass der Wert nildie Adresse eines Speicherbereichs ist, der für das Programm verboten ist, wodurch eine Art von Fehler (möglicherweise eine Unterbrechung) verursacht wird, wenn das Programm versucht, eine Dereferenzierung durchzuführen nil, was nur ein Fehler sein kann.
Das Vorhandensein eines eindeutigen vordefinierten Standardwerts für diese Rolle ist in Sprachen unbedingt erforderlich, in denen Zeiger explizit verwendet werden, da es wichtig ist, testen zu können, ob ein Zeiger tatsächlich auf einen Speicherort verweist oder nicht. Typischerweise wurde in Lisp eine Liste als Folge von "cons" -Paaren erstellt, die einen "car" -Zeiger auf ein Listenelement und einen "cdr" -Zeiger auf das nächste Paar enthielten. Im letzten Listenpaar war der zweite Zeiger nil.
Dies entspricht der rekursiven Definition einer Liste als leere Liste oder als mit einer Liste verkettetes Listenelement. Daher wurde eine Liste ohne Element durch dargestellt nil. Diese leere Liste ist zufällig die Identität des Listenmonoids.
Da Listen zur Darstellung von Mengen verwendet werden können, kann die leere Menge in diesem Fall auch durch dargestellt werden nil.
Dies nilwar historisch gesehen ein spezieller Zeigerwert, wurde jedoch als spezieller Identitätswert für andere abstraktere Bereiche wie Listen oder Mengen verstanden.
Ein Zeiger gleich nilwar ein Nullzeiger, wobei Null eher ein Adjektiv als ein Substantiv (dh ein Substantiv) ist.
Die koordinierte Verwendung von beiden Wörtern als Adjektiv und Substantiv steht im Einklang mit anderen Praktiken. Das Qualifikationsmerkmal null wird häufig für die Null einer algebraischen Struktur verwendet, beispielsweise für die Identität eines Monoids: das Null-Element . Listen bilden ein Monoid , wobei der Wert nil die Identität ist. Gleiches gilt für Mengen (obwohl sie eine Algebra mit viel mehr Eigenschaften bilden). Man sagt ähnlich, dass eine ganze Zahl null ist, wenn sie null ist.
Es gibt viele Variationen bei der Verwendung dieser und anderer Wörter, wie z. B. keine, abhängig von den Autoren und Besonderheiten der Programmiersprachen.
Die beiden wichtigsten Konnotationen lauten wie oben erläutert
als Standard "undefinierter Wert", der tatsächlich das Fehlen eines verwendbaren Werts darstellt.
als Identitätswert einer Domain
Dies zeigt, dass es nicht ganz richtig ist, zu behaupten, dass NIL " ein Wert ist, der die" Abwesenheit eines Wertes "darstellt, wie dies Gilles in der akzeptierten Antwort getan hat . Das hängt von der Sprache und ihren Verwendungszwecken ab. Die Programmiersprache LISP hat NIL wahrscheinlich vor 55 Jahren in die Programmierterminologie aufgenommen. In LISP NIList die leere Liste und kann äquivalent notiert werden, ()was die natürliche Darstellung der leeren Liste ist.Es stellt nicht das Fehlen eines Wertes dar. Es wird manchmal als Platzhalter für fehlende Werte verwendet. Dies ist jedoch häufig zu vermeiden, da es sich bei der leeren Liste um einen Wert handelt. Was für einen fehlenden Wert in einer Struktur in einem beliebigen, vom Programmierer ausgewählten Objekt steht, kann nicht mit akzeptablen Werten verwechselt werden.
Die beiden Konzepte sind ziemlich unterschiedlich, obwohl wir oben gezeigt haben, dass sie zusammenhängen können. Es könnte interessant sein, eine detaillierte Taxonomie der Verwendung der von Gilles'answer aufgezählten Terminologie zu haben, um zu sehen, ob die Verwendung jedes dieser Wörter mehr auf die eine oder die andere Konnotation ausgerichtet ist.
Namen sind nicht mehr als das, was sie in einem bestimmten Kontext bedeuten, von wem auch immer der Diskurs definiert wird. Einige Verwendungen sind häufiger, natürlicher oder konsistenter, aber man sollte immer nach Definitionen suchen und sicherstellen, welche Bedeutung in jedem Kontext beabsichtigt war. Und man sollte nicht immer erwarten, dass die Terminologie mit Geschmack oder Beständigkeit gewählt wurde.
NIL ist ein Objekt mit einem Wert, der dem Programmierer mitteilt, dass das Objekt ungültig ist. Dies ist besonders nützlich in C ++, wo NULL als 0 definiert ist. Wenn Sie die Referenzierung von NULL in C ++ aufheben, tritt undefiniertes Verhalten auf. Wenn Sie den Verweis auf NIL aufheben (einen Zeiger auf ein leeres Objekt, das Sie definiert haben), erhalten Sie ein Objekt, von dem Sie erkennen können, dass es sich jenseits des Endes Ihrer Datenstruktur befindet. Es ist großartig, um katastrophale Programmfehler zu verhindern und Fehler zu erkennen.
Sie können NIL in Fällen wie doppelt verknüpften Listen verwenden. Dabei muss es sich um den Anfang und das Ende der Liste handeln, um den Überblick über Kopf und Ende zu behalten. Stellen Sie außerdem sicher, dass die Verweise -> next und -> prev NULL nicht de-referenzieren.
Ich denke, Sie haben meine Antwort falsch interpretiert. Der von Ihnen angegebene Link hat keine Korrelation mit meiner Antwort. Ich schlug vor, dass nil ein benutzerdefiniertes Objekt ist, das auf Klassenbasis definiert wird, um auf ein leeres (aber gültiges) Objekt dieser Klasse zu verweisen.
Bastion
Die Art und Weise, wie Sie "NIL ist ein Objekt" (meine Betonung) schreiben, anstatt zu sagen, "NIL kann als Objekt definiert werden", lässt es so aussehen, als würden Sie ein Sprachmerkmal beschreiben, anstatt einen Programmierstil. Wenn es sich bei Ihrer Antwort jedoch nur um einen Programmierstil handelt, geht es hier nicht wirklich um ein Thema.
NULL(für C-Kompatibilität) als auchnil; Aufrufen von Methodennilist ein No-Op. JavaScript hat sowohlnull(ein Wert, der nichts darstellt) als auchundefined(der Wert ist nicht einmal festgelegt).nilist ein Objekt wie jedes andere, es ist eine Instanz vonNilClass, es gibt kein anderes Konzept von "Null-Ness", und insbesondere gibt es keinen Null-Zeiger. In Scala unterscheidetNiles sich stark von einem Nullzeigernull,nullist ein bisschen wie ein Nullzeiger, hat jedoch tatsächlich ein type (Null),Nilist ein reguläres altes Objekt, die Singleton-Instanz derEmptyListKlasse, wenn man so will, und es gibt auch ...NothingWelches der unterste Typ ist und keine Instanz hat, undUnitwelches der Typ von Subroutinen ist, die keinen Wert zurückgeben und die Singleton-Instanz haben().nullIrgendwie wird der Begriff "Nullzeiger" oder "Nullreferenz" verwendet, nicht weil dies dem Begriff inhärent ist, sondern einfach weil Sprachen wie C, C ++, D, Java, C #, die ihn verwenden, allgegenwärtig sind Weise.NILträgt diese Konnotation nicht, obwohl sie tatsächlich so verwendet wird, z. B. in Pascal, Modula-2 und Oberon. In Rubynilhat viele nützliche Methoden:nil.to_i # => 0,nil.to_s # => '', ...nil.to_a # => [],nil.to_h # => {},nil.to_f # => 0.0,nil.inspect # => 'nil', und so weiter. Die vollständige Liste finden Sie hier .Ich glaube, der Grund für die Verwendung von Null und Null ist, dass ersteres in erster Linie ein Substantiv und letzteres in erster Linie ein Adjektiv ist (ich habe es im Internet und in meinem Tagebuch nachgeschlagen: American Heritage 1992).
In Bezug auf Bedeutung und Geschichte ist NIL eine Kontraktion aus dem Lateinischen "nihil", was "nichts" bedeutet.
Meines Wissens wurde die Verwendung des Namens
nilzur Bezeichnung eines Nullzeigers mit der Programmiersprache Lisp (1958) eingeführt.Ein Nullzeiger ist ein Zeigerwert, der auf nichts zeigen soll und daher nicht dereferenziert werden sollte. In den meisten Fällen sind Zeiger einfach Speicheradressen. Jede Variable (dh jeder Ort), der einen solchen Zeiger enthalten soll, enthält immer eine Konfiguration von Bits, und jede solche Konfiguration kann als Speicheradresse gelesen werden. Daher ist es häufig der Fall, dass der Wert
nildie Adresse eines Speicherbereichs ist, der für das Programm verboten ist, wodurch eine Art von Fehler (möglicherweise eine Unterbrechung) verursacht wird, wenn das Programm versucht, eine Dereferenzierung durchzuführennil, was nur ein Fehler sein kann.Das Vorhandensein eines eindeutigen vordefinierten Standardwerts für diese Rolle ist in Sprachen unbedingt erforderlich, in denen Zeiger explizit verwendet werden, da es wichtig ist, testen zu können, ob ein Zeiger tatsächlich auf einen Speicherort verweist oder nicht. Typischerweise wurde in Lisp eine Liste als Folge von "cons" -Paaren erstellt, die einen "car" -Zeiger auf ein Listenelement und einen "cdr" -Zeiger auf das nächste Paar enthielten. Im letzten Listenpaar war der zweite Zeiger
nil.Dies entspricht der rekursiven Definition einer Liste als leere Liste oder als mit einer Liste verkettetes Listenelement. Daher wurde eine Liste ohne Element durch dargestellt
nil. Diese leere Liste ist zufällig die Identität des Listenmonoids.Da Listen zur Darstellung von Mengen verwendet werden können, kann die leere Menge in diesem Fall auch durch dargestellt werden
nil.Dies
nilwar historisch gesehen ein spezieller Zeigerwert, wurde jedoch als spezieller Identitätswert für andere abstraktere Bereiche wie Listen oder Mengen verstanden.Ein Zeiger gleich
nilwar ein Nullzeiger, wobei Null eher ein Adjektiv als ein Substantiv (dh ein Substantiv) ist.Die koordinierte Verwendung von beiden Wörtern als Adjektiv und Substantiv steht im Einklang mit anderen Praktiken. Das Qualifikationsmerkmal null wird häufig für die Null einer algebraischen Struktur verwendet, beispielsweise für die Identität eines Monoids: das Null-Element . Listen bilden ein Monoid , wobei der Wert nil die Identität ist. Gleiches gilt für Mengen (obwohl sie eine Algebra mit viel mehr Eigenschaften bilden). Man sagt ähnlich, dass eine ganze Zahl null ist, wenn sie null ist.
Es gibt viele Variationen bei der Verwendung dieser und anderer Wörter, wie z. B. keine, abhängig von den Autoren und Besonderheiten der Programmiersprachen.
Die beiden wichtigsten Konnotationen lauten wie oben erläutert
als Standard "undefinierter Wert", der tatsächlich das Fehlen eines verwendbaren Werts darstellt.
als Identitätswert einer Domain
Dies zeigt, dass es nicht ganz richtig ist, zu behaupten, dass NIL " ein Wert ist, der die" Abwesenheit eines Wertes "darstellt, wie dies Gilles in der akzeptierten Antwort getan hat . Das hängt von der Sprache und ihren Verwendungszwecken ab. Die Programmiersprache LISP hat NIL wahrscheinlich vor 55 Jahren in die Programmierterminologie aufgenommen. In LISP
NIList die leere Liste und kann äquivalent notiert werden,()was die natürliche Darstellung der leeren Liste ist.Es stellt nicht das Fehlen eines Wertes dar. Es wird manchmal als Platzhalter für fehlende Werte verwendet. Dies ist jedoch häufig zu vermeiden, da es sich bei der leeren Liste um einen Wert handelt. Was für einen fehlenden Wert in einer Struktur in einem beliebigen, vom Programmierer ausgewählten Objekt steht, kann nicht mit akzeptablen Werten verwechselt werden.Die beiden Konzepte sind ziemlich unterschiedlich, obwohl wir oben gezeigt haben, dass sie zusammenhängen können. Es könnte interessant sein, eine detaillierte Taxonomie der Verwendung der von Gilles'answer aufgezählten Terminologie zu haben, um zu sehen, ob die Verwendung jedes dieser Wörter mehr auf die eine oder die andere Konnotation ausgerichtet ist.
Namen sind nicht mehr als das, was sie in einem bestimmten Kontext bedeuten, von wem auch immer der Diskurs definiert wird. Einige Verwendungen sind häufiger, natürlicher oder konsistenter, aber man sollte immer nach Definitionen suchen und sicherstellen, welche Bedeutung in jedem Kontext beabsichtigt war. Und man sollte nicht immer erwarten, dass die Terminologie mit Geschmack oder Beständigkeit gewählt wurde.
quelle
NIL ist ein Objekt mit einem Wert, der dem Programmierer mitteilt, dass das Objekt ungültig ist. Dies ist besonders nützlich in C ++, wo NULL als 0 definiert ist. Wenn Sie die Referenzierung von NULL in C ++ aufheben, tritt undefiniertes Verhalten auf. Wenn Sie den Verweis auf NIL aufheben (einen Zeiger auf ein leeres Objekt, das Sie definiert haben), erhalten Sie ein Objekt, von dem Sie erkennen können, dass es sich jenseits des Endes Ihrer Datenstruktur befindet. Es ist großartig, um katastrophale Programmfehler zu verhindern und Fehler zu erkennen.
Sie können NIL in Fällen wie doppelt verknüpften Listen verwenden. Dabei muss es sich um den Anfang und das Ende der Liste handeln, um den Überblick über Kopf und Ende zu behalten. Stellen Sie außerdem sicher, dass die Verweise -> next und -> prev NULL nicht de-referenzieren.
quelle