c#常用的数据结构

Array数组

内存上连续存储，

数组是引用类型而不是值类型。

优点：

按照索引查询元素速度很快。

按照索引遍历数组很方便。

缺点：

声明数组时大小必须确定，且大小不能改变。

添加和删除元素的速度很慢，因为需要移动其它元素。

数组只能存储一种数据类型。

一维数组的声明和创建形式:

数组类型 [ ] 数组名 = new 数组类型 [数组长度]

如 int [ ] one = new int [5] { 1, 2, 3, 4, 5 }; 

相当于MFC 的CArray

二维数组

int [,] one = new int [2,3];

位数组 BitArray

ArrayList 

ArrayList类相当于一种高级的动态数组，它是Array类的升级版本.本质是一个object类型的数组.ArrayList类是引用类型。连续的内存。在存和使用值类型的对象时或发生装箱/拆箱的操作。

using System.Collections;

ArrayList List=new ArrayList();

ArrayList 转Array的函数

Array ToArray(Type type);

 ArrayList List = new ArrayList();

 for (int i = 0; i < 10; i++)

       List.Add(i);

int[] values = (int[])List.ToArray(typeof(int)); //正确

List

List 等效于ArrayList,性能比Arraylist高。 List的内部是用数组实现的，而不是链表,所以也是连续内存。当元素被添加到List中时，List的容量会根据需要自动增加，通过重新分配内部数组。

    public class person

    {

        public int age { set; get; }

        public string name { set; get; }

    }

            List personlist = new List ();

            person pspn1 = new person();

            pspn1.age = 1;

            pspn1.name = "qw";

            personlist.Add(pspn1);

            person pspn2 = new person();

            pspn2.age = 2;

            pspn2.name = "re";

            personlist.Add(pspn2);

            foreach (var val in personlist)

            {

                Console.WriteLine("age{0},name{1}",val.age,val.name);

            }

            int index = personlist.IndexOf(pspn2);

            index = personlist.FindIndex( r=> r.age == 1);

Find、FindIndex、Exists、RemoveAll支持Predicate match（即委托，该委托返回一个bool值）

public delegate bool Predicate<in T>(T obj);

index = personlist.FindIndex( r=> r.age == 1);

排序：

public void Sort(Comparison comparison);

public delegate int Comparison<in T>(T x, T y);

 personlist.Sort((x,y) => x.age.CompareTo(y.age)); //升序

personlist.Sort((x, y) => y.age.CompareTo(x.age));//降序

只有集合的元素实现了ICompareble接口，才能使用不带参数的sort方法。如常见数据类型：int

public void Sort();  

List<int> numbers = new List<int> { 5, 2, 9, 1, 6 };

 numbers.Sort();

List转Array的函数

 List<int> primeNumbers = new List<int>();

 for (int i = 0; i < 10; i++)

       primeNumbers.Add(i);

  int[] Numbers = primeNumbers.ToArray();

Array转List的函数

 int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ,10};

  List<int> list = new List<int>(array);

相当于 c++ 的vector

LinkedList（双向链表）

内存非连续的、非顺序的存储结构，无法通过下标查找元素，在查找链表元素时，总是从头结点开始查找；动态调整容量。

查询复杂度为 O(n)，操作复杂度为 O(1)。

遍历：

LinkedListNode nowNode=linkedList.First;

while(nowNode!=null)

{

  nowNode=nowNode.Next;

}

或者

foreach(int item in linkedList)

{

  Console.WriteLine(item);

}

Array转LinkedList的函数

int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ,10};

LinkedList<int> linkedList = new LinkedList<int>(array);

相当于c++的 list

Stack(栈)

  栈是有顺序的，保持着先进后出的原则。

  Stack<string> numbers = new Stack<string>();

  numbers.Push("one");

  string str = numbers.Peek(); //获取不出栈

  str = numbers.Pop();//获取并出栈

Queue(队列)

先进先出，存在装箱拆箱，存储任意类型，无法获取指定位置元素，只能取出最先存储的元素。

Queue<string> queue = new Queue<string>();

//向队列中添加元素

ueue.Enqueue("老一");

queue.Enqueue("老二");

queue.Dequeue();获取并移除队列中队首的元素

queue.Peek();返回顶部的对象而不将其从队列中移除

HashSet

是基于哈希表的原理实现的，根据key直接访问存储位置的数据结构

无序、不重复；

插入、查找时间复杂度为O(1)；

不使用索引；

容量不足时自动扩容，但扩容成本高；

HashSet<string> hashSet = new HashSet<string>();

hashSet.Add("123");

 hashSet.Add("456");

//转换成List集合

 hashSet.ToList();

相当于STL 的hash_set或者说unordered_set

SortedSet

基于红黑树实现，有序、不重复的集合

 SortedSet<string> SortSet = new SortedSet<string>();

 SortSet.Add("123");

 hashSet.Add("456");

 foreach (var index in SortSet)

 {   

  }

//转换成List集合

SortSet.ToList();

相当于STL的set

Hashtable

基于哈希表实现，一系列基于键的哈希代码组织起来的 键/值对 。它使用键来访问集合中的元素。

特点：

key(键) 是唯一的，不可重复，

只能通过 key 查询对应 的value

Hashtable hashtable = new Hashtable();

hashtable.Add(0, 1);

hashtable.Add(1, 'a');

foreach (var key in hashtable.Keys)

{

   var tablekey = key;

   var value = hashtable[key];

}

相当于STL 的unordered_map （hash_map）

Dictionary（字典）

基于哈希表实现，字典中的key值是唯一的。

字典底层将数据储存在数组里面，通过哈希函数建立Key——Value的对应关系，利用拉链法处理哈希冲突。另外，字典是线程不安全的，如果需要线程安全，需要自己加锁

Dictionary<int, string> _testDic = new Dictionary<int, string>();

     _testDic.Add(24, "Canon");

     // 注意相同相同Key值只能Add一次

     _testDic.Add(34, "Jason");                                      // foreach遍历

     foreach (var kvp in _testDic)

    {

          Console.WriteLine("Key = {0}, Value = {1}", kvp.Key, kvp.Value);

      }

相当于STL 的unordered_map （hash_map）

延伸到：Lookup类

Lookup 把键映射到一个值集合上，相当与STL的unordered_map<TKey,Vector<TElement>>

    class Person

    {

        public int age { set; get; }

        public string name { set; get; }

    }

            Person p1 = new Person();

            Person p2 = new Person();

            List personlist = new List();

            personlist.Add(p1);

            personlist.Add(p2);

            var look = personlist.ToLookup( r=>r.age);

            foreach (var item in look[1])

            {

                string name = item.name;

            }

Dictionary和Hashtable对比

Dictionary是泛型的，当K或V是值类型时，其速度远远超过Hashtable。

由于 Hashtable 和 Dictionary 同时存在, 在使用场景上必然存在选择性, 并不任何时刻都能相互替代.
[1] 单线程程序中推荐使用 Dictionary, 有泛型优势, 且读取速度较快, 容量利用更充分.
[2] 多线程程序中推荐使用 Hashtable, 默认的 Hashtable 允许单线程写入, 多线程读取, 对 Hashtable 进一步调用 Synchronized() 方法可以获得完全线程安全的类型. 而 Dictionary 非线程安全, 必须人为使用 lock 语句进行保护, 效率大减.
[3] Dictionary 有按插入顺序排列数据的特性 (注: 但当调用 Remove() 删除过节点后顺序被打乱), 因此在需要体现顺序的情境中使用 Dictionary 能获得一定方便.

SortedDictionary

基于使用红黑树实现的键值对集合。

时间复杂度：O(logN)

特点：

有序，键唯一

只能通过 key(键) 查询对应 的 value(值) 

SortedDictionary 可对未排序的数据执行更快的插入和移除操作：它的时间复杂度为 O(log n)

 SortedDictionary<int, string> My_sdict = new SortedDictionary<int, string>();

 My_sdict.Add(004, "Ask.com");

 My_sdict.Add(003, "Yahoo");

foreach (var kvp in My_sdict)

{     

     Console.WriteLine("Key = {0}, Value = {1}", kvp.Key, kvp.Value);

  }

相当于STL的map

SortedList

SortedList对象在内部维护两个用于存储列表元素的数组; 即，一个数组用于存储键，另一个数组用于关联值。

排序列表是数组和哈希表的组合，使用索引访问各项，则它是一个动态数组，如果您使用键访问各项，则它是一个哈希表。整个集合是按键值排序。

var books = new SortedList();

books.Add("Professional WPF Programming", "978–0–470–04180–2");

books.Add("Professional ASP.NET MVC 3", "978–1–1180–7658–3");

　还可以使用索引器将元素添加到列表中

books["Beginning Visual C# 2010"] = "978–0–470-50226-6";

可以使用foreach语句遍历列表，枚举器返回的元素是KeyValuePair类型，其中包含了键和值：

foreach (KeyValuePair book in books)

{

Console.WriteLine("{0}, {1}", book.Key, book.Value);

}

也可以使用Values和Keys属性访问值和键：

foreach (string isbn in books.Values)

{

Console.WriteLine(isbn);

}

各数据结构对比

数据结构 类型及备注 插入和删除 查找
Array 顺序存储的线性表、定长 不支持（这里的插入与删除指会更改表长的行为） O(N)
LinkedList 链式存储的线性表、不定长 O(1) O(N)
List 顺序存储的线性表、不定长、动态扩容 O(N)，结尾则是O(1) O(N)
Stack 栈、不定长、动态扩容 O(1) 只能访问栈顶
Queue 队列、不定长、动态扩容 O(1) 只能访问队列头部
Dictionary 保存键值对、使用开散列法、不定长、动态扩容、长度总为质数 O(1) O(1)
SortedList 保存键值对、内部使用数组实现、保持有序、不定长 O(logN) O(logN)
SortedDictionary 保存键值对、内部使用红黑树实现、保持有序、不定长 O(logN) O(logN)
HashSet 使用开散列法、不定长、动态扩容、长度总为质数、是不含值的字典，故复杂度和它完全相同 O(1) O(1)
SortedSet 内部使用红黑树实现、保持有序、不定长、是不含值的SortedDictionary，故复杂度和它完全相同 O(logN) O(logN)

LINQ:

LINQ代表语言集成查询，是.net框架的扩展，它允许我们用SQL查询数据库的方式来查询数据的集合.

LINQ延迟查询的特性:

延迟查询是指查询操作并不是在定义的时候执行，而是在遍历集合中的数据时才执行

因为作为yield迭代器的主体，只有使用foreach遍历执行到MoveNext时才会真正执行方法.

延伸：yield关键字

yield主要用于在迭代器块中定义返回集合的迭代器函数。当使用yield return语句时，会将当前元素作为yield return表达式的值返回，并暂停迭代器函数的执行，直到再次调用该迭代器函数。

using System.Collections;

var numbers = GetNumbers(5);

foreach (var number in numbers)

{

    Console.WriteLine("当前时间：{0}，返回值：{1}", DateTime.Now.ToString("yyyy-MM-dd HH:mm:ss"), number);

}

IEnumerable GetNumbers(int count)

{

    for (int i = 1; i <= count; i++)

    {

        yield return i;

        //休眠5秒        

        Thread.Sleep(5000);    

    }

}

耗时方法无需等待，直接返回。

yield优点：

内存优化：yield可以预先返回值，而不是一次性将所有数据加载到内存中。这对于处理大量数据的情况非常有用，因为它可以显著降低内存占用。

延迟计算：使用yield可以让程序员轻松实现延迟计算的机制。方便我们实现某些计算密集型任务可以在需要时才进行，而不是在程序启动时就执行。这可以提高程序的性能和响应速度。

代码简洁：可以使代码更加简洁和易于理解。它允许程序员将复杂的逻辑分解为更小、更易于管理的部分。

易于扩展：可以轻松地扩展生成器和迭代器的功能。

yield缺点：

复杂性增加：对于初学者来说，理解yield关键字可能需要一些时间。正确地使用yield需要一定的经验和技巧，因此可能会增加代码的复杂性和维护难度。

性能开销：虽然yield关键字可以优化内存使用和提高代码的可读性，但在某些情况下，它可能会导致额外的性能开销。例如，每次使用yield return或yield break时，都会进行函数调用和对象创建，这可能会对性能产生一定的影响。

错误排查难度增加：不正确地使用yield关键字可能会导致意外的行为和难以调试的问题。例如，如果在迭代器方法中修改了正在迭代的集合，那么结果可能会出现不一致或不可预测。

扩展方法用法

Linq有两种写法，查询表达式写法(from.....in.....)和扩展方法写法，两种方法都是相互兼容的，程序编译时会将查询表达式转换为扩展方法，只要实现了IEnumerable的接口就可以使用Linq的扩展方法。

    class Person

    {

        public int Id;

        public string Name;

        public int Age;

        public int Score;

    }

    static List personList = new List()

    {

        new Person(){ Id=1,Name="小明",Age=20,Score=100},

        new Person(){ Id=2,Name="小王",Age=40,Score=80},

        new Person(){ Id=3,Name="小刘",Age=60,Score=60},

};

Select：返回指定类型:即把对象转换成另一个类型的新对象。

 var list = personList.Select(p => new { id = p.Id, name = p.Name });

Where：查询特定条件,返回还是原来的类型。

  var list = personList.Where((p) => p.Score >= 80 && p.Age < 50);

OfType：查询特定数据类型

 var list = personList .OfType();

OrderBy：对集合排序，升序排序.OrderByDescending降序排序。ThenBy、ThenByDescending第一次排序结果相同，进行第二次排序。

var list = personList.OrderBy((p) => p.Age).ThenBy((p) => p.Score);

Join：将一个集合与另一个集合通过指定键合并，返回合并后的集合。

static List rewardList = new List()

    {

        new Reward(){ Id=1,Score=100,RewardName="奖励1"},

        new Reward(){ Id=2,Score=80,RewardName="奖励2"},

        new Reward(){ Id=3,Score=60,RewardName="奖励3"},

};

var list1 = personList.Join(rewardList, p => p.Score, r => r.Score, (p, r) => new { pList = p, rList = r });

GroupBy：自身分组查询

var list2 = personList.GroupBy((p) => p.Score, (score, p) => new { score = score, count = p.Count() });

聚合操作符：Sum、Average、Max、Min：计算集合中指定数字类型数据的总和、平均值、最大值、最小值。

var sum = personList.Sum((p) => p.Age);

var avg = personList.Average((p) => p.Age);

转换操作符：

ToDictionary：将集合转换为字典

var list = personList.ToDictionary(p => p.Id);

ToList： 将集合转换为list

var dict = personList.ToDictionary(p => p.Id);

List list = dict.Values.ToList();

ToArray： 将集合转换为数组

var list5 = personList.ToArray();

限定操作符：

Any和All：判断集合中是否满足某个/条件，Contains检查某个元素是否在集合中。返回值都是布尔值。

 bool b1 = personList.Any((p) => p.Age < 50);

分页操作符：

Take：只查询指定个数的元素。

 var list7 = personList.Take(2);//只取前两个结果

Skip:跳过指定元素的个数的元素，提取其他元素。

var list6 = personList.Skip(2); //跳过前2个元素，其他其他元素

TakeWhile操作符用于从输入序列中返回指定数量且满足一定条件的元素。而TakeWhile会选取满足条件的集合，一旦遇到不满足条件的会中止搜索.而Where会选取所有满足条件的集合。

 var list7 = personList.TakeWhile( p => p.Age < 50);

Distinct：从集合中去除掉重复的元素，并返回一个新的集合

List numList = new List() { 1, 2, 3, 1};

var list = numList.Distinct();

Union：合并多个集合，并去除重复的元素，返回一个新的集合

  List List1 = new List() { 10, 20, 30, 40, 50 };

List List2 = new List() { 10, 40, 60, 80, 90 };

var result = List1.Union(List2);

Intersect：取交集 找到多个序列中共同存在的元素，并返回一个新的序列

  List List1 = new List() { 10, 20, 30, 40, 50 };

List List2 = new List() { 10, 40, 60, 80, 90 };

var result = List1.Intersect(List2);

First和Last：得到集合中第一个/最后一个元素。

var val =  personList.First( p => p.Age > 50);