欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构学习之线性表(二)

程序员文章站 2022-10-08 18:37:37
开篇:上次我们讲到,实现基本的数组的增删改查。现在我们来优化和改善,并且分析一下。 1. 首先我们定义的数组类型 不支持泛型。 2. 当容量不够使用的时候, 应该可以自动触发扩容操作。 我们来实现一下。我们使用泛型的T类型来代表。 此时 增删改查都应该操作泛型T变量 比如 add ,此时我们增加扩容 ......

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

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

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