数据结构与算法（C#实现）001--线性表

一、定义

  线性表(Linear List)是一种由同类型数据元素构成有序序列的线性结构

• 表中元素个数称为线性表的长度
• 线性表没有元素时，称为空表
• 表起始位置称表头，表结束位置称表尾

二、抽象数据类型描述

• 类型名称：线性表（$List$）
• 数据对象集：线性表是 $n(≥0)$个元素构成的有序序列 $(a_1, a_2, \cdot\cdot\cdot,a_n)$
• 操作集：线性表 $L \in List$，整数 $i$ 表示位置，元素 $X \in ElementType$
• 线性表主要操作包括：
  1. int GetLength(); // 求线性表的长度
  2. void Clear(); // 清空线性表
  3. bool IsEmpty(); // 判断线性表是否为空
  4. void Append(T item); // 在线性表末尾附加元素
  5. void Insert(T item, int i); // 将元素插入到线性表中第i个元素之前
  6. T Delete(int i); // 删除线性表中第i个元素
  7. T GetElem(int i); // 获取线性表中第i个元素的值
  8. int Locate(T value); // 获取指定值在线性表中的排序位置

接口代码实现（T为泛型）:

public interface IListDS<T>
{
    /// <summary>
    /// 求长度
    /// </summary>
    /// <returns></returns>
    int GetLength();

    /// <summary>
    /// 清空
    /// </summary>
    void Clear();

    /// <summary>
    /// 判断线性表是否为空
    /// </summary>
    /// <returns></returns>
    bool IsEmpty();

    /// <summary>
    /// 附加
    /// </summary>
    /// <param name="item"></param>
    void Append(T item);

    /// <summary>
    /// 插入
    /// </summary>
    /// <param name="item"></param>
    /// <param name="i">线性表的第i个数据元素</param>
    void Insert(T item, int i);

    /// <summary>
    /// 删除
    /// </summary>
    /// <param name="i">线性表的第i个数据元素</param>
    /// <returns></returns>
    T Delete(int i);

    /// <summary>
    /// 取表元
    /// </summary>
    /// <param name="i">线性表的第i个数据元素</param>
    /// <returns></returns>
    T GetElem(int i);

    /// <summary>
    /// 按值查找
    /// </summary>
    /// <param name="value"></param>
    /// <returns>元素在线性表中的排序，从1开始</returns>
    int Locate(T value);
}

三、线性表的顺序存储实现--顺序表

  利用数组的连续存储空间顺序存放线性表的各元素，数组初始化时需要有长度限制，所以会有Maxsize属性指定数组的最大容量，因此顺序表中需要有<font color=red>判断表是否满</font>的操作。

代码实现:

/// <summary>
/// 顺序表
/// </summary>
/// <typeparam name="T"></typeparam>
public class SequenceList<T> : IListDS<T>
{
    // 数组，用于存储顺序表中的数据元素
    private T[] data;

    // 索引器
    public T this[int index]
    {
        get => data[index];
        set => data[index] = value;
    }

    // 顺序表最后一个元素的位置属性
    public int Last { get; set; }

    // 顺序表的容量属性
    public int Maxsize { get; set; }

    // 构造器
    public SequenceList(int size)
    {
        data = new T[size];
        Maxsize = size;
        Last = -1;
    }

    /// <summary>
    /// 求顺序表的长度
    /// </summary>
    /// <returns></returns>
    public int GetLength()
    {
        return Last + 1;
    }

    /// <summary>
    /// 清空顺序表
    /// </summary>
    public void Clear()
    {
        Last = -1;
    }

    /// <summary>
    /// 判断顺序表是否为空
    /// </summary>
    /// <returns></returns>
    public bool IsEmpty()
    {
        return Last == -1;
    }

    /// <summary>
    /// 判断顺序表是否为满
    /// </summary>
    /// <returns></returns>
    public bool IsFull()
    {
        return Last == Maxsize - 1;
    }

    /// <summary>
    /// 在顺序表的末尾添加新元素==附加
    /// </summary>
    /// <param name="item"></param>
    public void Append(T item)
    {
        if (IsFull())
        {
            Console.WriteLine("顺序表已满，无法附加元素");
            return;
        }
        data[++Last] = item;
    }

    /// <summary>
    /// 在顺序表的第i个数据元素的位置之前插入一个数据元素==插入
    /// </summary>
    /// <param name="item"></param>
    /// <param name="i">顺序表的第i个数据元素</param>
    public void Insert(T item, int i)
    {
        if (IsFull())
        {
            Console.WriteLine("顺序表已满，无法附加元素");
            return;
        }
        if (i < 1 || i > Last + 2)
        {
            Console.WriteLine("要插入的位置不存在，无法附加元素");
            return;
        }

        // 如果i=last+2，会跳出循环，相当于附加元素
        // 从后往前向后移动一位
        for (int j = Last; j >= i - 1; j--)
        {
            data[j + 1] = data[j];
        }
        data[i - 1] = item;
        Last++;
    }

    /// <summary>
    /// 删除顺序表的第i个数据元素，并抛出删除的元素值==删除
    /// </summary>
    /// <param name="i">顺序表的第i个数据元素</param>
    /// <returns></returns>
    public T Delete(int i)
    {
        T tmp = default(T);
        if (IsEmpty())
        {
            Console.WriteLine("顺序表已空，无法删除元素");
        }
        else if (i < 1 || i > Last + 1)
        {
            Console.WriteLine("要删除的位置不存在，无法删除元素");
        }
        else
        {
            tmp = data[i - 1];
            // 从前往后向前移动一位
            for (int j = i; j <= Last; j++)
            {
                data[i - 1] = data[i];
            }
            Last--;
        }
        return tmp;
    }

    /// <summary>
    /// 获取顺序表的第i个数据元素==取表元
    /// </summary>
    /// <param name="i">顺序表的第i个数据元素</param>
    /// <returns></returns>
    public T GetElem(int i)
    {
        T tmp = default(T);
        if (IsEmpty())
        {
            Console.WriteLine("顺序表已空，无法获取元素");
        }
        else if (i < 1 || i > Last + 1)
        {
            Console.WriteLine("要删除的位置不存在，无法获取元素");
        }
        else
        {
            tmp = data[i - 1];
        }
        return tmp;
    }

    /// <summary>
    /// 在顺序表中查找值为value的数据元素的位置==按值查找
    /// </summary>
    /// <param name="value"></param>
    /// <returns>元素在顺序表中的排序，从1开始</returns>
    public int Locate(T value)
    {
        if (IsEmpty())
        {
            Console.WriteLine("顺序表已空，没有值可供查找");
            return 0;
        }

        int i;
        for (i = 0; i <= Last; i++)
        {
            if (value.Equals(data[i]))
            {
                break;
            }
        }

        if (i > Last)
        {
            return 0;
        }
        return i+1;
    }
}

四、线性表的链式存储实现--单链表

链式存储不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系。

代码实现：

/// <summary>
/// 单链表结点
/// </summary>
/// <typeparam name="T"></typeparam>
public class Node<T>
{
    public T Data { get; set; }       //数据域
    public Node<T> Next { get; set; }  //引用域（指针域）

    // 构造器
    public Node()
    {
        Data = default(T);
        Next = null;
    }

    public Node(T value)
    {
        Data = value;
        Next = null;
    }

    public Node(Node<T> next)
    {
        Data = default(T);
        Next = next;
    }

    public Node(T value, Node<T> next)
    {
        Data = value;
        Next = next;
    }
}

/// <summary>
/// 不带头结点的单链表
/// </summary>
/// <typeparam name="T"></typeparam>
public class LinkList<T> : IListDS<T>
{
    public Node<T> Head { get; set; }    // 头引用

    // 构造器
    public LinkList()
    {
        Head = null;
    }

    /// <summary>
    /// 求单链表长度
    /// </summary>
    /// <returns></returns>
    public int GetLength()
    {
        Node<T> p = Head;
        int len = 0;
        while (p != null)
        {
            len++;
            p = p.Next;
        }
        return len;
    }

    /// <summary>
    /// 清空
    /// </summary>
    public void Clear()
    {
        Head = null;
    }

    /// <summary>
    /// 判断单链表是否为空
    /// </summary>
    /// <returns></returns>
    public bool IsEmpty()
    {
        return Head == null;
    }

    /// <summary>
    /// 附加
    /// </summary>
    /// <param name="item"></param>
    public void Append(T item)
    {
        Node<T> q = new Node<T>(item);
        Node<T> p = Head;
        if (p == null)
        {
            Head = q;
            return;
        }
        while (p.Next != null)
        {
            p = p.Next;
        }
        p.Next = q;
    }

    /// <summary>
    /// 在单链表的第i个结点的位置前插入一个值为item的结点
    /// </summary>
    /// <param name="item"></param>
    /// <param name="i">单链表的第i个结点的位置</param>
    public void Insert(T item, int i)
    {
        if (IsEmpty() || i < 1)
        {
            Console.WriteLine("链表为空或要插入的位置不存在");
            return;
        }
        if (i == 1)
        {
            Node<T> q = new Node<T>(item);
            q.Next = Head;
            Head = q;
            return;
        }
        Node<T> curr = Head;          // 当前结点
        Node<T> pre = new Node<T>();   // 前驱结点
        int k = 1;
        while (curr.Next != null && k < i)
        {
            k++;
            pre = curr;
            curr = curr.Next;
        }
        if (k == i)
        {
            Node<T> q = new Node<T>(item);
            q.Next = curr;
            pre.Next = q;
            return;
        }
        Console.WriteLine($"当前链表不存在第{i}个结点");
    }

    /// <summary>
    /// 在单链表的第i个结点的位置后插入一个值为item的结点
    /// </summary>
    /// <param name="item"></param>
    /// <param name="i">单链表的第i个结点的位置</param>
    public void InsertPost(T item, int i)
    {
        if (IsEmpty() || i < 1)
        {
            Console.WriteLine("链表为空或要插入的位置不存在");
            return;
        }
        Node<T> p = Head;
        int k = 1;
        while (p.Next != null && k < i)
        {
            k++;
            p = p.Next;
        }
        if (k == i)
        {
            Node<T> q = new Node<T>(item);
            q.Next = p.Next;
            p.Next = q;
            return;
        }
        Console.WriteLine($"当前链表不存在第{i}个结点");
    }

    /// <summary>
    /// 删除
    /// </summary>
    /// <param name="i">单链表的第i个结点的位置</param>
    /// <returns></returns>
    public T Delete(int i)
    {
        T result = default(T);
        if (IsEmpty() || i < 1)
        {
            Console.WriteLine("链表为空或要删除的结点不存在");
            return result;
        }
        if (i == 1)
        {
            result = Head.Data;
            Head = Head.Next;
            return result;
        }
        Node<T> curr = Head;
        Node<T> pre = new Node<T>();
        int k = 1;
        while (curr.Next != null && k < i)
        {
            k++;
            pre = curr;
            curr = curr.Next;
        }
        if (k == i)
        {
            result = curr.Data;
            pre.Next = curr.Next;
        }
        else
        {
            Console.WriteLine($"当前链表不存在第{i}个结点");
        }
        return result;
    }

    /// <summary>
    /// 取表元
    /// </summary>
    /// <param name="i">单链表的第i个结点的位置</param>
    /// <returns></returns>
    public T GetElem(int i)
    {
        T result = default(T);
        if (IsEmpty() || i < 1)
        {
            Console.WriteLine("链表为空或要删除的结点不存在");
            return result;
        }

        Node<T> p = Head;
        int k = 1;
        while (p.Next != null && k < i)
        {
            k++;
            p = p.Next;
        }
        if (k == i)
        {
            result = p.Data;
        }
        else
        {
            Console.WriteLine($"当前链表不存在第{i}个结点");
        }
        return result;
    }

    /// <summary>
    /// 按值查找
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    public int Locate(T value)
    {
        if (IsEmpty())
        {
            Console.WriteLine("链表为空");
            return 0;
        }
        Node<T> p = Head;
        int k = 1;
        while (p != null)
        {
            if (value.Equals(p.Data))
            {
                return k;
            }
            p = p.Next;
            k++;
        }
        Console.WriteLine($"当前链表不存在值为{value}的结点");
        return 0;
    }
}