数据结构学习之线性表（二）

开篇：上次我们讲到，实现基本的数组的增删改查。现在我们来优化和改善,并且分析一下。

1. 首先我们定义的数组类型 不支持泛型。

2. 当容量不够使用的时候, 应该可以自动触发扩容操作。

我们来实现一下。我们使用泛型的t类型来代表。

public class array<t>
    {
        private t[] data;
        private int size;
        private int capacity;
        public bool isfull => this.capacity == this.size;
        public array(int capacity = 20)
        {
            this.capacity = capacity;
            this.data = new t[this.capacity];
        }
}

此时 增删改查都应该操作泛型t变量

比如 add ，此时我们增加扩容操作，我们来新增个数组 遍历复制操作，容量的大小应该视数组的容量大小来定。

public void add(t value)
        {
            if (isfull)
                this.expandcapacity(this.capacity * 2);
            this.size++;
            this.data[this.size - 1] = value;
        }
}

private void expandcapacity(int capacity)
 {
        var newdata = new t[capacity];
        for (int i = 0; i < newdata.length; i++)
        {
            newdata[i] = this.data[i];
        }
        this.data = newdata;
        this.capacity = capacity;
 }

删除操作

public t delete(int index)
{
        if (index < 0)
            throw new exception("index is less than zero");
        if (index > this.capacity-1)
            throw new exception("index is more than capacity");
        if (index > this.size-1)
            return default;
        var value = this.data[index];
        for (int i = index; i < this.size-1; i++)
        {
            this.data[i] = this.data[i+1];
        }
        this.setempty(this.size-1);
        this.size--;
        if (this.size <= this.capacity/2)
           this.narrowcapacity(this.capacity / 2);
        return value;
 }

private void narrowcapacity(int capacity)
{
        var newdata = new t[capacity];
        for (int i = 0; i < this.data.length; i++)
        {
            newdata[i] = this.data[i];
        }
         this.data = newdata;
         this.capacity = capacity;
}

 

此时查找等需要比较的操作 需要 t类型去重写 object基类的equals()规则

public bool iscontain(int value)
{
        var iscontain = false;
        for (int i = 0; i < this.size; i++)
        {
            if (this.data[i].equals(value))
                iscontain = true;
        }
        return iscontain;
}

 

此时我们来看我们的算法的复杂度

1.增加 o(1) 这个没什么好说 ，但如果已满，触发了扩容复杂度为 o(n)。

2.插入  插入的话，如果插入的index为size ,此时的复杂度为 o(1) ,但最坏情况下为插入到第一个,此时的复杂度为 o(n),平均复杂度为(n/2),还是 o(n)

3.删除 删除也是一样。也会有最坏情况,复杂度为 o(n).

4.查找 o(1) 

 

但是有个问题,比如,此时的容量已满我们增加了一个，触发扩容，此时又删除最后一个，此时的数组的size为容量的一半，又要缩容器。都是o(1)的操作，此时的复杂度就会是o(n),(复杂度震荡),此时我们可以改一下。当size小于容器的1/4，才触发缩容器。避免了这种又增又删o(1)一次的操作带来的复杂度震荡。

if (this.size <= this.capacity/4)
               this.narrowcapacity(this.capacity / 2);

如下我的项目的 github地址  有需要的同学可以自取哦 地址: https://github.com/guanzhengxin/datastruct

这样我们就简单实现了一个基本的数组结构，下期我们来学习一下栈的结构和实现。