线性表，栈，队列，串

雨点打透心脏的1/2处 2022-03-17 06:56 178阅读 0赞

一个线性表是n个具有相同特性的数据元素的有限序列（有序性）。  
1 顺序存储：数组，通过存储位置维护有序性  
2 链式存储：链表，通过指针维护有序性  
双向链表，循环链表（有环，从head出发回到head，若为6形环，快慢指针判别，一个跳1步，一个2步，是否会相遇）

栈：LIFO，栈顶操作  
1 顺序存储：顺序栈，使用数组  
2 链式存储：链表

队列：FIFO，队尾插入，队头删除  
1 链队列：头尾指针，单向，头结点（不代表任何实际数据，起始头尾指针都指向头结点，加入元素尾指针后移，移除元素头结点指向往后一个元素，头指针永远指向头结点，判空条件：头尾指针都指向头结点）  
2 循环队列：数组，起始头尾指针=0，循环使用数组空间，rear=front(队列为空或为满)，怎么解决？留空一个元素，即rear=front为空，（rear+1）% length=front 为满  
deque（双端队列）：两端都可插入，删除

串：字符串，零或多个字符的有限序列，零个字符为空(字符)串，一个或多个空格为空格串  
模式匹配：子串m，目标串n  
1 两层循环，O(mn)

char[] t = ts.toCharArray();
    char[] p = ps.toCharArray();
    int i = 0; // 主串的位置
    int j = 0; // 模式串的位置
      while (i < t.length && j < p.length) {
           if (t[i] == p[j]) { // 当两个字符相同，就比较下一个
               i++;
               j++;
           } else {
               i = i - j + 1; // 一旦不匹配，i后退
               j = 0; // j归0
           }
        }
        if (j == p.length) {
           return i - j;
        } else {
           return -1;
        }

2 KMP，思想是：匹配失败后，i不变，j移动到某个位置，重新i++，j++匹配，某个位置怎么算？ next数组，数组下标为j，对应内容为j移动到的位置，O(m+n)

int[] next = getNext(ps);
        while (i < t.length && j < p.length) {
           if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，当然j也要归0
               i++;
               j++;
           } else {
               // i不需要回溯了
               // i = i - j + 1;
               j = next[j]; // j回到指定位置
           }
        }
        
        public static int[] getNext(String ps) {
        char[] p = ps.toCharArray();
        int[] next = new int[p.length];
        next[0] = -1;
        int j = 0;
        int k = -1;
        while (j < p.length - 1) {
           if (k == -1 || p[j] == p[k]) {
               next[++j] = ++k;
           } else {
               k = next[k];
           }
        }
        return next;
    }