数据结构解读、常规排序算法、常规查找算法、字典-hash-树-图、高级查找-高级排序
首页> 学海无涯> 算法> C#常用的数据结构
C#常用的数据结构
摘要 数据结构解读、常规排序算法、常规查找算法、字典-hash-树-图、高级查找-高级排序
Array数组
public class ArrayDemo
    {
        public static void Show()
        {
            {
                Console.WriteLine("***************Array******************");
                int[] intArray = new int[3];
                intArray[0] = 123;
                string[] stringArray = new string[] { "123", "234" };
            }
            {

                Console.WriteLine("***************多维Array******************");
                int[,] a = new int[3, 4] {
                                 {0, 1, 2, 3} ,   /*  初始化索引号为 0 的行 */
                                 {4, 5, 6, 7} ,   /*  初始化索引号为 1 的行 */
                                 {8, 9, 10, 11}   /*  初始化索引号为 2 的行 */
                                };
            }
{ Console.WriteLine("***************锯齿Array******************");
int[][] a = new int[2][]; a[0] = new int[] { 1, 2, 3 }; a[1] = new int[] { 2 }; } { Console.WriteLine("***************ArrayList******************"); ArrayList arrayList = new ArrayList(); arrayList.Add(Contione"); arrayList.Add("Is"); arrayList.Add(32);//add增加长度 //arrayList[4] = 26;//索引复制,不会增加长度 //删除数据 //arrayList.RemoveAt(4); var value = arrayList[2]; arrayList.RemoveAt(0);//开辟空间--copy arrayList.Remove("Contione");
{ ArrayList arrayList1 = new ArrayList(); arrayList1.Add("Contione"); arrayList1.Add("Is"); Console.WriteLine(arrayList1.Capacity); arrayList1.TrimToSize(); Console.WriteLine(arrayList1.Capacity); } { ArrayList arrayList1 = new ArrayList(6); arrayList1.Add("Contione"); arrayList1.Add("Is"); arrayList1.Add("Contione"); arrayList1.Add("Is"); Console.WriteLine(arrayList1.Capacity); arrayList1.TrimToSize(); Console.WriteLine(arrayList1.Capacity); } } { //List:也是Array,内存上都是连续摆放;不定长;泛型,保证类型安全,避免装箱拆箱 //读取快--增删慢 Console.WriteLine("***************List<T>******************"); List<int> intList = new List<int>() { 1, 2, 3, 4 }; intList.Add(123); intList.Add(123); //intList.Add("123"); //intList[0] = 123; List<string> stringList = new List<string>(); //stringList[0] = "123";//异常的
{ List<int> intList1 = new List<int>() { 1, 2, 3, 4, 5 }; intList1.Add(123); intList1.Add(123); intList1.Add(123); intList1.Add(123); Console.WriteLine(intList1.Capacity); intList1.TrimExcess(); Console.WriteLine(intList1.Capacity); } { List<int> intList1 = new List<int>(3) { 1, 2, 3, 4 }; intList1.Add(123); intList1.Add(123); intList1.Add(123); Console.WriteLine(intList1.Capacity); //intList1.TrimToSize(); Console.WriteLine(intList1.Capacity); } } } }

Array在内存上是连续摆放的(节约空间,查找也快,增删慢) 、定长多维数组(矩阵数组,图)、锯齿数组

ArrayList 动态数组  



 我们在看下ArrayList 数组 在添加数据的时候 会调用 EnsureCapacity 这个方法 我们看看究竟干了什么 

 

总结下:变长 Capacity—TrimToSize 超出长度时,是x2,开辟全新空间,copy数据 List<> Capacity-- TrimExcess 动态数组数组大家应该都比较熟悉我们还是来看下数据底层是怎么实现的吧 ArrayList 默认指定长度是 4  如果超出了数据长度会 默认Copy一个新的数组数据长度*2    List<T>也是如此  只不过List 是泛型避免了装箱拆箱带来的性能损耗。


Stack 

首先栈我们第一反应是有底的瓶子 先进去后出来 我们先看下具体的API  

public static void Show()
{
Console.WriteLine("***************Stack<T>******************"); Stack<string> numbers = new Stack<string>(); numbers.Push("one"); numbers.Push("two"); numbers.Push("three"); numbers.Push("four"); numbers.Push("five");//放进去
foreach (string number in numbers) { Console.WriteLine(number); } Console.WriteLine($"Pop '{numbers.Pop()}'");//获取并移除 Console.WriteLine($"Peek at next item to dequeue: { numbers.Peek()}");//获取不移除 Console.WriteLine($"Pop '{numbers.Pop()}'"); Stack<string> stackCopy = new Stack<string>(numbers.ToArray()); foreach (string number in stackCopy) { Console.WriteLine(number); } //stackCopy.Capacity; stackCopy.TrimExcess(); Console.WriteLine($"stackCopy.Contains(\"four\") = {stackCopy.Contains("four")}"); stackCopy.Clear(); Console.WriteLine($"stackCopy.Count = {stackCopy.Count}"); }

   很多人觉得用链表可以实现栈 但是在C#里面栈的实现也是一个数组是不是觉得想研究下 、还是看下BCL 源码是怎么实现Stack 的 


 根据源码我们发现栈内部实现其实也是一个数组 其实是可以通多索引去访问的只是没有提供相应的API而已(和数据是一样扩容也是取每次往最下面拿而已) 后续我会用链表去实现一个栈 

 给大家分享下

Queue队列

先进先出

public class QueueDemo
    {
public static void Show() { Console.WriteLine("***************Queue<T>******************"); Queue<string> numbers = new Queue<string>(); numbers.Enqueue("one"); numbers.Enqueue("two"); numbers.Enqueue("three"); numbers.Enqueue("four"); numbers.Enqueue("four"); numbers.Enqueue("five"); foreach (string number in numbers)
{ Console.WriteLine(number); }
Console.WriteLine($"Dequeuing '{numbers.Dequeue()}'"); Console.WriteLine($"Peek at next item to dequeue: { numbers.Peek()}"); Console.WriteLine($"Dequeuing '{numbers.Dequeue()}'"); Queue<string> queueCopy = new Queue<string>(numbers.ToArray()); foreach (string number in queueCopy) { Console.WriteLine(number); }
//queueCopy.Capacity; queueCopy.TrimExcess(); Console.WriteLine($"queueCopy.Contains(\"four\") = {queueCopy.Contains("four")}"); queueCopy.Clear(); Console.WriteLine($"queueCopy.Count = {queueCopy.Count}"); } }


  接下来我们也来看下BCL源码 




我们可以发下入栈的时候长度等于栈的长度是 int newcapacity = (int)((long)_array.Length * (long)GrowFactor / 100);  它并不是直接*2 有一个GrowFactor  叫增长系数(这个系数对外是可以对外指定的) 其实队列可以进来很多任务 所以增长可能不是两倍的区别 还有就是除去的时候和栈不太一样 我们还是一起看下源码



这里有个小套路 并没有删除 只是把当前的设置了一个默认值,数组每次移除其实整个数组需要重置又需要Copy一个新的数组,但是在这里并没有当前置为空的了那这里就不用担心队列具体执行到哪里了吗 所以后面加了一个 MoveNext _head 会做+1 的处理保证继续使用这个数组 包括SetCapacity 也是从head开始(扩容)

接下来我们看下数据结构在实际项目中的应用

  • Stack进制转换  (10进制转2进制)
  • 回文检测          (上海自来上来在海上)  用stack 的时候 写入到一半的时候一个个弹出来 比较是否相等
  • 语法检测器       (比较括号检测代码语法) 
  • 公式解释器       (表达式目录树的解析、解析Sql) 
  • 顺序日志
  • 任务异步计算
  • 优先级队列       (带优先级的队列 RabbitMQ)
        /// <summary>
        /// Stack进制转化
        /// </summary>
        /// <param name="number">原进制的值</param>
        /// <param name="b">目标进制</param>
        private static void BinaryConversion(int number, int format)
        {
            Stack<int> targetStack = new Stack<int>();
            do
            {
                targetStack.Push(number % format);
                number = number / format;
            } 
            while (number != 0);

            while (targetStack.Count > 0)
            {
                Console.Write(targetStack.Pop());
            }
        }

 后续我会写一些其他场景使用对应的例子。


版权声明:本文由Contione原创出品,转载请注明出处!

本文链接:https://contione.cn/article/detail/6

本文配乐
来说两句吧
最新评论
  • 不想知道!
    不想知道!
    后续分享下,排序的各种算法。

  • 一眼半生筹~
    一眼半生筹~
    我是你爸爸,我真伟大,我养你这么大

  • 不想知道!
    不想知道!
    好看个鸡毛

    不想知道!
    一眼半生筹~ 回复 不想知道! 比心心

    4/11/2020 10:06:15 PM回复

  • 不想知道!
    不想知道!
    [熊猫]太厉害了

    不想知道!
    不想知道! 回复 一眼半生筹~ ??

    4/11/2020 9:10:42 PM回复

    不想知道!
    一眼半生筹~ 回复 不想知道!

    4/11/2020 8:59:32 PM回复