网站导航
> 技术文档 > C#数据结构详解

C#数据结构详解

网友: 技术文档 2025-07-30 11:26:51

C# 提供了丰富的数据结构集合，主要包含在 System.Collections 和 System.Collections.Generic 命名空间中。这些数据结构可以分为线性结构、非线性结构和特殊用途结构三大类。下面我将详细介绍 C# 中的主要数据结构及其使用场景。

一、线性数据结构

1. 数组 (Array)

​​特点​​：

  • 固定大小
  • 连续内存分配
  • 支持随机访问

​​示例​​：

// 一维数组int[] numbers = new int[5] {1, 2, 3, 4, 5};// 多维数组int[,] matrix = new int[3, 3] {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};// 数组操作Console.WriteLine(numbers[0]); // 访问元素Array.Sort(numbers); // 排序Array.Reverse(numbers); // 反转

适用场景​​：

  • 数据量已知且固定
  • 需要频繁随机访问元素
  • 内存效率要求高

2. ArrayList (非泛型)

​​特点​​：

  • 动态大小
  • 可以存储不同类型元素
  • 基于数组实现

​​示例​​：

ArrayList list = new ArrayList();list.Add(1);list.Add(\"string\");list.Add(3.14);// 需要类型转换int first = (int)list[0];

注意​​：

  • 由于是非泛型集合，存在装箱/拆箱操作，性能较低
  • 现代C#开发中推荐使用泛型集合替代

3. List (泛型)

​​特点​​：

  • 动态大小
  • 类型安全
  • 基于数组实现

​​示例​​：

List numbers = new List();numbers.Add(1);numbers.Add(2);numbers.Add(3);// 高效访问int first = numbers[0];// 其他操作numbers.Remove(2);numbers.Insert(1, 5);

适用场景​​：

  • 需要动态大小的集合
  • 需要类型安全
  • 需要频繁随机访问

4. LinkedList

​​特点​​：

  • 双向链表实现
  • 插入/删除操作高效(O(1))
  • 随机访问效率低(O(n))

​​示例​​：

LinkedList list = new LinkedList();list.AddLast(1);list.AddLast(2);list.AddLast(3);// 插入操作list.AddAfter(list.Find(2), 5);// 遍历foreach (var item in list){ Console.WriteLine(item);}

适用场景​​：

  • 需要频繁插入/删除操作
  • 不需要频繁随机访问
  • 实现队列或栈等数据结构

5. Queue (队列)

​​特点​​：

  • 先进先出(FIFO)结构
  • 基于链表实现

​​示例​​：

Queue queue = new Queue();queue.Enqueue(\"first\");queue.Enqueue(\"second\");queue.Enqueue(\"third\");// 出队string first = queue.Dequeue();string peek = queue.Peek(); // 查看但不移除

适用场景​​：

  • 任务调度
  • 消息队列
  • 需要按顺序处理的场景

6. Stack (栈)

​​特点​​：

  • 后进先出(LIFO)结构
  • 基于数组实现

​​示例​​：

Stack stack = new Stack();stack.Push(1);stack.Push(2);stack.Push(3);// 出栈int top = stack.Pop();int peek = stack.Peek(); // 查看但不移除

适用场景​​：

  • 函数调用栈
  • 表达式求值
  • 撤销操作实现

二、非线性数据结构

1. HashSet

​​特点​​：

  • 不允许重复元素
  • 无序集合
  • 基于哈希表实现

​​示例​​：

HashSet names = new HashSet();names.Add(\"Alice\");names.Add(\"Bob\");names.Add(\"Alice\"); // 不会添加重复项// 快速查找bool contains = names.Contains(\"Bob\");

适用场景​​：

  • 需要快速查找元素是否存在
  • 需要去重
  • 不关心元素顺序

2. SortedSet

​​特点​​：

  • 不允许重复元素
  • 自动排序
  • 基于平衡二叉搜索树实现

​​示例​​：

SortedSet numbers = new SortedSet();numbers.Add(3);numbers.Add(1);numbers.Add(2);// 自动排序foreach (var num in numbers){ Console.WriteLine(num); // 输出1,2,3}

适用场景​​：

  • 需要有序且不重复的集合
  • 需要范围查询

3. Dictionary

​​特点​​：

  • 键值对集合
  • 键唯一
  • 基于哈希表实现

​​示例​​：

Dictionary ages = new Dictionary();ages.Add(\"Alice\", 25);ages.Add(\"Bob\", 30);// 访问值int aliceAge = ages[\"Alice\"];// 检查键是否存在if (ages.ContainsKey(\"Charlie\")){ // ...}

适用场景​​：

  • 需要快速键值查找
  • 实现映射关系
  • 缓存实现

4. SortedDictionary

​​特点​​：

  • 键值对集合
  • 键唯一且有序
  • 基于平衡二叉搜索树实现

​​示例​​：

SortedDictionary sortedAges = new SortedDictionary();sortedAges.Add(\"Bob\", 30);sortedAges.Add(\"Alice\", 25);sortedAges.Add(\"Charlie\", 35);// 按键排序输出foreach (var pair in sortedAges){ Console.WriteLine($\"{pair.Key}: {pair.Value}\");}

适用场景​​：

  • 需要有序的键值对集合
  • 需要范围查询键

5. Hashtable (非泛型)

​​特点​​：

  • 键值对集合
  • 键唯一
  • 基于哈希表实现
  • 非泛型，存在装箱/拆箱

​​示例​​：

Hashtable table = new Hashtable();table.Add(\"Alice\", 25);table.Add(\"Bob\", 30);// 需要类型转换int aliceAge = (int)table[\"Alice\"];

注意​​：

  • 现代C#开发中推荐使用泛型Dictionary替代

三、特殊用途数据结构

1. BitArray

​​特点​​：

  • 位集合
  • 节省内存
  • 支持位运算

​​示例​​：

BitArray bits = new BitArray(8); // 8位bits[0] = true;bits[1] = false;bits[2] = true;// 位运算BitArray result = bits.And(new BitArray(8) { [0] = true, [1] = true, [2] = false });

适用场景​​：

  • 标志位集合
  • 节省内存的场景
  • 位运算操作

2. SortedList

​​特点​​：

  • 键值对集合
  • 键唯一且有序
  • 基于数组实现

​​示例​​：

SortedList sortedList = new SortedList();sortedList.Add(\"Bob\", 30);sortedList.Add(\"Alice\", 25);sortedList.Add(\"Charlie\", 35);// 按键排序输出foreach (var pair in sortedList){ Console.WriteLine($\"{pair.Key}: {pair.Value}\");}

适用场景​​：

  • 需要有序键值对
  • 内存比SortedDictionary更高效
  • 插入/删除操作不频繁

四、性能比较与选择指南

数据结构 插入/删除 查找 内存使用 顺序性 适用场景 Array O(n) O(1) 低 有序 固定大小集合 List O(1)追加/O(n)插入 O(1)索引/O(n)查找 中 有序 动态大小集合 LinkedList O(1) O(n) 中 有序 频繁插入/删除 Queue O(1) O(n) 中 FIFO 任务调度 Stack O(1) O(n) 中 LIFO 撤销操作 HashSet O(1) O(1) 中 无序 去重集合 SortedSet O(log n) O(log n) 中 有序 有序去重集合 Dictionary O(1) O(1) 中 无序 键值映射 SortedDictionary O(log n) O(log n) 中 有序 有序键值映射 BitArray O(1) O(1) 极低 有序 位标志集合

五、实际应用示例

1. 使用Dictionary实现缓存

public class SimpleCache{ private readonly Dictionary _cache = new Dictionary(); public bool TryGetValue(TKey key, out TValue value) { return _cache.TryGetValue(key, out value); } public void Add(TKey key, TValue value) { _cache[key] = value; } public void Remove(TKey key) { _cache.Remove(key); }}

2. 使用HashSet检测重复项

public bool HasDuplicates(IEnumerable items){ var set = new HashSet(); foreach (var item in items) { if (!set.Add(item)) { return true; } } return false;}

3. 使用Queue实现广度优先搜索

public void BFS(Node startNode){ var queue = new Queue(); var visited = new HashSet(); queue.Enqueue(startNode); visited.Add(startNode); while (queue.Count > 0) { var current = queue.Dequeue(); ProcessNode(current); foreach (var neighbor in current.Neighbors) { if (!visited.Contains(neighbor)) { visited.Add(neighbor); queue.Enqueue(neighbor); } } }}

C# 提供了丰富的数据结构集合，每种数据结构都有其特定的优势和适用场景。选择合适的数据结构可以显著提高程序的性能和可维护性。在实际开发中：

  1. 优先考虑泛型集合(List, Dictionary等)，它们提供类型安全且性能更好
  2. 根据操作特点选择数据结构：
    • 需要快速查找：HashSet/Dictionary
    • 需要有序集合：SortedSet/SortedDictionary
    • 频繁插入/删除：LinkedList/Queue/Stack
  3. 注意内存使用情况，特别是处理大数据量时
  4. 考虑线程安全需求，必要时使用并发集合(ConcurrentQueue, ConcurrentDictionary等)
网络标签：

相关问题