自定义类字符串列表的二叉搜索算法
本文关键字:搜索算法 列表 字符串 自定义 | 更新日期: 2024-09-21 20:11:11
基本上我需要帮助调整我的二叉搜索算法以使用我的字符串列表,如下所示。注意,我必须使用编写的二进制搜索算法,不使用内置的 c# 函数,如 .二进制搜索 .
我现在将向您展示列表的格式和列表本身:
// This class formats the list, might be useful to know
public class Demo
{
public string Col;
public string S1;
public string S2;
public string S3;
public override string ToString()
{
return string.Format("Col: {0}, S1: {1}, S2: {2}, S3: {3}", Col, S1, S2, S3);
}
}
// The list itself
var list = new List<Demo>
{
new Demo {Col = "Blue", S1 ="88", S2 ="Yes"},
new Demo {Col = "Green", S1 ="43", S2 ="Yes"},
new Demo {Col = "Red", S1 ="216", S2 ="No"},
new Demo {Col = "Yellow", S1 ="100", S2 ="No"}
};
该列表已经按"Col"字符串值的字母顺序排序,因此蓝色是第一个,黄色是最后一个。"Col"是列表中需要搜索的部分。下面我插入了我当前的二叉搜索,可以搜索 int 数组。
public static int BinarySearch_R(int key, int[] array, int low, int high)
{
if (low > high) return -1;
int mid = (low + high) / 2;
if (key == array[mid])
{
return mid;
}
if (key < array[mid]) {
return BinarySearch_R(key, array, low, mid - 1);
} else {
return BinarySearch_R(key, array, mid + 1, high);
}
}
我需要帮助调整我的二进制搜索算法以适用于上面的列表。如果你们有任何问题,或者需要查看更多我的代码,请询问。
具体答案:根据具体情况调整您的方法非常容易。
让我们首先更新现有方法,以使用更通用的方法(IComparable<T>.CompareTo
进行比较,而不是int
运算符:
public static int BinarySearch_R(int key, int[] array, int low, int high)
{
if (low > high) return -1;
int mid = (low + high) / 2;
int compare = key.CompareTo(array[mid]);
if (compare == 0)
{
return mid;
}
if (compare < 0)
{
return BinarySearch_R(key, array, low, mid - 1);
}
else {
return BinarySearch_R(key, array, mid + 1, high);
}
}
然后您所需要的只是复制/粘贴上述方法,将int key
替换为string key
,int[] array
替换为List<Demo> array
,array[mid]
替换为array[mid].Col
:
public static int BinarySearch_R(string key, List<Demo> array, int low, int high)
{
if (low > high) return -1;
int mid = (low + high) / 2;
int compare = key.CompareTo(array[mid].Col);
if (compare == 0)
{
return mid;
}
if (compare < 0)
{
return BinarySearch_R(key, array, low, mid - 1);
}
else {
return BinarySearch_R(key, array, mid + 1, high);
}
}
扩展答案:虽然您可以执行上述操作,但它需要对需要此类功能的任何其他属性/类执行相同的操作。
更好的方法是泛化代码。例如,int[]
和 List<Demo>
可以推广为 IReadOnlyList<T>
、 int/string key
TKey key
、 Demo.Col
Func<T, TKey>
、 CompareTo
IComparer<TKey>.Compare
,所以最终的泛型方法可以是这样的:
public static class MyAlgorithms
{
public static int BinarySearch<T, TKey>(this IReadOnlyList<T> source, Func<T, TKey> keySelector, TKey key, IComparer<TKey> keyComparer = null)
{
return source.BinarySearch(0, source.Count, keySelector, key, keyComparer);
}
public static int BinarySearch<T, TKey>(this IReadOnlyList<T> source, int start, int count, Func<T, TKey> keySelector, TKey key, IComparer<TKey> keyComparer = null)
{
// Argument validations skipped
if (keyComparer == null) keyComparer = Comparer<TKey>.Default;
int lo = start, hi = start + count - 1;
while (lo <= hi)
{
int mid = lo + (hi - lo) / 2;
int compare = keyComparer.Compare(key, keySelector(source[mid]));
if (compare < 0)
hi = mid - 1;
else if (compare > 0)
lo = mid + 1;
else
return mid;
}
return -1;
}
}
现在,您可以将该单一方法用于任何数据结构。例如,按Col
搜索您的List<Demo>
将是这样的:
int index = list.BinarySearch(e => e.Col, "Red");
我只用 C# 做了最基本的事情,所以这可能完全没用。我有一个CS 2类的作业,至少听起来有点类似于你想要的,但我们使用java。所以我假设您希望按某个关键字("蓝色","绿色"等(排序的项目列表。我使用了LinkedList,但这并不重要。
class Node {
String keyword;
LinkedList<String> records = new LinkedList<>();
Node left;
Node right;
public Node(String keyword, LinkedList<String> records) {
this.keyword = keyword;
this.records = records;
}
}
现在,至少我可以分辨出按字符串排序的BST和按数字排序的BST之间唯一真正的区别是,您需要某种类型的比较方法来查看一个单词在字母表中是>还是<。所以这是我如何执行插入功能:
/**
* insert node
* @param keyword compare it to other strings
*/
public void insert(String keyword, LinkedList<String> records) {
//create a new Node
Node n = new Node(keyword, records);
int result;
Node current = root;
Node parent = null;
//cont. until NULL
while (current != null) {
result = current.keyword.compareTo(n.keyword);
if (result == 0) return;
else if (result > 0) {
parent = current;
current = current.left;
}
else if (result < 0) {
parent = current;
current = current.right;
}
}
if (parent == null) root = n;
else {
result = parent.keyword.compareTo(n.keyword);
if (result > 0) parent.left = n;
else if (result < 0) parent.right = n;
}
}
因此,如果字符串在字母表中较高,则方法"compareTo(...("返回 1,如果相同,则返回 0,如果较低,则返回 -1。所以我会,如果我接近得到你的要求,获取此方法的 C# 版本并像往常一样实现 BST。
只需创建使类 IComparable 并创建自定义 CompareTo(( 方法。排序等标准方法将在类继承 IComparable 后自动工作。
public class Demo : IComparable
{
public string Color;
public int value;
public Boolean truth;
public int CompareTo(Demo other)
{
int results = 0;
if (this.Color == other.Color)
{
if (this.value == other.value)
{
results = this.truth.CompareTo(other.truth);
}
else
{
results = this.value.CompareTo(other.value);
}
}
else
{
results = this.Color.CompareTo(other.Color);
}
return results;
}