前言
在編程領(lǐng)域，數(shù)據(jù)結(jié)構(gòu)與算法是構(gòu)建高效、可靠和可擴(kuò)展軟件系統(tǒng)的基石。它們對(duì)于提升程序性能、優(yōu)化資源利用以及解決復(fù)雜問題具有至關(guān)重要的作用。今天大姚給大家分享四種C#中常見的經(jīng)典查找算法。
C#二分查找算法
簡(jiǎn)介
二分查找算法是一種在有序數(shù)組中查找特定元素的搜索算法。
代碼實(shí)現(xiàn)
public class 二分查找算法
{
/// <summary>
/// 二分查找算法
/// </summary>
/// <param name="arr">arr是已排序的數(shù)組</param>
/// <param name="target">target是要查找的目標(biāo)值</param>
/// <returns>目標(biāo)值在數(shù)組中的索引，如果未找到則返回-1</returns>
public static int BinarySearch(int[] arr, int target)
{
int left = 0; // 定義左指針
int right = arr.Length - 1; // 定義右指針
while (left <= right)
{
// 計(jì)算中間元素的索引
int mid = left + (right - left) / 2;
if (arr[mid] == target)
{
// 如果中間元素等于目標(biāo)值
return mid; // 查找成功，返回索引
}
else if (arr[mid] < target)
{
// 如果目標(biāo)值小于中間元素，則在左半部分查找
left = mid + 1;
}
else
{
// 如果目標(biāo)值大于中間元素，則在右半部分查找
right = mid - 1;
}
}
// 未找到 target，返回-1
return -1;
}
public static void BinarySearchRun()
{
int[] arr = { 1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 }; //注意：這里的數(shù)組是已排序的數(shù)組
int target = 31; //需要要查找的目標(biāo)值
int result = BinarySearch(arr, target); //調(diào)用二分查找方法
if (result == -1)
{
Console.WriteLine("元素未找到");
}
else
{
Console.WriteLine($"元素找到，索引為：{result}，值為：{arr[result]}");
}
}
}
C#線性查找算法
簡(jiǎn)介
線性查找算法是一種簡(jiǎn)單的查找算法，用于在一個(gè)數(shù)組或列表中查找一個(gè)特定的元素。它從數(shù)組的第一個(gè)元素開始，逐個(gè)檢查每個(gè)元素，直到找到所需的元素或搜索完整個(gè)數(shù)組。線性查找的時(shí)間復(fù)雜度為O(n)，其中n是數(shù)組中的元素?cái)?shù)量。
代碼實(shí)現(xiàn)
public static void LinearSearchRun()
{
int[] arr = { 2, 3, 4, 10, 40, 50, 100, 77, 88, 99 };
int target = 100;
int result = LinearSearch(arr, target);
// 輸出結(jié)果
if (result == -1)
{
Console.WriteLine("元素未找到");
}
else
{
Console.WriteLine($"元素在索引 {result} 處找到，index = {result}");
}
}
/// <summary>
/// 線性查找函數(shù)
/// </summary>
/// <param name="arr">arr</param>
/// <param name="target">target</param>
/// <returns></returns>
public static int LinearSearch(int[] arr, int target)
{
// 遍歷數(shù)組
for (int i = 0; i < arr.Length; i++)
{
// 如果找到目標(biāo)值，返回其索引
if (arr[i] == target)
{
return i;
}
}
// 如果沒有找到，則返回-1
return -1;
}
C#二叉搜索樹算法
簡(jiǎn)介
二叉搜索樹（Binary Search Tree，簡(jiǎn)稱BST）是一種節(jié)點(diǎn)有序排列的二叉樹數(shù)據(jù)結(jié)構(gòu)。
代碼實(shí)現(xiàn)
namespace HelloDotNetGuide.常見算法
{
public class 二叉搜索樹算法
{
public static void BinarySearchTreeRun()
{
var bst = new BinarySearchTree();
// 插入一些值到樹中
bst.Insert(50);
bst.Insert(30);
bst.Insert(20);
bst.Insert(40);
bst.Insert(70);
bst.Insert(60);
bst.Insert(80);
bst.Insert(750);
Console.WriteLine("中序遍歷（打印有序數(shù)組）：");
bst.InorderTraversal();
Console.WriteLine("\n");
// 查找某些值
Console.WriteLine("Search for 40: " + bst.Search(40)); // 輸出: True
Console.WriteLine("Search for 25: " + bst.Search(25)); // 輸出: False
Console.WriteLine("\n");
// 刪除某個(gè)值
bst.Delete(50);
Console.WriteLine("刪除50后：");
bst.InorderTraversal();
}
}
/// <summary>
/// 定義二叉搜索樹的節(jié)點(diǎn)結(jié)構(gòu)
/// </summary>
public class TreeNode
{
public int Value;
public TreeNode Left;
public TreeNode Right;
public TreeNode(int value)
{
Value = value;
Left = null;
Right = null;
}
}
/// <summary>
/// 定義二叉搜索樹類
/// </summary>
public class BinarySearchTree
{
private TreeNode root;
public BinarySearchTree()
{
root = null;
}
#region 插入節(jié)點(diǎn)
/// <summary>
/// 插入新值到二叉搜索樹中
/// </summary>
/// <param name="value">value</param>
public void Insert(int value)
{
if (root == null)
{
root = new TreeNode(value);
}
else
{
InsertRec(root, value);
}
}
private void InsertRec(TreeNode node, int value)
{
if (value < node.Value)
{
if (node.Left == null)
{
node.Left = new TreeNode(value);
}
else
{
InsertRec(node.Left, value);
}
}
else if (value > node.Value)
{
if (node.Right == null)
{
node.Right = new TreeNode(value);
}
else
{
InsertRec(node.Right, value);
}
}
else
{
//值已經(jīng)存在于樹中，不再插入
return;
}
}
#endregion
#region 查找節(jié)點(diǎn)
/// <summary>
/// 查找某個(gè)值是否存在于二叉搜索樹中
/// </summary>
/// <param name="value">value</param>
/// <returns></returns>
public bool Search(int value)
{
return SearchRec(root, value);
}
private bool SearchRec(TreeNode node, int value)
{
// 如果當(dāng)前節(jié)點(diǎn)為空，表示未找到目標(biāo)值
if (node == null)
{
return false;
}
// 如果找到目標(biāo)值，返回true
if (node.Value == value)
{
return true;
}
// 遞歸查找左子樹或右子樹
if (value < node.Value)
{
return SearchRec(node.Left, value);
}
else
{
return SearchRec(node.Right, value);
}
}
#endregion
#region 中序遍歷
/// <summary>
/// 中序遍歷（打印有序數(shù)組）
/// </summary>
public void InorderTraversal()
{
InorderTraversalRec(root);
}
private void InorderTraversalRec(TreeNode root)
{
if (root != null)
{
InorderTraversalRec(root.Left);
Console.WriteLine(root.Value);
InorderTraversalRec(root.Right);
}
}
#endregion
#region 刪除節(jié)點(diǎn)
/// <summary>
/// 刪除某個(gè)值
/// </summary>
/// <param name="val">val</param>
public void Delete(int val)
{
root = DeleteNode(root, val);
}
private TreeNode DeleteNode(TreeNode node, int val)
{
if (node == null)
{
return null;
}
if (val < node.Value)
{
node.Left = DeleteNode(node.Left, val);
}
else if (val > node.Value)
{
node.Right = DeleteNode(node.Right, val);
}
else
{
// 節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
if (node.Left != null && node.Right != null)
{
// 使用右子樹中的最小節(jié)點(diǎn)替換當(dāng)前節(jié)點(diǎn)
TreeNode minNode = FindMin(node.Right);
node.Value = minNode.Value;
node.Right = DeleteNode(node.Right, minNode.Value);
}
// 節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)或沒有子節(jié)點(diǎn)
else
{
TreeNode? temp = node.Left != null ? node.Left : node.Right;
node = temp;
}
}
return node;
}
/// <summary>
/// 找到樹中的最小節(jié)點(diǎn)
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
private TreeNode FindMin(TreeNode node)
{
while (node.Left != null)
{
node = node.Left;
}
return node;
}
#endregion
}
}
C#哈希查找算法
簡(jiǎn)介
哈希查找算法是一種高效的查找算法，通過將鍵值映射到哈希表中的位置來實(shí)現(xiàn)快速訪問。在C#中，哈希查找通常通過哈希表（Hashtable）或字典（Dictionary）來實(shí)現(xiàn)。
代碼實(shí)現(xiàn)
public class 哈希查找算法
{
/// <summary>
/// 哈希查找函數(shù)
/// </summary>
/// <param name="target">target</param>
public static void HashSearchFunctionRun(int target)
{
//創(chuàng)建一個(gè)字典來存儲(chǔ)鍵值對(duì)
var dic = new Dictionary<int, string>();
dic.Add(1, "one");
dic.Add(2, "two");
dic.Add(3, "three");
//查找目標(biāo)值是否在Dictionary中存在
//TryGetValue方法可以返回一個(gè)bool值和值，如果找到了目標(biāo)值，則返回true和對(duì)應(yīng)的值，否則返回false和默認(rèn)值
string value;
if (dic.TryGetValue(target, out value))
{
Console.WriteLine("Found Data: " + value);
}
else
{
Console.WriteLine("Not Found Data.");
}
}
}
該文章在 2024/10/24 9:20:58 編輯過
400 186 1886
