C#数据结构之顺序表(SeqList)实例详解

顺序表(SeqList)概述

顺序表(SeqList)是一种线性表存储结构，它的特点是元素的存储位置是连续的。因为它的存储结构是数组，所以在访问和修改元素时，可以通过数组下标进行快速定位。顺序表在内存中的存储相对紧凑，因此查找和修改效率都很高，适用于大多数元素较少、但是需要频繁访问的场景。

实现顺序表(SeqList)

public class SeqList<T> : IList<T>
{
    private T[] items;
    private int count = 0;

    public int Count => count;

    public bool IsReadOnly => false;

    public T this[int index]
    {
        get
        {
            if (index < 0 || index >= count)
            {
                throw new ArgumentOutOfRangeException();
            }
            return items[index];
        }
        set
        {
            if (index < 0 || index >= count)
            {
                throw new ArgumentOutOfRangeException();
            }
            items[index] = value;
        }
    }

    public SeqList()
    {
        items = new T[4];
    }

    public SeqList(int capacity)
    {
        items = new T[capacity];
    }

    public void Add(T item)
    {
        if (count == items.Length)
        {
            Array.Resize(ref items, count * 2);
        }
        items[count++] = item;
    }

    public void Clear()
    {
        Array.Clear(items, 0, count);
        count = 0;
    }

    public bool Contains(T item)
    {
        for (int i = 0; i < count; i++)
        {
            if (Equals(items[i], item))
            {
                return true;
            }
        }
        return false;
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        if (array == null)
        {
            throw new ArgumentNullException(nameof(array));
        }
        if (arrayIndex < 0 || arrayIndex > array.Length)
        {
            throw new ArgumentOutOfRangeException(nameof(arrayIndex));
        }
        if (count > array.Length - arrayIndex)
        {
            throw new ArgumentException("The number of elements in the source ICollection<T> is greater than the available space from arrayIndex to the end of the destination array.");
        }
        for (int i = 0; i < count; i++)
        {
            array[arrayIndex + i] = items[i];
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        for (int i = 0; i < count; i++)
        {
            yield return items[i];
        }
    }

    public int IndexOf(T item)
    {
        for (int i = 0; i < count; i++)
        {
            if (Equals(items[i], item))
            {
                return i;
            }
        }
        return -1;
    }

    public void Insert(int index, T item)
    {
        if (index < 0 || index > count)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
        if (count == items.Length)
        {
            Array.Resize(ref items, count * 2);
        }
        Array.Copy(items, index, items, index + 1, count - index);
        items[index] = item;
        count++;
    }

    public bool Remove(T item)
    {
        int index = IndexOf(item);
        if (index < 0)
        {
            return false;
        }
        RemoveAt(index);
        return true;
    }

    public void RemoveAt(int index)
    {
        if (index < 0 || index >= count)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
        Array.Copy(items, index + 1, items, index, count - index - 1);
        items[--count] = default(T);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

在上述代码中，我们实现了IList<T>接口来定义了一个支持动态增加、删除、查找等操作的顺序表。其中包括以下几个方法：

• 构造函数：支持无参构造和指定初始容量的构造函数
• Add(T item)：在列表末尾添加一个元素
• Clear()：删除列表中所有元素
• Contains(T item)：判断列表中是否包含指定元素
• CopyTo(T[] array, int arrayIndex)：将列表中所有元素复制到目标数组中的指定位置
• GetEnumerator()：返回一个IEnumerator<T>对象，用于遍历列表中的元素
• IndexOf(T item)：返回指定元素的索引位置
• Insert(int index, T item)：在列表中指定位置插入一个元素
• Remove(T item)：删除列表中指定的元素
• RemoveAt(int index)：删除列表中指定位置的元素

示例演示

示例1：使用SeqList存储字符串

下面的示例演示用SeqList<string>存储一些字符串，并对其进行遍历、增加、删除等操作。

SeqList<string> list = new SeqList<string>();
list.Add("C#");
list.Add(".NET");
list.Add("Visual Studio");
foreach (string s in list)
{
    Console.WriteLine(s);
}
Console.WriteLine("list[1] = {0}", list[1]);
list.Insert(1, "ASP.NET");
Console.WriteLine("After Insert(1, \"ASP.NET\"):");
foreach (string s in list)
{
    Console.WriteLine(s);
}
list[2] = "WPF";
Console.WriteLine("After list[2] = \"WPF\":");
foreach (string s in list)
{
    Console.WriteLine(s);
}
list.Remove("ASP.NET");
Console.WriteLine("After Remove(\"ASP.NET\"):");
foreach (string s in list)
{
    Console.WriteLine(s);
}

输出结果如下：

C#
.NET
Visual Studio
list[1] = .NET
After Insert(1, "ASP.NET"):
C#
ASP.NET
.NET
Visual Studio
After list[2] = "WPF":
C#
ASP.NET
WPF
Visual Studio
After Remove("ASP.NET"):
C#
WPF
Visual Studio

示例2：使用SeqList存储自定义对象

下面的示例演示用SeqList<Person>存储一些自定义对象，并进行遍历、删除等操作。

public class Person
{
    public string Name { get; set; }
    public int Age { get; set; }

    public Person(string name, int age)
    {
        Name = name;
        Age = age;
    }
}

SeqList<Person> persons = new SeqList<Person>();
persons.Add(new Person("Tom", 18));
persons.Add(new Person("Jerry", 22));
persons.Add(new Person("Amy", 25));
persons.ForEach(p => Console.WriteLine(p.Name + ", " + p.Age));
persons.Remove(persons[1]);
Console.WriteLine("After Remove(\"Jerry\"):");
persons.ForEach(p => Console.WriteLine(p.Name + ", " + p.Age));

输出结果如下：

Tom, 18
Jerry, 22
Amy, 25
After Remove("Jerry"):
Tom, 18
Amy, 25