数据结构 – 数组-牛翰网

数据结构 – 数组

今天我们将开始第一个数据类型-数组的学习。

经常会看到这样的问题,怎么学习数据结构,我的答案是搞清楚具体数据结构对应的抽象数据类型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、定义类

如果我们要实现上面关于数组的定义,那么需要哪些字段来给这些功能提供支持呢?

因为我们需要直接管理内存,所以需要一个管理内存的指针字段;

因为我们需要直接获取数组长度,所以需要一个存储数组长度字段;

因此我们的类初步是这样的:

public class MyselfArray
{
    //申请内存起始位置指针
    private IntPtr _pointer;
    //数组长度
    private int _length;
}

3、初始化Init

先想下我们平时是怎么使用数组的?

int[] array = new int[5]

我们平时写的很简单一行代码就定义好了一个指定长度的数组,但是它的背后却做了很多事。new int[5] 相当于分配了一个能存储5个整数的内存空间,并且都初始化为0。

那我们现在就自己在实现这个过程。我们首先需要申请能存放5个整数的空间,然后再初始化每个元素值,具体实现代码如下:

//初始化数组为指定长度,并元素设置默认值0
public MyselfArray Init(int capacity)
{
    //初始化数组长度为capacity
    _length = capacity;
    //分配指定字节数的内存空间
    _pointer = Marshal.AllocHGlobal(capacity * sizeof(int));
    //初始化数组元素
    for (int i = 0; i < _length; i++)
    {
        //初始化每个元素为0
        Marshal.WriteInt32(_pointer + i * sizeof(int), 0);
    }
    //返回数组
    return this;
}

以下两点需要单独说明一下。

怎么计算需要分配的字节数?因为数组中所有元素都是同类型的,这里我们是用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

这个比较简单直接把数组长度私有字段返回即可。

//数组长度
public int Length
{
    get
    {
        return _length;
    }
}

5、根据索引获取元素值Get

在获取元素时,我们首先需要校验索引是否有效,首先索引小于0肯定是无意义的;其次大于数组最大元素索引也是没有意义的,具体代码如下:

//根据索引获取元素
public int Get(int index)
{
    //索引小于0 或者索引大于数组长度-1 则报错
    if (index < 0 || index > _length - 1) throw new IndexOutOfRangeException();
    //读取指定索引元素值
    return Marshal.ReadInt32(_pointer + index * sizeof(int));
}

6、根据索引设置元素值Set

同样的设置元素值时,也需要校验索引有效性。

//根据索引设置元素
public void Set(int index, int value)
{
    //索引小于0 或者索引大于数组长度-1 则报错
    if (index < 0 || index > _length - 1) throw new IndexOutOfRangeException();
    //根据索引设置元素值
    Marshal.WriteInt32(_pointer + index * sizeof(int), value);
}

7、根据索引插入元素Insert

这块逻辑是目前最复杂的一个,首先需要对索引有效性校验,其次需要判断当前索引位置上是否有值,没值直接插入,有值则继续查看其后是否有空位,无空位直接报错,有空位则移动元素腾出索引处位置用于插入新元素。具体实现代码如下:

//根据索引插入元素
public void Insert(int index, int value)
{
    //索引小于0 或者索引大于数组长度-1 则报错
    if (index < 0 || index > _length - 1) throw new IndexOutOfRangeException();
    //获取索引处的值
    var v = Get(index);
    //如果索引处无值
    if (v == 0)
    {
        //直接在索引处插入新元素并返回
        Set(index, value);
        return;
    }
    //定义空位置索引
    var nullIndex = -1;
    //检查插入位置之后是否有空位
    for (int i = index + 1; i < _length; i++)
    {
        //有空位
        if (Get(i) == 0)
        {
            //记录空位置处索引,并结束检查
            nullIndex = i;
            break;
        }
    }
    //如果没找到空位,则报错
    if (nullIndex == -1)
    {
        throw new InvalidOperationException("没有可用的空位用于插入。");
    }
    //从插入位置到空位之前的元素向后移动一位
    for (int i = nullIndex; i > index; i--)
    {
        Set(i, Get(i - 1));
    }
    //在指定索引处插入新元素
    Set(index, value);
}

注:这里使用值为0判断是否为空位,因为数组初始化就是默认值0,因此使用0表示空位即还没赋值,这是我们自己的定义。实际上可能0本身也是有意义的,如果要想准确判断是否有空位还需额外的处理,这里我们只是为了理解数组核心概念而进行简单演示,不用纠结这个0判断。

8、根据索引移除元素Remove

这个方法逻辑也比较简单,先验证索引有效性,然后从要移除索引位置处开始把后面所有元素向前移动一位,最后一位则变为默认值0。

//根据索引移除元素
public void Remove(int index)
{
    //索引小于0 或者索引大于数组长度-1 则报错
    if (index < 0 || index > _length - 1) throw new IndexOutOfRangeException();
    //后面的元素(除了最后一个元素)向前移动一位
    for (int i = index; i < _length - 1; i++)
    {
        Set(i, Get(i + 1));
    }
    //最后一位设为默认值0
    Set(_length - 1, 0);
}

9、释放内存Dispose

支持数组类型基本完成,还差最后关键一步,因为内存是我们直接申请的,所以用完后还需要释放,因此我们的类需要实现IDisposable接口,并实现Dispose方法,具体方法如下:

public void Dispose()
{
    if (_pointer != IntPtr.Zero)
    {
        Marshal.FreeHGlobal(_pointer);
        _pointer = IntPtr.Zero;
    }
}

自此我们的数组类型大功告成。

通过上面方法实现我们也能发现插入元素和删除元素是很繁琐的,特别是一些特殊情况怎么处理,不同的定义就是不同的实现。比如上面的插入元素,插入后面如果有多个空位怎么办?是后面所有元素都向后移动一位,还是只用到第一个空位处向后移动一位?如果全部向后移动一位,那么如果最后一位是直接扔掉还是报错不让操作?

而且涉及到移动元素,就涉及性能问题,因此像C#语言数组本身是没有插入、删除方法的。我们这里这样定义数组,并且来实现这些方法,主要还是学习数据结构。

同时还是那句话数据结构终究还是我们人为定义出来的,我们定义有就有,我们怎么定义那么这个数据结构就是什么样子的,所以数据结构没有你像的那么难,那么难以理解。只要把关键要素理解掌握了你就会了。

:测试方法代码以及示例源码都已经上传至代码库,有兴趣的可以看看。https://gitee.com/hugogoos/Planner

请登录后发表评论

    没有回复内容