数据结构(二) - 旧游无处不堪寻

本篇，我们将会复习一下比较简单但是应用非常广泛的一种数据结构 —— 线性表。

线性表

线性表(List): 零个或多个数据元素的有限序列。

如果用数学语言定义如下:
若将线性表记为(a₁, …, a_i-1, a_i, a_i+1, …, a_n)，则表中 a_i-1 领先于 a_i，a_i 领先于 a_i+1，称 a_i-1 是 a_i 的直接前驱元素，a_i+1 是 a_i 的直接后继元素。当 i = 1, 2, …, n-1 时，a_i 有且仅有一个直接后继，当 i = 2, …, n 时，a_i 有且仅有一个直接前驱。

线性表元素的个数 n(n >= 0) 称为线性表的长度，当 n = 0 时，称为空表。

线性表的顺序存储结构

线性表的顺序存储结构指的是，用一段地址连续的存储单元依次存储线性表的数据元素。
一般用一维数组来实现顺序存储结构。

public class SqList<T>
{
    public const int Maxsize = 20;
    public T[] Data = new T[Maxsize];
    public int Length;

    /// <summary>
    /// 获取第 i 位的元素
    /// </summary>
    /// <param name="i"></param>
    /// <param name="e"></param>
    /// <returns></returns>
    public Status GetElement(int i, out T e)
    {
        if (Length == 0 || i < 0 || i >= Length)
        {
            e = default(T);
            return Status.Error;
        }

        e = Data[i];
        return Status.Ok;
    }

    /// <summary>
    /// 在第 i 位插入元素
    /// </summary>
    /// <param name="i"></param>
    /// <param name="e"></param>
    /// <returns></returns>
    public Status ListInsert(int i, T e)
    {
        if (Length == Maxsize)
        {
            return Status.Error;
        }

        if (i < 0 || i > Length)
        {
            return Status.Error;
        }

        if (i != Length)
        {
            for (var j = Length - 1; j >= i; j++)
            {
                Data[j + 1] = Data[j];
            }
        }
        Data[i] = e;
        Length++;

        return Status.Ok;
    }

    /// <summary>
    /// 删除第 i 位元素
    /// </summary>
    /// <param name="i"></param>
    /// <param name="e"></param>
    /// <returns></returns>
    public Status ListDelete(int i, out T e)
    {
        if (Length == 0)
        {
            e = default(T);
            return Status.Error;
        }

        if (i < 0 || i > Length - 1)
        {
            e = default(T);
            return Status.Error;
        }

        e = Data[i];
        for (var j = i; j < Length; j++)
        {
            Data[j] = Data[j + 1];
        }

        Length--;
        return Status.Ok;
    }
}

线性表顺序存储结构的优缺点

优点

可以快速存取表中任一位置元素

缺点

插入和删除操作需要移动大量元素
造成存储空间碎片化

线性表的链式存储结构

线性表的链式存储结构的特点是，可以用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。

在顺序存储结构中，每个数据元素只需要存储数据元素信息就可以了，但是在链式存储结构中，除了要存储数据元素信息外，还要存储他的后继元素的地址。

因此，为了表示每个数据元素 a_i 与其直接后继元素 a_i+1 之间的逻辑关系，对于数据元素 a_i 来说，除了存储本身信息之外，还需要存储一个指示其直接后继的信息。我们把存储数据元素信息的域称为数据域，把存储直接后继信息的域称为指针域(对于高级语言，我们可以把它理解成对象引用域)。把这两部分组成的数据元素称为节点(Node)。
n 个节点链接成一个链表，即线性表的链式存储结构。因为此链表每个节点只有一个指针域，因此称为单链表。

我们把第一个节点的指针域称为头指针。为了方便操作链表，会在单链表的第一个节点前设置一个节点，称为头节点。头节点的数据域不存储任何信息。
注意: 如果设置了头节点，那么头节点的指针域存储的就是头指针。

单链表

public class Node<T>
{
    public T Element;
    public Node<T> NextNode;

    public Node(T t)
    {
        Element = t;
    }
}

public class LinkList<T>
{
    //头节点(数据域无意义)
    public Node<T> HeadNode = new Node<T>(default(T));

    public Status GetElement(int i, out Node<T> node)
    {
        var j = 0;
        var temp = HeadNode;
        while (temp != null && j < i + 1)
        {
            temp = temp.NextNode;
            j++;
        }

        node = temp;
        return temp == null ? Status.Error : Status.Ok;
    }
    
    public Status ListInsert(int i, Node<T> node)
    {
        var status = GetElement(i - 1, out var prevNode);
        if (status != Status.Ok) return status;
        
        node.NextNode = prevNode.NextNode;
        prevNode.NextNode = node;
        
        return status;
    }

    public Status ListDelete(int i, out Node<T> node)
    {
        node = null;
        var status = GetElement(i - 1, out var prevNode);
        if (status != Status.Ok) return status;

        var current = prevNode.NextNode;
        prevNode.NextNode = current.NextNode;
        node = current;
        
        return status;
    }
}

循环链表

将单链表中尾节点的指针域指向头节点，使链表形成一个环，这种头尾相接的链表称为单循环链表，简称为循环链表。

循环链表和单链表的主要差异就是判断结束条件由指针域是否为空变为指针域是否是头节点。

双向链表

双向链表是在单向链表的每个节点中，再设置一个指向前驱节点的指针。所以在双向链表中存在两个指针域，一个指向直接前驱，一个指向直接后继。

public class DoubleLinkList<T>
{
    //头节点(数据域无意义)
    public Node<T> HeadNode = new Node<T>(default(T));

    public Status GetElement(int i, out Node<T> node)
    {
        var j = 0;
        var temp = HeadNode;
        while (temp != null && j < i + 1)
        {
            temp = temp.NextNode;
            j++;
        }

        node = temp;
        return temp == null ? Status.Error : Status.Ok;
    }

    public Status ListInsert(int i, Node<T> node)
    {
        var status = GetElement(i - 1, out var prevNode);
        if (status != Status.Ok) return status;

        node.PrevNode = prevNode;
        node.NextNode = prevNode.NextNode;
        prevNode.NextNode.PrevNode = node;
        prevNode.NextNode = node;

        return status;
    }

    public Status ListDelete(int i, out Node<T> node)
    {
        node = null;
        var status = GetElement(i - 1, out var prevNode);
        if (status != Status.Ok) return status;
        var current = prevNode.NextNode;
        current.NextNode.PrevNode = prevNode;
        prevNode.NextNode = current.NextNode;
        node = current;
        return status;
    }
}

在对链表进行操作时要记住一个原则: 后继指针很重要，在使用完之前不要赋新值。