线性表

发表于 | 分类于 |

线性表

线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是$n$个具有相同特性的数据元素的有限序列。

前驱元素：若A元素在B元素的前面，则称A为B的前驱元素。

后继元素：若B元素在A元素的后面，则称B为A的后继元素。

线性表的特征：数据元素之间具有一种“一对一”的逻辑关系。

  • 第一个数据元素没有前驱，这个元素被称为头结点；
  • 最后一个数据元素没有后继，这个元素被称为尾结点；
  • 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。

如果把线性表用数学语言来定义，则可以表示为$(a_1,a_2…a_i,a_{i+1}…a_n)$，称$a_{i-1}$是$a_i$的前驱元素，$a_{i+1}$是$a_i$的后继元素。

线性表的分类：

线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为顺序表和链表。

顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指一组地址连续的存储单元，依次存储线性表中的各个元素、使得线性表中在逻辑结构上相应的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

顺序表的API设计：

类名 SequenceList\
构造方法 SequenceList(int capacity)
成员方法 public void clear()
public boolean isEmpty()
public int length()
public T get(int i)
public void insert(int i, T t)
public void insert(T t)
public T remove(int i)
public int indexOf(T t)
成员变量 private T[] eles
private int 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
public class SequenceList<T>{
    //存储元素的数组
    private T[] eles;
    //记录当前顺序表中的元素个数
    private int N;
    //构造方法
    public SequenceList(int capacity){
        //初始化数组
        this.eles = (T[])new Object[capacity];
        //初始化长度
        this.N = 0;
    }
    //将一个线性表置空
    public void clear(){
        this.N = 0;
    }
    //判断当前线性表是否为空
    public boolean isEmpty(){
        return this.N == 0;
    }
    //获取当前线性表的长度
    public int length(){
        return this.N;
    }
    //获取指定位置的元素
    public T get(int i){
        return eles[i];
    }
    //向线性表中添加元素t
    public void insert(T t){
        eles[N++] = t;
    }
    //在i元素处插入元素t
    public void insert(int i, T t){
        //先把i索引处及其后面的元素依次向后移动
        for(int index = N; index > i; index--){
            eles[index] = eles[index - 1];
        }
        //把t元素放到i索引处
        eles[i] = t;
        N++;
    }
    //删除指定位置i处的元素，并返回该元素
    public T remove(int i){
        //记录索引i处的指
        T current = eles[i];
        //索引i后面的元素依次向前移动一位
        for(int index = i; index < N -1; index++){
            eles[index] = eles[index + 1];
        }
        N--;
        return current;
    }
    //查找t元素第一次出现的位置
    public int indexOf(T t){
        for(int i = 0; i < N; i++){
            if(eles[i].equals(t)){
                return i;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class SequenceListTest{
    public static void main(String[] args){
        //创建顺序表对象
        SequenceList<String> sl = new SequenceList<>(10);
        //测试插入
        sl.insert("qwe");
        sl.insert("asd");
        sl.insert(1,"zxc");
        //获取测试
        String result = sl.get(1);
        System.out.println(result);
        //测试删除
        String removeResult = sl.remove(0);
        System.out.println(removeResult);
        //测试清空
        sl.clear();
        System.out.println(sl.length());
    }
}

顺序表的遍历：

一般作为容器存储数据，都需要向外部提供遍历的方式，因此我们需要给顺序表提供遍历方式。在Java中，遍历集合的方式一般都是$foreach$循环，如果想让我们的$SequenceList$也能支持$foreach$循环，则需要做如下操作：

  • 让$SequenceList$实现$Iterable$接口，重写iterator方法；
  • 让$SequenceList$内部提供一个内部类$SIterator$，实现$Iterator$接口，重写$hasNext$方法和$next$方法；
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
public class SequenceList<T> implements Iterable<T>{
    //存储元素的数组
    private T[] eles;
    //记录当前顺序表中的元素个数
    private int N;
    //构造方法
    public SequenceList(int capacity){
        //初始化数组
        this.eles = (T[])new Object[capacity];
        //初始化长度
        this.N = 0;
    }
    //将一个线性表置空
    public void clear(){
        this.N = 0;
    }
    //判断当前线性表是否为空
    public boolean isEmpty(){
        return this.N == 0;
    }
    //获取当前线性表的长度
    public int length(){
        return this.N;
    }
    //获取指定位置的元素
    public T get(int i){
        return eles[i];
    }
    //向线性表中添加元素t
    public void insert(T t){
        eles[N++] = t;
    }
    //在i元素处插入元素t
    public void insert(int i, T t){
        //先把i索引处及其后面的元素依次向后移动
        for(int index = N; index > i; index--){
            eles[index] = eles[index - 1];
        }
        //把t元素放到i索引处
        eles[i] = t;
        N++;
    }
    //删除指定位置i处的元素，并返回该元素
    public T remove(int i){
        //记录索引i处的指
        T current = eles[i];
        //索引i后面的元素依次向前移动一位
        for(int index = i; index < N -1; index++){
            eles[index] = eles[index + 1];
        }
        N--;
        return current;
    }
    //查找t元素第一次出现的位置
    public int indexOf(T t){
        for(int i = 0; i < N; i++){
            if(eles[i].equals(t)){
                return i;
            }
        }
        return -1;
    }
    
    @Override
    public Iterator<T> iterator(){
        return new SIterator();
    }
    
    private class SIterator implements Iterator{
        private int cusor;
        public SIterator(){
            this.cusor = 0;
        }
        @Override
        public boolean hasNext(){
            return this.cusor < N;
        }
        
        @Override
        public Object next(){
            return eles[cusor++];
        }
    }
}

顺序表的容量可变：

在之前的实现中，当我们使用$SequenceList$时，先$new SequenceLsit(5)$创建一个对象，创建对象时就需要指定容器大小，初始化指定大小的数组来存储元素，当我们插入元素时，如果已经插入了5个元素，还要继续插入数据，就会报错，就不能插入了。这种设计不符合容器的设计理念，因此我们在设计顺序表时，应该它的容量的伸缩性。

  • 添加元素时：添加元素时，应该检查当前数组的大小是否能够容纳新的元素，如果不能容纳，则需要创建新的容量更大的数组，我们这里创建一个是原数组两倍容量的新数组存储元素。
  • 移除元素时，应该检查当前数组的大小是否太大，比如正在用100个容量的数组存储10个元素，这样就会造成内存空间的浪费，应该创建一个容器更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4，则创建一个是原数组容量的1/2的新数组存储元素。
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
public class SequenceList<T> implements Iterable<T>{
    //存储元素的数组
    private T[] eles;
    //记录当前顺序表中的元素个数
    private int N;
    //构造方法
    public SequenceList(int capacity){
        //初始化数组
        this.eles = (T[])new Object[capacity];
        //初始化长度
        this.N = 0;
    }
    //将一个线性表置空
    public void clear(){
        this.N = 0;
    }
    //判断当前线性表是否为空
    public boolean isEmpty(){
        return this.N == 0;
    }
    //获取当前线性表的长度
    public int length(){
        return this.N;
    }
    //获取指定位置的元素
    public T get(int i){
        return eles[i];
    }
    //向线性表中添加元素t
    public void insert(T t){
        if(this.N == eles.length){
            resize(2 * eles.length);
        }
        eles[N++] = t;
    }
    //在i元素处插入元素t
    public void insert(int i, T t){
        if(N==eles.length){
            resize(2 * eles.length);
        }
        //先把i索引处及其后面的元素依次向后移动
        for(int index = N; index > i; index--){
            eles[index] = eles[index - 1];
        }
        //把t元素放到i索引处
        eles[i] = t;
        N++;
    }
    //删除指定位置i处的元素，并返回该元素
    public T remove(int i){
        //记录索引i处的指
        T current = eles[i];
        //索引i后面的元素依次向前移动一位
        for(int index = i; index < N -1; index++){
            eles[index] = eles[index + 1];
        }
        N--;
        
        if(N < (eles.length / 4)){
            resize(eles.length / 2);
        }
        return current;
    }
    //查找t元素第一次出现的位置
    public int indexOf(T t){
        for(int i = 0; i < N; i++){
            if(eles[i].equals(t)){
                return i;
            }
        }
        return -1;
    }
    //根据参数newSize，重置eles的大小
    public void resize(int newSize){
        //定义一个临时数组，指向原数组
        T[] temp = this.eles;
        //创建新数组
        eles = (T[])new Object[newSize];
        //把原数组的数据拷贝到新数组即可
        for(int i = 0; i < N; i++){
            eles[i] = temp[i];
        }
    }
    
    @Override
    public Iterator<T> iterator(){
        return new SIterator();
    }
    
    private class SIterator implements Iterator{
        private int cusor;
        public SIterator(){
            this.cusor = 0;
        }
        @Override
        public boolean hasNext(){
            return this.cusor < N;
        }
        
        @Override
        public Object next(){
            return eles[cusor++];
        }
    }
}

顺序表的时间复杂度：

  • $get(i)$：不难看出，不论数据元素量N有多大，只需要$eles[i]$就可以获取到对应的元素，所以时间复杂度为$O(1)$；
  • $insert(int i, T t)$：每一次插入，都需要把$i$位置后面的元素移动一次，随着元素数量$N$的增大，移动的元素也越多，时间复杂度为$O(n)$；
  • $remove(int i)$：每一次删除，都需要把$i$位置后面的元素移动一次，随着元素数量$N$的增大，移动的元素也越多，时间复杂度为$O(n)$；

由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些需要扩容处的节点处，耗时会突增，尤其是元素越多，这个问题越明显。

Java中$ArrayList$实现：

Java中$ArrayList$集合的底层也是一种顺序表，使用数组实现，同样提供了增删改查以及扩容等功能。

链表

前面已经使用顺序存储结构实现了线性表，我们可以发现虽然顺序表的查询很快，时间复杂度为$O(1)$，但是增删的效率是比较低的，因为每一次增删操作都伴随着大量的数据元素移动。

链表是一种物理存储单元非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点(链表中的每一个元素称为结点)组成，结点可以在运行时动态生成。

结点API设计：

类名 Node\
构造方法 Node(T t, Node next)
成员变量 T item
Node next

结点类的实现：

1
2
3
4
5
6
7
8
public class Node<T>{
    public T item;
    public Node next;
    public Node(T item, Node next){
        this.item = item;
        this.next = next;
    }
}

生成链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) throws Exception{
    //构建结点
    Node<Integer> first = new Node<Integer>(11,null);
    Node<Integer> second = new Node<Integer>(13,null);
    Node<Integer> third = new Node<Integer>(12,null);
    Node<Integer> fourth = new Node<Integer>(8,null);
    Node<Integer> fifth = new Node<Integer>(9,null);
    //生成链表
    first.next = second;
    second.next = third;
    third.next = fourth;
    fourth.next = fifth;
}

单向链表

单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据，指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。

单向链表的API设计：

类名 LinkList\
构造方法 LinkList()
成员方法 public void clear()
public boolean isEmpty()
public int length()
public T get(int i)
public void insert(T t)
public void insert(int i, T t)
public T remove(int i)
public int indexOf(T t)
成员内部类 private class Node\
成员变量 private Node head
private int 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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
public class LinkList<T> implements Iterable<T>{
    //记录头结点
    private Node head;
    //记录链表长度
    private int N;
    //结点类
    private class Node{
        //存储数据
        T item;
        //下一结点
        Node next;
        public Node(T item, Node next){
            this.item = item;
            this.next = next;
        }
    }
    
    public LinkList(){
        //初始化头结点
        this.head = new Node(null,null);
        //初始化元素个数
        this.N = 0;
    }
    
    //清空链表
    public void clear(){
        this.head.next = null;
        this.N = 0;
    }
    
    //获取链表长度
    public int length(){
        return this.N;
    }
    
    //判断链表是否为空
    public boolean isEmpty(){
        return this.N == 0;
    }
    
    //获取指定位置i处的元素
    public T get(int i){
        //通过循环，从头结点往后找，依次找i次
        Node n = head.next;
        for(int index = 0; index < i; index++){
            n = n.next;
        }
        return n.item;
    }
    
    //向链表中插入元素t
    public void insert(T t){
        //找到当前最后一个结点
        Node n = head;
        while(n.next != null){
            n = n.next;
        }
        //创建新结点，保存元素t
        n.next = new Node(t,null);
        //让当前最后一个节点指向新节点
        N++;
    }
    
    //在指定的位置i处，添加元素t
    public void insert(int i, T t){
        //找到i位置前一个结点
        Node pre = head;
        for(int index = 0; index < i; i++){
            pre = pre.next;
        }
        //找到i位置的结点
        //创建新结点，并且新结点需要指向原来i位置的结点
        pre.next = new Node(t,pre.next);
        N++;
    }
    
    //删除指定位置i处的元素，并返回被删除的元素
    public T remove(int i){
        //找到i位置的前一个结点
        Node pre = head;
        for(int index = 0; index < i; index++){
            pre = pre.next;
        }
        //找到i位置的结点
        Node curr = pre.next;
        //找到i位置的下一个结点
        Node nextNode = curr.next;
        //前一结点指向下一结点
        pre.next = nextNode;
        //元素个数-1
        N--;
        return curr.item;
    }
    
    //查找元素t在链表中第一次出现的位置
    public int indexOf(T t){
        Node temp = head;
        for(int i = 0; temp != null;i++){
            temp = temp.next;
            if(temp.item.equals(t)){
                return i;
            }
        }
        return -1;
    }
    
    @Override
    public Iterator<T> iterator(){
        return new LIterator()
    }
    
    private class LIterator implements Iterator{
        private Node temp;
        public LIterator(){
            this.temp = head;
        }
        @Override
        public boolean hasNext(){
            return temp.next != null;
        }
        
        @Override
        public Object next(){
            temp = temp.next;
            return temp.item;
        }
    }
    
}

双向链表

双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域合和两个指针域组成，数据域用来存储数据，其中一个指针域用来指向后继结点，另一个指针用来指向前驱结点。链表的头结点的数据域不存储数据，指向前驱结点的指针值为null，指向后继结点的指针域指向第一个真正存储数据的结点。

结点API的设计：

类名 Node\
构造方法 Node(T t, Node pre, Node next)
成员变量 T item
Node next
Node pre

双向链表API的设计：

类名 TowWayLinkList\
构造方法 TowWayLinkList()
成员方法 public void clear()
public boolean isEmpty()
public int length()
public void insert(T t)
public void insert(int i, T t)
public T remove(int i)
public int indexOf(T t)
public T getFirst()
public T getLast()
成员内部类 private class Node\
成员变量 private Node first
private Node last
private int 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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
public class TowWayLinkList<T> implements Iterable<T>{
    //首结点
    private Node head;
    //尾结点
    private Node last;
    //链表长度
    private int N;
    //结点类
    private class Node{
        public T item;
        public Node pre;
        public Node next;
        
        public Node(T item, Node pre, Node next){
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }
    
    public TowWayLinkList(){
        //初始化头结点和尾结点
        this.head = new Node(null,null,null);
        this.last = null;
        //初始化元素个数
        this.N = 0;
    }
    
    //清空链表
    public void clear(){
        this.head.next = null;
        this.head.pre = null;
        this.head.item = null;
        this.last = null;
        this.N = 0;
    }
    
    //获取链表的长度
    public int length(){
        return this.N;
    }
    
    //判断链表是否为空
    public boolean isEmpty(){
        return this.N == 0;
    }
    
    //获取第一个元素
    public T getFirst(){
        if(isEmpty()){
            return null;
        }
        return head.next.item;
    }
    
    //获取最后一个元素
    public T getLast(){
        if(isEmpty()){
            return null;
        }
        return last.item;
    }
    
    //插入元素t
    public void insert(T t){
        //如果链表为空
        if(isEmpty){
            last = new Node(t,head,null);
            head.next = last;
        }else{
            last.next = new Node(t,last,null);
            last = last.next;
        }
        N++;
    }
    
    //在指定位置i处插入元素
    public void insert(int i, T t){
        //找到i位置前一个结点
        Node pre = head;
        for(int index = 0; index < i; index++){
            pre = pre.next;
        }
        //找到当前结点
        Node curr = pre.next;
        //创建新结点
        Node newNode = new Node(t,pre,curr);
        pre.next = newNode;
        curr.pre = newNode;
        N++;
    }
    
    //获取指定位置i处的元素
    public T get(int i){
        Node temp = head.next;
        for(int index = 0; index < i; index++){
            temp = temp.next;
        }
        return temp.item;
    }
    
    //找到元素t在链表中第一次出现的位置
    public int indexOf(T t){
        Node temp = head;
        for(int i = 0; temp.next != null; i++){
            temp = temp.next;
            if(temp.item.equals(t)){
                return i;
            }
        }
    }
    
    //删除位置i处的元素
    public T remove(int i){
        //找到i位置的前一个结点
        Node pre = head;
        for(int index = 0; index < i; i++){
            pre = pre.next;
        }
        //找到i位置的结点
        Node curr = pre.next;
        //找到i位置的下一个结点
        Node nextNode = curr.next;
        //让i位置的前一个结点的下一个结点变为i位置的下一个结点
        pre.next = nextNode;
        nextNode.pre = pre;
        N--;
        
        return curr.item;
    }
    
    @Override
    public Iterator<T> iterator(){
        return new Titerator();
    }
    
    private class TIterator implements Iterator{
        private Node n;
        public TIterator(){
            this.n = head;
        }
        
        @Override
        public boolean hasNext(){
            return n.next != null;
        }
        
        @Override
        public Object next(){
            n = n.next;
            return n.item;
        }
    }
}

Java中LinkedList实现：

java中LinkedList集合也是使用双向链表实现，并提供了增删改查等相关方法。

链表的复杂度分析：

  • $get(int i)$：每一次查询，都需要从链表的头部开始，依次向后查找，随着数据元素N的增多，比较元素越多，时间复杂度为$O(n)$。
  • $insert(int i, T t)$：每一插入，需要找到i位置的前一个元素，然后完成插入操作，随着元素数量N的增多，查找的元素越多，时间复杂度为$O(n)$。
  • $remove(int i)$：每一次移除，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为$O(n)$。

相比较顺序表，链表插入和删除的时间复杂度虽然一样，然仍然有很大的优势，因为链表的物理地址是不连续的，它不需要预定指定存储空间大小，或者在存储过程中涉及到扩容等操作，同时它并没有涉及到元素的交换。

相比较顺序表，链表的查询操作性能会比较低。因此，如果我们的程序中查询操作比较多，建议使用顺序表，增删操作比较多，建议使用链表。

链表反转：

需求：

  • 原链表中数据为：1->2->3->4
  • 反转后链表中数据为：4->3->2->1

反转API：

  • public void reverse()：对整个链表反转
  • public Node reverse(Node curr)：反转链表中某个节点curr，并把反转后的curr结点返回

使用递归可以完成反转，递归反转其实就是从原链表的第一个存放数据的结点开始，依次递归调用反转每一个节点，直到把最后一个结点反转完毕，整个链表就反转完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void reverse(){
    if(isEmpty()){
        return;
    }
    reverse(head.next);
}

public Node reverse(Node curr){
    if(curr.next == null){
        head.next = curr;
        return curr;
    }
    Node pre = reverse(curr.next);
    pre.next = curr;
    curr.next = null;
    return curr;
}

快慢指针：

快慢指针的定义是，这两个指针的移动速度一快一慢，以此来制造出自己想要的差值，这个差值可以让我们找到链表上相应的结点。一般情况下，快指针的移动步长为慢指针的两倍。

中间值问题：

1
2
3
4
5
6
7
8
9
10
public static String getMid(Node<String> first){
    Node<String> fast = first;
    Node<String> slow = first;
    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow.item;
}

单向链表是否有环问题：

1
2
3
4
5
6
7
8
9
10
11
12
public static boolean isCircle(Node first){
    Node fast = first;
    Node slow = first;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
        if(fast = slow){
            return true
        }
    }
    return false;
}

有环链表入口问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static Node getEntrance(Node first){
    Node fast = first;
    Node slow = first;
    Node temp = null;
    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast){
            temp = first;
            continue;
        }
        if(temp != null){
            temp = temp.next;
            if(temp == slow){
                break;
            }
        }
    }
    return temp;
    
}

循环链表：

链表整体要形成一个圆环状。在单向链表中，最后一个结点的指针为null，不指向任何结点，因为没有下一个元素了。要实现循环链表，我们只需要让单向链表的最后一个结点的指针指向头结点即可。

约瑟夫问题：

41个人坐一圈，第一个人编号为1，第二个编号为2，第n个人编号为n。编号为1的人开始报数，依次向后，报数为3的那个人退出圈；自退出那个人开始的下一个人再次从1开始报数，以此类推；求出最后退出的那个人的编号。

解题思路：

构建含有41个结点的单向循环链表，分别存储1~41的值，代表这41个人；使用计数器count，记录当前报数的值；遍历链表，每循环一次，count++；判断count的值，如果是3，则从链表中删除这个结点并打印结点的值，把count重置为0。

代码实现：

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
public class JosephTest{
    public static void main(String[] args){
        Node<Integer> first = null;
        Node<Integer> pre = null;
        for(int i = 1; i <= 41; i++){
            if(i == 1){
                first = new Node<>(i,null);
                pre = first;
                continue;
            }
            Node<Integer> newNode = new Node<>(i,null);
            pre.next = newNode;
            pre = newNode;
            if(i == 41){
                pre.next = first;
            }
        }
        int count = 0;
        Node<Integer> temp = first;
        Node<Integer> before = null;
        while(temp != temp.next){
            count++;
            if(count == 3){
                before.next = temp.next;
                System.out.println(temp.item);
                count = 0;
                temp = temp.next;
            }else{
                before = temp;
                temp = temp.next;
            }
        }
    }
    
    private static class Node<T>{
        T item;
        Node next;
        
        public Node(T item, Node next){
            this.item = item;
            this.next = next;
        }
    }
}

栈

栈是一种基于先进后出(FILO)的数据结构，是一种只能进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。

我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。

栈的API设计：

类名 Stack\
构造方法 Stack()
成员方法 public boolean isEmpty()
public int size()
public T pop()
public void push(T t)
成员变量 private Node head
private int N
成员内部类 private class Node

栈的代码实现：

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
71
72
73
74
public class Stack<T> implements Iterable<T>{
    private Node head;
    
    private int N;
    
    private class Node{
        public T item;
        public Node next;
        
        public Node(T item, Node next){
            this.item = item;
            this.next = next;
        }
    }
    
    public Stack(){
        this.head = new Node(null,null);
        this.N = 0;
    }
    
    public boolean isEmpty(){
        return this.N == 0;
    }
    
    public int size(){
        return this.N;
    }
    
    public void push(T t){
        //找到首结点指向第一个结点
        Node oldFirst = head.next;
        //创建新结点
        Node newNode = new Node(t,null);
        //让新结点指向原来的第一个结点
        head.next = newNode;
        newNode.next = oldForst;
        N++;
    }
    
    public T pop(){
        //找到首结点指向的第一个结点
        Node oldFirst = head.next;
        if(oldFirst == null){
            return null;
        }
        //让首结点指向原来的第一个结点的下一个结点
        head.next = oldFirst.next;
        //元素个数-1
        N--;
        return oldFirst.item;
    }
    
    @Override
    public Iterator<T> iterator(){
        return new SIterator()
    }
    
    private class SIterator implements Iterator{
        private Node temp;
        public SIterator(){
            this.temp = head;
        }
        @Override
        public boolean hasNext(){
            return temp.next != null;
        }
        
        @Override
        public Object next(){
            temp = temp.next;
            return temp.item;
        }
    }
}

括号匹配问题：

问题描述：

给定一个字符串，里面可能包含“()”小括号和其他字符，通过程序检查该字符串中的小括号是否成对出现。

例如：

  • “(上海)(长安)”正确匹配
  • “(上海((长安))”正确匹配
  • “上海(长安(北京)(深圳)南京)”正确匹配
  • “上海(长安))”匹配错误
  • “((上海)长安”匹配错误

示例代码：

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
public class BracketsMatchTest{
    public static void main(String[] args){
        String str = "(上海(长安)())";
        boolean match = isMatch(str);
        System.out.println(match);
    }
    
    public static boolean isMatch(String str){
        //创建栈对象，用来存储左括号
        Stack<String> chars = new Stack<>();
        //从左往右遍历字符
        for(int i = 0; i < str.length(); i++){
            String currChar = str.charAt(i) +"";
            if(currChar.equals("(")){
                chars.push(currChar);
            }else if(currChar.equals(")")){
                String pop = chars.pop();
                if(pop == null){
                    return false;
                }
            }
        }
        //判断当前字符是否为左括号，如果是，则把字符放入栈中
        //继续判断当前字符是否有括号，如果是，则从栈中弹出一个左括号，并判断弹出的结果为null，如果为null证明没有匹配的左括号，如果不为null，则证明有匹配的左括号
        //判断栈中还有没有剩余的左括号
        if(chars.size() == 0){
            return true;
        }else{
            return false;
        }
    }
}

逆波兰表达式求值问题

中缀表达式：

中缀表达式就是生活中使用的表达式，例如：$1+3*2,2-(1+3)$等等，中缀表达式的特点是：二元运算符总是置于两个操作数中间。中缀表达式是人们最喜欢的表达方式，因为简单。但对于计算机来说就不是这样了，因为中缀表达式的运算顺序不具有规律性。不同的运算符具有不同的优先级，如果计算机执行中缀表达式，需要解析表达式语义，做大量的优先级相关操作。

逆波兰表达式(后缀表达式)：

逆波兰表达式是波兰逻辑学家J·卢卡西维兹于1929年提出的一种表达式的表示方法，后缀表达式的特点：运算符总是放在跟它相关的操作数之后。

中缀表达式 逆波兰表达式
a+b ab+
a+(b-c) abc-+
a+(b-c)*d abc-d*+
a*(b-c)+d abc-*d+

需求：

给定一个只包含加减乘除四种运算的逆波兰表达式的数组表示方法，求出该逆波兰表达式的结果。

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
public class ReversePolishNotationTest{
    //(3*(17-15)+18/6)
    String[] notation={"3","17","15","-","*","18","6","/","+"};
    int result = caculate(notation);
    System.out.println(result);
    
    public static int caculate(String[] notation){
        Stack<Integer> oprands = new Stack<Integer>;
        for(int i = 0; i < notation.length; i++){
            String curr = notation[i];
            Integer o1,o2,result;
            switch(curr){
                case "+":
                    o2 = oprands.pop();//注意弹栈的顺序
                    o1 = oprands.pop();
                    result = o1+o2;
                    oprands.push(result);
                    break;
                case "-":
                    o2 = oprands.pop();
                    o1 = oprands.pop();
                    result = o1-o2;
                    oprands.push(result);
                    break;
                case "*":
                    o2 = oprands.pop();
                    o1 = oprands.pop();
                    result = o1*o2;
                    oprands.push(result);
                    break;
                case "/":
                    o2 = oprands.pop();
                    o1 = oprands.pop();
                    result = o1/o2;
                    oprands.push(result);
                    break;
                default:
                    oprands.push(Integer.parseInt(curr));
                    break;
            }
        }
    }
    int result = oprands.pop();
    return result;
}

分析：

  • 创建一个栈对象oprands存储操作数
  • 从左向右依次遍历逆波兰表达式，拿到每一个字符
  • 判断字符串是否为运算符？如果不是，把该操作数压入栈中
  • 如果是运算符，则从栈中弹出两个操作数
  • 使用该运算符计算得到结果
  • 把该结果压入栈中
  • 遍历结束后，拿出栈中的结果返回

队列

队列是一种基于先进先出(FIFO)的数据结构，是一种只能在一端进行插入，在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先被读出来。

队列的API设计：

类名 Queue
构造方法 Queue()
成员方法 public boolean isEmpty()
public int size()
public T dequeue()
public void enqueue(T t)
成员变量 private Node head
private int N
private Node last
成员内部类 private class Node

队列的代码实现：

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
71
public class Queue<T> implements Iterable<T>{
    private Node head;
    private Node last;
    private int N;
    priavte class Node{
        public T item;
        public Node next;
        public Node(T item, Node next){
            this.item = item;
            this.next = next;
        }
    }
    
    public Queue(){
        this.head = new Node(null,null);
        this.last = null;
        this.N = 0;
    }
    
    public boolean isEmpty(){
        return this.N == 0;
    }
    
    public int size(){
        return this.N;
    }
    
    public void enqueue(T t){
        if(last == null){
            last = new Node(t,null);
            head.next = last;
        }else{
            Node oldlast = last;
            last = new Node(t,null);
            oldlast.next = last;
        }
        N++;
    }
    
    public T dequeue(){
        if(isEmpty()){
            return null;
        }
        Node oldFirst = head.next;
        head.next = oldFirst.next;
        N--;
        if(isEmpty()){
            last = null;
        }
        return oldFirst.item;
    }
    
    public Iterator<T> iterator(){
        return new QIterator();
    }
    
    priavte class QIterator implements iterator{
        private Node temp;
        public QIterator(){
            this.temp = head;
        }
        public boolean hasNext(){
            return temp.next != null;
        }
        
        public Object next(){
            temp = temp.next;
            return temp.item;
        }
    }
}
Donate comment here