基本クラス ライブラリの実装を使用せずに、C# で次のデータ構造を実装する方法を知りたいです。
- リンクされたリスト
- ハッシュ表
- 二分探索木
- 赤黒の木
- Bツリー
- 二項ヒープ
- フィボナッチヒープ
そして、人々が考えることができる他の基本的なデータ構造!
これらのデータ構造の理解を深めたいので興味があります。インターネットに出回っている典型的な C の例ではなく、C# のバージョンを参照してください。
4478 次
5 に答える
9
このテーマに関する一連のMSDN 記事があります。とはいえ、私自身はテキストをよく読んだことがありません。.NET によるコレクション フレームワークはインターフェイスが壊れていて、うまく拡張できないと思います。
私が現在調査しているライブラリであるC5もあります。
上記の理由により、私は .NET 用に独自のコレクション ライブラリを実装するプロジェクトを持っていましたが、最初のベンチマークで、単純でスレッドセーフでない一般的なVector実装でさえネイティブよりも遅いことが明らかになった後、このプロジェクトを停止しました。 List<T>. 非効率な IL コードを作成しないように注意したので、これは、.NET が (まだ) 組み込みデータ構造の同等の置換を作成するのに適していないことを意味し、.NET フレームワークは背後でいくつかのコードを使用する必要があることを意味します。 -組み込みのコレクション クラスを最適化するためのシーンの知識。
于 2008-09-07T11:06:32.477 に答える
4
これが一般的な二分探索木です。私がしなかった唯一のことは、列挙子を使用してツリーをトラバースできるようにIEnumerable<T>を実装することでした。ただし、それはかなり簡単なはずです。
BSTTreeの記事を提供してくれたScottMitchelに特に感謝します。これを、deleteメソッドのリファレンスとして使用しました。
ノードクラス：
class BSTNode<T> where T : IComparable<T>
{
private BSTNode<T> _left = null;
private BSTNode<T> _right = null;
private T _value = default(T);
public T Value
{
get { return this._value; }
set { this._value = value; }
}
public BSTNode<T> Left
{
get { return _left; }
set { this._left = value; }
}
public BSTNode<T> Right
{
get { return _right; }
set { this._right = value; }
}
}
そして実際のTreeクラス：
class BinarySearchTree<T> where T : IComparable<T>
{
private BSTNode<T> _root = null;
private int _count = 0;
public virtual void Clear()
{
_root = null;
_count = 0;
}
public virtual int Count
{
get { return _count; }
}
public virtual void Add(T value)
{
BSTNode<T> newNode = new BSTNode<T>();
int compareResult = 0;
newNode.Value = value;
if (_root == null)
{
this._count++;
_root = newNode;
}
else
{
BSTNode<T> current = _root;
BSTNode<T> parent = null;
while (current != null)
{
compareResult = current.Value.CompareTo(newNode.Value);
if (compareResult > 0)
{
parent = current;
current = current.Left;
}
else if (compareResult < 0)
{
parent = current;
current = current.Right;
}
else
{
// Node already exists
throw new ArgumentException("Duplicate nodes are not allowed.");
}
}
this._count++;
compareResult = parent.Value.CompareTo(newNode.Value);
if (compareResult > 0)
{
parent.Left = newNode;
}
else
{
parent.Right = newNode;
}
}
}
public virtual BSTNode<T> FindByValue(T value)
{
BSTNode<T> current = this._root;
if (current == null)
return null; // Tree is empty.
else
{
while (current != null)
{
int result = current.Value.CompareTo(value);
if (result == 0)
{
// Found the corrent Node.
return current;
}
else if (result > 0)
{
current = current.Left;
}
else
{
current = current.Right;
}
}
return null;
}
}
public virtual void Delete(T value)
{
BSTNode<T> current = this._root;
BSTNode<T> parent = null;
int result = current.Value.CompareTo(value);
while (result != 0 && current != null)
{
if (result > 0)
{
parent = current;
current = current.Left;
}
else if (result < 0)
{
parent = current;
current = current.Right;
}
result = current.Value.CompareTo(value);
}
if (current == null)
throw new ArgumentException("Cannot find item to delete.");
if (current.Right == null)
{
if (parent == null)
this._root = current.Left;
else
{
result = parent.Value.CompareTo(current.Value);
if (result > 0)
{
parent.Left = current.Left;
}
else if (result < 0)
{
parent.Right = current.Left;
}
}
}
else if (current.Right.Left == null)
{
if (parent == null)
this._root = current.Right;
else
{
result = parent.Value.CompareTo(current.Value);
if (result > 0)
{
parent.Left = current.Right;
}
else if (result < 0)
{
parent.Right = current.Right;
}
}
}
else
{
BSTNode<T> furthestLeft = current.Right.Left;
BSTNode<T> furthestLeftParent = current.Right;
while (furthestLeft.Left != null)
{
furthestLeftParent = furthestLeft;
furthestLeft = furthestLeft.Left;
}
furthestLeftParent.Left = furthestLeft.Right;
furthestLeft.Left = current.Left;
furthestLeft.Right = current.Right;
if (parent != null)
{
result = parent.Value.CompareTo(current.Value);
if (result > 0)
{
parent.Left = furthestLeft;
}
else if (result < 0)
{
parent.Right = furthestLeft;
}
}
else
{
this._root = furthestLeft;
}
}
this._count--;
}
}
}
于 2008-09-07T14:18:26.930 に答える
2
あなたが言及したデータ構造については、2 つのリソースをお勧めします。まず、.NET Framework のソース コードがあります (情報は、ScottGu のブログ (こちら) にあります)。
もう 1 つの便利なリソースは、ここの Codeplex にある Wintellect の Power Collectionsです。
お役に立てれば！
于 2008-09-07T11:49:22.090 に答える
2
「標準の .NET フレームワークに実装されていない一般的なデータ構造とアルゴリズムを提供するクラス ライブラリ。」
于 2009-01-19T21:00:23.943 に答える
1
Rotor 2をチェックするか、リフレクターを使用して、Microsoft がどのようにそれを行ったかを確認してください!!!
また、 Microsoftの参照元を確認することもできます
于 2008-09-08T09:35:07.040 に答える