3.1.29 #
解答 #
官方实现：https://algs4.cs.princeton.edu/31elementary/TestBinarySearchST.java.html
官方实现中有几处错误，需要做一些修改。
/* 省略 */
Console.WriteLine("Testing Select()");
Console.WriteLine("-----------------------------------");
for (var i = 0; i < st.Size(); i++) // 循环条件不能有 '='
Console.WriteLine(i + " " + st.Select(i));
Console.WriteLine();
/* 省略 */
while (!st.IsEmpty())
st.Delete(st.Select(st.Size() / 2));
Console.WriteLine("After deleting the remaining keys");
Console.WriteLine("-----------------------------------");
// 异常处理
try
{
foreach (var s in st.Keys())
Console.WriteLine(s + " " + st.Get(s));
}
catch (Exception ex)
{
Console.WriteLine("Exception: " + ex.Message);
}
Console.WriteLine();
/* 省略 */
结果如下：
size = 10
min = A
max = X
Testing Keys()
-----------------------------------
A 8
C 4
E 12
H 5
L 11
M 9
P 10
R 3
S 0
X 7
Testing Select()
-----------------------------------
0 A
1 C
2 E
3 H
4 L
5 M
6 P
7 R
8 S
9 X
key Rank Floor Ceil
-----------------------------------
A 0 A A
B 1 A C
C 1 C C
D 2 C E
E 2 E E
F 3 E H
G 3 E H
H 3 H H
I 4 H L
J 4 H L
K 4 H L
L 4 L L
M 5 M M
N 6 M P
O 6 M P
P 6 P P
Q 7 P R
R 7 R R
S 8 S S
T 9 S X
U 9 S X
V 9 S X
W 9 S X
X 9 X X
Y 10 X
Z 10 X
After deleting the smallest 3 keys
-----------------------------------
H 5
L 11
M 9
P 10
R 3
S 0
X 7
After deleting the remaining keys
-----------------------------------
Exception: called Min() with empty table
After adding back N keys
-----------------------------------
A 8
C 4
E 12
H 5
L 11
M 9
P 10
R 3
S 0
X 7