| 
今天我们将开始第一个数据类型-数组的学习全国安全配资平台。 经常会看到这样的问题，怎么学习数据结构，我的答案是搞清楚具体数据结构对应的抽象数据类型ADT，抛开语言层面自带的数据类型，然后自己从头 实现一遍。 其实数据结构没多复杂，数据结构就是人们的经验总结，根据其特定进行抽象定义命名，说到底就是我们定义的，你叫它是数组它就是数组，叫它是数集那它就是数集，所有我们只需要知道一个数据结构的定义，并且可以自己实现其定义，那么可以说你已经完全掌握这个数据结构了。 01、定义什么是数组？数组是同类型的元素序列，数组是一种线性数据结构，它用一组连续的内存空间来存储一组类型相同的元素。 一个长度为10的int类型数组，在内存中存储类似下图布局。 数组的线性数据结构体现为数据一个挨着一个，连续的内存空间体现为在存储地址[1000-1039]这个空间中间是一个整体没有间隙的，相同元素指的是所有空间都用来存储int类型。 因此我们可以总结出数组的以下特性： 长度固定，因为内存一旦分配后大小将无法直接改变。 内存空间地址是连续的。 元素类型相同，既可以是值类型也可是引用类型。 索引一般从0开始。 随机访问，能够通过索引即下标直接访问到元素。 02、实现1、ADT定义 抽象数据类型（Abstract Data Type，简称ADT），是一种数据抽象方法，用于描述数据对象的逻辑特征和操作，通常使用三元组表示法，即ADT=(D，S,P)，具体含义如下： D（Data Objects）：数据对象，定义数据的集合和性质。 S（Structure）：数据对象之间的关系集，描述了数据对象内部各元素之间的结构和约束条件。 P（Primitive Operations）：数据对象的基本操作集，如插入、删除、修改、查找、遍历等。 如果我们要实现数组就要先定义好数组，下面我们用ADT定义下数组。 ADT Array{ 数据对象：D 是一个有限、非空的整数序列，D = {a1, a2, ..., an}，其中 ai 表示序列中的第i个元素，n是序列的长度。 数据关系：D中的元素通过它们的索引（位置）进行组织，索引是从0到n-1的整数。 基本操作：[ Init(n) ：初始化一个长度为n的数组，所有元素初始值为元素对应类型默认值。 Length：返回数组长度。 Get(i)：返回索引为i的元素，如果i无效，则报错。 Set(i,v)：设置索引为i的元素值为v。如果i无效，则报错。 Insert(i,v)：在索引为i位置处插入v。如果i处无元素，则直接插入v；如果i处有元素并且其后面存在还未存储元素的位置，则从未存储元素位置之前的元素开始都像后移动一个位置直至腾出i位置，然后插入v。如果i处有元素并且其后面所有位置中都已存储元素，则报错；如果i无效，则报错。 Remove(i)：移除索引为i位置处元素，并将其后所有元素都向前移动一位，永远保持元素是连续的，并且删除空间都移动到数组尾部，且不可访问。 ] } 定义好数组ADT，下面我们就可以开始自己实现一个int类型数组类型了。 2、定义类 如果我们要实现上面关于数组的定义，那么需要哪些字段来给这些功能提供支持呢？ 因为我们需要直接管理内存，所以需要一个管理内存的指针字段； 因为我们需要直接获取数组长度，所以需要一个存储数组长度字段； 因此我们的类初步是这样的： 3、初始化Init 先想下我们平时是怎么使用数组的？ int[] array = new int[5] 我们平时写的很简单一行代码就定义好了一个指定长度的数组，但是它的背后却做了很多事。new int[5] 相当于分配了一个能存储5个整数的内存空间，并且都初始化为0。 那我们现在就自己在实现这个过程。我们首先需要申请能存放5个整数的空间，然后再初始化每个元素值，具体实现代码如下： 以下两点需要单独说明一下。 怎么计算需要分配的字节数？因为数组中所有元素都是同类型的，这里我们是用int类型举例，所以申请的空间就是一个int类型的大小乘以数组长度即capacity * sizeof(int)。 怎么计算每个元素的位置？我们再来回顾一下这张图，因为每个元素类型是相同的，因此每个元素所占的空间大小也是相同的，因此我们可以通过下面的寻址公司计算出指定元素的内存地址。 a[i]内存地址 = a[0]内存地址 + i * 类型大小 我们代码中IntPtr _pointer就是表示分配的内存块首地址，也就是对应如图a[0]内存地址，类型大小可以通过sizeof(int)获取，所以我们就可以通过首地址指针和指定元素索引定位到具体元素，然后直接进行内存操作赋值。 这里还有一个有趣的小知识，为什么大多数语言索引都是从0开始？设想一下如果索引从1开始，上面的寻址公式为： a[i]内存地址 = a[0]内存地址 + (i-1) * 类型大小 这样就导致每次访问数组元素都要多一步减1的操作，而对应CPU来说就是多一次减法指令，所以索引从0开始很大一部分原因就是这样可以优化性能，简化计算。 4、数组长度Length 启动抓牛副图，在启动抓牛下穿为强势，上穿为弱势转折，红色为强势启动线，指标仅供学习参考请结合指标使用） 这个比较简单直接把数组长度私有字段返回即可。 5、根据索引获取元素值Get 在获取元素时，我们首先需要校验索引是否有效，首先索引小于0肯定是无意义的；其次大于数组最大元素索引也是没有意义的，具体代码如下： 6、根据索引设置元素值Set 同样的设置元素值时，也需要校验索引有效性。 7、根据索引插入元素Insert 这块逻辑是目前最复杂的一个，首先需要对索引有效性校验，其次需要判断当前索引位置上是否有值，没值直接插入，有值则继续查看其后是否有空位，无空位直接报错，有空位则移动元素腾出索引处位置用于插入新元素。具体实现代码如下： 注：这里使用值为0判断是否为空位，因为数组初始化就是默认值0，因此使用0表示空位即还没赋值，这是我们自己的定义。实际上可能0本身也是有意义的，如果要想准确判断是否有空位还需额外的处理，这里我们只是为了理解数组核心概念而进行简单演示，不用纠结这个0判断。 8、根据索引移除元素Remove 这个方法逻辑也比较简单，先验证索引有效性，然后从要移除索引位置处开始把后面所有元素向前移动一位，最后一位则变为默认值0。 9、释放内存Dispose 支持数组类型基本完成，还差最后关键一步，因为内存是我们直接申请的，所以用完后还需要释放，因此我们的类需要实现IDisposable接口，并实现Dispose方法，具体方法如下： 自此我们的数组类型大功告成。 通过上面方法实现我们也能发现插入元素和删除元素是很繁琐的，特别是一些特殊情况怎么处理，不同的定义就是不同的实现。比如上面的插入元素，插入后面如果有多个空位怎么办？是后面所有元素都向后移动一位，还是只用到第一个空位处向后移动一位？如果全部向后移动一位，那么如果最后一位是直接扔掉还是报错不让操作？ 而且涉及到移动元素，就涉及性能问题，因此像C#语言数组本身是没有插入、删除方法的。我们这里这样定义数组，并且来实现这些方法，主要还是学习数据结构。 同时还是那句话数据结构终究还是我们人为定义出来的全国安全配资平台，我们定义有就有，我们怎么定义那么这个数据结构就是什么样子的，所以数据结构没有你像的那么难，那么难以理解。只要把关键要素理解掌握了你就会了。 数据元素数组内存int发布于：上海市声明：该文观点仅代表作者本人，搜狐号系信息发布平台，搜狐仅提供信息存储空间服务。
|
