数据结构之常用表结构_.NET_编程开发_程序员俱乐部

    最近结合博客园和自己近几年的一些积累，觉得有必要对.Net常用的一些表进行一次总结，一边为了自己后面看另一方面也希望能够对各位博友有一定的帮助，有不正确的地方希望大家帮忙纠正，非常感谢！！！

表的数组结构（针对一维数组）：

    概述：数组是一个长度固定的表结构，它的元素必须存放在一个内存空间当中。

    功能说明：它提供了表的创建、清除、复制和元素的存取以及排序搜索功能（由于它长度固定所以不能对元素进行新增和删除）

    创建数组：创建数组通常采用初始化或者对下标进行赋值的方式进行创建

    清除数组：该功能主要由Array类的静态方法实现，可以将指定范围内的元素清空，重置为初始值

    复制数组：由Array类的静态方法实现的浅度复制，可以将源数组指定范围内的元素复制到目标数组中的指定位置

    元素搜索：由Array类的静态方法实现，元素可支持正向搜索、反响搜索、可以搜索元素在数组当中的位置、可以搜索指定元素、可以顺序搜索也可以二分法搜索（注意：使用二分法搜索表中的元素必须进行排序）

    元素排序：由Array类的静态方法实现，使用快速排序算法将数组元素进行重新排序，一边能够使用二分法搜索

    元素存取：由实例方法实现，使用元素在表中的位置通过下标访问符或 GetValue、SetValue 方法对表元素进行随机存取

 1        //创建数组：初始化数组（初始化的方式创建）
 2        int[] arr_int = new int[] { 1, 2, 3, 4, 5 };
 3        //数组输出结果：｛1，2，3，4，5｝
 4 
 5        //创建数组：通过赋值下标的方式创建数组
 6        int[] array_int = new int[2];
 7        array_int[0] = 1;
 8        array_int[1] = 1;
 9        //数组输出结果：｛1，2｝
10        //清除数组：
12        Array.Clear(arr_int, 0, 1);
13        //数组输出结果：｛0，2，3，4，5｝
14 
15        //复制数组：
16        //var copyArr_int = new int[] { };//如果是复制到没有固定长度的数组会直接报错
17        var copyArr_int = new int[5];
18        Array.Copy(arr_int, copyArr_int, arr_int.Length);
19        //数组输出结果：｛0，2，3，4，5｝
20 
21        //数组搜索：
22        var number = Array.Find(arr_int, e => e == 3);//搜索指定的元素
23        var index = Array.IndexOf(arr_int, 2);//正向搜索
24        var lastvalue = Array.LastIndexOf(arr_int, 3);//反向搜索
25        var index1 = Array.FindIndex(arr_int, e => e == 2);//搜索元素在数组当中的位置
26 
27        Array.Sort(arr_int);
28        var binIndex = Array.BinarySearch(arr_int, 0);//二分法搜索表中的元素
29 
30        //数组排序：
31        Array.Sort(arr_int); 

   应用场景：当我们操作的数据满足如下的几个条件，那么我们则可以使用该数据结构

   1、元素数量固定（数组长度固定）

   2、无需动态添加或者删除元素

   3、可以通过元素在表中的位置尽心随机存取

   性能说明： 

   元素存取：由于我们只能通过下标或者GetValue、SetValue来存取数组元素，所以该方法的存取难度为0(1)，注意：由于GetValue 和 SetValue 方法来进行随机存取时，有可能出现装箱的额外操作，所以首先推荐使用通过下标的方式进行存取数据

   元素排序：使用快速排序法进行排序，该操作的时间复杂度为 O(N * log N)

   元素搜索：元素的搜索分为两种情况：顺序搜索和二分搜索。如果使用顺序搜索则该操作的时间复杂度为 O(N)；如果使用二分搜索则该操作的时间复杂度为 O(log N)

表的数组结构（针对ArrayList数组）：

   概述：ArrayListshi是通过维护一个object对象类型的_items的数组来存放所有元素

   功能说明：它提供了表的创建、清除、复制，表元素的存取、搜索、新增、删除和排序功能

   表的创建：实例化 _items，并可以将传入的元素集合拷贝（浅度拷贝）到 _items 中

   表的清除（Clear）：清除 _items 中的数据，通过调用 Array.Clear 方法来实现的

   表的复制（CopyTo）：将表中指定范围内的元素复制到目标表中指定的位置，通过调用 Array.Copy 方法来实现的

   元素的存取（this[]）：只能使用元素在表中的位置通过索引器来对元素进行随机存取

   元素的新增：可以将一个新元素添加到表的最后（Add），也可以将其插入到指定的位置（Insert）；可以将一组新元素添加到表的最后（AddRange），也可以将其插入到指定的位置（InsertRange）

   元素的删除：可以从表中删除指定的元素（Remove），也可以将表中指定位置的元素删除（RemoveAt），还可以将表中指定范围内的元素删除（RemoveRange）

   元素的排序（Sort）：将表中的元素进行快速排序，以便能够使用二分法进行元素的搜索

   元素的搜索：可以进行顺序搜索（IndexOf 和 LastIndexOf，通过调用Array.IndexOf和Array.LastIndexOf方法实现）；也可以使用二分法进行搜索（BinarySearch，调用Array.BinarySearch 方法实现）

   性能说明

   元素的存取：虽然对于外部来说是使用索引器来对元素进行随机存取，其实其内部就是使用数组的下标对_items 的元素进行存取，所以该操作的时间复杂度为O(1)

   元素的新增：虽然对于外部来说它提供了元素的新增功能，但是对于其内部来说只是指定数组元素的赋值，

                         如果在表的尾部添加元素（Add），则只是简单的为指定的数组元素赋值，所以该操作的时间复杂度为O(1)；如果在表的中间插入元素（Insert），则需要将数组中指定位置之后的元素都向后移动，然后为指定位置的数组元素赋以新值，则该操作的时间复杂度为O(N)

                         只要存在元素的新增，这里就会存在一个扩容的问题。ArrayList内部是通过创建容量更大的新的数组，将所有已有元素拷贝到新数组中指定的位置，然后再将新增的元素存入数组

   元素的删除：当表中指定的元素被删除时，需要将 _items 中被删除元素之后的元素都向前移动，即 _items 中的所有元素必须集中在数组的前部，中间不能出现空元素，所以该操作的时间复杂度为 O(N)

   元素的排序：使用快速排序法对表中的元素进行重新排序，该操作的时间复杂度为 O(N * log N)

   元素的搜索：如果使用顺序搜索则该操作的时间复杂度 O(N)；如果表元素已经进行过排序，使用二分法搜索则该操作的时间复杂度为 O(log N)

   应用场景：当我们要操作的数据满足下面条件时就比较适合使用ArrayList：

   1、  能够通过元素在表中的位置进行随机存取；

   2、  能够动态新增和删除元素；

   3、  不能保证各个元素的数据类型能够兼容；

   4、  能够对元素进行排序；

表的泛型集合List<T>  

   概述

          它实现了一个可以动态添加、删除元素的强类型表结构，内部维护一个强类型T的数组 _items 来存放所有的元素，所以它只提供通过元素的位置来存取元素的方式。

   它所提供的功能和内部实现与ArrayList 一样，唯一的区别是：ArrayList 相对来说是弱类型的，没有类型安全保障；而List<T> 相对来说是强类型的，有类型安全保障。

   ArrayList：它操作的是一个 object 数组，所以加入它的数据都必须先转换为object 类型，这对于值类型来说就需要进行装箱操作，这也意味着ArrayList中可能存放着各种类型的数据，而且这些数据不一定兼容。

   List<T>：它操作的是一个指定类型T的数组，这不仅避免了值类型的装箱操作，也提供了类型安全，所有加入它的数据都必须与T类型兼容。

   功能说明：参照 ArrayList 的功能说明。

   性能说明：参照ArrayList 的性能说明。

   应用场景：List<T> 和 ArrayList 的适用场景也只有一个区别——能不能保证各个元素数据类型的兼容性：能够保证就使用List<T>，不能保证就使用ArrayList

表的链表结构

   概述：LinkedList<T> 提供了一个以双向链表方式实现的表结构，内部维护了一组 LinkedListNode<T> 类型的节点，每个节点都保存了自己所属的 LinkedList<T>（list）、前一个节点（prev）、后一个节点（next）和储存在该节点的元素（item）。在链表形式的表中存在节点和元素两个概念，它们虽有关联但不尽相同。元素是表结构需要存储的真正数据，但是它不包含任何能够访问其它元素的信息，这样不可能实现链表形式的表；而节点不仅存储了表结构需要储存的真正数据，还储存了访问其它节点的信息。由上可以看出：元素是表结构需要存储的真正数据；而节点是这些元素的载体，是组成链表的基本单位。

             由于链表的组成单位是节点，所以对表元素的存取都必须通过储存元素的节点间接存取，不能直接存取。又因为每个节点都记录了前一个节点和后一个节点的内存地址，所以这些节点不需要存放在连续的内存空间中。

   功能说明：它提供了表的创建、清除、复制，表元素的存取、新增、删除和搜索。

   表的创建：表的实例化，并可以根据传入的元素创建相应的节点，加入新建的表中。

   表的清除：清除表中所有的节点。

   表的复制：将表中所有节点中储存的元素复制（浅度复制）到指定数组的指定位置。

   元素的存取：必须要先通过元素的搜索获取储存该元素的节点，然后再通过该节点对元素进行存取。但是对于链表的第一个元素或最后一个元素的存取不用那么繁琐，只需要通过First 或 Last 这两个属性直接获取储存它们的第一个节点或最后一个节点。

   元素的新增：新增一个元素其实就是新增一个节点，所以新增元素时可以传入要新增的元素，也可以传入包含该新增元素的节点，但是同一个节点不能加入到不同的链表中。可以将元素添加到表头（AddFirst），也可以将元素添加到表尾（AddLast），还可以将元素插入到指定元素之前（AddBefore）或之后（AddAfter）。

   元素的删除：删除一个元素其实就是删除一个节点，所以删除元素时可以传入要删除的元素，也可以传入要删除的节点（这个节点必须属于该表）。当传入的是要删除的元素时，会先根据该元素搜索到储存该元素的节点，然后将该节点删除。除了可以删除指定的元素外，还可以删除特殊的元素：第一个元素（RemoveFirst）或最后一个元素（RemoveLast）。

元素的搜索：根据指定的元素从表中搜索储存该元素的节点。可以正向搜索（Find），也可以逆向搜索（FindLast）。

    性能说明

   元素的搜索：链表中的节点只能逐一的顺序访问，所以该操作的时间复杂度为 O(N)。

   元素的存取：链表的组成结构决定了它不能支持随机存取（即：不能通过元素位置来对元素进行直接存取），所以 LinkedList<T> 并不提供随机存取的方式。

                         因为可以通过 First 或 Last 属性直接获取链表的第一个节点或最后一个节点，所以链表中第一个元素或最后一个元素的存取操作的时间复杂度为 O(1)。

                         其它的元素都必须先搜索到储存该元素的节点，然后再通过搜索到的节点对元素进行存取，所以该操作的时间复杂度为O(N)。

   元素的新增：链表中新增元素的操作比较简单，只需要修改前一节点的next、后一节点的prev 和储存该元素的节点的 prev与next的值。该操作的时间复杂度为 O(1)。

   元素的删除：链表中删除元素的操作比较简单，只需要修改前一个节点的next、后一个节点的prev并将删除节点的next、prev和list都重置。该操作的时间复杂度为 O(1)。 

   应用场景：当我们要操作的数据满足下面条件时就比较适合使用LinkedList<T>：

   1、  会频繁的进行元素的新增和删除；

   2、  通常只会顺序的访问表中的所有元素，很少需要对元素进行随机存取；

   3、  不需要对表中的元素进行排序。

   应用实例：如果想要运行该实力，可以去掉redis缓存

using HB.Cache;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Serialization;

namespace HB.Test
{
    /// <summary>
    /// 
    /// </summary>
    class Program
    {
        /// <summary>
        /// 
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            try
            {
                //获取链表
                var documentLinkeList = GetDocumentLinkeList();

                //获取链表第一项
                var first = documentLinkeList.First;

                //获取链表最后一项
                var last = documentLinkeList.Last;

                //根据查询条件获取链表指定项
                var document = documentLinkeList.FirstOrDefault(e => e.Sequence == 1);
                var documentNote = documentLinkeList.Find(document);

                //阻塞线程
                Console.ReadKey();
            }
            catch (Exception ex)
            {
                Log4netHelper.Debug<Program>("异常：", ex);
            }
        }

        /// <summary>
        /// 获取文档双向链表
        /// 备注：有加redis缓存
        /// </summary>
        /// <returns></returns>
        private static LinkedList<Document> GetDocumentLinkeList()
        {
            var key = "DocumentLinkeList:Test";
            LinkedList<Document> documentLinkeList = null;
            ExchangeRedisHelper cache = new ExchangeRedisHelper();
            if (cache.ContainsKey(key))
            {
                documentLinkeList = cache.GetFromBinary<LinkedList<Document>>(key);
            }
            else
            {
                List<Document> documentList = new List<Document>();
                documentList.Add(new Document() { Title = "one", Content = "Sample_one", Priority = 8, Sequence = 1 });
                documentList.Add(new Document() { Title = "two", Content = "Sample_two", Priority = 8, Sequence = 2 });
                documentList.Add(new Document() { Title = "three", Content = "Sample_three", Priority = 8, Sequence = 3 });
                documentList.Add(new Document() { Title = "four", Content = "Sample_four", Priority = 8, Sequence = 4 });
                documentList.Add(new Document() { Title = "five", Content = "Sample_five", Priority = 8, Sequence = 5 });
                documentList.Add(new Document() { Title = "six", Content = "Sample_six", Priority = 8, Sequence = 6 });
                documentList.Add(new Document() { Title = "seven", Content = "Sample_seven", Priority = 8, Sequence = 7 });
                documentList.Add(new Document() { Title = "eight", Content = "Sample_eight", Priority = 8, Sequence = 8 });
                documentList.Add(new Document() { Title = "nine", Content = "Sample_nine", Priority = 8, Sequence = 9 });
                documentList.Add(new Document() { Title = "ten", Content = "Sample_ten", Priority = 8, Sequence = 10 });

                documentLinkeList = new LinkedList<Document>(documentList);
                var expireSeconds = (int)DateTime.Now.AddDays(1).Subtract(DateTime.Now).TotalSeconds;
                cache.SetToBinary(key, documentLinkeList, expireSeconds);
            }

            return documentLinkeList;
        }
    }

    /// <summary>
    /// 存储在链表中的元素是Document类型
    /// </summary>
    [Serializable]
    [DataContract]
    public class Document
    {
        /// <summary>
        /// 文档标题
        /// </summary>
        [DataMember(Order = 1)]
        public string Title { get; set; }

        /// <summary>
        /// 文档内容
        /// </summary>
        [DataMember(Order = 2)]
        public string Content { get; set; }

        /// <summary>
        /// 文档优先级
        /// </summary>
        [DataMember(Order = 3)]
        public byte Priority { get; set; }

        /// <summary>
        /// 排序字段
        /// </summary>
        [DataMember(Order = 4)]
        public int Sequence { get; set; }
    }
}