3.1.29

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

官方实现:https://algs4.cs.princeton.edu/31elementary/TestBinarySearchST.java.html

官方实现中有几处错误,需要做一些修改。

/* 省略 */

Console.WriteLine("Testing Select()");
Console.WriteLine("-----------------------------------");
for (int 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 (string 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

另请参阅

SymbolTable 库

上一题 下一题