数据结构笔记

线性表

线性表具有相同数据类型的n（≥0）个数据元素的有限序列。n=0时是空表。线性表中每个结点至多有一个直接前驱，至多有一个直接后继。

顺序实现

• 定义：一种随机存取的存储结构
• 特点：
  • 随机访问，访问第i个元素的时间是O(1)
  • 存储密度高
  • 拓展容量不方便
  • 插入、删除元素不便

public class SeqList<E> {
    private E[] elem; // 存储元素的数组
    private int len;  // 当前线性表的长度
    private int maxSize; // 最大容量
    private static final int INITSIZE = 10; // 默认初始容量

    // 构造方法，初始化线性表
    @SuppressWarnings("unchecked")
    public SeqList(int size) {
        maxSize = size;
        elem = (E[]) new Object[maxSize];
        len = 0;
    }

    // 默认构造方法，使用默认初始容量
    public SeqList() {
        this(INITSIZE);
    }

    // 判断线性表是否为空
    public boolean isEmpty() {
        return len == 0;
    }

    // 判断线性表是否已满
    public boolean isFull() {
        return len == maxSize;
    }

    // 获取线性表的长度
    public int length() {
        return len;
    }

    // 获取第 i 个位置的元素
    public E get(int i) {
        if (i < 0 || i >= len) {
            throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + len);
        }
        return elem[i];
    }

    // 查找值等于 e 的元素的索引，不存在返回 -1
    public int find(E e) {
        for (int i = 0; i < len; i++) {
            if (elem[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }

    // 在第 i 个位置插入元素 e
    public void insert(int i, E e) {
        if (isFull()) {
            expandCapacity();
        }
        if (i < 0 || i > len) {
            throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + len);
        }
        // 将第 i 位及以后的元素后移
        for (int j = len; j > i; j--) {
            elem[j] = elem[j - 1];
        }
        elem[i] = e;
        len++;
    }

    // 删除第 i 个位置的元素，并返回其值
    public E remove(int i) {
        if (i < 0 || i >= len) {
            throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + len);
        }
        E removedElement = elem[i];
        // 将第 i+1 位及以后的元素前移
        for (int j = i; j < len - 1; j++) {
            elem[j] = elem[j + 1];
        }
        len--;
        return removedElement;
    }

    // 清空线性表
    public void clear() {
        len = 0;
    }

    // 扩容数组
    @SuppressWarnings("unchecked")
    private void expandCapacity() {
        int newCapacity = maxSize * 2;
        elem = Arrays.copyOf(elem, newCapacity);
        maxSize = newCapacity;
    }

    // 打印线性表内容
    public void printList() {
        System.out.print("SeqList: [");
        for (int i = 0; i < len; i++) {
            System.out.print(elem[i]);
            if (i < len - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
}

单链表

template <typename T>
class SinglyLinkedList {
private:
    struct Node {
        T data; // 数据域
        Node* next; // 指针域，指向下一个节点

        // 构造方法
        Node(T data, Node* next) : data(data), next(next) {}
        Node(T data) : data(data), next(nullptr) {}
        Node() : data(), next(nullptr) {}
    };

    Node* head; // 头节点
    int size; // 链表的长度

public:
    // 构造方法
    SinglyLinkedList() : head(nullptr), size(0) {}

    // 析构方法，释放链表内存
    ~SinglyLinkedList() {
        clear();
    }

    // 判断链表是否为空
    bool isEmpty() const {
        return size == 0;
    }

    // 获取链表的长度
    int length() const {
        return size;
    }

    // 获取第 i 个位置的元素
    T get(int i) const {
        if (i < 0 || i >= size) {
            throw std::out_of_range("Index out of range");
        }
        Node* current = head;
        for (int j = 0; j < i; ++j) {
            current = current->next;
        }
        return current->data;
    }

    // 查找值等于 e 的元素的索引，不存在返回 -1
    int find(const T& e) const {
        Node* current = head;
        int index = 0;
        while (current != nullptr) {
            if (current->data == e) {
                return index;
            }
            current = current->next;
            ++index;
        }
        return -1;
    }

    // 在第 i 个位置插入元素 e
    void insert(int i, const T& e) {
        if (i < 0 || i > size) {
            throw std::out_of_range("Index out of range");
        }
        if (i == 0) {
            head = new Node(e, head); // 插入到头部
        } else {
            Node* current = head;
            for (int j = 0; j < i - 1; ++j) {
                current = current->next;
            }
            current->next = new Node(e, current->next); // 插入到中间或尾部
        }
        ++size;
    }

    // 在链表末尾添加元素 e
    void add(const T& e) {
        if (head == nullptr) {
            head = new Node(e);
        } else {
            Node* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = new Node(e);
        }
        ++size;
    }

    // 删除第 i 个位置的元素，并返回其值
    T remove(int i) {
        if (i < 0 || i >= size) {
            throw std::out_of_range("Index out of range");
        }
        Node* toDelete;
        T removedElement;
        if (i == 0) {
            toDelete = head;
            removedElement = head->data;
            head = head->next; // 删除头部节点
        } else {
            Node* current = head;
            for (int j = 0; j < i - 1; ++j) {
                current = current->next;
            }
            toDelete = current->next;
            removedElement = toDelete->data;
            current->next = toDelete->next; // 删除中间或尾部节点
        }
        delete toDelete;
        --size;
        return removedElement;
    }

    // 清空链表
    void clear() {
        while (head != nullptr) {
            Node* toDelete = head;
            head = head->next;
            delete toDelete;
        }
        size = 0;
    }
};

链表的排序

归并排序

找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。

public ListNode sortList(ListNode head) {
        return doSort(head,null);
    }
    public ListNode doSort(ListNode head,ListNode tail){
        if(head==null){
            return head;
        }
        //不要漏掉
        if(head.next==tail){
            head.next=null;
            return head;
        }
        ListNode fast=head,slow=head;
        while(fast!=tail&&fast.next!=tail){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode left=doSort(head,slow);
        ListNode right=doSort(slow,tail);
        ListNode dummy=new ListNode();
        ListNode tmp=dummy;
        while(left!=null&&right!=null){
            int val=0;
            if(left.val<right.val){
                val=left.val;
                left=left.next;
            }else{
                val=right.val;
                right=right.next;
            }
            ListNode node=new ListNode(val);
            tmp.next=node;
            tmp=tmp.next;
        }
        if(left==null){
            tmp.next=right;
        }else{
            tmp.next=left;
        }
        return dummy.next;
}

循环链表

找到链表中开始循环的节点

public ListNode detectCycle(ListNode head) {
        
        ListNode fast=head,slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                ListNode p=fast,q=head;
                while(p!=q){
                    p=p.next;
                    q=q.next;
                }
                return p;
            }
        }
        return null;
}

翻转链表

ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL)
        return head;
        ListNode* p=NULL;
        ListNode* q=head;
        while(q!=NULL){
            ListNode* tmp=q->next;
            q->next=p;
            p=q;
            q=tmp;
        }
        return p;
}

栈和队列

括号匹配

bool isValid(string s) {
        stack<char>st;
        int i=0;
        for(i=0;i<s.size();i++){
            if(s[i]=='(')
            st.push(')');
            else if(s[i]=='[')
            st.push(']');
            else if(s[i]=='{')
            st.push('}');

            else if(st.empty()||s[i]!=st.top()){
                return 0;
            }
            else if(st.top()==s[i]){
                st.pop();
            }
        }
        return st.empty();

}

单调栈

可用于求当前元素坐标或右边第一个比这个元素大的或小的元素。栈里面的元素是递增或递减的。栈内存放元素下标，标记遍历过的元素

• 递增栈：求第一个比他大的元素的位置
• 递减栈：求第一个比他小的元素的位置

以递增栈为例，实现递增栈包含以下几个步骤：

• 当前元素比栈顶元素大：
  • 记录结果，弹出栈顶元素，直到当前元素比栈顶元素小，再将当前元素下标入栈
• 当前元素比栈顶元素小：
  • 将当前元素下标入栈
• 当前元素和栈顶元素相同（注意如果是求大于等于，则这一步要记录结果）：
  • 将当前元素下标入栈

    stack<int> st;
    st.push(0);
    for (int i = 1; i < temperatures.size(); i++) {
        if (temperatures[i] > temperatures[st.top()]) {
            while (!st.empty() &&
            temperatures[i] > temperatures[st.top()]) {
            result[st.top()] = i - st.top();
            st.pop();
            }
            st.push(i);
        } else
            st.push(i);
    }