我正在调试来自我的数据结构类项目的错误搜索返回。当前的这个项目要求我们构建一个有序展开链表,并对内容进行搜索,然后返回从包含起点到排他终点的项目子列表。为此,我必须搜索内部数组以找到起始元素的索引点。我通过二分搜索来做到这一点,但由于这只返回第一个找到的匹配并且在它之前可能还有其他匹配,所以我必须在数组中返回以找到第一个真正的匹配。我这样做是通过
//get first index match, work backwards
int index= binarySearch(node.items, 0, node.numUsed, item, comp);
while (index>0 && comp.compare(node.items[index], item)==0){
index--;
}
教授提供了测试代码,它分解了一个字符串并将每个字符作为一个项目添加到结构中。他还包括一个嵌套的 StringCmp 类,它在上面的二分搜索声明中被引用comp
。他的比较方法是
public int compare(String s1, String s2) {
cmpCnt++;
return s1.compareTo(s2);
}
但是,当对从 i 到 o 的子列表方法运行测试时,此方法在何时返回一个真值comp.compare(h,i)==0
,这会从我编写的搜索类中抛出我的开始结果。我最初的补偿return index++
足以通过结构测试,但将预期的起点偏离了一个。
那么,当它显然是错误的时候,为什么它会返回 true 呢?
编辑添加了子列表方法的打印输出,预计从 i 运行到 o
输入测试字符串 =abcdefghijklmnopqrstuvwxyzaeiou
从子列表方法返回:
块 1(使用 4 of 10):[h][i][i][j]
块 2(使用 4 of 10):[k][l][m][n ]
h 根本不应该在列表中,但是comp.compare(node.items[index], item)==0
i == h 返回 true,这显然是错误的。
编辑二 项目的第二部分要求我们解析一个文本文件,从 Artist、Title 和 Lyrics 字段构建 Song 对象,然后使用前缀对标题进行搜索。这里发生的错误不会出现在单字母和多字母搜索中,所以我认为问题出在测试中的 StringCmp 嵌套类。