数据结构与算法总结——线性表

数组和链表

数组

数组内存分配在连续的内存区域上。
数组需要预申请大小，可能造成内存浪费。
随机读取效率高，因为数组内存是连续的，知道每一个数据的地址，可以直接找到指定索引数据。
增删效率低，需要移动受影响的数据的位置。
由于内存区域连续，有CPU缓存命中高的优势，访问效率高。

链表

链表可分配在内存任意地方，不要求连续。
无需预指定大小，可自由调整数据量。
不支持随机读取，查询数据较慢，需要从头开始遍历查找。
增删速度快，只需要修改指针指向即可。
由于内存分散，往往前后节点数据不能同时处于缓存中，访问效率低。

时间复杂度

-	数组	链表
读取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

时间复杂度

动态数组

根据元素个数动态调整数组大小

实现

public class List<T>
{
    private T[] array;
    private int count;

    public int Count => count;

    public int Capacity => array.Length;

    private static T[] emptyArray = new T[0];

    public List()
    {
        array = emptyArray;
        count = 0;
    }

    public List(int capacity)
    {
        array = new T[capacity];
        count = 0;
    }

    public void Set(int index, T value)
    {
        if (count == Capacity)
            Resize((Capacity == 0) ? 4 : Capacity * 2);//容量从4起步，每次扩容翻倍

        array[index] = value;
        count++;
    }

    public T Get(int index)
    {
        if (index > count - 1)
        {
            throw new Exception("List out of range");
        }

        return array[index];
    }

    public void RemoveAt(int index)
    {
        for (int i = index; i < count ; i++)
        {
            array[i] = array[i + 1];        
        }

        count--;

        //若实际数据小于当前容量的1/4，容量缩小至原本的1/2
        if (count > 0 && count <= Capacity / 4)
        {
            Resize(Capacity / 2);
        }
    }

    //调整内部数组大小，新开辟数组，并把旧数组内容拷贝至新数组
    private void Resize(int count)
    {
        T[] _array = new T[count];
        Array.Copy(array, 0, _array, 0, this.count);
        array = _array;
    }
}

单链表

实现

public class ListNode<T> where T : IComparable<T>
{
    public ListNode<T> next;
    public T value;

    public ListNode(T value)
    {
        this.value = value;
    }

    public ListNode(ListNode<T> next, T value)
    {
        this.next = next;
        this.value = value;
    }
}

class LinkedList<T> where T : IComparable<T>
{
    private ListNode<T> head;
    private int count;
    public int Count => count;

    public ListNode<T> First => head.next;


    public LinkedList()
    {
        head = new ListNode<T>(default(T));
    }

    public void AddFirst(T value)
    {
        AddFirst(new ListNode<T>(value));
    }

    public void AddFirst(ListNode<T> node)
    {
        if (node == null)
            return;

        AddNode(head, node);
    }

    public void AddLast(T value)
    {
        AddLast(new ListNode<T>(value));
    }

    public void AddLast(ListNode<T> node)
    {
        if (node == null)
            return;

        ListNode<T> last = head;
        while (last.next != null)
        {
            last = last.next;
        }

        AddNode(last, node);
    }

    public void AddBefore(ListNode<T> node, T value)
    {
        if (node == null)
            return;

        AddBefore(node, new ListNode<T>(value));
    }

    public void AddBefore(ListNode<T> node, ListNode<T> value)
    {
        if (node == null || value == null)
            return;

        ListNode<T> pre = head;
        ListNode<T> addNode = First;
        while (addNode != null && addNode != node)
        {
            pre = pre.next;
            addNode = addNode.next;
        }

        if (addNode == null || addNode.value.CompareTo(node.value) != 0)
            return;

        AddNode(pre, value);
    }

    public void AddAfter(ListNode<T> node, T value)
    {
        if (node == null)
            return;

        AddAfter(node, new ListNode<T>(value));
    }

    public void AddAfter(ListNode<T> node, ListNode<T> value)
    {
        if (node == null || value == null)
            return;

        ListNode<T> addNode = First;
        while (addNode != null && addNode != node)
        {
            addNode = addNode.next;
        }

        if (addNode == null || addNode.value.CompareTo(node.value) != 0)
            return;

        AddNode(node, value);
    }

    public void DeleteNode(T value)
    {
        ListNode<T> pre = head;
        ListNode<T> deleteNode = First;
        while (deleteNode != null && deleteNode.value.CompareTo(value) != 0)
        {
            pre = pre.next;
            deleteNode = deleteNode.next;
        }

        if (deleteNode == null)
            return;

        DeleteNode(pre, deleteNode);
    }

    public void DeleteNode(ListNode<T> node)
    {
        if (node == null)
            return;

        ListNode<T> pre = head;
        ListNode<T> deleteNode = First;
        while (deleteNode != null && deleteNode != node)
        {
            pre = pre.next;
            deleteNode = deleteNode.next;
        }

        if (deleteNode == null)
            return;

        DeleteNode(pre, deleteNode);
    }

    private void DeleteNode(ListNode<T> pre, ListNode<T> deleteNode)
    {
        if (pre == null || deleteNode == null)
            return;

        ListNode<T> next = deleteNode.next;
        pre.next = next;
        count--;
    }

    public ListNode<T> Find(T value)
    {
        ListNode<T> node = First;
        while (node != null && node.value.CompareTo(value) != 0)
        {
            node = node.next;
        }

        return node;
    }

    private void AddNode(ListNode<T> pre, ListNode<T> node)
    {
        if (pre == null || node == null)
            return;

        ListNode<T> next = pre.next;
        pre.next = node;
        node.next = next;
        count++;
    }

    public void Clear()
    {
        head.next = null;
        count = 0;
    }
}

双链表

实现

public class ListNode<T> where T : IComparable<T>
{
    public ListNode<T> pre;
    public ListNode<T> next;
    public T value;

    public ListNode(T value)
    {
        this.value = value;
    }

    public ListNode(ListNode<T> pre, ListNode<T> next, T value)
    {
        this.pre = pre;
        this.next = next;
        this.value = value;
    }
}

class LinkedList<T> where T : IComparable<T>
{
    private ListNode<T> head;
    private ListNode<T> tail;
    private int count;
    public int Count => count;

    public ListNode<T> First
    {
        get
        {
            if (count > 0)
                return head.next;
            else
                return null;
        }
    }

    public ListNode<T> Last
    {
        get
        {
            if (count > 0)
                return tail.pre;
            else
                return null;
        }
    }


    public LinkedList()
    {
        head = new ListNode<T>(default(T));
        tail = new ListNode<T>(default(T));
        head.next = tail;
        tail.pre = head;
    }

    public void AddFirst(T value)
    {
        AddFirst(new ListNode<T>(value));
    }

    public void AddFirst(ListNode<T> node)
    {
        if (node == null)
            return;

        ListNode<T> next = First;
        head.next = node;
        node.next = next;
        if (next != null) next.pre = node;
        count++;
    }

    public void AddLast(T value)
    {
        AddLast(new ListNode<T>(value));
    }

    public void AddLast(ListNode<T> node)
    {
        if (node == null)
            return;

        node.pre = tail.pre;
        tail.pre.next = node;
        tail.pre = node;

        count++;
    }

    public void AddBefore(ListNode<T> node, T value)
    {
        if (node == null)
            return;

        AddBefore(node, new ListNode<T>(value));
    }

    public void AddBefore(ListNode<T> node, ListNode<T> value)
    {
        if (node == null || value == null)
            return;

        ListNode<T> pre = head;
        ListNode<T> addNode = First;
        while (addNode != null && addNode != node)
        {
            pre = pre.next;
            addNode = addNode.next;
        }

        if (addNode == null)
            return;

        pre.next = value;
        if (pre != head) value.pre = pre;
        value.next = node;
        node.pre = value;

        count++;
    }

    public void AddAfter(ListNode<T> node, T value)
    {
        if (node == null)
            return;

        AddAfter(node, new ListNode<T>(value));
    }

    public void AddAfter(ListNode<T> node, ListNode<T> value)
    {
        if (node == null || value == null)
            return;

        ListNode<T> addNode = First;
        while (addNode != null && addNode != node)
        {
            addNode = addNode.next;
        }

        if (addNode == null)
            return;

        ListNode<T> next = node.next;
        node.next = value;
        value.pre = node;
        value.next = next;
        if (next == null) tail.pre = value;

        count++;
    }

    public void DeleteNode(T value)
    {
        ListNode<T> pre = head;
        ListNode<T> deleteNode = First;
        while (deleteNode != null && deleteNode.value.CompareTo(value) != 0)
        {
            pre = pre.next;
            deleteNode = deleteNode.next;
        }

        if (deleteNode == null)
            return;

        DeleteNode(pre, deleteNode);
    }

    public void DeleteNode(ListNode<T> node)
    {
        if (node == null)
            return;

        ListNode<T> pre = head;
        ListNode<T> deleteNode = First;
        while (deleteNode != null && deleteNode != node)
        {
            pre = pre.next;
            deleteNode = deleteNode.next;
        }

        if (deleteNode == null)
            return;

        DeleteNode(pre, deleteNode);
    }

    private void DeleteNode(ListNode<T> pre, ListNode<T> deleteNode)
    {
        if (pre == null || deleteNode == null)
            return;

        ListNode<T> next = deleteNode.next;
        pre.next = next;
        if (pre != head) next.pre = pre;

        count--;
    }

    public ListNode<T> Find(T value)
    {
        ListNode<T> node = First;
        while (node != null && node.value.CompareTo(value) != 0)
        {
            node = node.next;
        }

        return node;
    }

    public void Clear()
    {
        head.next = tail;
        tail.pre = head;
        count = 0;
    }
}

栈

先进后出

应用

基于栈实现的UI框架
编辑器中撤回和重做的操作
括号合法检查
基于栈实现简单的表达式计算

数组实现

public class Stack<T>
{
    private T[] array;
    private int count;

    public int Count => count;

    private static T[] emptyArray = new T[0];

    public Stack()
    {
        array = emptyArray;
        count = 0;
    }

    public Stack(int capacity)
    {
        array = new T[capacity];
        count = 0;
    }

    public bool IsEmpty()
    {
        return count <= 0;
    }

    public T Peek()
    {
        if (count == 0)
        {
            throw new Exception("Stack count is 0.");
        }
        else
        {
            return array[count - 1];
        }
    }

    public void Push(T t)
    {
        if (count == array.Length)
        {
            Resize((array.Length == 0) ? 4 : (2 * array.Length));
        }

        array[count++] = t;
    }

    public T Pop()
    {
        if (count == 0)
        {
            throw new Exception("Stack count is 0.");
        }

        T t = array[--count];
        array[count] = default(T);

        if (count > 0 && count == array.Length / 4)
        {
            Resize(array.Length / 2);
        }

        return t;
    }

    private void Resize(int count)
    {
        T[] _array = new T[count];
        Array.Copy(array, 0, _array, 0, this.count);
        array = _array;
    }
}

链表实现

public class Stack<T>
{
    private class ListNode<Y>
    {
        public ListNode<Y> next;
        public Y value;

        public ListNode(Y value)
        {
            this.value = value;
        }

        public ListNode(ListNode<Y> node, Y value)
        {
            this.next = node;
            this.value = value;
        }
    }

    private ListNode<T> first;
    private int count;

    public int Count => count;

    public bool IsEmpty()
    {
        return first == null;
    }

    public T Peek()
    {
        if (first == null)
        {
            throw new Exception("Stack count is 0.");
        }
        else
        {
            return first.value;
        }
    }

    public void Push(T value)
    {
        ListNode<T> oldFirst = first;
        first = new ListNode<T>(value);
        first.next = oldFirst;

        count++;
    }

    public T Pop()
    {
        if (count == 0)
        {
            throw new Exception("Stack count is 0.");
        }

        T value = first.value;
        first = first.next;

        count--;

        return value;
    }
}

队列

先进先出

应用

消息队列，降低峰值
动画队列，按顺序逐个播放动画
BFS
排队问题等

数组实现

public class Queue<T>
{
    private int front;
    private int rear;
    private T[] array;

    private static T[] emptyArray = new T[4];

    public int Capacity => array.Length;
    public int Count => (rear + Capacity - front) % Capacity;
    public bool IsEmpty => front == rear;
    private bool IsFull => (rear + 1) % Capacity == front;

    public Queue()
    {
        array = emptyArray;
        front = 0;
        rear = 0;
    }

    public Queue(int capacity)
    {
        array = new T[capacity];
        front = 0;
        rear = 0;
    }

    public void Enqueue(T value)
    {
        if (IsFull)
        {
            Resize(Capacity * 2);
        }

        array[rear] = value;
        rear = (rear + 1) % Capacity;
    }

    public T Dequeue()
    {
        if (IsEmpty)
        {
            throw new Exception(("Queue count is 0."));
        }

        T value = array[front];
        array[front] = default(T);
        front = (front + 1) % Capacity;

        if (Count > 0 && Count == Capacity / 4)
        {
            Resize(Capacity / 2);
        }

        return value;
    }

    public T Peek()
    {
        if (IsEmpty)
        {
            throw new Exception("Queue count is 0.");
        }

        return array[front];
    }

    private void Resize(int size)
    {
        T[] newArray = new T[size];

        int index = front;
        int newIndex = 0;
        while (newIndex < Count)
        {
            newArray[newIndex++] = array[index];
            index = (index + 1) % Capacity;
        }
        front = 0;
        rear = newIndex;
        array = newArray;
    }
}

链表实现

public class Queue<T>
{
    private class Node<Y>
    {
        public Node<Y> next;
        public Y value;

        public Node(Y value)
        {
            this.value = value;
        }

        public Node(Node<Y> node, Y value)
        {
            this.next = node;
            this.value = value;
        }
    }

    private Node<T> first;
    private Node<T> last;
    private int count;

    public int Count => count;
    public bool IsEmpty => first == null;

    public void Enqueue(T value)
    {

        Node<T> oldLast = last;
        last = new Node<T>(value);
        if (IsEmpty)
        {
            first = last;
        }
        else
        {
            oldLast.next = last;
        }

        count++;
    }

    public T Dequeue()
    {
        if (IsEmpty)
        {
            throw new Exception("Queue count is 0.");
        }

        T value = first.value;
        first = first.next;

        if (IsEmpty)
            last = null;

        count--;
        return value;
    }

    public T Peek()
    {
        if (IsEmpty)
        {
            throw new Exception("Queue count is 0.");
        }

        return first.value;
    }
}

双端队列

双端队列同时具有栈的先进后出特性，也具有队列的先进先出特性。

应用

KTV式可插歌的点歌系统
LRU

数据结构与算法总结——线性表

数组和链表

数组

链表

时间复杂度

动态数组

实现

单链表

实现

双链表

实现

栈

应用

数组实现

链表实现

队列

应用

数组实现

链表实现

双端队列

应用

Lua知识点整理

数据结构与算法总结——哈希表

阿花

Comments | NOTHING

取消回复

无境