张利源 blog

数据结构学习笔记【持续更新。。】

队列

  • 队列是一个有序列表，可以用数组或者链表实现。(数组实现是顺序存储，链表实现是链式存储)。
  • 遵循先入先出的原则，及现存如的数据，要先取出。后存入的数据要后取出。

数组模拟队列

代码实现

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
package day1队列;

/**
 * @author zhang
 * @date 2020/12/15 20:55
 */
public class ArrayQueueDemo {
    public static void main(String[] args) {
        ArrayQueue queue = new ArrayQueue(3);
        queue.addQueue(1);
        queue.addQueue(2);
        queue.addQueue(3);
        System.out.println(queue.headQueue());
        //queue.showQueue();
        int i = queue.getQueue();
        //queue.showQueue();
        System.out.println(queue.headQueue());
    }
}

class ArrayQueue{
    private int maxSize;//最大容量
    private int front;//队列头
    private int rear;//队列尾
    private int[] arr;//该数组用于存放数据，模拟队列

    public ArrayQueue(int maxSize){
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
        front = -1;//指向队列头部，分析出front是指向队列头的前一个位置
        rear = -1;
    }

    //判断队列是否满
    public boolean isFull(){
        return rear == maxSize - 1;
    }

    //判断队列是否为空
    public boolean isEmpty(){
        return rear == front;
    }

    //添加数据到队列
    public void addQueue(int n){
        //判断队列是否满了
        if (isFull()){
            System.out.println("队列已经满了");
            return;
        }
        rear++;
        arr[rear] = n;
    }

    //数据取出队列，出队列
    public int getQueue(){
        //判断数组是否为空
        if (isEmpty()){
            //抛出异常
            throw new RuntimeException("队列为空，不能取数据");
        }

        front++;
        return arr[front];
    }

    //显示队列的所有数据
    public void showQueue(){
        if (isEmpty()){
            System.out.println("队列为空，没有数据");
            return;
        }
        //Arrays.toString(arr);
        for (int i = front + 1; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    //显示对头数据
    public int headQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列空的，没有数据");
        }
        return arr[front + 1];
    }

}

数据不能重复使用。

数组模拟环形队列

思路调整

  1. front变量的含义做一个调整:front就是指向队列的第一个元素，front的初始值为0。
  2. rear变量的含义做一个调整:rear指向队列的最后元素的后一个位置，rear的初始值为0。
  3. 当队列满时，条件是(rear + 1) % maxSize = front
  4. 队列为空时，条件是rear == front
  5. 队列中有效数据的个数(rear + maxSize - front) % 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
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
package day1队列;

/**
 * @author zhang
 * @date 2020/12/15 22:23
 */
public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        CircleArrayQueue queue = new CircleArrayQueue(4);//有效数据最大是3
        queue.addQueue(1);
        queue.addQueue(2);
        queue.addQueue(3);
        int i = queue.getQueue();
        int i2 = queue.getQueue();
        queue.showQueue();
        System.out.println(queue.size());
        System.out.println(queue.headQueue());
    }
}

class CircleArrayQueue{
    private int maxSize;//最大容量
    private int front;//队列头
    private int rear;//队列尾
    private int[] arr;//该数组用于存放数据，模拟队列

    public CircleArrayQueue(int maxSize){
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
        front = 0;//指向队列头部，分析出front是指向队列头的前一个位置
        rear = 0;
    }

    //判断队列是否满
    public boolean isFull(){
        return (rear + 1) % maxSize == front;
    }

    //判断队列是否为空
    public boolean isEmpty(){
        return rear == front;
    }

    //添加数据到队列
    public void addQueue(int n){
        //判断队列是否满了
        if (isFull()){
            System.out.println("队列已经满了");
            return;
        }
        arr[rear] = n;
        //将rear后移
        rear = (rear + 1) % maxSize;
    }

    //数据取出队列，出队列
    public int getQueue(){
        //判断数组是否为空
        if (isEmpty()){
            //抛出异常
            throw new RuntimeException("队列为空，不能取数据");
        }

        int val = arr[front];
        //front后移
        front = (front + 1) % maxSize;
        return val;
    }

    //显示队列的所有数据
    public void showQueue(){
        if (isEmpty()){
            System.out.println("队列为空，没有数据");
            return;
        }
        //Arrays.toString(arr);
        for (int i = front ; i < front + size(); i++) {
            System.out.printf("arr[%d]=%d\n",i % maxSize,arr[i % maxSize]);
        }
    }

    //显示对头数据
    public int headQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列空的，没有数据");
        }
        return arr[front];
    }

    //求出当前队列有效数据的个数
    public int size(){
        return (rear + maxSize - front) % maxSize;
    }

}

链表

![链表物理结构示意图](https://cdn.jsdelivr.net/gh/zhangliyuangit/img/未命名文件 (1).png)

![逻辑结构示意图](https://cdn.jsdelivr.net/gh/zhangliyuangit/img/未命名文件 (2).png)

  • 链表以节点的方式来存储，是链式存储。
  • 每个节点包含data域，next域(指向下一个节点)。
  • 内内地址不一定连续。
  • 链表分为带头结点的链表和不带头节点的链表。

单链表的实际应用

使用带头结点的单链表实现-水浒英雄排行榜管理

1）完成对英雄人物的增删改查

2）第一种方式在添加英雄时，根据排名将英雄插入到链表的尾部

3）第二种方式在添加英雄时，根据排名将英雄插入到指定位置

![](https://cdn.jsdelivr.net/gh/zhangliyuangit/img/未命名文件 (3).png)

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
package day2链表;

/**
 * @author zhang
 * @date 2020/12/16 22:33
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(new HeroNode(1,"松江","及时雨"));
        singleLinkedList.add(new HeroNode(2,"卢俊义","玉麒麟"));
        singleLinkedList.add(new HeroNode(3,"吴用","智多星"));
        singleLinkedList.add(new HeroNode(4,"林冲","豹子头"));
        singleLinkedList.list();
    }
}


/**
 * 定义一个SingleLinedList管理我们的英雄
 */
class SingleLinkedList{

    //初始化一个头节点
    private HeroNode head = new HeroNode(0,"","");

    /**
     *  添加节点到单链表
     *  1.找到当前链表的的最后节点(next为空)
     *  2.将最后节点的next指向新的节点
     */
    public void add(HeroNode heroNode){
        HeroNode temp = head;
        while (temp.next != null){
            //后移
            temp = temp.next;
        }
        temp.next = heroNode;
    }

    public void list(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //头节点不能动，需要一个辅助变量来遍历
        HeroNode temp = head;
        while (temp.next != null){
            System.out.println(temp.next);
            //将next后移
            temp = temp.next;
        }
    }

}

/**
 * 每一个英雄都是一个节点
 */
class HeroNode{
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;//指向下一个节点


    public HeroNode(int no,String name,String nickName){
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

第二种方式在添加英雄时，根据排名将英雄插入到指定位置

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
/**
 * 第二种方式在添加英雄时，根据排名将英雄插入到指定位置
 */
public void addByOrder(HeroNode heroNode){
    HeroNode temp = head;
    boolean flag = false;//表示添加的编号是否存在默认为false
    while (true){
        if (temp.next == null){
            //说明temp已经在链表的最后面了
            break;
        }
        if (temp.next.no > heroNode.no){
            //位置找到，就在temp的后面插入
            break;
        }
        else if (temp.next.no == heroNode.no){
            //说明要添加的编号已经存在了
            flag = true;
            break;
        }
        //后移，遍历链表
        temp = temp.next;
    }

    if (flag == true){
        System.out.printf("待插入的英雄的编号[%d]已经存在了，不能加入\n",heroNode.no);
    }else {
        //新的节点的next指向temp.next
        //temp.next等于新的节点
        heroNode.next = temp.next;
        temp.next = heroNode;
    }
}

删除节点

思路：

  1. 首先找到要删除节点的前一个节点temp
  2. temp.next = temp.next.next
  3. 被删除的节点，没有任何引用指向它，将会被GC回收

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void delete(int no){
    HeroNode temp = head;
    boolean flag = false;//表示是否找到待删除节点
    while (true){
        if (temp.next == null){
            //已经到链表的最后了
            break;
        }
        if (temp.next.no == no){
            //说明找到了待删除节点的前一个节点temp
            flag = true;
            break;
        }
        temp = temp.next;
    }

    if (flag){
        //找到
        temp.next = temp.next.next;
    }else {
        System.out.printf("没有找到待删除的节点[%d]\n",no);
    }
}

单链表常见面试题

1.单链表的反转

思路：

  • 先定义一个节点reverseHead = new Node();
  • 从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新链表reverseHead的最前端
  • 原来的链表的head.next = reverseHead.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
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
155
package day3双向列表;

/**
 * @author zhang
 * @date 2020/12/27 17:17
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        DoubleLindedList doubleLindedList = new DoubleLindedList();
        doubleLindedList.add(new Node(1,"宋江"));
        doubleLindedList.add(new Node(2,"卢俊义"));
        doubleLindedList.add(new Node(3,"吴用"));
        doubleLindedList.add(new Node(4,"林冲"));

        doubleLindedList.list();

        doubleLindedList.update(new Node(3,"公孙胜"));
        doubleLindedList.list();

        doubleLindedList.delete(2);
        doubleLindedList.list();

    }
}

//创建一个双向链表的类
class DoubleLindedList{
    private Node head = new Node(0,"");


    //返回头节点
    public Node getHead(){
        return head;
    }

    //遍历双向链表的一个方法
    public void list(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }

        Node temp = head.next;
        while (true){
            //判断链表是否到最后
            if (temp.next == null){
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //节点后移
            temp = temp.next;
        }
    }

    //添加一个节点到双向链表的最后
    public void add(Node node){
        Node temp = head;
        //遍历节点，找到最后
        while (true){
            //找到链表最后
            if (temp.next == null){
                break;
            }
            temp = temp.next;
        }
        //形成一个双向链表
        temp.next = node;
        node.pre = temp;
    }

    //修改一个节点的内容
    public void update(Node node){
        //判断是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        Node temp = head;
        boolean flag = false;//表示是否找到该节点
        while (true){
            if (temp == null){
                break;
            }
            if (temp.no == node.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag){
            temp.name = node.name;
        }else {
            System.out.printf("没有找到编号为[%d]的节点",node.no);
        }

    }

    /**
     *   删除一个节点
     *   对于双向链表，我们直接找到要删除的节点，找到后自我删除即可
     */
    public void delete(int no){
        //判断当前链表是否为空
        if (head.next == null){
            System.out.println("链表为空,无法删除");
            return;
        }
        Node temp = head.next;
        boolean flag = false;
        while (true){
            if (temp == null){
                //已经到链表的最后节点的next
                break;
            }
            if (temp.no == no){
                //找到待删除的节点
                flag = true;
                break;
            }
            //temp后移
            temp = temp.next;
        }
        if (flag){
            //删除
            temp.pre.next = temp.next;
            //这样有风险，如果是最后一个节点，就不需要执行，否则空指针异常
            if (temp.next != null){
                temp.next.pre = temp.pre;
            }
        }
    }
}

class Node{
    public int no;
    public String name;
    public Node next;//指向下一个节点,默认为null
    public Node pre;//指向前一个节点，默认为null

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}

单向环形链表

约瑟夫问题

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

假设n=5，即有5个人。

k=1，从第一个人开始报数

m=2，数两下

构建一个单向循环链表的的思路(curNode的next指向新的元素，新的元素的next指向first，curNode后移)

  1. 先构建第一个节点，让first指向该节点，并形成环。
  2. 后面我们没创建一个新的节点，就把该节点，加入到已有的环形链表即可

遍历环形链表

  1. 先让一个辅助指针指向first节点
  2. 后通过一个while循环遍历该环形链表即可(current.next == first)

出圈

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
package day4单向循环链表;

/**
 * @author zhang
 * @date 2020/12/27 20:39
 */
public class Josepfu {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addNode(5);//加入5个节点
        //circleSingleLinkedList.list();

        //测试出圈
        circleSingleLinkedList.out(1,2,5);
    }
}

//创建一个环形的单向链表
class CircleSingleLinkedList{
    //创建一个first节点，当前没有编号
    private Node first = null;

    //添加node节点，构建成一个环形链表
    public void addNode(int nums){
        //数据校验
        if (nums < 1){
            throw new RuntimeException("非法参数");
        }
        Node curNode = null;//辅助指针
        for (int i = 1; i <= nums; i++) {
            //根据编号创建node节点
            Node node = new Node(i);
            //如果是第一个node
            if (i == 1){
                first = node;
                first.setNext(first);//构成一个环，只是环中只有一个元素
                curNode = first;//curNode指向第一个节点
            }else {
                curNode.setNext(node);
                node.setNext(first);
                curNode = node;
            }
        }
    }

    //遍历当前环形链表
    public void list(){
        //判空
        if (first == null){
            System.out.println("链表为空");
            return;
        }

        //first不能动，使用辅助指针完成遍历
        Node curNode = first;
        while (true){
            System.out.printf("NODE节点的编号 %d \n",curNode.getNo());

            if (curNode.getNext() == first){
                //说明遍历完毕
                break;
            }
            //后移
            curNode = curNode.getNext();
        }
    }

    /**
     * 根据用户的输入，计算出出圈的顺序
     * @param startNode 从第几个节点开始
     * @param countNum  表示数几下
     * @param nums      表示最初有多少节点在圈中
     */
    public void out(int startNode,int countNum,int nums){
        //数据校验
        if (first == null || startNode < 1 || startNode > nums){
            throw new RuntimeException("非法参数");
        }

        //创建一个辅助指针
        Node helper = first;
        //让helper指向了最后一个节点
        while (helper.getNext() != first) {
            helper = helper.getNext();
        }
        //报数之前，first和helper先移动k-1次
        for (int i = 0; i < startNode - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }

        //当小孩报数时，让first和helper指针移动m-1次，然后出圈
        while (true){
            if (helper == first){
                //说明圈中只有一个节点
                break;
            }
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //这是first指向的节点，就是要出圈的节点
            System.out.printf("节点%d出圈 \n",first.getNo());

            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的节点 %d \n",first.getNo());

    }
}


//节点类
class Node{
    private int no;
    private Node next;//下一个节点，默认是null

    public Node(int no){
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

评论