C#数据结构与算法—动态数组

数据结构主要研究的是数据怎么在计算机中组织和存储，是的我们可以高效的获取数据或修改数据。
算法可以节约更多的资源，让我们完成一些看起来本不该完成的任务，可将程序的运行速度提高数百万倍。

数组的各种方法

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStructure
{
    class Array1
    {
        private int[] data;//使用私有的是为了防止外部的成员访问数组，对其造成破坏
        private int N;//动态数组实际存在的变量数
        public Array1(int capacity)//方法 
        {
            data = new int[capacity];
            N = 0;
        }

        public Array1() : this(10) { }//等价于下方的方法
        //public Array1()
        //{
        //    data = new int[10];
        //    N = 0;
        //}
        public int Capacity//数组容量
        {
            get { return data.Length; }
        }
        public int Count//数组真实存储元素的个数
        {
            get { return N; }
        }
        public bool IsEmpty
        {
            get { return N == 0; }//=0返回true
        }

        //往数组添加元素 
        public void Add(int index, int e)//在数组index位置（此位置已有元素）添加元素
        {
            if(index<0||index>N)
            {
            throw new ArgumentException("数组索引越界");
            }
            if(N==data.Length)
            {
                ResetCapacity(2*data.Length);
            }

            for (int i = N - 1; i >= index; i--)//从index到N-1的元素都向后移动
            {
                data[i + 1] = data[i];
            }
            data[index] = e;
            N++;
        }
        public void AddLast(int e)//在数组的末尾添加元素

        {
            Add(N, e);
        }
        public void AddFirst(int e)//在数组首位添加元素
        {
            Add(0, e);
        }
        //查询数组元素方法
        public int Get(int index)
        {
            if(index<0||index>=N)
            {
                throw new ArgumentException("数组索引越界");
            }
            return data[index];
        }

        public int GetFirst()
        {
            return Get(0);
        }
        
        public int GetLast()
        {
            return Get(N - 1);
        }
        
        //数组中是否包含某元素
        public bool Contains(int e)
        {
            for(int i=0;i<N;i++)
            {
                if(data[i]==e)
                {
                    return true;
                }
            }
            return false;
        }
        //查看数组元素存在哪个位置
        public int IndexOf(int e)
        {
            for (int i = 0; i < N; i++)
            {
                if (data[i] == e)
                {
                    return i;
                }
            }
            return -1;
        }
        //删除数组里某个位置的元素
        public int RemoveAt(int index)
        {
            if(index<0||index>=N)
            {
                throw new ArgumentException("索引超出数组界限");
            }
            int del = data[index];
            for(int i=index+1;i<=N-1;i++)
            {
                data[i - 1] = data[i];
            }
            N--;
            data[N] = default(int);
            if (N == data.Length / 4)
                ResetCapacity(data.Length / 2);  
            return del;
        }

        //简便方法
        public int RemoveFirst()
        {
            return RemoveAt(0);
        }
        public int RemoveLast()
        {
            return RemoveAt(N - 1);
        }
        public void Remove(int e)
        {
            int index = IndexOf(e);
            if(index!=-1)
            {
                RemoveAt(index);
            }

        }

        //调整数组容量的方法
        private void ResetCapacity(int newCapacity)
        {
            int[] newData = new int[newCapacity];
            for(int i=0;i<N;i++)
            {
                newData[i] = data[i];
            }
            data = newData;
        }

        //数组修改方法
        public void Set(int index,int newE)
        {
            try
            {
                data[index] = newE;
            }
            catch(Exception ex)
            {
                Console.WriteLine(ex.ToString());
            }
        }
        
        
        //重写
        public override string ToString()
        {
            StringBuilder res = new StringBuilder();
            res.Append(string.Format("Array1:count={0} capacity={1}\n", N, data.Length));
            res.Append("[");
            for(int i=0;i<N;i++)
            {
                res.Append(data[i]);
                if(i!=N-1)
                {
                    res.Append(", ");
                }
            }
            res.Append("]");
            return res.ToString();
        }
    }
    
}

在主函数里测试各个方法

		using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStructure
{
    class Program
    {
        static void Main(string[] args)
        {
            Array1 a = new Array1(20);
            for(int i=0;i<10;i++)//需将Tostring方法重写
            {
                a.AddLast(i);
            }
            Console.WriteLine(a);

            a.AddFirst(66);
            Console.WriteLine(a);

            a.Add(2, 77);
            Console.WriteLine(a);

            Console.WriteLine(a.GetFirst());
            Console.WriteLine(a.GetLast());
            Console.WriteLine(a.Get(1));
            a.Set(1, 1000);
            Console.WriteLine(a);

            //[66, 1000, 77, 1, 2, 3, 4, 5, 6, 7, 8, 9]

            a.RemoveAt(2);
            a.RemoveFirst();
            a.RemoveLast();
            a.Remove(4);
            Console.WriteLine(a);
            Console.ReadKey();
        }
    }
}

结果：

Array1:count=10 capacity=20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array1:count=11 capacity=20
[66, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array1:count=12 capacity=20
[66, 0, 77, 1, 2, 3, 4, 5, 6, 7, 8, 9]
66
9
0
Array1:count=12 capacity=20
[66, 1000, 77, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array1:count=8 capacity=20
[1000, 1, 2, 3, 5, 6, 7, 8]

数组扩容和缩容

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStructure
{
    class Program
    {
        static void Main(string[] args)
        {
            Array1 a = new Array1(10);
            for (int i = 0; i < 10; i++)//需将Tostring方法重写
            {
                a.AddLast(i);
            }
            Console.WriteLine(a);
            a.AddLast(55);
            Console.WriteLine(a);
            for(int i=0;i<6;i++)
            {
                a.RemoveLast();
                Console.WriteLine(a);
            }
            Console.Read();
        }
    }
}

结果：

Array1:count=10 capacity=10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array1:count=11 capacity=20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 55]
Array1:count=10 capacity=20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array1:count=9 capacity=20
[0, 1, 2, 3, 4, 5, 6, 7, 8]
Array1:count=8 capacity=20
[0, 1, 2, 3, 4, 5, 6, 7]
Array1:count=7 capacity=20
[0, 1, 2, 3, 4, 5, 6]
Array1:count=6 capacity=20
[0, 1, 2, 3, 4, 5]
Array1:count=5 capacity=10
[0, 1, 2, 3, 4]

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
using System.Diagnostics;

namespace DataStructure
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 10000000;
            Stopwatch t1 = new Stopwatch();
            Stopwatch t2= new Stopwatch();
            Stopwatch t3 = new Stopwatch();
            Stopwatch t4 = new Stopwatch();
            Console.WriteLine("测试值类型int");
            t1.Start();
            List<int> l = new List<int>();
            for(int i=0;i<n;i++)
            {
                l.Add(i);//不发生装箱
                int x = l[i];//不发生拆箱
            }
            t1.Stop();
            Console.WriteLine("List'time:" + t1.ElapsedMilliseconds + "ms");

            t2.Start();
            ArrayList a = new ArrayList();
            for(int i=0;i<n;i++)
            {
                a.Add(i);//发生装箱
                int x =(int) a[i];//发生拆箱
            }
            t2.Stop();
            Console.WriteLine("ArrayList'time:" + t2.ElapsedMilliseconds + "ms");


            Console.WriteLine("测试引用类型对象string");
            t3.Start();
            List<string> l2 = new List<string>();
            for (int i = 0; i < n; i++)
            {
                l2.Add("x");//不发生装箱
                string x = l2[i];//不发生拆箱
            }
            t3.Stop();
            Console.WriteLine("List'time:" + t3.ElapsedMilliseconds + "ms");

            t4.Start();
            ArrayList a2 = new ArrayList();
            for (int i = 0; i < n; i++)
            {
                a2.Add("x");//不发生装箱，ArrayList是object类型其与string都是引用类型所以不需要
                string x = (string)a2[i];//不发生拆箱
            }
            t4.Stop();
            Console.WriteLine("ArrayList'time:" + t4.ElapsedMilliseconds + "ms");
            Console.Read();
            
        }
    }
}

结果：

测试值类型int
List'time:129ms
ArrayList'time:1706ms
测试引用类型对象string
List'time:243ms
ArrayList'time:409ms

总结

• List 必须指定一个类型，且只能存储这个类型的元素

• ArrayList 采用的是object类型进行元素的存储，什么类型的元素都可以存储进去

• 想要使数组存储任意类型的元素有两种方法：

  1.将int类型转换成object类型的数组进行元素的存储 ArrayList
  2.使用泛型 List

泛型方法

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStructure
{
    class Array1<E>
    {
        private E[] data;//使用私有的是为了防止外部的成员访问数组，对其造成破坏
        private int N;//动态数组实际存在的变量数
        public Array1(int capacity)//方法 
        {
            data = new E[capacity];
            N = 0;
        }

        public Array1() : this(10) { }//等价于下方的方法
        //public Array1()
        //{
        //    data = new int[10];
        //    N = 0;
        //}
        public int Capacity//数组容量
        {
            get { return data.Length; }
        }
        public int Count//数组真实存储元素的个数
        {
            get { return N; }
        }
        public bool IsEmpty
        {
            get { return N == 0; }//=0返回true
        }

        //往数组添加元素 
        public void Add(int index, E e)//在数组index位置（此位置已有元素）添加元素
        {
            if(index<0||index>N)
            {
            throw new ArgumentException("数组索引越界");
            }
            if(N==data.Length)
            {
                ResetCapacity(2*data.Length);
            }

            for (int i = N - 1; i >= index; i--)//从index到N-1的元素都向后移动
            {
                data[i + 1] = data[i];
            }
            data[index] = e;
            N++;
        }
        public void AddLast(E e)//在数组的末尾添加元素

        {
            Add(N, e);
        }
        public void AddFirst(E e)//在数组首位添加元素
        {
            Add(0, e);
        }
        //查询数组元素方法
        public E Get(int index)
        {
            if(index<0||index>=N)
            {
                throw new ArgumentException("数组索引越界");
            }
            return data[index];
        }

        public E GetFirst()
        {
            return Get(0);
        }
        
        public E GetLast()
        {
            return Get(N - 1);
        }
        
        //数组中是否包含某元素
        public bool Contains(E e)
        {
            for(int i=0;i<N;i++)
            {
                if(data[i].Equals(e))
                {
                    return true;
                }
            }
            return false;
        }
        //查看数组元素存在哪个位置
        public int IndexOf(E e)
        {
            for (int i = 0; i < N; i++)
            {
                if (data[i] .Equals( e))
                {
                    return i;
                }
            }
            return -1;
        }
        //删除数组里某个位置的元素
        public E RemoveAt(int index)
        {
            if(index<0||index>=N)
            {
                throw new ArgumentException("索引超出数组界限");
            }
             E del = data[index];
            for(int i=index+1;i<=N-1;i++)
            {
                data[i - 1] = data[i];
            }
            N--;
            data[N] = default(E);//如果是引用类型赋值为空，如果为值类型则赋值为0
            if (N == data.Length / 4)
                ResetCapacity(data.Length / 2);  
            return del;
        }

        //简便方法
        public E RemoveFirst()
        {
            return RemoveAt(0);
        }
        public E RemoveLast()
        {
            return RemoveAt(N - 1);
        }
        public void Remove(E e)
        {
            int index = IndexOf(e);
            if(index!=-1)
            {
                RemoveAt(index);
            }

        }

        //调整数组容量的方法
        private void ResetCapacity(int newCapacity)
        {
            E[] newData = new E[newCapacity];
            for(int i=0;i<N;i++)
            {
                newData[i] = data[i];
            }
            data = newData;
        }

        //数组修改方法
        public void Set(int index,E newE)
        {
            try
            {
                data[index] = newE;
            }
            catch(Exception ex)
            {
                Console.WriteLine(ex.ToString());
            }
        }
        
        
        //重写
        public override string ToString()
        {
            StringBuilder res = new StringBuilder();
            res.Append(string.Format("Array1:count={0} capacity={1}\n", N, data.Length));
            res.Append("[");
            for(int i=0;i<N;i++)
            {
                res.Append(data[i]);
                if(i!=N-1)
                {
                    res.Append(", ");
                }
            }
            res.Append("]");
            return res.ToString();
        }
    }
    
}

主函数中泛型测试

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
using System.Diagnostics;

namespace DataStructure
{
    class Program
    {
        static void Main(string[] args)
        {
            //！！测试泛型数组 
            int[] n = { 1, 2, 3, 4, 5, 6, 7 };
            Array1<int> a = new Array1<int>();
            for(int i=0;i<n.Length;i++)
            {
                a.AddLast(n[i]);
            }
            Console.WriteLine(a);

            string[] s = { "a", "b", "c", "d" };
            Array1<string> a2 = new Array1<string>();
            for(int i=0;i<s.Length;i++)
            {
                a2.AddLast(s[i]);
            }
            Console.WriteLine(a2);

            Console.Read();
        }
    }
}

结果：

Array1:count=7 capacity=10
[1, 2, 3, 4, 5, 6, 7]
Array1:count=4 capacity=10
[a, b, c, d]