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

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > .NET > 数据结构之常用表结构

数据结构之常用表结构

 2017/11/13 17:03:25  ζ?蜗牛  程序员俱乐部  我要评论(0)
  • 摘要:最近结合博客园和自己近几年的一些积累,觉得有必要对.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; }
    }
}
发表评论
用户名: 匿名