C#.Net-数据结构-学习笔记一、数据结构概述数据结构是底层数据的存储方式分四大类Set集合纯粹的容器无序存储元素唯一线性结构一对一存储如数组、链表、队列、栈树形结构一对多存储如二叉树、表达式目录树、菜单结构图状结构多对多存储如拓扑图、地图网络二、线性结构连续存储(数组类)Array内存连续分配元素类型相同长度固定。支持索引访问读取快增删需要移动元素慢。int[] intArray new int[3]; intArray[0] 123; string[] stringArray new string[] { 123, 234 };ArrayList长度可动态增加元素类型为object值类型存入时会装箱取出时需拆箱和强转。非泛型性能低现代项目基本不用。ArrayList arrayList new ArrayList(); arrayList.Add(Richard); arrayList.Add(32); // 值类型装箱 var value (int)arrayList[2]; // 拆箱 强转ListT底层也是数组但泛型、类型安全避免装箱拆箱性能高于 ArrayList。读取快增删慢。Listint intList new Listint() { 1, 2, 3, 4 }; intList.Add(123); int val intList[0]; // 直接访问无需转换性能排序Array ≈ ListT ArrayList非连续存储(链表类)LinkedListT双向链表每个节点记录前后节点地址内存非连续。不支持索引访问查找只能遍历(慢)增删只需修改指针(快)。LinkedListint linkedList new LinkedListint(); linkedList.AddFirst(123); linkedList.AddLast(456); LinkedListNodeint node linkedList.Find(123); linkedList.AddBefore(node, 9); linkedList.AddAfter(node, 9); linkedList.Remove(node);QueueT先进先出(FIFO)像没有瓶底的瓶子。Queuestring queue new Queuestring(); queue.Enqueue(one); // 入队 string item queue.Dequeue(); // 出队并移除 string peek queue.Peek(); // 查看队首不移除应用场景任务队列、消息队列、日志异步处理。StackT先进后出(LIFO)像有瓶底的瓶子。Stackstring stack new Stackstring(); stack.Push(one); // 入栈 string item stack.Pop(); // 出栈并移除 string peek stack.Peek(); // 查看栈顶不移除应用场景表达式求值、撤销操作、解析表达式目录树。三、Set 集合(去重容器)HashSetT基于哈希分布自动去重无序存储。对于引用类型默认按引用判断是否重复若要按值去重需重写Equals和GetHashCode。HashSetstring hashSet new HashSetstring(); hashSet.Add(123); hashSet.Add(123); // 重复不会添加 Console.WriteLine(hashSet.Count); // 1 // 集合运算 HashSetstring set1 new HashSetstring() { A, B, C }; HashSetstring set2 new HashSetstring() { B, C, D }; set1.UnionWith(set2); // 并集 set1.IntersectWith(set2); // 交集 set1.ExceptWith(set2); // 差集 set1.SymmetricExceptWith(set2); // 对称差(补集)应用场景点赞去重、IP统计、好友推荐(求差集找出对方认识但我不认识的人)。SortedSetT自动去重 自动排序。可通过IComparerT自定义排序规则。SortedSetstring sortedSet new SortedSetstring(); sortedSet.Add(689); sortedSet.Add(123); sortedSet.Add(456); // 遍历输出123, 456, 689应用场景实时排行榜。四、键值对结构(Key-Value)哈希散列的核心思想用 key 计算哈希值映射到数组索引实现 O(1) 的增删查改。代价是用空间换性能数据量过大时散列冲突增多性能下降。Hashtable非泛型key 和 value 均为object有装箱拆箱开销。支持线程安全包装。Hashtable table new Hashtable(); table.Add(key1, value1); table[key2] value2; // 直接赋值key不存在则新增存在则覆盖 Hashtable.Synchronized(table); // 线程安全版本(单写多读)DictionaryTKey, TValue泛型版哈希表类型安全性能高。按插入顺序遍历(但官方不保证顺序不应依赖此特性)。非线程安全多线程场景用ConcurrentDictionaryTKey, TValue。Dictionaryint, string dic new Dictionaryint, string(); dic.Add(1, HaHa); dic[4] HuHu; // 不存在则新增存在则覆盖 // dic.Add(4, HuHu); // key已存在会抛异常 foreach (var item in dic) { Console.WriteLine($Key:{item.Key}, Value:{item.Value}); }SortedDictionaryTKey, TValue自动按 Key 排序性能略低于 Dictionary。SortedDictionaryint, string dic new SortedDictionaryint, string(); dic.Add(5, HoHo); dic.Add(1, HaHa); dic.Add(3, HeHe); // 遍历输出顺序1, 3, 5SortedList非泛型按 Key 排序支持索引访问内存占用比 SortedDictionary 小。TrimToSize()可最小化内存开销。SortedList sortedList new SortedList(); sortedList.Add(First, Hello); sortedList[Third] ~~; sortedList.TrimToSize(); // 释放多余内存五、接口体系IEnumerable所有集合都实现了此接口提供统一的遍历方式(foreach)核心方法是GetEnumerator()返回迭代器ICollectionT继承自 IEnumerableT增加了 Count、CopyTo、Contains 等方法以及 Add、Remove(泛型版本才有增删)IListT继承自 ICollectionT增加了索引访问(this[int index])和 Insert、RemoveAtIQueryable用于延迟查询(LINQ、EF)基于表达式目录树遍历时才真正执行查询六、迭代器模式结论迭代器模式为不同数据结构提供统一的访问接口客户端无需关心底层是数组还是链表。C# 中所有集合都实现了IEnumerableforeach 本质上就是调用GetEnumerator()获取迭代器再反复调用MoveNext()和Current。自定义迭代器有两种方式实现自定义迭代器方式一用 yield(推荐简洁)public class EnumeratorIteratorTSource : IEnumerableTSource { private readonly IEnumerableTSource source; private readonly FuncTSource, bool predicate; public EnumeratorIterator(IEnumerableTSource source, FuncTSource, bool predicate) { this.source source; this.predicate predicate; } public IEnumeratorTSource GetEnumerator() { foreach (var item in source) { if (predicate(item)) yield return item; // 编译器生成状态机 } } IEnumerator IEnumerable.GetEnumerator() GetEnumerator(); }方式二手动实现 IEnumerator(理解底层用)public class ManualIteratorT : IEnumeratorT { private readonly T[] _data; private int _index -1; public ManualIterator(T[] data) { _data data; } public T Current _data[_index]; object IEnumerator.Current Current; public bool MoveNext() { _index; return _index _data.Length; } public void Reset() { _index -1; } public void Dispose() { } }方式二展示了 yield 背后编译器实际生成的逻辑维护一个_index状态每次MoveNext()推进一步Current返回当前值。迭代器模式实战统一访问不同菜单KFC 菜单用数组存储麦当劳菜单用 List 存储通过统一的IIteratorFood接口访问IIteratorFood iterator kfcMenu.GetEnumerator(); while (iterator.MoveNext()) { Food food iterator.Current; Console.WriteLine(food.Name); } // 换成麦当劳菜单调用方式完全一样 IIteratorFood iterator1 macDonaldMenu.GetEnumerator(); while (iterator1.MoveNext()) { ... }七、yield 关键字结论yield 是语法糖编译器自动生成状态机(迭代器)实现MoveNext、Current、Reset让按需返回数据变得极其简洁。yield return按需返回public IEnumerableint Power() { for (int i 0; i 10; i) { yield return Get(i); // 每次调用 MoveNext 才执行到这里 Console.WriteLine(yield 之后继续执行); } }调用Power()时不会立即执行任何代码只有 foreach 遍历时每次MoveNext()才推进一步。yield break提前终止public IEnumerableint CreateEnumerable() { for (int i 0; i 5; i) { yield return i; if (i 4) yield break; // 终止迭代后续代码不再执行 } yield return -1; // 不会执行到 }yield 与 finally含有 yield 的方法中finally块会在迭代器被释放(Dispose)时执行即使中途 break 也会触发public IEnumerableint CreateEnumerable() { try { for (int i 0; i 5; i) { yield return i; } } finally { Console.WriteLine(停止迭代); // foreach break 后也会执行 } }yield vs 普通方法// yield按需获取延迟执行节省内存 public IEnumerableint Power() { for (int i 0; i 10; i) yield return Get(i); // 要一个拿一个 } // 普通方法一次性全部计算全部放入内存 public IEnumerableint Common() { Listint list new Listint(); for (int i 0; i 10; i) list.Add(Get(i)); // 先全部算完 return list; }自定义 LINQ 扩展方法public static IEnumerableT ElevenWhereT( this IEnumerableT source, FuncT, bool func) { foreach (var item in source) { if (func.Invoke(item)) yield return item; // 延迟执行遍历时才过滤 } } // 使用 var result studentList.ElevenWhere(s s.Age 30); foreach (var item in result) // 遍历时才真正执行过滤逻辑 { Console.WriteLine(item.Name); }yield 的应用场景大数据集分页加载、无限序列生成、LINQ 的 Where/Select 等延迟查询。八、dynamic 关键字结论dynamic 是 C# 4.0 引入的动态类型让 C# 具备弱类型特点类型检查推迟到运行时。// 强类型编译时检查 string s abcd; // int i (int)s; // 编译错误 // dynamic运行时检查 dynamic d abcd; int i (int)d; // 编译通过运行时报错 d.Hello(); // 编译通过运行时报错任何与 dynamic 交互的表达式结果也是 dynamicdynamic str abcd; Console.WriteLine(str.Length); // dynamic Console.WriteLine(str.Substring(1)); // dynamicdynamic 的三个主要用途代替反射性能比反射高object obj new YieldDemo(); // 反射方式 Type type obj.GetType(); type.GetMethod(Power).Invoke(obj, null); // dynamic 方式(更简洁性能更好) dynamic dObj obj; dObj.Power();简化数据绑定无需强转与 COM/C 互操作更方便注意dynamic 失去了编译时类型检查错误只在运行时暴露使用时需谨慎。九、线程安全集合System.Collections.Concurrent命名空间提供线程安全版本ConcurrentQueueT线程安全的队列(FIFO)ConcurrentStackT线程安全的栈(LIFO)ConcurrentBagT线程安全的无序集合ConcurrentDictionaryTKey, TValue线程安全的字典BlockingCollectionT支持阻塞和限界的集合十、性能对比与选型数据结构查询增加删除特点ArrayO(1)O(n)O(n)固定长度内存连续ListTO(1)O(1)/O(n)*O(n)动态长度内存连续LinkedListTO(n)O(1)O(1)链表非连续HashSetTO(1)O(1)O(1)去重无序DictionaryK,VO(1)O(1)O(1)键值对哈希散列*List 尾部追加不需扩容时 O(1)触发扩容或中间插入时 O(n)选型建议频繁随机访问、少量增删 → Array 或 ListT频繁头部/中间增删 → LinkedListT需要去重 → HashSetT需要键值映射增删查改都快 → DictionaryTKey, TValue需要自动排序 → SortedSetT 或 SortedDictionaryTKey, TValue多线程场景 → Concurrent 系列