我想知道人们如何在不使用基类库实现的情况下在C＃中实现以下数据结构：
-
链表
-
哈希表
-
二进制搜索树
-
红黑树
-
B树
-
二项式堆
-
斐波那契堆
以及人们能想到的任何其他基本数据结构！
我很好奇，因为我想提高我对这些数据结构的理解，很高兴看到C＃版本而不是互联网上的典型C示例！
关于此主题有一系列MSDN文章。但是，我自己还没有真正阅读过该文本。我相信.NET的collections框架的接口已损坏，无法很好地扩展。
还有C5，我现在正在研究的一个图片库。
由于上述原因，我已经有一个项目为.NET实现我自己的集合库，但是在第一个基准测试表明即使是一个简单的，非线程安全的通用Vector实现也较慢之后，我就停止了该项目。比原生的List< T >。由于我一直在注意不要产生任何效率低下的IL代码，因此这意味着.NET根本不适合(尚未)编写内部数据结构的按比例替换，而且.NET框架必须使用一些隐藏的替代方法。 -场景知识以优化内置集合类。
这是通用的二进制搜索树。我唯一没有做的就是实现IEnumerable < T >，因此您可以使用枚举器遍历树。但是，这应该很简单。
特别感谢Scott Mitchel的BSTTree文章，我将其用作delete方法的参考。
节点类：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 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类：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
| 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--;
}
}
} |
NGenerics
"一个类库，提供未在标准.NET框架中实现的通用数据结构和算法。"
对于您提到的数据结构，我建议两个资源：
首先，有.NET Framework源代码(有关信息，请参见ScottGu的博客)。
另一个有用的资源是在Codeplex上的Wintellect的Power Collections。
希望这可以帮助！
也可以查看Rotor 2(http://research.microsoft.com/sscli/)或使用反射器(http://www.red-gate.com/products/reflector/)，看看微软是如何做到的！！
