Datenstrukturen: Unterschied zwischen den Versionen

Aus Das Sopra Wiki
← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
VisuellWikitext
Dietsch (Diskussion | Beiträge)
Bürokraten, sopra, sopra17, sopradozenten, soprapre17, Administratoren
2.877 Bearbeitungen
Keine Bearbeitungszusammenfassung
Dietsch (Diskussion | Beiträge)
Bürokraten, sopra, sopra17, sopradozenten, soprapre17, Administratoren
2.877 Bearbeitungen
Zeile 165: Zeile 165:
|}
|}


=== zwei-elementige Datenstrukturen ===
<h3> zwei-elementige Datenstrukturen </h3>
<p>Alle Datenstrukturen in dieser Liste haben folgendes gemeinsam:
</p><p><br />
</p>
<ul><li>Keys müssen eindeutig sein.
</li></ul>
<ul><li>Die Add-Methode wirft eine Exception wenn der Key bereits vorhanden ist.
</li></ul>
<ul><li>Die Values können über die <a href="http://msdn.microsoft.com/en-us/library/9tee9ht2.aspx">Item-Property</a> der Datenstruktur angesprochen werden:<br /><span class="fck_mw_source" _fck_mw_customtag="true" _fck_mw_tagname="source" lang="csharp">myDataStructure[key] = expression;</span>Dabei wird ein Wert
</li></ul>
<ul><li><ul><li>wenn der Key bereits vorhanden ist überschrieben
</li></ul>
</li></ul>
<ul><li><ul><li>wenn der Key noch nicht vorhanden ist neu angelegt.
</li></ul>
</li></ul>
<ul><li>Sie implementieren das <a href="http://msdn.microsoft.com/en-us/library/system.collections.idictionary.aspx">IDictionary</a>-Interface.
</li></ul>
<p><br />
</p><p><br />
</p>
<table class="default">


{| class="default"
<tr>
|-
<td class="blank"> <br />
| class="blank" | <br>
</td><th colspan="6"> Laufzeiten von Methoden
! colspan="6" | Laufzeiten von Methoden
</th><td class="blank"> <br />
| class="blank" | <br>
</td></tr>
|-
<tr>
| class="blank" | <br>
<td class="blank"> <br />
! Add
</td><th> Add
! Remove
</th><th> Remove
! ElementAt
</th><th> ElementAt
! Contains
</th><th> Contains
! Clear
</th><th> Clear
! Count
</th><th> Count
! Element-Typ
</th><th> Element-Typ
! [[ThreadSafety|Thread-safe]]
</th><th> <a href="ThreadSafety">Thread-safe</a>
! Bemerkungen
</th><th> Bemerkungen
|-
</th></tr>
! [http://msdn.microsoft.com/en-us/library/xfhwa508.aspx Dictionary&lt;TKey, TValue&gt;]
<tr>
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity<br>
<th> <a href="http://msdn.microsoft.com/en-us/library/xfhwa508.aspx">Dictionary&lt;TKey, TValue&gt;</a>
| O(1)<br>
</th><td> O(1)<br />O(n) wenn Count + 1 &gt; Capacity<br />
| <br>
</td><td> O(1)<br />
| O(1)<br>
</td><td> <br />
| <br>
</td><td> O(1)<br />
| <br>
</td><td> <br />
| <br>
</td><td> O(1)<br />
| Nein<br>
</td><td> <a href="http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx">KeyValuePair&lt;TKey,TValue&gt;</a><br />
| class="close" | <br>
</td><td> Nein<br />
|-
</td><td class="close">
! [http://msdn.microsoft.com/en-us/library/f7fta44c.aspx SortedDictionary&lt;TKey, TValue&gt;]
<p>Verfügt über <a _fcknotitle="true" href="TryGetValue">TryGetValue</a>-Methode<br />
| O(log n)<br>
</p><p><br />
| O(log n)<br>
</p>
| <br>
</td></tr>
| O(log n)<br>
<tr>
| <br>
<th> <a href="http://msdn.microsoft.com/en-us/library/f7fta44c.aspx">SortedDictionary&lt;TKey, TValue&gt;</a>
| <br>
</th><td> O(log n)<br />
| <br>
</td><td> O(log n)<br />
| Nein<br>
</td><td> <br />
| class="close" | schneller als SortedList bei unsortierten Daten<br>
</td><td> O(log n)<br />
|-
</td><td> <br />
! [http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx Hashtable]
</td><td> <br />
| <br>
</td><td> <br />
| <br>
</td><td> Nein<br />
| <br>
</td><td class="close">
| <br>
<p>Verfügt über <a _fcknotitle="true" href="TryGetValue">TryGetValue</a>-Methode
| <br>
</p><p>schneller als SortedList bei unsortierten Daten<br />
| <br>
</p><p><br />
| <br>
</p>
| Read-Only mit einem schreibenden Thread<br>
</td></tr>
| class="close" | <br>
<tr>
|-
<th> <a href="http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx">Hashtable</a>
! [http://msdn.microsoft.com/en-us/library/ms132319.aspx SortedList&lt;TKey, TValue&gt;]
</th><td> <br />
| O(n)<br>
</td><td> <br />
| O(n)<br>
</td><td> <br />
| <br>
</td><td> <br />
| O(log n)<br>
</td><td> <br />
| <br>
</td><td> <br />
| <br>
</td><td> <br />
| <br>
</td><td> Read-Only mit einem schreibenden Thread<br />
| Nein<br>
</td><td class="close">
| class="close" | schneller als SortedDictionary bei vorsortierten Daten<br>
<p><br />
|}
</p><p><br />
</p>
</td></tr>
<tr>
<th> <a href="http://msdn.microsoft.com/en-us/library/ms132319.aspx">SortedList&lt;TKey, TValue&gt;</a>
</th><td> O(n)<br />
</td><td> O(n)<br />
</td><td> <br />
</td><td> O(log n)<br />
</td><td> <br />
</td><td> <br />
</td><td> <br />
</td><td> Nein
</td><td class="close">
<p>Verfügt über <a _fcknotitle="true" href="TryGetValue">TryGetValue</a>-Methode
</p><p>schneller als SortedDictionary bei vorsortierten Daten<br />
</p><p><br />
</p>
</td></tr></table>


== Referenzen ==
== Referenzen ==
Abgerufen von „https://sopranium.de/Datenstrukturen“