- 队列的特点
- 单向队列
- 环形队列
- 单向链表
- 双向链表
- 环形链表
以下只给出思路与关键方法，算法的源代码放在了git中，需要的自取
https://gitee.com/leidl97/algor
队列的特点
先进先出 （FIFO）
可以理解为排队，先排的先进入。如图所示
出自《算法第四版》第78页
单向队列
思想（如何定义数据）
用数组实现，头指针指向开始的前一个位置用-1表示，默认位置为0
尾指针指向最后一个元素的位置也用-1表示（初始情况下，没有元素，所以指向-1，当元素加入后尾指针会+1，将值添加到尾指针所在的位置）
判断队列为满
尾指针指向元素的最后一个位置
判断队列为空
头指针=尾指针
存入数据
先移在存。先让尾指针+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.maxSize = maxSize;
this.arr = new int[maxSize];
this.begin = -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()) {
throw new RuntimeException("队列空，不可以取数据");
}
return this.arr[++this.begin];
}
|
显示队列数据
1
2
3
4
5
6
7
8
|
public int getQueue(){
if (isEmpty()) {
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
判断队列为空
头指针=尾指针。比如刚开始的时候
判断队列为满
（尾指针+1）%数组大小为头指针所在位置的时候队列为满
存入数据
与单向不同的是，这次是先存在移。先将尾指针指向的区域存入指定数据，然后移动到下一个位置
取出数据
先取在移。取出当前头指针指向的元素，然后移动到下一个位置
获取所有元素
遍历需要想明白?的位置应该怎么填写
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.maxSize = maxSize;
this.arr = new int[maxSize];
this.begin = 0;
this.end = 0;
}
|
判断队满
1
2
3
4
|
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
|
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
|
public int getQueue(){
if (isEmpty()) {
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域
不一定是连续存储
图片来源于网络
单向链表
思路
首先定义一个节点类Node
有编号（ID），数据和下一个节点至少三个属性
定义一个节点类，初始化头节点，因为头节点不可以动所以定义辅助节点，用来添加和遍历
添加：尾插法，判断当前元素的下一个元素是否为空，如果是则在当前节点插入下一个节点，如果不是依次往后寻找，直到找到下一个为空的那个节点然后插入
遍历：先判断头节点的下一个元素是否为空，否则往下进行寻找，然后一次输出节点
缺点：不能按照编号顺序添加
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
|
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)
画个图
第一次移动
第二次移动
代码实现
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("链表为空！");
}
Node cur = headNode.next;
Node next = null;
Node newHead = new Node(0,"");
while (cur != null) {
next = cur.next;
cur.next = newHead.next;
newHead.next = cur;
cur = next;
}
headNode.next = newHead.next;
}
|
效果截图
双向链表
思路
与单向链表不同的是属性增加了一个指向前一个节点的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.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.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.next;
}
return mangerCircleNode;
}
|
经典问题：约瑟夫问题
编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人具有一个编号（正整数）。从第n个数，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，从下一个人在数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求 利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。实现提示 程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设n≤30。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。
图片来源于网络
图片来源于网络
以此类推
图片来源于网络
模拟：传入一个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
|
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);
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的数组，如下表
应用需求
五子棋
二维—>稀疏
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) {
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){
System.out.printf("%d\t",data);
if (data != 0){
k++;
}
}
System.out.println();
}
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){
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
|
