1. 队列的特点
  2. 单向队列
  3. 环形队列
  4. 单向链表
  5. 双向链表
  6. 环形链表

以下只给出思路与关键方法,算法的源代码放在了git中,需要的自取

https://gitee.com/leidl97/algor

队列的特点

先进先出 (FIFO)

可以理解为排队,先排的先进入。如图所示

img

出自《算法第四版》第78页

单向队列

思想(如何定义数据)

用数组实现,头指针指向开始的前一个位置用-1表示,默认位置为0

尾指针指向最后一个元素的位置也用-1表示(初始情况下,没有元素,所以指向-1,当元素加入后尾指针会+1,将值添加到尾指针所在的位置)

img

判断队列为满

尾指针指向元素的最后一个位置

img

判断队列为空

头指针=尾指针

存入数据

先移在取。先让尾指针+1,在将值赋给尾指针所在的位置

取出数据

先移在取。取尾部数据,先让头指针+1,将头指针指向的位置取出

Java实现

写出这个队列的入队和出队方法,一般采用数组的方式实现

属性定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//数组最大容量
private int maxSize;
//队列头
private int begin;
//队列尾
private int end;
//存放队列的数组
private int[] arr;

public ArrayQueue(int maxSize){
//this可以省略,但是写上显得思路更清晰
this.maxSize = maxSize;
this.arr = new int[maxSize];
//队列头指向开始的前一个位置
this.begin = -1;
//队列尾指向最后的位置。虽然都是-1但表示的意义不同
this.end = -1;
}

判断队满

1
2
3
4
//判断队列是否未满,队列尾为数组最后一个元素
public boolean isFull(){
return this.end == this.maxSize - 1;
}

判断队空

1
2
3
4
//判断队列是否为空 头尾指针相等的时候
public boolean isEmpty(){
return this.begin == this.end;
}

添加数据到队列

1
2
3
4
5
6
7
8
//添加数据到队列
public void addQueue(int data){
//判断是否满
if (isFull()) {
throw new RuntimeException("队列满,不能加入数据");
}
this.arr[++this.end] = data;
}

获取队列数据

1
2
3
4
5
6
7
8
//获取队列的数据,取数据从后面取
public int getQueue(){
if (isEmpty()) {
//抛出异常,不用在写return
throw new RuntimeException("队列空,不可以取数据");
}
return this.arr[++this.begin];
}

显示队列数据

1
2
3
4
5
6
7
8
//获取队列的数据,取数据从后面取
public int getQueue(){
if (isEmpty()) {
//抛出异常,不用在写return
throw new RuntimeException("队列空,不可以取数据");
}
return this.arr[++this.begin];
}

显示队列头数据

1
2
3
4
5
6
7
//显示队列的头数据
public int getBegin(){
if (isEmpty()) {
throw new RuntimeException("该队列为空");
}
return this.arr[begin+1];
}

缺陷

不能够复用,用一次就废了,不能频繁添加和删除元素,解决方式为使用环形队列

环形队列

思想

可以想下需要用什么方法来实现复用呢,没错就是取模

所以定义数组的时候牺牲一个空间来做判断

不同的是,我们定义头指针指向第一个元素也就是0

尾指针指向数组末尾的下一个位置也为0

判断队列为空

头指针=尾指针。比如刚开始的时候

img

判断队列为满

(尾指针+1)%数组大小为头指针所在位置的时候队列为满

img

存入数据

与单向不同的是,这次是先存在移。先将尾指针指向的区域存入指定数据,然后移动到下一个位置

取出数据

先取在移。取出当前头指针指向的元素,然后移动到下一个位置

获取所有元素

遍历需要想明白?的位置应该怎么填写

1
for(int i = ?; i < ?; i++) 

第一个?的位置应该是当前头指针指向的元素下标

第二个?应该为当前头指针下标+元素的有效个数

如果不这么判断,那就需要判断两个指针谁前谁后的位置了

获取有效个数

(尾指针-头指针+数组大小)%数组大小

其实也就是尾指针-头指针的绝对值

Java实现

属性定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//数组最大容量
private int maxSize;
//队列头
private int begin;
//队列尾
private int end;
//存放队列的数组
private int[] arr;

//如果按照头指向第一个元素,尾指向最后一个元素,当为起始状态时无法判断为空还是为满
//定义添加数据尾指针移动,取数据头指针移动,这样设计牺牲了一个空间,也就是说默认最后一个位置不存数据
public CircleArrayQueue(int maxSize){
//this可以省略,但是写上显得思路更清晰
this.maxSize = maxSize;
this.arr = new int[maxSize];
//队列头指向元素的第一个位置
this.begin = 0;
//队列尾指向元素最后的位置
this.end = 0;
}

判断队满

1
2
3
4
//判断队列是否为满,尾+1%maxsize = 头 :头始终指向第一个元素当加1取模等于尾的时候说明满(尾表示最后一个元素+1)
public boolean isFull(){
return (this.end + 1)%maxSize == this.begin;
}

判断队空

1
2
3
4
//判断队列是否为空 头尾指针相等的时候
public boolean isEmpty(){
return this.begin == this.end;
}

添加数据

1
2
3
4
5
6
7
8
9
10
//添加数据到队列,尾指针+1
public void addQueue(int data){
//判断是否满
if (isFull()) {
throw new RuntimeException("队列满,不能加入数据");
}
arr[end] = data;
end = (end + 1) % maxSize;
System.out.println("存数据:"+data);
}

获取队列头数据

1
2
3
4
5
6
7
8
9
10
11
//获取队列的数据,头指针+1
public int getQueue(){
if (isEmpty()) {
//抛出异常,不用在写return
throw new RuntimeException("队列空,不可以取数据");
}
int data = arr[begin];
begin = (begin + 1) % maxSize;
System.out.println("取数据:"+data);
return data;
}

显示队列的所有数据

1
2
3
4
5
6
7
8
9
10
//显示队列的所有数据[注意取模]
public void getAllQueue(){
StringBuffer sb = new StringBuffer();
if (isEmpty()) {
throw new RuntimeException("该队列为空");
}
for (int i = begin; i< begin+getActive(); i++) {
System.out.println("arr["+i%maxSize+"]="+arr[i%maxSize]);
}
}

显示队列的有效数据

1
2
3
4
//显示队列的有效数据
public int getActive(){
return (end + maxSize - begin) % maxSize;
}

链表

又叫linked list,是有序的列表,一个地址,一个data域用于存数据,一个next域用于指向下一个地址

链表是以节点的方式存储的

每个节点包含data域,和next域

不一定是连续存储

img

图片来源于网络

单向链表

思路

首先定义一个节点类Node

有编号(ID),数据和下一个节点至少三个属性

定义一个节点类,初始化头节点,因为头节点不可以动所以定义辅助节点,用来添加和遍历

添加:尾插法,判断当前元素的下一个元素是否为空,如果是则在当前节点插入下一个节点,如果不是依次往后寻找,直到找到下一个为空的那个节点然后插入

遍历:先判断头节点的下一个元素是否为空,否则往下进行寻找,然后一次输出节点

缺点:不能按照编号顺序添加

img

Java实现

测试部分

1
2
3
4
5
6
7
8
9
10
MangerNode mangerNode = new MangerNode();
Node node1 = new Node(1, "1号老婆");
Node node2 = new Node(2, "2号老婆");
Node node3 = new Node(3, "3号老婆");
Node node4 = new Node(4, "4号老婆");
mangerNode.add(node1);
mangerNode.add(node2);
mangerNode.add(node3);
mangerNode.add(node4);
mangerNode.show();

定义结点

1
2
3
4
5
6
7
8
9
10
11
//标记当前节点序号
public int no;
//数据域
public String data;
//下一个节点
public Node next;

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

添加结点

1
2
3
4
5
6
7
8
9
10
11
//添加一个节点
public void add(Node node){
temp = head;
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
}
temp.next = node;
}

遍历链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//遍历链表
public void show(){
temp = head.next;
//判断是否为空
if(temp == null) {
System.out.println("链表为空");
} else {
while (true) {
System.out.println(temp);
if (temp.next == null){
break;
}
temp = temp.next;
}
}
}

如果要按照编号顺序添加

需要去遍历并且判断。从头节点开始,用temp作为辅助变量指向头节点,判断下一个元素的序号no是否大于插入的节点,如果是则找到当前元素。如果等于则为重复节点,否则继续遍历,直到下一个元素为空

添加代码如下

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
//添加一个节点(高级版)
public void addPro(Node node){
temp = head;
//默认没有重复元素
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.no > node.no) {
break;
} else if (temp.next.no == node.no) {
flag = true;
break;
}
temp = temp.next;
}
//添加元素
if (flag) {
System.out.println("有no为"+node.no+"重复元素不可以 添加");
} else {
node.next = temp.next;
temp.next = node;
}
}

修改:找到后直接修改即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//找到修改即可
public void update(Node node){
if (head.next == null) {
System.out.println("链表为空!");
} else {
temp = head.next;
while (true) {
if (temp.next == null){
break;
}
if (temp.no == node.no) {
temp.data = node.data;
break;
}
temp = temp.next;
}
}
}

删除:除了找到需要删除的B之外,还需要找到前一个节点A,原来A指向B,现在A指向C,最后删除B(直接赋值就相当于删除)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//找到A指向B成为指向C然后删除B
public void delete(Node node){
if (head.next == null) {
System.out.println("链表为空!");
} else {
temp = head;
while (true) {
if (temp.next == null){
break;
}
if (temp.next.no == node.no) {
temp.next = temp.next.next;
break;
}
temp = temp.next;
}
}
}

链表反转

思路

分为原来的链表和现在的链表

重要的核心步骤为

1、原来当前节点(cur)指向新头节点的下一个节点(new.next)

2、新头节点(new.next)的下一个指向当前节点(cur)

画个图

img

第一次移动

img

第二次移动

代码实现

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
public void reverse(Node headNode){
//当没有节点或者只有一个节点的时候直接返回结果
if (headNode.next == null || headNode.next.next == null) {
System.out.println("链表为空!");
}

//定义辅助变量cur,用于遍历原链表
Node cur = headNode.next;
//定义cur的下一个节点next,用来记录
Node next = null;
//定义新节点的头节点
Node newHead = new Node(0,"");
while (cur != null) {
//next指向cur的下一个节点
next = cur.next;
//cur的下一个节点指向新头节点的下一个节点
cur.next = newHead.next;
//新头节点的下一个节点指向cur节点
newHead.next = cur;
//cur后移
cur = next;
}
//此时cur已经是head之后反转的一串链表,从新节点给到原节点上,实现原节点的反转
headNode.next = newHead.next;
}

效果截图

img

双向链表

思路

与单向链表不同的是属性增加了一个指向前一个节点的pre

在增删改查上做了些许改变,但也容易实现

增加:除了需要指向下一个,现在还需要指向上一个

删除:找到需要删除的节点后,用该节点的前一个指向该节点的后一个,同样的后一个也指向前一个。

修改:这个没有变化,根据节点找到具体元素后,修改数据即可

查询:可以进行next遍历,也可以进行pre遍历

注意:实现toString方法的时候如果带上next和pre会报栈溢出,已踩坑

Java实现

测试部分

1
2
3
4
5
6
7
8
9
10
11
        DoubleNode node1 = new DoubleNode(1,"老婆1号");
DoubleNode node2 = new DoubleNode(2,"老婆2号");
DoubleNode node3 = new DoubleNode(3,"老婆3号");
//更新节点
DoubleNode node4 = new DoubleNode(1,"老婆4号");
ManagerDoubleNode.add(node1);
ManagerDoubleNode.add(node2);
ManagerDoubleNode.add(node3);
// ManagerDoubleNode.delete(node3.getNo());
ManagerDoubleNode.update(node4);
ManagerDoubleNode.show();

结点定义

1
2
3
4
5
6
7
8
9
10
11
12
13
//定义节点编号
private int no;
//定义前一个节点
public DoubleNode pre;
//定义数据
public String data;
//定义后一个节点
public DoubleNode next;

DoubleNode(int no, String data) {
this.no = no;
this.data = data;
}

增加结点

1
2
3
4
5
6
7
8
9
//增加一个节点
public static void add(DoubleNode node) {
DoubleNode temp = ManagerDoubleNode.head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
node.pre = temp;
}

删除结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//删除一个节点
public static void delete(int no) {
DoubleNode temp = ManagerDoubleNode.head.next;
boolean flag = false;
while (temp != null) {
if (temp.getNo() == no) {
//找到该节点,进行删除
flag = true;
temp.pre.next = temp.next;
if (temp.next != null) {
//如果该节点不是最后一个节点,则它的下一个节点指向temp的前一个节点
temp.next.pre = temp.pre;
}
break;
}
//如果找不到就挪到下一个位置
temp = temp.next;
}
if (flag) {
System.out.println("该节点已删除!");
} else {
System.out.println("该节点不存在,无法删除!");
}
}

更新结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void update(DoubleNode node) {
DoubleNode temp = ManagerDoubleNode.head.next;
boolean flag = false;
while (temp != null) {
if (temp.getNo() == node.getNo()) {
//找到该节点,进行更新操作
flag = true;
temp.data = node.data;
break;
}
//如果找不到就挪到下一个位置
temp = temp.next;
}
if (flag) {
System.out.println("该节点已更新!");
} else {
System.out.println("该节点不存在,无法更新!");
}
}

展示结点

1
2
3
4
5
6
7
public static void show() {
DoubleNode temp = ManagerDoubleNode.head.next;
while (temp != null) {
System.out.println(temp);
temp = temp.next;
}
}

环形链表

单向环形链表

实现思路及代码

与之前节点定义相同,编号,数据域,下一个指向

增删改查略有不同,next现在不会指向null,即使只有一个元素也会指向自己

判断结束的条件改变,需要判断当前节点的下一个节点是否为头节点

遍历代码实现

1
2
3
4
5
6
7
8
9
10
11
public CircleNode show() {
cur = first;
while (true) {
System.out.println(cur);
if (cur.next == first) {
break;
}
cur = cur.next;
}
return cur;
}

增加不变,找到最后一个位置然后增加

1
2
3
4
5
6
7
8
9
10
11
public void add(CircleNode circleNode) {
cur = first;
while (true) {
if (cur.next == first) {
break;
}
cur = cur.next;
}
cur.next = circleNode;
circleNode.next = first;
}

修改不变,找到对应的no然后修改

需要注意的是没有了结束的判断条件,所以要先进行no判断然后进行遍历一次的判断

否则如果没有需要修改的元素,就是一直查找下去,删除同理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void update(int no, String data) {
cur = first;
while (true) {
if (cur.no == no) {
cur.data = data;
System.out.println("数据修改成功!");
break;
}
if (cur.next == first) {
System.out.println("未找到需要修改的数据!");
break;
}
cur = cur.next;
}
}

删除需要注意的地方为:如果删除的为头节点,则需要将头节点变换,我这里将头节点顺延,然后再让需要删除的节点的前一个指向修改后的头节点,因为是单链表,所以需要利用当前节点的下一个进行遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void delete(CircleNode circleNode) {
cur = first;
while (true) {
if (cur.next.no == circleNode.no) {
if (cur.next == first) {
first = cur.next.next;
cur.next = first;
System.out.println("删除的数据为头节点,当前头节点顺延为"+first);
break;
}
cur.next = cur.next.next;
System.out.println("数据删除成功!");
break;
}
if (cur.next == first) {
System.out.println("未找到需要删除的数据!");
break;
}
cur = cur.next;
}
}

如果指定一个环形链表的大小,需要注意的地方是,在方法中初始化,而不是创建对象的时候进行初始化,i=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
public MangerCircleNode addByNum(int num) {
if (num < 1) {
System.out.println("大小不能小于1!");
return null;
}
MangerCircleNode mangerCircleNode = new MangerCircleNode();
CircleNode newNode = null;
for (int i = 1; i<=num; i++) {
if (i == 1){
//初始化
mangerCircleNode.first = new CircleNode(i,"老婆"+i+"号");
mangerCircleNode.first.next = mangerCircleNode.first;
cur =mangerCircleNode.first;
} else {
//添加环形节点
newNode = new CircleNode(i,"老婆"+i+"号");
cur.next = newNode;
newNode.next = mangerCircleNode.first;
}
//cur指向下一个节点
cur = cur.next;
}
return mangerCircleNode;
}

实际经典问题:约瑟夫问题

编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人具有一个编号(正整数)。从第n个数,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,从下一个人在数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求 利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。实现提示 程序运行后,首先要求用户指定初始报数上限值,然后读取各人的密码。可设n≤30。此题所用的循环链表中不需要“头结点”,请注意空表和非空表的界限。

img

图片来源于网络

img

图片来源于网络

以此类推

img

图片来源于网络

模拟:传入一个m,表示隔m个遍历一次,最后输出遍历后的结果

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
public void yusefu(int m){
int count = getCount();
if (m > count) {
System.out.println("输入的数字不能大于链表大小");
} else {
//复位
cur = first;
while (true) {
if (count == 0) {
break;
}
for (int j = 0; j<m-1; j++){
cur = cur.next;
}
System.out.println(cur);
first = cur.next;
this.delete(cur);
cur = first;
count--;
}
}
}
//获得该链表的个数
public int getCount() {
cur = first;
int count = 0;
while (true) {
count++;
if(cur.next == first){
break;
}
cur = cur.next;
}
return count;
}

加强版,输入三个数字,输出遍历结果

从第几个数,数几次,创建多大的链表

模拟一个实际问题

从第几个小朋友数,数几次,有多少小朋友

需要注意的是变量的作用域问题

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
/**
*
* @param startNo 从第几个数
* @param countNo 数几次
* @param size 一共多少人
*/
public void yusefu(int startNo, int countNo, int size){
if (startNo < 1 || countNo < 1 || size < 1 || startNo > size) {
System.out.println("输入的数字不合理!");
return;
}
MangerCircleNode mangerCircleNode = new MangerCircleNode(size);
//确认first为哪一个节点,此时已经是一个环,循环获取即可
for (int i = 0; i<startNo-1; i++) {
mangerCircleNode.first = mangerCircleNode.first.next;
}
//复位
mangerCircleNode.cur = mangerCircleNode.first;
while (true) {
if (size == 0) {
System.out.println("最后出圈的编号为:"+mangerCircleNode.cur.no);
break;
}
for (int j = 0; j<countNo-1; j++){
mangerCircleNode.cur = mangerCircleNode.cur.next;
}
System.out.println(mangerCircleNode.cur);
mangerCircleNode.first = mangerCircleNode.cur.next;
mangerCircleNode.delete(mangerCircleNode.cur);
mangerCircleNode.cur = mangerCircleNode.first;
size--;
}
}

补充:稀疏数组

什么是稀疏数组?

将一个二维数组变为一个3xn的数组,这样更省空间,提高存储效率

思想

当一个数组大部分元素为0,或者一个固定值,可以使用稀疏数组保存

会将一个2x2的二维数组转化为一个3xn的数组,如下表

img

应用需求

五子棋

二维—>稀疏

1、遍历原始的二维数组,得到有效数据的个数sum

2、根据sum创建稀疏数组 sparseArr int[sum+1][3]

3、将二维数组的有效数据存入稀疏数组中

稀疏—>二维

1、先读取稀疏数组的第一行,根据得到的数据创建原始的二维数组,chessArr = int[row][col]

2、读区稀疏数组后几行的数据,并赋给原有的二维数组即可

Java实现

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
public static void main(String[] args) {
//创建一个棋盘,0表示未落子,1表示黑子,2表示白子
int chessArr[][] = new int[11][10];
chessArr[1][2] = 1;
chessArr[2][3] = 2;
chessArr[3][4] = 1;
int k = 0;
//输出原始的二维数组
for (int[] row : chessArr){
for (int data : row){
//按十进制输出+tab
System.out.printf("%d\t",data);
if (data != 0){
k++;
}
}
System.out.println();
}

//转稀疏 row为列 col为行
int row = chessArr[0].length;
int col = chessArr.length;
System.out.println("row="+row+"col="+col);
int a = 1,b = 0;
//创建稀疏数组
int sparseArr[][] = new int[k+1][3];
sparseArr[0][0] = col;
sparseArr[0][1] = row;
sparseArr[0][2] = k;
for (int i = 0; i<chessArr.length; i++){
for (int j = 0; j<chessArr[i].length; j++){
if (chessArr[i][j] != 0){
sparseArr[a][0] = i;
sparseArr[a][1] = j;
sparseArr[a][2] = chessArr[i][j];
a++;
}
}
}

for (int[] row1 : sparseArr){
for (int data : row1){
//按十进制输出+tab
System.out.printf("%d\t",data);
}
System.out.println();
}
//怎么遍历数组的行数与列数
}

输出结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
0   0   0   0   0   0   0   0   0   0   
0 0 1 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
row=10col=11
11 10 3
1 2 1
2 3 2
3 4 1

Process finished with exit code 0