Diskussion:Datenstruktur

„Felder“ (und Arrays) werden auch „Reihung“ genannt

Zu Feldern(Arrays) sagt man heutzutage Reihung. -- Meiko Michalsky 217.225.24.32 10:25, 22. Jun 2004 (CEST)

Das bezweifle ich. Die meisten sagen Feld, Array oder Vektor. --Coma 11:11, 22. Jun 2004 (CEST)

Der Begriff Reihung wurde ca. 1958 von Bauer geprägt im Rahmen der begrifflichen Eindeutschung der Informatikbegriffe --SonniWP2 22:12, 8. Aug. 2007 (CEST) ^{<ref>Bauer+Goos: Einführung in die Informatik, Band 1 </ref>}

Danke für die Hinweise. Es ist schön zu sehen, daß es auch (noch/wieder) Bestrebungen in diese Richtung gibt – also was den Erhalt und die Pflege unserer Sprache angeht. Zudem habe ich dazu mal eben auch noch das Wort (zusammen mit einem Beleg, siehe auch [1]) in den nebenstehenden Artikel eingefügt. MfG, 92.226.62.88 12:19, 6. Mai 2013 (MESZ)

Der Referenzlink zeigte auf ein Buch, nach dem 'Reihung' als Synonym für 'Array' benutzt wird - was ich grds. für OK halte. 'Datenstruktur' ist aber der Überbegriff, und für den Steht 'Reihung' wohl nicht. Mann könnte den Link evtl. bei 'Array' nachtragen. --VÖRBY (Diskussion) 12:32, 6. Mai 2013 (CEST)

Das schließt sich doch aber nicht aus. Soweit ich das in dem genannten Buch eben gelesen habe, wird das Wort dort sowohl für ein „Datenfeld“ (kurz „Feld“ oder englisch und daher hier fremd und zudem auch noch etwas länger

array

) als auch allgemeine(er u.a.) für (beliebige) „Datenstrukturen“ genutzt. Zudem wird auch genau das dort mit „Das Konzept der Reihung ist zu allgemein (nicht nur Zahlen können aufgereiht werden), [..]“ dort beschrieben. Deine totale Zurücksetztung des Beitrages dazu erscheint hier deshalb als völlig unangebracht – ebenso was deine nebensächliche Randbemerkung zu den beiden dabei wohl etwas besser übersetzten Fremdwörtern Definition (zu dt. oder de eben auch die „Festlegung“) sowie das im selben Satz etwas später genannte Spezifikation (zu dt. auch die „(genaue) Beschreibung“) angeht. 92.225.50.73 16:08, 7. Mai 2013 (MESZ)

Sorry, ich kann dir nicht zustimmen: In S.66 ist 'Reihung' klar als Synonym für Array beschrieben - die mit Schleifen und Index durchlaufen werden. Auch S. 71 handelt noch von 'Schleifen', also indiziert bearbeiteten Tabellen/Arrays. S79/80 unterscheiden Reihung (= Array) und 'unterschiedliche Daten' (= 'Verbund'). S81 führt 'bedarfsgerechte' Reihungen auf; ja das sind unterschiedliche Varianten von Arrays. S83 beschreibt die Kombination von Reihung und Verbund. Auch S87: ... Elemente eines jeden Typs IN DER REIHUNG. S 126 Reihung = array. S 136 zeigt zweidimensionale Arrays/Reihungen. Weiter will ich nicht zutieren, du verwechselst da also eindeutig etwas. Und Reihung ist keinesfalls ein Synonym zu 'Datenstruktur', das schließt sich wohl aus, weil Array eine Variante von DS ist, DS aber der Überbegriff.
Zu deinem Argument: Natürlich können nicht nur Zahlen gereiht werden - sondern alle Datentypen (bin, Text ...), aber immer als Array/Tabelle verstanden. Für 'beliebige Datenstrukturen' verwendet deine Quelle den Begriff 'Reihung' NICHT. Deine Ergänzung und der dazu vermeintlich passende Beleg waren also ein Missverständnis.

• Zu 'Definition': Du hattest einfach das Synonym 'Abgrenzung' aus dem Artikel Definition eingesetzt und nicht bemerkt, dass mit 'Definition' hier etwas anderes (und hier Unpassendes) gemeint ist als das dort Beschriebene; zur Klarstellung habe ich auch dort die Bedeutung von 'Definition' i.S. von 'Deklaration (Programmierung)' ergänzt.
  
• Auch unter Spezifikation ist nicht das beschrieben, was hier im Artikel gemeint ist; das ist nämlich eine Deklaration, während unter Sp. üblicherweise eine Vorgabe zur Implementierung verstanden wird.

Insofern sind die beiden Begriffe jetzt wohl passender. Leider war schon der erste Satz hier in der Diskussion uneindeutig (Zu Feldern (Arrays) sagt man heutzutage „Reihung“). Das kam wohl daher, dass das aus der BKS Reihung verlinkte Feld (Datentyp) verwirrend beschrieben ist - dort heißt es aber schließlich, ein Feld sei ein Array (was ich für unkorrekt halte). Beweis: Dort ist 'Standardfeld' (als Reihung (mit Index) beschrieben) und auch andere Formen von Array-Strukturen, was also mit deiner Quelle übereinstimmt. 'Feld' ist m.E. elementar und kann in unterschiedlichen Strukturvarianten auftreten.
Danke trotzdem für deine Bemühungen. --VÖRBY (Diskussion) 18:53, 7. Mai 2013 (CEST)

Abstimmung mit Artikel Datentyp dringend nötig

Hallo Coma, warum hast du denn so einen kurzen und unvollständigen Stub zu Abstrakter Datentyp erstellt, ohne die bereits vorhandenen Informationen aus Datentyp zu berücksichtigen. Mir ist aufgefallen, dass du ebenfalls unter Datenstruktur eine sehr lange Liste von Beispielen aufgebaut hast. Wenigstens das, was du konkrete Datenstruktur nennst, ist aber ein Datentyp. Ich würde mich freuen, wenn du versuchen könntest, den Artikel Datenstruktur in enger Abstimmung zu Datentyp weiterzuentwickeln. So ist es jedenfalls der klare Weg in eine Baustelle. Antworten auf diese Frage bitte in Diskussion:Datenstruktur, wohin ich diese Anfrage kopieren werde.
(Der vorstehende Beitrag stammt von Frank Jacobsen – 20:41, 25. Sep. 2004 (MESZ) – und wurde nachträglich unterschrieben.)

Ich habe mir dazu nicht all zu viele Gedanken gemacht, weil der Artikel erstmal nur als Stub für andere Artikel in der Kategorie Datenstruktur herhalten muss. Ich habe das ganze auch nicht wirklich verbrochen, sondern nur versucht etwas in der Kategorie Datenstruktur aufzuräumen und an den wichtigen Stellen Erweiterungen vorzunehmen, speziell arbeite ich gerade an den Heaps. Ursprünglich gab es glaube diesen doofen Redirect von abstrakte Datenstruktur auf abstrakter Datentyp. Da ich mir nur wenig Gedanken gemacht habe, habe und es an sich möglich war, habe ich einfach auch abstrakte Datenstruktur mit in den Artikel reingeschrieben. Jetzt erkenne ich aber, dass es eigentlich blödsinn war, besser wäre ein eigener Artikel zu Abstrakte Datenstruktur, denn eine Datenstruktur ist etwas anderes, als ein Datentyp. Ersteres kann nämlich durchaus aus mehreren Datentypen aufgebaut sein. Ich werde das entsprechend ändern. Was du mit dem Artikel abstrakter Datentyp dann machst, ist mir egal. Was ich konkrete Datenstruktur nenne, ist also nicht unbedingt ein Datenyp und auch die lange Liste stammt nicht nur von mir, ich habe sie nur zuletzt mal wieder aufgeräumt und auf wichtige Strukturen beschränkt. --Coma 22:06, 25. Sep 2004 (CEST)

Um das ganze mal ein wenig konkreter zu fassen. Es gibt aus meiner Sicht in den beiden Artikeln Datentyp und Datenstruktur nun zumindest die sechs folgenden Begriffe:

1. Datentyp
2. Datenstruktur
3. Abstrakter Datentyp
4. Konkreter Datentyp
5. Abstrakte Datenstruktur
6. Konkrete Datenstruktur

Diese werden zum Teil nicht konsistent verwendet. Hier muss eine Harmonisierung her. Ich mache mal einen Versuch:
Sowohl mit dem Lemma von Datentyp und auch Datenstruktur bin ich einverstanden.
Im Artikel Datentyp heisst im Abschnitt Abstrakter Datentyp: Alle Datentypen, die über die zugehörigen Operationen eine Funktionalität bieten, die von dem verwendeten Wertebereich bzw. Objekt unabhängig ist, sind abstrakte Datentypen (ADT). Auch bei den abstrakten Datentypen ist die Abgrenzung zu den Datenstrukturen schwierig, da die Datentypen je nachdem, ob der Schwerpunkt der Betrachtung auf den Daten oder auf den darauf definierten Operationen liegt, Datenstruktur oder Abstrakter Datentyp genannt werden.
Die Aussage im zweiten Satz stützt die These, dass jede Datenstruktur automatisch abstrakt ist. Natürlich ist es richtig zu sagen, dass jede Datenstruktur nur eine Spezifikation ihrer Operationen beinhaltet. Ob man dies jedoch sprachlich durch Voranstellung des Begriff Abstrakt betonen muss, halte ich für zweifelhalt. Aus meiner Sicht ist es vollkommend ausreichend, ja sogar zielführender, im Artikel Datenstruktur daraufhinzuweisen, dass die konkreten Implementierungen der Datenstrukturen stark differieren können. Die Schwierigkeit mit dem Begriff Konkrete/Abstrakte Datenstruktur zeigt sich auch schon an der Liste in diesem Artikel. Aus meiner Sicht sind dies alles Datenstrukturen, auch wenn man über das Array streiten könnte. ( Ja, im Sinne deiner Argumentation, dass Datenstrukturen aus verschiedenen Datentypen aufgebaut sein können, ist auch ein Array eine Datenstruktur.) Welcher der genannten Datenstrukturen soll den eine Konkrete Datenstruktur sein ??
Zu guter letzt wird in diesem Artikel auch noch der Begriff Konkreter Datentyp verwendet. Was ist denn das ???
Meine Konklusio: Ein Abstrakter Datentyp läßt sich schwer von einer Datenstruktur unterscheiden. Eine Differenzierung in Abstrakte und Konkrete Datenstruktur bedarf es nicht. Sinnvoll wäre es vielleicht den Abschnitt Abstrakter Datentyp aus Datentyp und den Artikel Datenstruktur zu einem guten Artikel zu kombinieren, weil diese Begriffe sehr schwierig voneiander abzugrenzen sind. Den Begriff Konkreter Datentyp gibt es nach meiner Kenntnis nicht, er sollte nicht weiter verwendet werden.
Und zum Abschluß noch folgender Hinweis: Das ich im Artikel Abstrakter Datentyp machen dürfe, was ich wolle, legt unterschwellig die Vermutung nahe, das damit eine Aufteilung in: Mach du, was du willst bei den Datentypen, ich mach dann, was ich will bei den Datenstrukturen erreicht werden soll. Ich wünsche mir, dass wir mit der Bündelung unseren Know-Hows beide Artikel, die sehr grundlegend für die Informatik sind, so aufeinander abstimmen, dass sie in sich schlüssig sind. --Friese 23:13, 25. Sep 2004 (CEST)

Zur letzten Bemerkung: Das war so nat. nicht gemeint und Abstimmen tun wir uns ja gerade.

Zum Inhalt: Offensichtlich gibt es das Problem die Begriffe Datentyp und Datenstruktur voneinander zu trennen, da sind wir uns wohl einig. Das Problem besteht darin, dass die Unterschiede nicht ganz offensichtlich sind und daher schwierig herauszuarbeiten. Ich versuche jetzt mal einen anderen Ansatz.

• Der Begriff Datentyp orientiert sich stark an Programmiersprachen, die nat. eine saubere Definition, insbesondere auch des Attributes "abstrakt" verlangen. In einer Programmiersprache muss ein Datentyp genau sagen, was er ist und was man mit ihm machen kann.
• Der Begriff Datenstruktur entstammt eher aus der Sichtweise der Mathematik/theoretischen Informatik und lehnt sich maximal an Pseudocode an. Eine Datenstruktur ist damit immer ein etwas schwammigeres Konzept. Dennoch unterscheidet man hier zwischen "abstrakt" und "konkret", wobei beide Begriffe hier etwas vom Standpunkt des Betrachters abhängen. Die Datenstruktur Heap ist natürlich zunächst als "abstrakt" zu bewerten, weil sie nur bestimmte Operationen verlangt (insert, delete, extractMin). Die Datenstrukturen Binärer Heap, Binomial-Heap und Fibonacci-Heap sind hingegen sehr konkret und es ist hinreichend genau beschrieben, wie sie zu arbeiten haben, auch wenn einige unwichtige Details der Implementierung nicht genannt werden oder Implementierungen aus gutem Grund (besserer Performance) vom Original-Paper abweichen, welches aus Gründen der Kürze, Lesbarkeit und Beweisbarkeit diese Details auslässt.

Das Attribut konkret stellt in gewisser Hinsicht das Gegenteil von abstrakt dar. Ist aber zumindest bei Datentypen scheinbar weniger gebräuchlich.

Ansonsten hatten wir eine Unterscheidung von Datentyp und Datenstruktur dahingehend gemacht, dass Datenstrukturen aus mehreren Datentypen bestehen können. Das ist bestenfalls verkürzt dargestellt. Ich will mal probieren es etwas zu präzisieren. Eine Datenstruktur kann aus unterschiedlichen Datentypen aufgebaut sein, die irgendwie ineinandergreifen und zusammenhängen. Erst dieses Konglomerat zusammen mit den Operationen auf diesem bildet dann die Datenstruktur. Wobei auch letzteres wieder Auslegungssache sein könnte. Datenstruktur meint ja scheinbar mehr die Form der Daten, weniger wie auf ihnen operiert wird. Dennoch ist eine Beschreibung der Struktur relativ nutzlos, wenn man nicht weiß, wie darauf effizient operiert werden kann. Insofern sollte man die Operationen nat. schon zur Datenstruktur dazurechnen, zumal diese auf der selben Struktur unterschiedlich ausfallen können. --Coma 15:29, 26. Sep 2004 (CEST)

Ich denke, wir sind inhaltlich sehr nah beieinander. Ich habe schon mal den Teil des Abstrakten Datentyp aus Datentyp ausgelagert. Am Stil werde ich noch ein wenig feilen, sobald die beiden aufeinander abgestimmt sind, werde ich auch die Abgrenzung zu den Datenstrukturen hier noch einbringen. Ausserdem werde ich mich dran machen und aus der unsäglichen Liste in diesem Artikel Fließtext zu erzeugen. Zu deiner Überarbeitung: ich würde wirklich nicht empfehlen noch weitere Artikel für abstrakte und konkrete Datenstrukturen anzulegen. Besser ist es, denke ich, in diesem Artikel noch weiter auszuführen, dass Datenstrukturen durch ihre vorhandene Spezifikation (wenig Relevanz der Implementation) stets abstrakt sind. Dass man jedoch durch weitere Konkretisierung der Datenstrukturvorschriften und Vorgabe zu den Operationen zu spezielleren Datenstrukturen kommt. Z.T. sind die Vorgaben dann sehr konkret. Jedoch durch die fehlenden Implementationsvorschriften sind und bleiben auch diese konkretisierten Datenstrukturen abstrakt. Um mal mit deinen ;-) Heaps zu sprechen: Heap (abstrakte Datenstruktur und je nach Blinkwinkel auch abstrakter Datentyp), Binomialheap (teilweise sehr konkrete Vorgaben zu den Operationen, weniger abstrakt, aber letztlich immer noch Heap und auch ein abstraktes Gedankengebilde, welches erst durch eine Implementierung konkret würde.) Na ja, ich werde das morgen mal in ordentliche Sätze fassen und hier ergänzen--Friese 23:41, 27. Sep 2004 (CEST)

Heißt es nicht Implementierung statt Implementation?

(Der vorstehende Beitrag stammt von 88.76.58.167 – 12:39, 15. Apr. 2007 (MESZ) – und wurde nachträglich unterschrieben.)

Jain, im latein-amerikanisch-englisch angehauchten Fachsprech heißt es wohl Implementation oder Implementierung, und hier im Deutschen heißt es wohl (besser) „Ausführung“, „Umsetzung“ oder „Verwirklichung“. ;-) MfG, 92.225.56.249 15:27, 5. Mai 2013 (MESZ)

Ich hab mir erlaubt das Thema mal wieder aufzugreifen und hab unter Diskussion:Datentyp eine Diskussion dazu gestartet ... rege Beteiligung wäre gut ;-) Gruß --Jkrieger 11:28, 30. Jun 2005 (CEST)

Liste zu Fließtext

Mit der neuen Reihenfolge bin ich einverstanden. Einzig der Text im Abschnitt Liste erscheint mir verschlimmbessert. Ich finde ihn zu wenig konkret, auch wenn ich weiß, was du meinst. Ein Ausdruck wie 'relativ unspezifiziert' oder 'sie scheint aber nach außen so' sollte nochmal überdacht werden. Ansonsten sind wir nicht mehr weit davon entfernt, dass ich für meinen Teil zufrieden bin. Coma, könntest du im WikiProjekt Informatik, mal diejenigen Artikel aus dem Unterbereich Datenstruktur ent-kursiv-fizieren, die du für ok hältst.
(Der vorstehende Beitrag stammt von Frank Jacobsen – 19:37, 5. Okt. 2004 (MESZ) – und wurde nachträglich unterschrieben.)

"Liste" ist auch nicht korrekt. Eine Liste ist nicht automatisch eine verkettete Liste, wobei die Art des Zusammenhanges dann doch eher Richtung Datentyp, anstatt Datensturktur geht. Eine Liste hat im Gegensatz zum Array in erster Linie keine fixen Indizes. Wäre es vielleicht auch denkbar "Treap" zu erklären? "Ein Heap ist eine Mischung aus Baum und ..." und ein Treap ist eine Mischung aus "Baum und Heap"?

(Der vorstehende Beitrag stammt von 85.178.176.73 – 02:48, 11. Feb. 2009 (MEZ) – und wurde nachträglich unterschrieben.)

Beispiele

Ein paar aussagekräftige Beispiele für einzelne Datenstrukturen könnten dem Leser helfen, die Inhalte "intuitiv" zu verstehen. Gruss, --Markus Bärlocher 16:55, 29. Mai 2007 (CEST)

Definition balancierter Binärbaum falsch

Die Definition im Artikel zielt zu sehr auf AVL-Bäume ab. Richtiger fände ich es wenn man sagt, dass die Höhe des Baumes O(log n) (wobei n anzahl der Knoten) beträgt
(Der vorstehende Beitrag stammt von 212.5.16.225 – 14:41, 4. Dez. 2009 (MEZ) – und wurde nachträglich unterschrieben.)

Datenstruktur VS Datenbank

...da wäre noch eine genaue Abgrenzung hilfreich -- 131.173.197.199 21:19, 28. Mär. 2010 (CEST)

ist doch im ersten Satz - "mathematisches Objekt". "Datenbank" schreibt dagegen "System zur elektronischen Datenverwaltung". --Chire 14:56, 20. Apr. 2010 (CEST)

Record als Strukturvariante

Im Artikel werden (in #Grundlegende Datenstrukturen) nur die einzelnen Varianten, in denen Daten abgelegt werden können, als 'Datenstruktur' bezeichnet. Dies finde ich, auch i.Z. mit der 'uneindeutigen' Einleitung, für unvollständig.
Im englischen Artikel heißt die Einleitung einfach: In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.[1][2] Außerdem beschreibt die en:WP (in Overview) auch 'Record' als Strukturtyp (siehe dort). HIER IM Artikel fehlt dieser Typ - was mir deshalb problematisch erscheint, weil gerade diese Strukturvariante (~Datensatz) in vielen Fällen als 'klassische Bedeutung' von 'Datenstruktur' verstanden wird, manchmal sogar als Synonym. Der Artikel sollte insofern ergänzt werden.--VÖRBY (Diskussion) 13:51, 21. Mär. 2013 (CET)

'Datensatz' als Strukturvariante (aus en:WP ergänzt; Einleitung ebenfalls geringfügig angepasst. Verwendung von Datensatz als 'Synonym' für Datenstruktur nicht eingefügt. --VÖRBY (Diskussion) 09:31, 28. Mär. 2013 (CET)

Speicherplatzverschwendung

Speicherplatzverschwendung macht wenig Sinn, denn der Platz ist ja nicht verschwendet, sondern hat auch einen Nutzen (bessere Laufzeit gewisser Operationen). Eigentlich ist es ja nur zusätzlich notwendiger Speicherplatz, dafür gibt es sicher ein passenderes Wort (mir fällt leider gerade keines ein). -- 10:54, 20.07.2013

Hab das mal ersetzt --Jkrieger (Diskussion) 11:14, 20. Jul. 2013 (CEST)

"Indizierung"

Bei der Gelegenheit "Speicherplatzverschwendung" in der Tabelle (siehe letzter Diskussionsabschnitt), frage ich mich, was mit "Indizierung" gemeint ist: Ein Indexzugriff? Also "gib mir das 5. Element", oder das Erstellen eines Index (denke ich nicht, das wäre bei einem Array nicht O(1)). Soll man also "Indizierung" durch "Indexzugriff" ersetzen? Dabei stellt sich natürlich auch die Frage, warum man so eine Operation in einem Baum durchführen will und welche Ordnung dabei gewünscht ist, die ist ja per-se für einen Baum nicht definiert und davon hängt ja auch die Komplexität des "Indexzugriffs" ab (und natürlich von der Implementierung des Baums!). --Jkrieger (Diskussion) 11:14, 20. Jul. 2013 (CEST)

Mit "Indizierung" ist hier der Zugriff auf ein beliebiges/zufälliges Element gemeint. Ich habe das mal korrigiert.

Und ja, es ist korrekt, dass man bei einem Baum auch eine zugehörige Ordnung definieren muss. Warum allerdings Werte in einem Baum gespeichert werden, hängt stark von der konkreten Verwendung ab. Typischerweise werden Indizes (in diesem Fall ein Index der Daten :) ) in einem Baum gespeichert, da die Suche dort konstant und mit geringem Aufwand möglich ist. --Plankton314 (Diskussion) 11:47, 20. Jul. 2013 (CEST)

Moin! ja, so ist's deutlich klarer ... mit dem Baum: eben ... einen "random access" hat man eigentlich (fast) nur, wenn über alle Elemente des Baums iteriert werden soll ... ansonsten hätte man wohl eher keinen Baum als Datenstruktur gewählt ;-) --Jkrieger (Diskussion) 13:52, 20. Jul. 2013 (CEST)

Θ?

Dem Verständnis zuträglich wäre, wenn im Absatz "Speicher- und Rechenaufwand von Datenstrukturen" ein Link ist, der auf das Lemma verweist, welches die "Θ"s erklärt, falls ein solcher existiert. Ich kenne mich da nicht aus, darum möchte ich die Experten bitten, es zu machen. 46.114.31.119 13:20, 22. Okt. 2014 (CEST)

Erledigt, ich habe das erste Θ (Theta) zu "Landau-Symbole" verlinkt. Ist das so okay? --Divof (Diskussion) 14:53, 25. Mär. 2016 (CET)

Zugriff auf ein beliebiges/zufälliges Element

Ich verstehe nicht, was damit gemeint ist. Es erinnert ein bisschen an RANDOM. Das wäre „direkter Zugriff“. „beliebig/zufällig“ könnte man ja einfach würfeln und dann kommt es darauf an, wie man mit dem Würfelergebnis in die Datenstruktur kommt. Ich hab's mal nach unten degradiert, ich befürworte aber eine Streichung der Zeile. --Nomen4Omen (Diskussion) 20:04, 7. Jan. 2016 (CET)

Speicher- und Rechenaufwand von Datenstrukturen

Wäre es hier nicht hilfreich, eine textuelle Erläuterung anzufügen? --Divof (Diskussion) 14:45, 25. Mär. 2016 (CET)

Grundsprachumfang

Unter Datenstruktur#Array ist im Februar 2018 zu lesen: "Wegen ihrer Einfachheit und grundlegenden Bedeutung bieten die allermeisten Programmiersprachen eine konkrete Umsetzung dieser Datenstruktur als zusammengesetzten Datentyp Array im Grundsprachumfang an.".

Was ist ein Grundsprachumfang? --2.247.243.157 21:56, 25. Feb. 2018 (CET)