计算机内存

在正式介绍数组之前，我们先来了解一下计算机内存。
通俗一点来说，计算机内存就是有一堆0和1组成的一连串的二进制，比如1101010111001。这一连串的数据中每一位我们叫比特位（bit），一个bit表示一个0或者1。但是我们的计算机CPU并不是针对每个bit位进行操作，cpu调度和操作的内存最小单位是字节（byte），一个字节由8bit组成。后续我们涉及到的内存相关的单位也都是基于字节的。
总结： 内存就是由无数个格子组成的连续集合，每个格子中有8个bit位，格子的地址从0开始，依次为0，1，2，3......

计算机内存有一系列的单位转换
1Byte=8Bit
1KB=1024Byte
1MB=1024KB=1024*1024Byte
1GB=1024MB=102410241024Byte
所以说，对于一个4GB的内存条来说，它的内存是0到2^32Byte，说的再简单一点，4GB的内存有2^32个格子，每个格子中有八个bit位。大概示意图如下：

介绍完内存，接下来介绍一下数组是什么，数组就是在内存中申请一片连续的空间用于存放数据。数组在内存中的地址是连续的，它的索引下标从0开始。
假设我们申请了一个长度为5的int数组，每个int类型占四个字节，那么这个数组在内存中的模型是下面这样的，一个格子占4个字节，如果第一个格子的地址为1000，那么第二个格子、第三个格子的地址依次在第一个格子的地址上加上4和8，其地址就是1004、1008。

一维数组的声明

C#中，一维数组的声明格式如下：
数据类型[] 数组名=new 数据类型[元素个数]
如：申请一个长度为10的int数组，写法就是：int[] _array = new int[10]

一维数组的具体算法

首先我们声明一个名为Array的类，里面定义一个int数组，用于存放线性表的数据，再定义一个 _length 字段，表示线性表的实际长度。代码如下：

internal class Array
{
    private int[] _array;//声明数组 用于存放数据
    int _length;//线性表的实际长度
}

这里大家对数组的长度和线性表的长度 _length 要有一个正确的认识，数组只是存放数据元素的一个容器，而实际存放了多少个数据元素，需要有一个单独的变量 _length 来表示。

算法1:查询线性表中是否存在某一个值

查询一个值的算法比较简单，我们只需要从线性表的第一个元素开始，将数组中的每一个值和要查询的值一一比对，如果存在，就返回这个值的下标.如果查到最后一个元素还是找到对应的值，则直接返回-1；

public int Get(int data)
{
    for(int  i = 0; i < _length; i++)
    {
        if(_array[i] == data)
        {
            return i;
        }
    }
    return -1;
}

算法2：修改线性表中某一个值

数组值的修改在C#中也是非常简单的，因为数组在内存中是连续的一块内存，可以通过首地址计算出后续任何一个索引的地址并进行修改。基本格式如下：
数组名[数组下标]=要修改的值。比如我要把一个名为array的数组的第3个元素的元素值改为4，这里注意，数组的索引下标是从0开始的，所以第3个元素的下标为2，语法为:array[2]=4
下面这个方法，index代表要修改的下标，data表示要修改的值

public bool Update(int index, int data)
{
    if(index<0 || index >= _length)
    {
        return false;
    }
    _array[index] = data;
    return true;
}

算法3：插入一个值 在线性表的指定索引处插入一个元素。

数组在内存中因为是连续的一块内存，当我们想在中间某个位置插入一个数据的话，那么这个位置后面的所有元素(包括这个位置的元素)都要向后移动。同时要将线性表的实际长度 _length 加上1。
这里有一点要注意，如果存放线性表的数组已经满了，我们就需要扩容。比如声明了一个长度为10的数组存放线性表元素，但是线性表的实际长度也是10，如果这个时候再插入一个元素的话，数组就放不下了，我们就需要扩容。扩容的意思就是声明一个长度更大的新数组来存放数据,同时把原来数组的元素复制到新数组中。我们这里的扩容后方案是：每一次都将数组的长度增加一倍。

public bool Insert(int index, int data)
{
    if (_array.Length == _length)
    {
        int[] newArray = new int[_length * 2];
        for (int i = 0; i < _length; i++)
        {
            newArray[i] = _array[i];
        }
        _array = newArray;
    }
    for (int i = _length - 1; i >= index; i--)
    {
        _array[i + 1] = _array[i];
    }
    _array[index] = data;
    _length++;
    return true;
}

算法4：删除数组中指定下标的元素

数组中删除元素和新增元素恰好相反，新增元素是把新增元素所在下标后面的所有元素后移动，删除元素则是把要删除下标后面的所有元素向前移动一个位置。

public bool Delete(int index)
{
    for (int i = index; i < _length - 1; i++)
    {
        _array[i] = _array[i + 1];
    }
    _array[_length - 1] = 0;
    _length--;
    return true;
}

当果然这里的示例代码的参数是要删除的数组下标，当然你也可以直接传递一个要删除的数据进来。这样的话，你就需要先找到这个数据对应的下标，然后再执行删除操作。

算法5：输出线性表

使用一个for循环输出数组中的所有元素，这里就直接给大家看一下代码

public void Print()
{
    Console.Write($"总共{_length}个元素:");
    for (int i = 0; i < _length; i++)
    {
        Console.Write(_array[i] + " ");
    }
    Console.WriteLine();
}

示例代码地址

https://gitee.com/jiamingyuanjin_admin/data_struct/blob/master/DataStruct/01Array.cs

总结

通过以上的代码我们可以发现，对于数组的随机访问效率非常高，查询和更新的效率都很快。但是新增元素和删除元素的效率却很低，因为新增和删除都需要大量移动数组中的元素。当数组长度很长的时候，这个操作明显就不合适。不过没关系，后面的链表会帮助我们解决这个新增和删除效率低的问题。