C#数据结构与算法揭秘二 线性结构

C#数据结构与算法揭秘二 线性结构

线性结构是指数据元素之间一对一的关系，即数据元素之间存在一个前驱和一个后继。一般有两种基本形式：线性表和栈、队列。

• 线性表

线性表是由同类型数据元素构成有序序列的线性结构，常被用于实现基于数组的数据结构，如向量、矩阵等。

线性表可以分为顺序表和链表两种。

顺序表（Sequence List）：是把线性表的元素按照顺序存储在一段连续的内存空间中，又叫连续存储结构。

示例说明：以下是使用C#语言，对线性表的顺序存储结构操作的示例代码。

class SeqList<T>
{
    private T[] data;
    private int size;

    public SeqList(int capacity)
    {
        data = new T[capacity];
        size = 0;
    }

    //查找元素
    public int Find(T item)
    {
        for (int i = 0; i < size; i++)
        {
            if (data[i].Equals(item))
            {
                return i;
            }
        }
        return -1;
    }

    //添加元素
    public void Add(T item)
    {
        if (size==data.Length) //数组满了，需要扩容
        {
            Resize(2 * data.Length);
        }
        data[size] = item;
        size++;
    }

    //删除元素
    public void Remove(T item)
    {
        int index = Find(item);
        if (index==-1)
        {
            return;
        }
        for (int i = index+1; i < size; i++)
        {
            data[i - 1] = data[i];
        }
        size--;
        if (size==data.Length/4 && data.Length/2!=0) //当元素个数少于数组容量的一半，缩小数组
        {
            Resize(data.Length / 2);
        }
    }

    //扩容方法
    private void Resize(int newCapacity)
    {
        T[] newData = new T[newCapacity];
        for (int i = 0; i < size; i++)
        {
            newData[i] = data[i];
        }
        data = newData;
    }
}

• 栈和队列

栈（Stack）：一种线性结构，先进后出（Last In First Out）。

示例说明：以下是使用C#语言，对栈的操作的示例代码。

class Stack<T>
{
    private T[] data;
    private int size;

    public Stack()
    {
        data = new T[2];
        size = 0;
    }

    //压栈
    public void Push(T item)
    {
        if (size==data.Length)
        {
            Resize(2 * data.Length);
        }
        data[size] = item;
        size++;
    }

    //出栈
    public T Pop()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("Stack is empty");
        }
        T item = data[size - 1];
        size--;
        if (size==data.Length/4 && data.Length/2!=0)
        {
            Resize(data.Length / 2);
        }
        return item;
    }

    //获取栈顶元素
    public T Peek()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("Stack is empty");
        }
        return data[size - 1];
    }

    //判断栈是否为空
    public bool IsEmpty()
    {
        return size == 0;
    }

    //栈的数组大小调整
    private void Resize(int newCapacity)
    {
        T[] newData = new T[newCapacity];
        for (int i = 0; i < size; i++)
        {
            newData[i] = data[i];
        }
        data = newData;
    }

}

队列（Queue）：一种线性结构，先进先出（First In First Out）。

示例说明：以下是使用C#语言，对队列的操作的示例代码。

class Queue<T>
{
    private T[] data;
    private int front;
    private int tail;
    private int size;

    public Queue(int capacity)
    {
        data = new T[capacity];
        front = 0;
        tail = 0;
        size = 0;
    }

    //入队
    public void Enqueue(T item)
    {
        if (size == data.Length) //队列满了，需要扩容
        {
            Resize(2 * data.Length);
        }
        data[tail] = item;
        tail = (tail + 1) % data.Length; //tail指针绕一圈回到头部
        size++;
    }

    //出队
    public T Dequeue()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("Queue is empty");
        }
        T item = data[front];
        front = (front + 1) % data.Length; //front指针绕一圈回到头部
        size--;
        if (size == data.Length / 4 && data.Length / 2 != 0) //当元素个数少于数组容量的一半，缩小数组
        {
            Resize(data.Length / 2);
        }
        return item;
    }

    //获取队首元素
    public T GetFront()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("Queue is empty");
        }
        return data[front];
    }

    //获取队列大小
    public int GetSize()
    {
        return size;
    }

    //判断队列是否为空
    public bool IsEmpty()
    {
        return front == tail;
    }

    //队列的数组大小调整
    private void Resize(int newCapacity)
    {
        T[] newData = new T[newCapacity];
        for (int i = 0; i < size; i++)
        {
            newData[i] = data[(front + i) % data.Length];
        }
        data = newData;
        front = 0;
        tail = size;
    }
}

以上是对线性结构的一些常见操作和代码实现，同时在实际的开发中，我们根据具体的需求，将会针对性的选择不同的数据结构来完成我们的任务和目标。