logo
DEEPLEARN
banner
NEWS LETTER

Java数据结构与算法

Scroll down

Java数据结构与算法

绪论

数据结构是指所涉及的数据元素的集合以及数据元素之间的关系

逻辑结构的类型

  • 集合

  • 线性结构

  • 树形结构

  • 图形结构

存储结构

  • 顺序存储结构

  • 链式存储结构

  • 索引存储结构

  • 哈希（散列）存储结构

数据类型 是一组性质相同的值的集合和定义在此集合上的一组操作的总称

ADT(抽象数据类型)

算法

  • 有穷性 —>不会出现无限循环

  • 确定性—>不会出现二义性

  • 可行性—>算法每条指令都可执行

  • 输入性—>零个或者多个输入

  • 输出性—>至少一个输出

算法时间复杂度

  • 用T(n)的数量级表示，记作T(n)=O(f(n))

最好时间复杂度–》min{T(n)}

最坏时间复杂度–》max{T(n)}

平均时间复杂度–》概率

线性表

线性表的顺序存储结构—顺序表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//顺序表泛型类
public class SqListClass<E> {
    final int initCapacity = 10; //顺序表初始容量
    public E[] data; //存放顺序表中的元素
    public int size; //存放顺序表长度
    public int capacity; //顺序表的容量

    public SqListClass() {
        this.data = (E[]) new Object[initCapacity];
        this.capacity = initCapacity;
        size = 0;
    }

    //    更改容量
    private void updateCapacity(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < this.data.length; i++) {
            newData[i] = this.data[i];
        }
        this.capacity = newCapacity;
        this.data = newData;
    }

    //    整体建立顺序表
    public void createList(E[] a) {
        this.size = 0;
        for (int i = 0; i < a.length; i++) {
            if (this.size == this.capacity) {
                this.updateCapacity(this.size * 2);
            }
            data[i] = a[i];
            size++;
        }
    }

    //    add
    public void add(E e) {
        if (this.size == capacity) {
            this.updateCapacity(size * 2);
        }
        data[size] = e;
        size++;
    }

    //    长度
    public int size() {
        return this.size;
    }

    //    设置长度,主要用于缩短长度
    public void setSize(int nLen) {
        if (nLen < 0 || nLen > this.size) {
            throw new IllegalArgumentException("设置长度不在范围内");
        }
        this.size = nLen;
    }

    //    获取线性表中序号为i的元素
    public E getElem(int i) {
        if (i < 0 || i > size - 1)
            throw new IllegalArgumentException("位置i不在有效范围内");
        return (E) this.data[i];
    }
//    setElem();
//    求线性表中第一个为e的元素的序号：getNo(E e);
//    将序号为i和j的元素交换位置：swap(int i, int j);
//    在线性表中序号为i的位置插入元素e:insert(int i, E e);
//    删除线性表中序号为i的元素：delete(int i);
//    toString();
}

线性表的链式存储结构–链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package 线性表;
//单链表

//单链表结点类
public class LinkNode<E> {
    E data;
    LinkNode<E> next;

    public LinkNode() {
        next = null;
    }

    public LinkNode(E data) {
        this.data = data;
        this.next = null;
    }
}

//单链表类
//public class LinkList{
class LinkList<E> {
    LinkNode<E> head; //存放头结点

    public LinkList() {
        head = new LinkNode<E>();//设置头结点
        head.next = null;
    }

//    将s结点插入到p结点后面--> s.next = p.next;p.next = s;
//    删除结点p的后继结点--> p.next = p.next.next;
}

建立单链表的方法(下面的代码块均位于LinkList类里)

  • 头插法(数据结点次序和数组中数据次序正好相反)

1
2
3
4
5
6
7
8
public void createListF(E[]e){
        LinkNode<E> s;
        for(int i=0;i<e.length();i++){
        s=new LinkNode<E>(e[i]); //循环建立结点
        s.next=this.head.next;
        this.head.next=s;
        }
        }

  • 尾插法(数据结点次序和数组中数据次序相同)

1
2
3
4
5
6
7
8
9
10
public void createListR(E[]e){
        LinkNode<E> s t;
        t=this.head;
        for(int i=0;i<e.length();i++){
        s=new LinkNode<E>(e[i]);
        t.next=s;
        t=s;
        }
        t=null;
        }

线性表的基本运算在单链表中的实现

  • 获得序号为i的元素（0<= i <=n-1）

1
2
3
4
5
6
7
8
9
public LinkNode<E> getI(int i){
        LinkNode<E> h=this.head;
        int j=-1;
        while(j<i){
        j++;
        h=h.next;
        }
        return h;
        }

  • 将元素e添加到线性表末尾

1
2
3
4
5
6
7
8
public void add(E e){
        LinkNode<E> s=new LinkNode<>(e);
        LinkNode<E> p=head;
        while(p.next!=null){
        p=p.next;
        }
        p.next=s;
        }

  • 求线性表的长度

1
2
3
4
5
6
7
8
9
public int size(){
        LinkNode<E> p=head;
        int size;
        while(p.next!=null){
        size++;
        p=p.next;
        }
        return size;
        }

  • 设置线性表的长度

1
2
3
4
5
6
7
8
public void setSize(int nLen){
        int len=this.size();
        if(nLen< 0||nLen>len)
        throw new IllegalArgumentException('err-msg');
        if(nLen==len)return;
        LinkNode<E> p=this.getI(nLen-1);//获取序号为 nLen-1 的结点
        p.next=null;//截断
        }

  • 获取线性表中序号为i的元素（data）

1
2
3
4
5
6
7
public E getElem(int i){
        int len=this.size();
        if(i< 0||i>len-1)
        throw new IllegalArgumentException('err-msg');
        LinkNode<E> p=getI(i);//获取结点
        return(E)p.data;
        }

  • 设置线性表中序号为i的元素setElem(int i,E e) (与获取相似)

  • 求线性表中第一个为e的元素的逻辑序号

1
2
3
4
5
6
7
8
9
10
public int getNo(E e){
        int j;
        LinkNode<E> p=this.head;
        while(p!=null&&!p.data.equals(e)){
        j++;
        p=p.next;
        }
        if(p==null)return-1;
        return j;
        }

  • 交换序号为 i 和 j 的元素

1
2
3
4
5
6
7
public void swap(int i,int j){
        LinkNode<E> p=getI(i);
        LinkNode<E> q=getI(j);
        E temp=p.data;
        p.data=q.data;
        q.data=temp;
        }

  • 插入 e 作为第i个元素(序号为i)

1
2
3
4
5
6
7
public void insert(int i,E e){
        if(i< 0||i>size())throw new IllegealArgumentException();
        LinkNode<E> p=new LinkNode<>(e);
        LinkNode<E> s=getI(i-1);
        s.next=p.next;
        p.next=s;
        }

  • 删除第i个元素(序号为i)

1
2
3
4
5
public void delete(int i){
        if(i< 0||i>size())throw new IllegealArgumentException();
        LinkNode<E> p=getI(i-1);
        p.next
        }

快慢指针法(返回单链表中间位置元素)(P66)

1
2
3
4
5
6
7
8
9
public static E middle(LinkList<E> l){
        LinkNode<E> fast=l.head.next;
        LinkNode<E> slow=l.head.next;
        while(fast.next!=null&&fast.next.next!=null){
        slow=slow.next;
        fast=fast.next.next;
        }
        return slow.data;
        }

利用头插法让单链表l逆序，如（1,2,3,4,5）==>（5,4,3,2,1）

1
2
3
4
5
6
7
8
9
10
11
public static void reverse(LinkList<E> l){
        LinkNode<E> p=l.head.next;//p指向头结点
        LinkNode<E> q;
        l.head.next=null;//将l设置为一个空表
        while(p!=null){
        q=p.next;//先用q临时保存p的后继结点
        p.next=l.head.next;
        l.head.next=p;
        p=q;
            }
        }

将两个递增有序单链表合并为一个递增有序单链表（二路归并 + 尾插法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static LinkNodeClass<Integer> Merge(LinkListClass<Integer> A,
        LinkListClass<Integer> B){
        LinkNode<Integer> p=A.head.next;
        LinkNode<Integer> q=B.head.next;//p,q均指向头结点
        LinkListClass<Integer> C=new LinkListClass<>();
        LinkNode<Integer> t=C.head;
        while(p!=null&&q!=null){
        if(p.data<q.data){
        t.next=p;
        t=p;
        p=p.next;
        }else{
        t.next=q;
        t=q;
        q=q.next;//将较小的结点链接到C的末尾
        }
        }
        t.next=null;//将C的尾结点的next设置为空
        if(p!=null)t.next=p;
        if(q!=null)t.next=q;
        return C;//返回新链表
        }

双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//双链表的结点泛型类
public DLinkNode<E>{
        E data;
        DlinkNode<E> prior;//前驱结点
        DlinkNode<E> next;//后继结点
public DlinkNode(){
        prior=null;
        next=null;
        }
public DlinkNode(E e){
        data=e;
        this.DlinkNode();
        }
        }
1
2
3
4
5
6
7
8
9
//双链表的泛型类
public DlinkListClass<E>{
        DlinkNode<E> dhead;//头结点
public DlinkListClass(){
        dhead=new DLinkNode<E>();
        dhead.prior=null;
        dhead.next=null;
        }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
//头插法建立双链表
public void createListF(E[]a){
        DLinkNode<E> s;
        for(int i=0;i<a.length();i++){
        s=new DLinkNode<E>(a[i]);
        s.next=dhead.next;//dhead 为类里面的头结点
        if(dhead.next!=null){
        dhead.next.prior=s;
        }
        dhead.next=s;
        s.prior=dhead;
        }
        }
1
2
3
4
5
6
7
8
9
10
11
12
//尾插法建立双链表
public void createListR(E[]a){
        DLinkNode<E> s;
        t=dhead;
        for(int i=0;i<a.length();i++){
        s=new DLinkNode<E>(a[i]);
        t.next=s;
        s.prior=t;
        t=s;
        }
        t.next=null;
        }

循环链表

1
2
3
4
5
6
7
8
9
//循环单链表泛型类
public class CLinkListClass {
    LinkNode<E> head;

    public ClinkListClass() {
        head = new LinkNode<E>();
        head.next = head;
    }
}

循环双链表

1
2
3
4
5
6
7
8
9
public class CDLinkNodeList<E> {
    DLinkNode<E> dhead;//存放头结点

    public CDLinkNodeList {
        dhead = new DLinkNode<E>();
        dhead.next = dhead;
        dhead.prior = dhead;
    }
}

顺序表和链表的比较

  • 基于时间考虑

存储密度 = 结点中数据本身所占用的存储量/整个结点占用的内存量

一般情况下，存储密度越大，存储空间利用率就越大

当线性表长度变化不大，易于事先估计的情况，为了节省内存空间，宜采用顺序表

反之，当变化较大，难以估计其内存大小时，为了节省存储空间，宜采用链表

  • 基于时间考虑

在顺序表进行插入删除操作时平均需要移动一半的元素；

二路归并 + 顺序存储结构求解多项式相加（主要算法）

  • 用i，j分别遍历L1和L2有序多项式顺序表的元素，先建立一个空的多项式顺序表L3，在L1，L2都没有遍历完时循环

    1. 若i指向的元素的指数比较大，则根据其系数和指数新建一个元素并将其添加到L3，i++

    2. 若j指向的元素的指数比较大，则根据其系数和指数新建一个元素并将其添加到L3，j++

    3. 若i和j指向的元素的指数相同，则求出系数之和c，若c != 0,则由该系数和指数新建一个元素并将其添加到L3，否则不新建元素。最后 i++，j++

采用链式存储结构求解多想是相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//一个多项式对应的结点类
public class PolyNode {
    public double coef;//系数
    public int exp;//指数
    public PolyNode next;//指向下一项

    public PolyNode() {
        next = null;
    }

    public PolyNode(double coef, int exp) {
        this.coef = coef;
        this.exp = exp;
        next = null;
    }
}
1
2
3
4
5
6
7
8
//多项式单链表PolyClass类
public class PolyClass {
    PolyNode head;

    public PolyClass() {
        head = new PolyClass();
    }
}

对单链表设置一个头结点的作用是什么？

栈和队列

栈

抽象来说，栈是一种只能在一段进行插入或者删除操作的线性表，允许插入和删除的一段叫做栈顶，另一端叫做栈底，插入操作通常称为进栈或入栈，删除操作通常称为退栈或出栈

设n个元素进栈顺序为1,2,3…n，出栈顺序为p1p_1,p2p_2,…pnp_n,若p1p_1 = n,p2p_2 = n-1,…,pnp_n= 1,

即：pip_i +ii = nn + 1, pip_i = nn - ii + 1

顺序栈

  1. 顺序栈四要素：

  • 栈空的条件是 top = -1;

  • 栈满（栈上溢出）的条件是 top = capacity -1 ，采用动态扩容的方法，即栈满时将data数组的容量扩大两倍;

  • 元素e进栈的操作是先将 top+1，然后将元素放在栈顶指针 top 处;

  • 出栈操作先将栈顶指针top处的元素取出，再将top - 1;

  1. 顺序栈的泛型类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class S    qStackClass<E>{
final int initcapacity=10;//初始容量
private int capacity;//存放顺序栈容量
private E[]data;//存放顺序栈元素
private int top;//存放栈顶指针

public SqStackClass(){
        data=(E[])new Object[initcapacity];//强制转换为E类型数组
        capacity=initcapacity;
        top=-1;
        }

//改变栈的容量大小
public void updateCapacity(int newcapacity){
        E[] newdata=(E[])new Object[newcapacity];
        for(int i=0;i<top+1;i++){
        newdata[i]=data[i];
        }
        capacity=newcapacity;
        data=newdata;
        }

//判断栈是否为空
public boolean empty(){
        return top==-1;
        }

//进栈
public void push(E e){
        if(top==capacity-1){
        updateCapacity(2*(top+1));
        }
        top++;
        data[top]=e;
        }

//出栈
public E pop(){
        if(empty()){
        throw new illegalArgumentException("栈空");
        }
        E e=data[top];
        top--;
        if(capacity>initcapacity&&top+1<capacity/4){
        updateCapacity(capacity/4);
        }
        return e;
        }

//获取栈顶元素，但是top指针不移动，只是查看
public E peek(){
        if(empty()){
        throw new illegalArgumentException("栈空");
        }
        return(E)data[top];
        }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//检查用户输入的括号是否配对
public boolean isMatch(String str){
        int i=0;
        char e;
        SqStackClass<Character> st=new SqStackClass<>();//建立顺序栈
        while(i<str.length){
        e=str.charAt(i);
        if(e=='('||e=='{'||e=='['){
        st.push(e);//左括号入栈
        }else{
        if(e==')'){
        if(st.empty())return false;//栈空
        if(st.peek()!='(')return false;
        st.pop();
        }else if(e==']'){
        if(st.empty())return false;//栈空
        if(st.peek()!='[')return false;
        st.pop();
        }else if(e=='}'){
        if(st.empty())return false;//栈空
        if(st.peek()!='{')return false;
        st.pop();
        }
        }
        i++;
        }
        return!empty();
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//判断回文字符串
public boolean isPalindrome(String str){
        SqStackClass<Character> st=new SqStackClass<>();//建立顺序栈
        int i=0;
        //将前半字符入栈
        while(i<n/2){
        st.push(str.charAt(i));
        }
        //n为奇数跳过最中间的字符
        if(n%2==1){
        i++;
        }
        //将后面的一半字符从栈顶开始比较
        while(i<n){
        //取出栈最上面的字符比较
        if(!str.charAt(i).equals(st.pop())){
        return false;
        }
        i++;
        }
        return true;
        }

栈的链式存储结构（不用考虑栈满上溢出的情况）

  • 栈空的条件为head.next == null, 初始时只有一个头结点

  • 由于只有内存溢出才会出现栈满的情况，所有一般不考虑

  • 元素e入栈时将包含该元素的结点插入作为首结点

  • 出栈操作返回首结点的值并删除该结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//结点泛型类
public class LinkNode<E> {
    E data;
    LinkNode<E> next;

    public LinkNode() {
        next = null;
    }

    public LinkNode(E data) {
        this.data = data;
        next = null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//链栈泛型类
public class LinkStackClass<E>() {
    LinkNode<E> head;

    public LinkStackClass() {
        head = new LinkNode<E>();
        head.next = null;
    }

    //判断链栈是否为空
    public boolean empty() {
        return head.next == null;
    }

    //进栈
    public void push(E e) {
        LinkNode<E> s = new LinkNode<>(e);
        s.next = head.next;
        head.next = s;
    }

    //出栈
    public E pop() {
        if (empty()) {
            throw new illegalArgumentException("空栈");
        }
        E e = (E) head.next.data;
        head.next = head.next.next;
        return e;
    }

    //取栈顶元素值
    public E peek() {
        if (empty()) {
            throw new illegalArgumentException("空栈");
        }
        return (E) head.next.data;
    }
}

中缀表达式转后缀表达式【java】中缀表达式转后缀表达式 java实现-阿里云开发者社区 (aliyun.com)

队列

  • 队列的顺序存储结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class SqQueueClass<E> {
    final int MaxSize = 100;
    private E[] data;
    private int front, rear;

    public SqQueueClass() {
        data = (E[]) new Object[MaxSize];
        front = -1;
        rear = -1;
    }

    //判断为空
    public boolean empty() {
        return front == rear;
    }

    //进队，先将rear+1，然后再将元素e放在该位置（总是尾部插入）
    public void push(E e) {
        if (rear = MaxSize - 1) {
            throw new IllegalArgumentException("队满");
        }
        rear++;
        data[rear] = e;
    }

    //出队，现将front+1，然后再将该位置的元素取出（出队的元素总是从队头出来的）
    public E pop() {
        if (empty()) {
            throw new IllegalArgumentException("队空");
        }
        front++;
        return (E) data[front];
    }

    //取队头元素
    public E peek() {
        if (empty()) {
            throw new IllegalArgumentException("队空");
        }
        return (E) data[front + 1];
    }
}

假溢出

进队时rear增加，出队rear不变，front增加，当rear==MaxSize-1队满，这种队列中有空位置但是满足队满条件的上溢出称为假溢出

循环队列

循环队列首尾相连，当队尾指针rear=MaxSize-1时再前进一个位置就到达0位置，这个可以用%（求余）来实现

  • 队首指针循环进1：front = (front+1) % MaxSize;

  • 队尾指针循环进1：rear = (rear+1) % MaxSize;

循环队列的队头指针和队尾指针的初始化位置都是0，即front = rear = 0

  • 队空条件：rear = front

  • 队满的条件为（rear+1）% MaxSize == front,(相当于试探进队一次，若rear达到了front，则认为队满了)

  • 元素e进队时，rear = (rear+1) % MaxSize,将元素e放置在该位置

  • 元素出队时，front = (front+1) % MaxSize,取出该位置元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class CSqQueueClass<E> {
    final int MaxSize = 100;//容量
    private E[] data;
    private int front, rear;

    public CSqQueueClass() {
        data = (E[]) new Object[MaxSize];
        front = 0;
        rear = 0;
    }

    //判断队空
    public boolean empty() {
        return rear == front;
    }

    //进队
    public void push(E e) {
        if ((rear + 1) % MaxSize == front) {
            throw new IllegalArguementException("队满");
        }
        rear = (rear + 1) % MaxSize;
        data[rear] = e;
    }

    //出队
    public E pop() {
        if (empty()) {
            throw new IllegalArguementException("队空");
        }
        front = (front + 1) % MaxSize;
        return (E) data[front];
    }

    //取队头元素
    public E peek() {
        if (empty()) {
            throw new IllegalArguementException("队空");
        }
        return (E) data[(front + 1) % MaxSize];
    }
}

队列的链式存储结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//结点泛型类
public class LinkNode<E> {
    E data;
    LinkNode<E> next;

    public LinkNode() {
        next = null;
    }

    public LinkNode(E e) {
        data = e;
        next = null;
    }
}
1
2
3
4
5
6
7
8
9
public class LinkQueueClass<E> {
    LinkNode<E> front;
    LinkNode<E> rear;

    public LinkNode() {
        front = null;
        rear = null;
    }
}

  • 链队队空条件为front = rear = null或者front==null

  • 只有内存溢出才会出现队满，通常不考虑

  • 元素e进队操作：在单链表的尾部插入存放e的s结点，并让队尾指针指向它

  • 元素出队操作：取出队首结点的data值，并将其从链队中删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//基本方法
//队空
public boolean empty(){
        return front==null;
        }
//进队
public void push(E e){
        LinkNode<E> s=new LinkNode<>(e);
        if(empty()){
        front=rear=s;
        }
        }
//出队
public E pop(){
        E e;
        if(empty()){
        throw new IllegalArguementException("队空")
        }
        if(rear==front){
        //只有一个结点
        e=(E)front.data;
        front=rear=null;
        }else{
        //多个结点
        e=(E)front.data;
        front=front.next;
        }
        return e;
        }
//取队头元素
public E peek(){
        if(empty()){
        throw new IllegalArguementException("队空")
        }
        return(E)front.data;
        }

串

基本概念

  • 串是由零个或多个字符组成的有限序列，里面的单个字符称为串的元素，是构成串的基本单位，串中包含的字符数称为串的长度，当个数为0为空串

串的存储结构

  • 顺序存储结构–顺序串

1
2
3
4
5
6
7
8
9
10
11
//顺序串类
public class SqStringClass {
    final int MaxSize = 100;
    char[] data;
    int size;

    public SqStringClass() {
        data = new char[MaxSize];
        size = 0;
    }
}

  • 串的链式存储结构–链串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//链串结点类
public class LinkNode {
    char data;
    LinkNode next;

    public LinkNode() {
        next = null;
    }

    public LinkNode(char ch) {
        data = ch;
        next = null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
//链串类
public class LinkStringClass {
    LinkNode head;
    int size;

    public LinkStringClass() {
        head.next = null;
        size = 0;
    }
//尾插法插入
}

Java 里面的字符串

串的模式匹配

  • Brute-Force算法（BF算法）（简单匹配算法）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public int BF(String s, String t){
        int i=0,j=0;
        while( i<s.length() && j<t.length() ){//s,t都没遍历完时循环
            if(s.charAt(i) == t.charAt(j)){
                i++;
                j++;
            }
            else{
                i = i-j+1;
                j = 0;
            }
        }
        if(j >= t.length()) return ( i-t.length );
        return -1;
    }

  • KMP算法

  • 求模式串的next数组

  1. 对于序号0，规定next[0] = -1;
  
  2. 对于序号1，置next[1] = 0;
  
  3. 如果{% _internal_math_placeholder 46 %}有多个相同的前后缀，应该取最长的长度为其next[{% _internal_math_placeholder 47 %}]值；

递归

条件

  • 调用次数有限

  • 有终止条件

  • 把一个问题化成很多小问题解决，这些小问题和大问题求解方法一样，只是规模不同

递归模型

f(s1)=m1f(s_1)=m_1 f(sn)=g(f(sn−1),cn−1)f(s_n)=g(f(s_{n-1}),c_{n-1})

在递归算法的执行中最长的递归调用的链长称为该算法的递归调用深度

例如n!n!的递归算法在求fun(5)fun(5)的递归调用深度为5

递归算法时间复杂度

  1. 给出执行时间对应的递推式；

  2. 求解递推式得出算法的执行时间T(n)T(n);

  3. 最后由T(n)T(n)得出时间复杂度。

递归算法的空间复杂度

  • 根据递归深度得到（同时间复杂度求法，T(n)−−>S(n)T(n)-->S(n)）

数组和稀疏矩阵

一维数组

LOC(ai)=LOC(a0)+i∗kLOC(a_i)=LOC(a_0)+i*k

d维数组

对于数组a[m][n]a[m][n]，假设每个元素占kk个存储单元，LOC(a0,0)LOC(a_{0,0})表示a0,0a_{0,0}元素的存储地址

  • 行优先

    LOC(ai,j)=LOC(a0,0)+(i∗n+j)∗kLOC(a_{i,j})=LOC(a_{0,0})+(i*n+j)*k

  • 列优先

    LOC(ai,j)=LOC(a0,0)+(j∗m+i)∗kLOC(a_{i,j})=LOC(a_{0,0})+(j*m+i)*k

稀疏数组

  • 利用一个三元组(i,j,ai,j)(i,j,a_{i,j})来表示，三元组每个元素的类定义如下：

1
2
3
4
5
6
7
8
9
10
11
public class TupElem {
    int r;//行号
    int c;//列号
    int d;//元素值

    public TupElem(int r1, int c1, int d1) {
        r = r1;
        c = c1;
        d = d1;
    }
}

  • 稀疏矩阵三元组类定义

1
2
3
4
5
6
7
8
9
10
11
public class TupClass {
    int rows;//行数
    int cols;//列数
    int nums;//非0元素个数
    ArrayList<TupElem> data;

    public TupClass() {
        data = new ArrayList<TupElem>();
        nums = 0;
    }
}

特殊矩阵的压缩存储

  • 对称矩阵的压缩存储

    • 可以使对称元素共享同一存储空间，可以将n2n^2个元素压缩存储到n(n+1)/2n(n+1)/2 个元素的空间中。按照行优先存储时仅仅存储其下三角和主对角线部分的元素。

      • A中任一元素ai,ja_{i,j}和B中的元素bkb_k之间的关系如下：
k={i(i+1)2+j       i>=jj(j+1)2+i       i<j k=\left\{ \begin{matrix} {i(i+1) \over 2}+j~~~~~~~i>=j \\ \\ \\ {j(j+1) \over 2}+i~~~~~~~i<j \end{matrix} \right.

树和二叉树

树的基本术语

  • 结点的度：树中某个结点的子树的个数

  • 树的度：树中各结点的度的最大值（通常将度为m的树称为m次树）

  • 分支结点：度不为0的结点

  • 叶子结点：度为0 的结点

  • 双亲结点、孩子结点

  • 树的高度（深度）：根节点为第一层，树的最大层级称为树的高度

树的性质

  • 树中的结点数 等于 所有结点的度之和加一

  • 度为m的树的第 ii 层上最多有 mi−1m^{i-1} 个结点

  • 高度为 hh 的 mm 次树最多有 (mh−1)(m−1){(m^h-1) \over (m-1)}个结点

  • 具有 nn 个结点的 mm 次树的最小高度为 [logm(n(m−1)+1)][log_m(n(m-1)+1)]

在mm次树中计算结点时常用的关系式有：

  1. 树中所有结点的度之和 = 分支数 = n−1n-1

  2. 所有结点的度之和 = n1+2n2+⋅⋅⋅+m∗nmn_1 + 2n_2 + ··· + m*n_m

  3. n=n0+n1+⋅⋅⋅+nmn = n_0 + n_1 +···+ n_m

树的存储结构

  • 双亲存储结构

为一种顺序存储结构，双亲存储结构结点类如下：

1
2
3
4
public class PTree<E> {
    E data;//存放结点的值
    int parent;//存放双亲结点的位置
}

  • 孩子链存储结构

1
2
3
4
public class TSonNode<E> {
    E data;//结点的值
    TSonNode<E>[] sons;//指向孩子结点
}

二叉树（二分树）

  • 二叉树的5中基本形态

    • 空二叉树

    • 单结点二叉树

    • 右子树为空的二叉树

    • 左子树为空的二叉树

    • 左右子树都不为空的二叉树
      二叉树的5种状态

  • 满二叉树的特点

    • 叶子结点都在最下一层；

    • 只有度为0和度为2 的结点；

    • 含nn个结点的满二叉树的高度为log2(n+1)log_2(n+1)，叶子结点个数为(n/2)+1(n/2)+1，度为2的结点个数为(n/2)(n/2)。

  • 完全二叉树的特点：

    • 叶子结点只可能出现在最下面两层；

    • 最下一层的叶子结点都依次排列在改层最左边的位置上；

    • 如果有度为 1 的结点，只可能有一个，且该结点最多只有左孩子而无右孩子；

    • 按照层序编号后，一旦出现某结点（编号为ii）为叶子结点或只有左孩子，则编号大于 ii 的结点均为叶子结点。

  • 完全二叉树的计算：

    • 结点数为偶——>只有一个分支

    • 结点数为奇——>无单分支

    • (n−1)/2(n-1)/2个双分支

  • 二叉树的性质:

    • 非空二叉树上叶子结点数等于双分支结点数加一；

    • 非空二叉树的第ii层上最多有2i−12^{i-1}个结点(i>=1)(i>=1);

    • 高度为hh的二叉树最多有2h−12^h-1个结点；

    • 具有nn个结点的完全二叉树的高度为log2(n+1)log_2(n+1)或log2n+1log_2n+1。

二叉树的存储结构

  • 二叉树的顺序存储结构

    • 完全二叉树和满二叉树采用顺序存储结构比较合适，既能最大限度节省存储空间，又能利用下标迅速确定二叉树中位置和结点之间的关系
    • 编号为i i 的结点的层次为⌊log2(i+1)⌋\lfloor log_2(i+1) \rfloor

  • 二叉树的链式存储结构(二叉链)

    • 二叉链结点类

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      public class BTNode<E>{
      E data;
      BTNode lchild;//指向左结点
      BTNode rchild;//指向右结点

      public BTNode(){
          lchild=rchild=null;
      }
      public BTNode(E e){
          this.data = e;
          lchild=rchild=null;
      }
      }

      二叉树的基本运算

  • 二叉树的类设计

    1
    2
    3
    4
    5
    6
    7
    public class BTreeClass{
      BTNode<Character> b;//根结点
      String bstr;//根结点字符串表达式
      public BTreeClass(){
          b = null;
      }
    }

  • 二叉树的基本运算

    1
    2
    3
    4
    5
    6
    7
    8
    //创建二叉树
    public void CreateBTree(String str)
    //返回二叉树括号表示字符串
    public String toString()
    //查找值为x的结点(递归查找)
    FindNode(x)
    //求高度h(递归)
    Height()

二叉树的遍历

  • 先序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //先序遍历的递归算法
    public void PreOrder1(BTreeClass bt){
      PreOrder11(bt.b);
    }
    public void PreOrder11(BTNode<Character> t){
      if(t!=null){
          System.out.print(t.data + " ");
          PreOrder11(t.lchild);//先序遍历左子树
          PreOrder11(t.rchild);//先序遍历右子树
      }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //中序遍历的递归算法
    public void InOrder1(BTreeClass bt){
      InOrder11(bt.b);
    }
    public void InOrder11(BTNode<Character> t){
      if(t!=null){
          InOrder11(t.lchild);//中序遍历左子树
          System.out.print(t.data + " ");//访问根结点
          InOrder11(t.rchild);//中序遍历右子树
      }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //后序遍历的递归算法
    public void PostOrder1(BTreeClass bt){
      PostOrder11(bt.b);
    }
    public void PostOrder11(BtNode<Character> t){
      if(t!=null){
          PostOrder11(t.lchild);//后序遍历左子树
          PostOrder11(t.rchild);//后序遍历右子树
          System.out.print(t.data + " ");
      }
    }

    二叉树的层次遍历

  • 层次遍历基本步骤

    • 访问根结点（第一层）
    • 从左到右访问第二层的所有结点
    • 从左到右访问第三层的所有结点，......，第h h 层的所有结点

  • 层次遍历算法设计

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public void LevelOrder(BTreeClass bt){
      BTNode<Character> p;
      Queue<BTNode> qu = new LinkedList<BTNode>();
      qu.offer(bt.b);//根结点进队
      while(!qu.isEmpty()){//队列不为空时循环
           P = qu.poll();//出队第一个结点
           System.out.print(p.data + " ");//输出
           if(p.lchild!=null){//有左孩子，进队
              qu.offer(p.lchild);
           }
           if(p.rchild!=null){//有右孩子，进队
              qu.offer(p.rchild);
           }
      }
    }

    关于二叉树构造的一些结论

  • 任何n(n>=0) n(n>=0) 个不同结点的二叉树都可以由它的中序序列和先序序列唯一地确定

  • 任何n(n>=0) n(n>=0) 个不同结点的二叉树都可以由它的中序序列和后序序列唯一地确定

线索二叉树

  • 定义对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

  • 区分“前驱结点”和“孩子结点”
    标识

    左标识ltag={0    表示lchild指向左孩子结点1    表示lchild指向前驱结点的线索 左标识ltag=\left\{ \begin{matrix} 0~~~~表示lchild指向左孩子结点\\\\ 1~~~~表示lchild指向前驱结点的线索 \end{matrix} \right.
右标识ltag={0    表示rchild指向右孩子结点1    表示rchild指向后继结点的线索 右标识ltag=\left\{ \begin{matrix} 0~~~~表示rchild指向右孩子结点\\\\ 1~~~~表示rchild指向后继结点的线索 \end{matrix} \right.

每个这样的结点存储结构如下：

ltag lchild data rchild rtag

线索化二叉树（建立线索二叉树）（以下以中序遍历为主）

  • 二叉链结点类

  • 左孩子为空

^ data rchild

左指针指向中序遍历的直接前驱

  • 右孩子为空

lchild data ^

右指针指向中序遍历的直接后继

1
2
3
4
5
6
7
8
9
public class ThNode{
    char data;//数据
    ThNode lchild, rchild;
    int ltag, rtag;
    public ThNode(){
        lchild = rchild = null;
        ltag = rtag = 0;
    }
}

  • 中序线索化二叉树类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class ThreadClass{
    ThNode b;//二叉树根结点
    ThNode root;//线索二叉树的头结点
    ThNode pre;//用于中序线索化，指向中序前驱结点
    String bstr;
    public ThreadClass(){
        root = null;
    }
    //基本运算
    //建立以root为头结点的中序线索二叉树
    public void createThread(){……}

    //对以P为根结点的二叉树进行中序线索化
    public void Thread(ThNode p){……}
}

遍历线索二叉树 <—click here to learn

哈夫曼树（最优二叉树）（P272）

  • 权值越大，离根结点越近

  • 权值越小，离根结点越远

  • 具有n0n_0个叶子结点的哈夫曼树共有2n0−12n_0-1个结点

哈夫曼编码

  • 在一组字符的哈夫曼编码中，任一字符的哈夫曼编码不可能是另一字符的哈夫曼编码的前缀。

二叉树与树、森林之间的转换

  • 树到二叉树的转换步骤

    • 加线：在各兄弟结点之间加一连线
    • 抹线：对于任意结点，除了其最左子树之外，抹掉该结点与其他子树之间的双亲-孩子关系
    • 调整：（排列整齐）

  • 一棵由树转换的二叉树与还原为树

    • 加线：在各结点的双亲与该结点右链上的每个结点之间加一条连线
    • 抹线：抹掉二叉树中所有双亲结点与其右孩子之间的双亲-右孩子关系
    • 调整：（排列整齐）

森林到二叉树的转换及还原

  • 森林转换为二叉树

    • 转换：将森林中每一棵树转换为二叉树
    • 连接：将转换后的二叉树根结点相连
    • 调整：（排列整齐）

  • 二叉树还原为森林

    • 抹线：抹掉根结点右链上所有双亲-右孩子关系
    • 转换：分别将抹线后的二叉树还原为树
    • 调整：（排列整齐）

图

基本概念

  • 图GG由两个集合V和EV和E组成，记为G=(V,E)G=(V,E)，其中VV是顶点的有限集合,记为V(G)V(G),

    EE是连接两个不同顶点的边的有限集合，记为E(G)E(G)。

    +无向图：在图GG中，如果代表边的顶点对（或序偶）是无序的，则成GG为无向图，−−>(a,b)-->(a,b)

  • 有向图：顶点对有序−−><a,b>和<b,a>--><a,b>和<b,a>不一样

基本术语

  • 端点和邻接点

    (a,b)−−>a,b互为邻接点,a、b顶点称为该边的两个端点(a,b)-->a,b互为邻接点,a、b顶点称为该边的两个端点

  • 顶点的度、入度、出度

    • 顶点的度：顶点所关联的边的数目
    • 入度、出度：以该顶点为终点的边的数目，反之，以该端点为起点的边的数目为出度若一个图中有nn个顶点和ee条边，每个顶点的度为 di(0<=i<=(n−1)) d_i(0<=i<=(n-1)),则有：
e=12∑i=0n−1di e = \frac{1}{2}\sum_{i=0}^{n-1}d_i

相当于一个图中顶点的度之和等于边数的两倍

  • 完全图有向图每两个顶点之间都存在着方向相反的两条边

graph TD;
0-->1
1-->0
1-->2
2-->1
2-->3
3-->2
3-->0
0-->3
3-->1
1-->3
0-->2
2-->0

无向图每两个端点之间都存在一条边

graph LR;
0---1
1---2
2---3
3---0
3---1
2---0

  • 稠密图和稀疏图

    • 当一个图接近万全图时称为稠密图
    • 当一个图边数较少[有向图e<<n(n−1),无向图e<<n(n−1)2e<<n(n-1),无向图e<<\frac{n(n-1)}{2}]称为稀疏图

  • 子图

    • 两个图G=(V,E)和G′=(V′,E′),若V′是V的子集，且E′是E的子集，则G′是G的子图G=(V,E)和G'=(V',E'),若V'是V的子集，且E'是E的子集，则G'是G的子图

  • 路径和路径长度

    • 从顶点i到顶点j顶点i到顶点j的一条路径是一个顶点序列(i,i1,i2,...,im,j)(i,i_1,i_2,...,i_m,j)
    • 路径长度是指一条路径上经过的边的数目
    • 简单路径是指一条路径上除开始点和结束点可以相同外，其余端点均不相同

  • 回路和环

    • 一条路径开始点和结束点相同，该路径被称为回路或环

  • 连通、连通图、连通分量

    • 图的任意两个端点都是连通的图称为连通图，否则为非连通图
    • 无向图G的极大连通子图称为G的连通分量

  • 强连通图和强连通分量

    • 强连通图：从顶点i到j和j到i都有路径从顶点i到j和j到i都有路径
    • 强连通分量：有向图的极大强连通子图称为该图的强连通分量

  • 关结点和重连通图

  • 权和网

    • 边上带有权的图称为带权图，也称作网

图的存储结构

  • 邻接矩阵

    • 存储方法
      • G不带权
A[i][j]={1    ，(i,j)∈E(G)或者<i,j>∈E(G)0    ，其他 A[i][j]=\left\{ \begin{matrix} 1~~~~，(i,j) \in E(G)或者<i,j> \in E(G)\\ 0~~~~，其他 \end{matrix} \right.
      • G带权
A[i][j]={wij    ，i≠j并且(i,j)∈E(G)或者<i,j>∈E(G)0    ，i=j∞    ,其他 A[i][j]=\left\{ \begin{matrix} w_{ij}~~~~，i \neq j 并且(i,j) \in E(G) 或者 <i,j> \in E(G) \\ 0~~~~，i = j \\ \infty~~~~,其他 \end{matrix} \right.
      • 三个邻接矩阵
A1=[0101110110010111110110110] A_1=\begin{bmatrix} 0&1&0&1&1\\ 1&0&1&1&0\\ 0&1&0&1&1\\ 1&1&1&0&1\\ 1&0&1&1&0\\ \end{bmatrix} A2=[0101000110000110000010010]A_2=\begin{bmatrix} 0&1&0&1&0\\ 0&0&1&1&0\\ 0&0&0&1&1\\ 0&0&0&0&0\\ 1&0&0&1&0\\ \end{bmatrix} A3=[08∞5∞∞03∞∞∞∞0∞6∞∞90∞∞∞∞∞0]A_3=\begin{bmatrix} 0&8&\infty&5&\infty\\ \infty&0&3&\infty&\infty\\ \infty&\infty&0&\infty&6\\ \infty&\infty&9&0&\infty\\ \infty&\infty&\infty&\infty&0\\ \end{bmatrix}

如果这篇文章对你有帮助，你可以请作者喝一杯蜜雪冰城。

其他文章
cover
code
JWT入门与实践
  • 23/03/29
  • 21:03
  • 3.2k
  • 14
cover
算法
Leetcode刷题笔记
  • 23/03/23
  • 19:23
  • 5.5k
  • 21
© 2023- 2023 一个很闲的vegetable
由 Hexo 驱动 v6.3.0 主题 - Async v2.0.4
我们永远不会止步不前！！！