资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

C#数据结构与算法：从基础到高阶

创作时间:

作者:

@小白创作中心

C#数据结构与算法：从基础到高阶

引用

CSDN

https://blog.csdn.net/m0_38141444/article/details/143798234

数据结构和算法是计算机科学的核心，掌握它们不仅能提高代码的性能和效率，还能帮助你在面试中脱颖而出。对于 C# 开发者而言，了解常见的数据结构和算法，能帮助你在处理复杂问题时做出最优的选择。
本文将详细介绍 C# 中常用的数据结构和算法，涵盖基础到高阶内容，帮助你从零开始逐步深入。

1.数据结构概述

数据结构是计算机中存储和组织数据的方式。不同的数据结构适用于不同类型的问题，选择合适的数据结构可以提高程序的运行效率。

1.1 常见数据结构

数组（Array）：线性数据结构，具有固定大小的元素集合。
链表（Linked List）：由一系列节点组成的线性数据结构，节点之间通过指针连接。
栈（Stack）：后进先出（LIFO）结构，适用于处理递归、撤销操作等问题。
队列（Queue）：先进先出（FIFO）结构，常用于任务调度、消息传递等场景。
哈希表（Hash Table）：基于哈希算法实现的映射结构，支持快速查找。
树（Tree）：层级数据结构，用于组织具有层次关系的数据。
图（Graph）：由节点和边组成的结构，适合表示网络关系。

1.2 C# 中的数据结构

C# 提供了许多内置的集合类型，如：

Array
：内置数组类型，支持快速随机访问。

List
：动态数组，支持扩展。

LinkedList
：双向链表。

Stack
：栈实现。

Queue
：队列实现。

Dictionary<TKey, TValue>
：哈希表（键值对映射）。

2.算法基础

算法是解决问题的一组步骤或规则。在解决问题时，算法的效率往往比代码的实现方式更为重要。常见的算法类型包括：

排序算法：如快速排序、归并排序、冒泡排序。
查找算法：如线性查找、二分查找。
递归与迭代：许多问题可以通过递归或迭代的方式解决。
动态规划：通过将问题分解为子问题来优化计算过程，常用于解决最优化问题。
图算法：如广度优先搜索（BFS）、深度优先搜索（DFS）、Dijkstra 算法等。

3.C# 实现基本数据结构

3.1 数组（Array）

数组是最简单的数据结构，它在 C# 中通过
Array
类型或
List
类型实现。数组的大小固定，访问元素的时间复杂度为 O(1)。

  
int[] arr = { 1, 2, 3, 4, 5 };
Console.WriteLine(arr[2]);  // 访问数组元素，输出 3

3.2 链表（Linked List）

链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。C# 提供了
LinkedList
类型来实现双向链表。

  
var linkedList = new LinkedList<int>();
linkedList.AddLast(1);
linkedList.AddLast(2);
linkedList.AddLast(3);
foreach (var item in linkedList)
{
    Console.WriteLine(item);  // 输出 1 2 3
}

3.3 栈（Stack）

栈遵循后进先出（LIFO）原则，C# 提供了
Stack
类。

  
Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);
Console.WriteLine(stack.Pop());  // 输出 3
Console.WriteLine(stack.Peek()); // 输出 2（但不删除）

3.4 队列（Queue）

队列遵循先进先出（FIFO）原则，C# 提供了
Queue
类。

  
Queue<int> queue = new Queue<int>();
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
Console.WriteLine(queue.Dequeue());  // 输出 1
Console.WriteLine(queue.Peek());     // 输出 2（但不删除）

3.5 哈希表（Dictionary）

哈希表通过键值对存储数据，C# 提供了
Dictionary<TKey, TValue>
类。

  
Dictionary<string, int> dictionary = new Dictionary<string, int>();
dictionary["apple"] = 5;
dictionary["banana"] = 10;
Console.WriteLine(dictionary["apple"]);  // 输出 5

4.常见算法实现

4.1 排序算法

4.1.1 冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法，通过重复交换相邻元素，直到整个序列有序。

  
void BubbleSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                // 交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

4.1.2 快速排序（Quick Sort）
快速排序是一种分治法排序算法，它选择一个“基准”元素，将数组分为两部分，一部分元素小于基准，另一部分元素大于基准，然后递归地对每部分进行排序。

  
void QuickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        int pivot = Partition(arr, low, high);
        QuickSort(arr, low, pivot - 1);
        QuickSort(arr, pivot + 1, high);
    }
}
int Partition(int[] arr, int low, int high)
{
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp2 = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp2;
    return i + 1;
}

4.2 查找算法

4.2.1 线性查找
线性查找从数组的第一个元素开始，逐个检查每个元素，直到找到目标元素或遍历完所有元素。

  
int LinearSearch(int[] arr, int target)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == target)
            return i;  // 返回元素的索引
    }
    return -1;  // 如果没有找到元素
}

4.2.2 二分查找
二分查找是一种高效的查找算法，要求数据已经排序。每次将查找范围减半，直到找到目标元素或范围为空。

  
int BinarySearch(int[] arr, int target)
{
    int left = 0, right = arr.Length - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return mid;  // 找到目标元素
        if (arr[mid] < target)
            left = mid + 1;  // 在右半部分继续查找
        else
            right = mid - 1;  // 在左半部分继续查找
    }
    return -1;  // 没有找到目标元素
}

5.递归与动态规划

5.1 递归（Recursion）

递归是函数调用自身的过程。许多问题可以通过递归来简化，常见的递归问题如斐波那契数列、阶乘计算等。
5.1.1 斐波那契数列

  
int Fibonacci(int n)
{
    if (n <= 1) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

5.2 动态规划（Dynamic Programming）

动态规划通过分解子问题并缓存结果来避免重复计算，常用于优化递归算法，如背包问题、最短路径问题等。
5.2.1 斐波那契数列的动态规划解法

  
int FibonacciDP(int n)
{
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

6.高级算法：图算法

图算法广泛应用于计算机网络、社交网络等领域。常见的图算法有广度优先搜索（BFS）、深度优先搜索（DFS）、Dijkstra 算法等。

6.1 广度优先搜索（BFS）

广度优先搜索是一种逐层遍历图的算法，通常用于寻找最短路径。

  
void BFS(Dictionary<int, List<int>> graph, int start)
{
    var visited = new HashSet<int>();
    var queue = new Queue<int>();
    queue.Enqueue(start);
    visited.Add(start);
    while (queue.Count > 0)
    {
        int node = queue.Dequeue();
        Console.WriteLine(node);
        foreach (var neighbor in graph[node])
        {
            if (!visited.Contains(neighbor))
            {
                visited.Add(neighbor);
                queue.Enqueue(neighbor);
            }
        }
    }
}

6.2 深度优先搜索（DFS）

深度优先搜索是通过递归或栈的方式逐层深入图中的每一个节点。

  
void DFS(Dictionary<int, List<int>> graph, int node, HashSet<int> visited)
{
    visited.Add(node);
    Console.WriteLine(node);
    foreach (var neighbor in graph[node])
    {
        if (!visited.Contains(neighbor))
        {
            DFS(graph, neighbor, visited);
        }
    }
}