【数据结构】二次封装自己的数组（三）升级为动态数组

MaybeHC

发布于 2024-04-23 19:02:06

690

发布于 2024-04-23 19:02:06

我们之前在我们的数组内部封装了静态的数组，如果当我们的数组增加，超过了我们数组所设置的容量时，程序会出现错误。这里我们修改代码，当数组数据超过数组容量时进行扩容

修改添加方法

  //在index位置插入一个新元素e
        public void add(int index, E e)
        {
            if (size == data.Length)
                //扩容两倍
                resize(2 * data.Length);
            if (index < 0 || index > size)
                throw new ArgumentException("Add failed.Require index < 0 || index > size");
            for (int i = size - 1; i >= index; i--)
                data[i + 1] = data[i];
            data[index] = e;
            size++;
        }

添加扩容数组的方法

在数组数据超过容量时，我们将数组扩容2倍。创建一个新数组，容量为原来容量的两倍，将原数据拷贝进新数组，并改变data的引用。

 //扩容数组
        private void resize(int newCapacity)
        {
            E[] newData = new E[newCapacity];
            for(int i = 0; i < size; i++)
            {
                newData[i] = data[i];
            }
            data = newData;
        }

测试

我们来测试一下数组添加内容时的情况

 static void Main(string[] args)
        {
            Array<int> arr = new DataStructure.Array<int>(8);
            for (int i = 0; i < 8; i++)
            {
                arr.addLast(i);
            }
            Console.WriteLine(arr);
            arr.addLast(111);
            Console.WriteLine(arr.ToString());
            arr.addLast(222);
            Console.WriteLine(arr.ToString());
            Console.ReadKey();
        }

我们在初始时设置数组的容量为8，并为其添加8个数据。我们再次添加111，发现数组扩容了两倍，capacity=16，再次添加222，数组数据增加1，容量不变。符合我们设计的预期。

如果容量比较大，我们存的数据使用的空间少，将会造成资源的浪费，我们这时设置，当数组中数据的量小于容量的1/2时，将数组容量缩减一半

修改删除方法

 //删除指定索引位置的元素
        public E remove(int index)
        {
            if (index < 0 || index >= size)
                throw new ArgumentException("Get failed.Index is illegal");
            E ret = data[index];
            for (int i = index + 1; i < size; i++)
            {
                data[i - 1] = data[i];
            }
            size--;
            data[size] = default(E);
            //元素减少到容量的1/2时，数组容量减少一半
            if (size == data.Length / 2)
                resize(data.Length / 2);
            return ret;
        }

测试

static void Main(string[] args)
        {
            Array<int> arr = new DataStructure.Array<int>(15);
            for (int i = 0; i < 8; i++)
            {
                arr.addLast(i);
            }
            Console.WriteLine(arr);
            arr.removeLast();
            //arr.addLast(111);
            Console.WriteLine(arr.ToString());
            //arr.addLast(222);
            arr.removeLast();
            Console.WriteLine(arr.ToString());
            Console.ReadKey();
        }