Algorithm
Search…
数据结构与算法

线性结构和非线性结构

数据结构包括:线性结构和非线性结构

线性结构:

  1. 1.
    线性结构作为最常用的数据结构,其特点是数据元素之间存一对一的线性关系
  2. 2.
    线性结构有两种不同的存储结构,及顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的
  3. 3.
    链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息
  4. 4.
    线性结构常见的有:数组、队列、链表和栈。

非线性结构

非线性结构包括:二维数组、多维数组、广义表、树、图。

稀疏数组(sparse array)

基本介绍:
当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
  1. 1.
    记录数组一共有几行几列,有多少个不同的值
  2. 2.
    把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
1567227428401
二维数组转稀疏数组的思路
  1. 1.
    遍历原始的二维数组,得到有效数据的个数sum
  2. 2.
    根据sum就可以创建稀疏数组sparseArr= int[sum+1][3]
  3. 3.
    将二维数组的有效数据数据存入到稀疏数组
稀疏数组转原始的二维数组的思路
  1. 1.
    先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的 chessArr2=int[11][11]
  2. 2.
    在读取稀疏数组后几行的数据,并赋给原始的二维数组即可。
1
public class SparseArray {
2
public static void main(String[] args) throws IOException {
3
/**
4
* 创建一个原始的二维数组 11*11
5
* 0:表示没有棋子,1表示黑子,2表示白子
6
*/
7
int[][] chessArray = new int[11][11];
8
chessArray[1][2] = 1;
9
chessArray[2][3] = 2;
10
// 输出原始的二维数组
11
System.out.println("原始的二维数组:\n");
12
toStringArray(chessArray);
13
14
/**
15
* 将二维数组转为稀疏数组
16
* 1.先遍历二维数组得到非0数据的个数
17
* 2.创建对应的稀疏数组
18
*/
19
int effectiveDataCount = 0;
20
for(int i = 0; i < 11; i++) {
21
for(int j = 0; j<11; j++) {
22
if(chessArray[i][j] != 0) {
23
effectiveDataCount++;
24
}
25
}
26
}
27
/**
28
* 创建对应的稀疏数组,行是有效数据的行数+1
29
* 多出的一行用来存储原二维数组的行和列以及有效数据的个数
30
* 3列是固定值,第一列存储行,第二列存储列,第三列存储实际的值
31
*/
32
int[][] sparseArray = new int[effectiveDataCount + 1][3];
33
// 给稀疏数组赋值,初始化第一行的值
34
sparseArray[0][0] = 11;
35
sparseArray[0][1] = 11;
36
sparseArray[0][2] = effectiveDataCount;
37
38
/**
39
* 遍历二维数组,将非0的值存放到稀疏数组中
40
* 再次遍历,如果不进行第一次遍历无法创建稀
41
* 疏数组的大小除非使用集合
42
*/
43
// 用于记录是第几个非0数据
44
int count = 0;
45
for(int i = 0; i < 11; i++) {
46
for(int j = 0; j<11; j++) {
47
if(chessArray[i][j] != 0) {
48
count++;
49
// 因为count = 0而存值是从第一行开始所以count先++
50
sparseArray[count][0] = i;
51
sparseArray[count][1] = j;
52
sparseArray[count][2] = chessArray[i][j];
53
}
54
}
55
}
56
// 输出稀疏数组
57
System.out.println("稀疏数组为:\n");
58
toStringArray(sparseArray);
59
60
/**
61
* 稀疏数组转原始二维数组
62
* 1.先读取稀疏数组的第一行,根据第一行数据创建原始二维数组
63
* 2.读取稀疏数组剩下的行数据,并赋值给原始的二维数组
64
*/
65
int row = sparseArray[0][0];
66
int col = sparseArray[0][1];
67
int[][] originalArray = new int[row][col];
68
// 遍历稀疏数组剩下的行数据赋值给原始数组,从第二行开始即index=1
69
for(int i = 1; i < sparseArray.length; i++) {
70
// 获取数据所在原始数组的行号
71
int originRow = sparseArray[i][0];
72
// 获取数据所在原始数组的列号
73
int originCol = sparseArray[i][1];
74
// 赋值
75
originalArray[originRow][originCol] = sparseArray[i][2];
76
}
77
System.out.println("稀疏数组恢复原始数组:\n");
78
toStringArray(originalArray);
79
80
// 将稀疏二维数组写入到文件并读取
81
readWriteSparseArray(sparseArray);
82
}
83
/**
84
* 格式化打印二维数组
85
* @param array
86
*/
87
private static void toStringArray(int[][] array) {
88
for(int[] row : array) {
89
for(int data : row) {
90
System.out.printf("%d\t", data);
91
}
92
System.out.println("\n");
93
}
94
}
95
96
/**
97
* 将稀疏矩阵写入到文件并读取出来恢复为稀疏矩阵
98
* @param sparseArray
99
* @throws IOException
100
*/
101
private static void readWriteSparseArray(int[][] sparseArray) throws IOException {
102
103
// 将稀疏数组保存到文件中在读取出来恢复成稀疏数组
104
System.out.println("将稀疏数组写入到map.data");
105
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter("src/map.data"));
106
for(int i=0; i < sparseArray.length; i++) {
107
for(int j=0; j<3; j++) {
108
bufferedWriter.write(sparseArray[i][j]+"\t");
109
}
110
bufferedWriter.write("\n");
111
}
112
bufferedWriter.close();
113
114
115
BufferedReader bufferedReader = new BufferedReader(new FileReader("src/map.data"));
116
String line = bufferedReader.readLine();
117
String[] stringArray = line.split("\t");
118
int coverRow = Integer.parseInt(stringArray[2]);
119
int[][] sparseArray2= new int[coverRow+1][3];
120
sparseArray2[0][0] = Integer.parseInt(stringArray[0]);
121
sparseArray2[0][1] = Integer.parseInt(stringArray[1]);
122
sparseArray2[0][2] = Integer.parseInt(stringArray[2]);
123
int readCount = 1;
124
String readLine = null;
125
while((readLine = bufferedReader.readLine())!= null) {
126
String[] temp = readLine.split("\t");
127
sparseArray2[readCount][0] = Integer.parseInt(temp[0]);
128
sparseArray2[readCount][1] = Integer.parseInt(temp[1]);
129
sparseArray2[readCount][2] = Integer.parseInt(temp[2]);
130
readCount++;
131
}
132
System.out.println("恢复后的稀疏数组");
133
toStringArray(sparseArray2);
134
bufferedReader.close();
135
}
136
}
Copied!

队列

  1. 1.
    队列是一个有序列表,可以用数组或者链表来实现
  2. 2.
    遵循先进限出的原则,即:先存入对列的数据,要先取出,后存入的元素后取出
u=3865082282,2895414691&fm=26&gp=0

数组模拟队列

当我们将数据存入队列时称之为“addQueue”,addQueue的处理需要两个步骤:
  1. 1.
    将尾指针往后移:rear+1,当front == rear则表示队列为空
  2. 2.
    若尾指针rear小于队列的最大下标maxSize-1,则将数据存入rear所指的数组元素中,否则无法存入数据,rear == maxSize-1表示队列满了
1
public class ArrayQueue {
2
/**
3
* 数组的最大容量
4
*/
5
private int maxSize;
6
/**
7
* 队头指针
8
*/
9
private int head;
10
/**
11
* 队尾指针
12
*/
13
private int tail;
14
/**
15
* 用于存放数据的容器,模拟队列
16
*/
17
private int[] element;
18
19
// 创建队列的构造器
20
public ArrayQueue(int maxSize) {
21
this.maxSize = maxSize;
22
this.element = new int[maxSize];
23
// 初始时element没有元素,head指向队列头部的前一个位置
24
this.head = -1;
25
// 初始时element没有元素,tail指向队列尾部的后一个位置
26
this.tail = -1;
27
}
28
29
public boolean isFull() {
30
return this.tail == this.maxSize -1;
31
}
32
33
public boolean isEmpty() {
34
return this.head == this.tail;
35
}
36
37
public void add(int elem) {
38
if(isFull()) {
39
System.out.println("队列满了,无法加入数据");
40
return;
41
}
42
// 后移一位
43
tail++;
44
this.element[tail] = elem;
45
}
46
47
public int get() {
48
if(isEmpty()) {
49
// 通过抛出异常处理
50
throw new RuntimeException("队列为空,无法取出数据");
51
}
52
head++;
53
return this.element[head];
54
}
55
56
@Override
57
public String toString() {
58
if(isEmpty()) {
59
return "[]";
60
}
61
return "ArrayQueue [" + Arrays.toString(element) + "]";
62
}
63
64
/**
65
* 显示队列的头数据,注意不是取数据
66
* @return 返回队头数据
67
*/
68
public int peek() {
69
if(isEmpty()) {
70
throw new RuntimeException("队列为空");
71
}
72
return this.element[head + 1];
73
}
74
75
public static void main(String[] args) {
76
ArrayQueue queue = new ArrayQueue(3);
77
// 测试添加
78
queue.add(20);
79
queue.add(30);
80
81
System.out.println("队列是否满:" + queue.isFull());
82
System.out.println("队列是否空:" + queue.isEmpty());
83
System.out.println(queue.toString());
84
}
85
}
Copied!
问题分析及优化:
  1. 1.
    目前数组使用一次就不能在使用了,无法复用
  2. 2.
    将这个数组使用算法,改进成一个环形队列使用取模方式:%
1567239121893
1
package xyz.guqing.queue;
2
3
import java.util.Arrays;
4
5
public class ArrayQueue {
6
/**
7
* 数组的最大容量
8
*/
9
private int maxSize;
10
/**
11
* 队头指针
12
*/
13
private int head;
14
/**
15
* 队尾指针
16
*/
17
private int tail;
18
/**
19
* 用于存放数据的容器,模拟队列
20
*/
21
private int[] element;
22
23
// 创建队列的构造器
24
public ArrayQueue(int maxSize) {
25
this.maxSize = maxSize;
26
this.element = new int[maxSize];
27
// 初始时element没有元素,head指向队列头部位置也就是第一个元素的位置
28
this.head = 0;
29
// 初始时element没有元素,tail指向队列尾部的后一个位置,tail = 0
30
this.tail = 0;
31
}
32
33
public boolean isFull() {
34
return (tail + 1) % maxSize == head;
35
}
36
37
public boolean isEmpty() {
38
return this.head == this.tail;
39
}
40
41
public void add(int elem) {
42
if(isFull()) {
43
System.out.println("队列满了,无法加入数据");
44
return;
45
}
46
// 直接将数据加入即可
47
this.element[tail] = elem;
48
// 将tail后移一位,这里必须考虑取模
49
tail = (tail + 1) % maxSize;
50
}
51
52
public int get() {
53
if(isEmpty()) {
54
// 通过抛出异常处理
55
throw new RuntimeException("队列为空,无法取出数据");
56
}
57
// 这里需要分析出head是指向队列的第一个元素
58
// 1. 先把head对应的值保存到一个临时的变量
59
// 2.将head后移,考虑取模,否则回越界
60
// 3.将临时保存的变量返回
61
int value = element[head];
62
head = (head + 1) % maxSize;
63
return value;
64
}
65
66
@Override
67
public String toString() {
68
if(isEmpty()) {
69
return "ArrayQueue []";
70
}
71
// 从head开始遍历,遍历多少个元素,数量是有效数据的个数
72
int size = size();
73
int count = 0;
74
int[] copyArray = new int[size];
75
for(int i = head; i < head + size; i++) {
76
copyArray[count] = element[i % maxSize];
77
count++;
78
}
79
return "ArrayQueue " + Arrays.toString(copyArray);
80
}
81
82
public int size() {
83
return (tail + maxSize - head) % maxSize;
84
}
85
86
/**
87
* 显示队列的头数据,注意不是取数据
88
* @return 返回队头数据
89
*/
90
public int peek() {
91
if(isEmpty()) {
92
throw new RuntimeException("队列为空");
93
}
94
return this.element[head];
95
}
96
97
public static void main(String[] args) {
98
// 传入3,有效数据最大是2,保留了一个
99
ArrayQueue queue = new ArrayQueue(3);
100
// 测试添加
101
queue.add(20);
102
queue.add(30);
103
104
System.out.println("队列是否满:" + queue.isFull());
105
System.out.println("队列是否空:" + queue.isEmpty());
106
System.out.println(queue.toString());
107
System.out.println("取数据:"+queue.peek());
108
}
109
}
Copied!

链表

链表是一个有序的列表,但是它在内存中是如下结构的:
1567245049449
  1. 1.
    链表是以节点的方式来存储的,链式存储
  2. 2.
    每个节点包含data域和next域,next域指向下一个节点
  3. 3.
    如图:链表的各个节点不一定是连续存储的
  4. 4.
    链表分为带头结点的链表和没有头节点的链表,根据实际需求来确定

单向链表

代码实现

1
/**
2
* 单链表管理Node
3
* @author guqing
4
*
5
*/
6
public class SingLinkedList<T> {
7
// 初始化一个头节点,头节点不能动,不存放具体的数据
8
private final Node<T> head = new Node<>(null);
9
private transient int size = 0;
10
// 添加节点
11
public void add(T t) {
12
/**
13
* 当不考虑顺序时,找到最后一个节点,让最后一个节点的next指行新节点
14
*/
15
// 创建数据域节点
16
Node<T> node = new Node<>(t);
17
// 指针
18
Node<T> pointer = head;
19
while(pointer.next != null) {
20
pointer = pointer.next;
21
}
22
// 当退出while循环时,pointer就指向了链表的最后
23
pointer.next = node;
24
size++;
25
}
26
27
public void remove(T t) {
28
// 头节点不能动,需要辅助指针
29
// 前驱指针
30
Node<T> prevPointer = head;
31
// 后继指针
32
Node<T> nextPointer = prevPointer.next;
33
while(nextPointer != null) {
34
if(nextPointer.data == t) {
35
// 删除元素
36
System.out.println("删除元素");
37
prevPointer.next = nextPointer.next;
38
nextPointer.next = null;
39
size--;
40
return;
41
}
42
prevPointer = nextPointer;
43
nextPointer = nextPointer.next;
44
}
45
}
46
47
public T get(int index) {
48
if(index > size() - 1) {
49
throw new RuntimeException("Array Index Out of Bounds.");
50
}
51
52
int count = 0;
53
Node<T> pointer = head.next;
54
while(pointer != null) {
55
if(count == index) {
56
return pointer.data;
57
}
58
count++;
59
pointer = pointer.next;
60
}
61
return null;
62
}
63
64
public int size() {
65
return size;
66
}
67
68
public void remove(int index) {
69
if(index > size() - 1) {
70
throw new RuntimeException("Array Index Out of Bounds.");
71
}
72
73
int count = 0;
74
// 前驱指针
75
Node<T> prevPointer = head;
76
// 后继指针
77
Node<T> nextPointer = prevPointer.next;
78
while(nextPointer != null) {
79
if(count == index) {
80
prevPointer.next = nextPointer.next;
81
nextPointer.next = null;
82
// 更新链表长度
83
size--;
84
return;
85
}
86
count++;
87
prevPointer = nextPointer;
88
nextPointer = nextPointer.next;
89
}
90
}
91
92
public void addAll(SingLinkedList<T> list) {
93
Node<T> pointer = head.next;
94
while(pointer.next != null) {
95
pointer = pointer.next;
96
}
97
// 追加在链表尾
98
pointer.next = list.head.next;
99
size = size + list.size();
100
}
101
102
@Override
103
public String toString() {
104
// 判断链表是否为空
105
if(head.next == null) {
106
return "[]";
107
}
108
// 因为头节点不能动,因为我们需要一个指针来遍历
109
Node<T> pointer = head.next;
110
StringBuilder sb = new StringBuilder();
111
sb.append("[");
112
while(pointer != null) {
113
// 输出节点信息
114
sb.append(pointer.data);
115
116
// 指针后移
117
pointer = pointer.next;
118
119
// 添加一个分割符
120
if(pointer != null) {
121
sb.append(", ");
122
}
123
}
124
sb.append("]");
125
return sb.toString();
126
}
127
128
/**
129
* Node类用于定义链表的基本结构包括两个域:数据域和指针域
130
* @author guqing
131
* @param <T> 数据类型
132
*/
133
private static class Node<T> {
134
final T data;
135
Node<T> next;
136
137
public Node(T data) {
138
super();
139
this.data = data;
140
}
141
}
142
143
public static void main(String[] args) {
144
SingLinkedList<User> userList = new SingLinkedList<>();
145
User user1 = new User();
146
user1.setId(1);
147
user1.setUsername("zhangsan");
148
user1.setNickname("张三");
149
user1.setGender("男");
150
userList.add(user1);
151
152
User user2 = new User();
153
user2.setId(2);
154
user2.setUsername("lisi");
155
user2.setNickname("李四");
156
user2.setGender("男");
157
userList.add(user2);
158
159
User user3 = new User();
160
user3.setId(3);
161
user3.setUsername("cuihua");
162
user3.setNickname("翠花");
163
user3.setGender("女");
164
userList.add(user3);
165
System.out.println("size:" + userList.size());
166
System.out.println(userList);
167
}
168
}
Copied!
其中用到的User类
1
public class User {
2
private Integer id;
3
private String username;
4
private String nickname;
5
private String gender;
6
}
Copied!

常见单链表题目

  1. 1.
    查找单链表的倒数第k个节点使用 T get(int index)方法即可,比如获取倒数第1个节点:
1
User user = userList.get(userList.size() - 1);
Copied!
  1. 1.
    链表反转,这里写两种方式,还有一种递归反转不会
1
/**
2
* 迭代头插法反转链表,遍历一个反转一个
3
*/
4
public void reverse() {
5
//如果链表为空或只有一个元素直接返回
6
if(head.next == null || head.next.next == null){
7
return;
8
}
9
// 新的头节点,让其next指向null
10
Node<T> newHead = new Node<T>(null);
11
newHead.next = null;
12
13
// 用于临时保存head的next指向
14
Node<T> temp = null;
15
while(head != null){
16
// 临时保存head的next指向
17
temp = head.next;
18
19
// 头部插入,先让head.next指向newHead.next,在链接头部和新节点
20
head.next = newHead.next;
21
newHead.next = head;
22
23
// 让head重新指向temp,达到向后移动遍历的目的
24
head = temp;
25
}
26
27
// 这里需要将head重新指向新的head处,否则head指向null
28
head = newHead;
29
}
30
31
32
/**
33
* 指针的next指向逆向法反转链表
34
*/
35
public void reverse1() {
36
//如果链表为空或只有一个元素直接返回
37
if(head.next == null || head.next.next == null){
38
return;
39
}
40
// 使用一个新head指行原head指向的位置,这样方便修改原head的指向
41
Node<T> newHead = head;
42
// 指向head第一个有数据的Node
43
Node<T> prevPointer = newHead.next;
44
// 指向prevPointer的下一个指针,因此如果数据都没有两个是不需要逆序的
45
Node<T> nextPointer = prevPointer.next;
46
// 临时指针
47
Node<T> temp = null;
48
while(nextPointer != null){
49
temp = nextPointer.next;
50
nextPointer.next = prevPointer;
51
prevPointer = nextPointer;
52
nextPointer = temp;
53
}
54
//设置链表尾
55
newHead.next.next = null;
56
//修改链表头
57
newHead.next = prevPointer;
58
head = newHead;
59
}
Copied!
  1. 1.
    逆序打印单链表
方式1:先将单链表进行反转在遍历(破坏了单链表的结构,不建议)
方式2:利用栈,将各个节点压入栈中,在弹栈。利用栈先进后出的特点
(还没有涉及到栈,先不实现,也可以用jdk的Stack)

单向链表的缺点

  1. 1.
    单向链表,查找方向只能是一个方向
  2. 2.
    单向链表不能自我删除,需要靠辅助节点

双向链表

双向链表的结构包含两个指针,一个指向前一个节点的前驱指针和一个指向下一个节点的后继指针。
u=4194072899,3280572795&fm=26&gp=0
双向链表的遍历、添加、删除的操作思路:
  1. 1.
    遍历方式和单链表一样,但是既可以向前查找也可以向后查找
  2. 2.
    添加(默认添加到双向链表的最后)
  3. 3.
    删除:因为是双向链表,因此可以实现自我删除某个节点,直接找到要删除的某个节点,比如指向删除数据的指针为pointer,则
1
//删除的不是最后一个节点否则回出现空指针
2
pointer.prev.next = pointer.next
3
pointer.next.prev = pointer.prev
4
5
// 删除的是最后一个节点
6
pointer.prev.next = pointer.next
Copied!

代码实现

1
/**
2
* 双向链表代码实现:
3
* void add(T t)
4
* void addAll(DoubleLinkedList list)
5
* void remove(T t)
6
* void remove(int index)
7
* T get(int index)
8
* int size()
9
* String toString()
10
*
11
* @author guqing
12
*/
13
public class DoubleLinkedList<T> {
14
private Node<T> head = new Node<>(null);
15
private int size = 0;
16
17
public void add(T t) {
18
/**
19
* 当不考虑顺序时,找到最后一个节点,让最后一个节点的next指向新节点
20
*/
21
// 创建数据域节点
22
Node<T> node = new Node<>(t);
23
// 指针
24
Node<T> pointer = head;
25
while(pointer.next != null) {
26
pointer = pointer.next;
27
}
28
// 当退出while循环时,pointer就指向了链表的最后
29
pointer.next = node;
30
node.prev = pointer;
31
size++;
32
}
33
34
public void addAll(DoubleLinkedList<T> list) {
35
Node<T> pointer = head.next;
36
while(pointer.next != null) {
37
pointer = pointer.next;
38
}
39
// 追加在链表尾
40
pointer.next = list.head.next;
41
list.head.next.prev = pointer;
42
// 更新链表的长度
43
size = size + list.size();
44
}
45
/**
46
* 双向链表可以自我删除,不需要前驱指针
47
* @param t 需要删除的对象
48
*/
49
public void remove(T t) {
50
// 头节点不能动,需要辅助指针
51
Node<T> pointer = head.next;
52
while(pointer != null) {
53
if(pointer.data == t && pointer.next != null) {
54
// 删除元素
55
pointer.prev.next = pointer.next;
56
pointer.next.prev = pointer.prev;
57
size--;
58
return;
59
} else if(pointer.data == t) {
60
// 删除最后一个元素
61
pointer.prev.next = pointer.next;
62
size--;
63
return;
64
}
65
pointer = pointer.next;
66
}
67
}
68
69
public void remove(int index) {
70
if(index > size() - 1) {
71
throw new RuntimeException("Array Index Out of Bounds.");
72
}
73
74
int count = 0;
75
// 遍历指针
76
Node<T> pointer = head.next;
77
while(pointer != null) {
78
if(count == index && count < size -1) {
79
pointer.prev.next = pointer.next;
80
pointer.next.prev = pointer.prev;
81
// 更新链表长度
82
size--;
83
return;
84
} else if(count == index){
85
// 删除最后一个节点
86
pointer.prev.next = pointer.next;
87
size--;
88
return;
89
}
90
count++;
91
pointer = pointer.next;
92
}
93
}
94
95
public T get(int index) {
96
if(index < 0 || index > size() - 1) {
97
throw new RuntimeException("Array Index Out of Bounds.");
98
}
99
100
int count = 0;
101
Node<T> pointer = head.next;
102
while(pointer != null) {
103
if(count == index) {
104
return pointer.data;
105
}
106
count++;
107
pointer = pointer.next;
108
}
109
return null;
110
}
111
112
public int size() {
113
return size;
114
}
115
116
@Override
117
public String toString() {
118
// 判断链表是否为空
119
if(head.next == null) {
120
return "[]";
121
}
122
// 因为头节点不能动,因为我们需要一个指针来遍历
123
Node<T> pointer = head.next;
124
StringBuilder sb = new StringBuilder();
125
sb.append("[");
126
while(pointer != null) {
127
// 输出节点信息
128
sb.append(pointer.data);
129
130
// 指针后移
131
pointer = pointer.next;
132
133
// 添加一个分割符
134
if(pointer != null) {
135
sb.append(", ");
136
}
137
}
138
sb.append("]");
139
return sb.toString();
140
}
141
142
/**
143
* Node类用于定义双向链表的基本结构包括三个域:数据域和前驱指针域和后继指针域
144
* @author guqing
145
* @param <T> 数据类型
146
*/
147
private static class Node<T> {
148
final T data;
149
Node<T> prev;
150
Node<T> next;
151
152
public Node(T data) {
153
super();
154
this.data = data;
155
}
156
}
157
158
public static void main(String[] args) {
159
DoubleLinkedList<User> userList = new DoubleLinkedList<>();
160
161
User user1 = new User();
162
user1.setId(1);
163
user1.setUsername("zhangsan");
164
user1.setNickname("张三");
165
user1.setGender("男");
166
userList.add(user1);
167
168
User user2 = new User();
169
user2.setId(2);
170
user2.setUsername("lisi");
171
user2.setNickname("李四");
172
user2.setGender("男");
173
userList.add(user2);
174
175
User user3 = new User();
176
user3.setId(3);
177
user3.setUsername("cuihua");
178
user3.setNickname("翠花");
179
user3.setGender("女");
180
userList.add(user3);
181
182
userList.remove(user1);
183
System.out.println(userList);
184
}
185
}
Copied!

单向循环链表

Josephu(约瑟夫、约瑟夫环)问题:
Josephu问题为:设编号为1,2,…n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。 提示:用一个不带头结点的循环链表来处理 Josephu问题:先构成一个有n个结点的单循环链表,然后由k结点起从1开始计数,计到m时,对应结点从链表中删除,然后再从被删除结点的下一个结点又从1开始计数,直到最后一个结点从链表中删除算法结束。
6f18498993b43b41373f9b25cf8582f6
构建一个单向循环链表思路:
  1. 1.
    先创建第一个节点,让head指向该节点,并形成环形。
  2. 2.
    然后当我们每创建一个新的节点,就把该节点加入到已有的环形链表中即可
遍历环形链表
  1. 1.
    先让一个辅助指针pointer(变量),指向head节点
  2. 2.
    然后通过一个while循环遍历该环形链表即可遍历结束的条件pointer.next == head

约瑟夫问题代码

使用不带头节点的单向循环链表完成
1
/**
2
* 没有头节点的单向循环链表(解决约瑟夫环问题)
3
* @author guqin
4
*
5
*/
6
public class JosephLinkedList<T> {
7
private Node<T> head = null;
8
private int size = 0;
9
10
public JosephLinkedList() {
11
}
12
13
public int size() {
14
return size;
15
}
16
17
/**
18
* 添加数据的方法
19
* @param t 数据
20
*/
21
public void add(T t) {
22
Node<T> data = new Node<>(t);
23
if(size == 0) {
24
head = data;
25
data.next = data;
26
size++;
27
return;
28
}
29
//辅助指针,用于构建环形链表,注意:这里指向head,判断条件是pointer.next不是head
30
Node<T> pointer = head;
31
while(pointer.next != head) {
32
pointer = pointer.next;
33
}
34
// 遍历到最后一个节点,添加数据并后成环
35
pointer.next = data;
36
data.next = head;
37
size++;
38
}
39
40
@Override
41
public String toString() {
42
// 判断链表是否为空
43
if(head == null) {
44
return "[]";
45
}
46
47
// 遍历时需要取数据所以要指向第一个有数据的节点
48
Node<T> pointer = head;
49
StringBuilder sb = new StringBuilder();
50
sb.append("[");
51
while(pointer.next != head) {
52
sb.append(pointer.data);
53
sb.append(", ");
54
55
// 移动指针
56
pointer = pointer.next;
57
}
58
// 头节点的数据
59
sb.append(pointer.data);
60
sb.append("]");
61
62
return sb.toString();
63
}
64
65
66
/**
67
* 约瑟夫问题出队序列方法
68
* 1.需要创建一个辅助指针pointer,事先应该指向环形链表的最后一个节点
69
* 2.从第k个元素开始数,数m次第m个元素被取出
70
* @param k 从第几个节点开始遍历
71
* @param m 遍历几个后取出节点
72
* @return 返回约瑟夫出队序列的字符串
73