第三章(2) 线性结构+链式存储= ? 循环单链表的实现以及链表的应用
2022/1/18 23:08:36
本文主要是介绍第三章(2) 线性结构+链式存储= ? 循环单链表的实现以及链表的应用，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
目录
- 一、单向循环链表
- 1、定义
- 2、代码
- 二、单链表(循环单链表)的应用
- （一）、约瑟夫环问题（循环单链表）
- （二）、单链表的反转(重点)
- （三）、逢七过（循环单链表）
- （四）、思考？
一、单向循环链表
1、定义
如果把单链表的最后一个节点的指针指向链表头部,
而不是指向NULL，那么就构成了一个单向循环链表
代码就是头尾结点增删以及循环迭代时有些不同，其他基本和单链表相似
2、代码
package p3.链式结构;
import p1.接口.List;
import java.util.Comparator;
import java.util.Iterator;
//单向循环链表
public class LinkedSinglyCircularList<E> implements List<E> {
//定义结点对象
private class Node {
E data; //数据域
Node next; //指针域
public Node(){
this(null,null);
}
public Node(E data) {
this(data,null);
}
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
@Override
public String toString() {
return data.toString();
}
}
private Node head; //头指针
private Node tail; //尾指针
private int size; //元素的个数
public LinkedSinglyCircularList() {
head = null;
tail = null;
size = 0;
}
public LinkedSinglyCircularList(E[] arr) {
if (arr == null || arr.length == 0) {
throw new IllegalArgumentException("arr is null");
}
for (int i = 0; i < arr.length; i++) {
add(arr[i]);
}
}
@Override
public void add(E element) {
add(size, element);
}
@Override
public void add(int index, E element) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("add index out of range");
}
Node n = new Node(element);
if (size == 0) {
head = n;
tail = n;
tail.next = head; //new code
} else if (index == 0) {
n.next = head;
head = n;
tail.next = head; //new code
} else if (index == size) {
n.next = tail.next; //new code
tail.next = n;
tail = n;
} else {
Node p = head;
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
n.next = p.next;
p.next = n;
}
size++;
}
@Override
public void remove(E element) {
int index = indexOf(element);
if (index != -1) {
remove(index);
}
}
@Override
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove index out of range");
}
E ret = null;
if (size == 1) {
ret = head.data;
head = null;
tail = null;
} else if (index == 0) {
Node n = head;
ret = n.data;
head = n.next;
n.next = null;
tail.next = head; //new code
} else if (index == size - 1) {
Node p = head;
while (p.next != tail) {
p = p.next;
}
ret = tail.data;
p.next = tail.next; //change code
tail = p;
} else {
Node p = head;
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
Node n = p.next;
ret = n.data;
p.next = n.next;
n.next = null;
}
size--;
return ret;
}
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get index out of range");
}
if (index == 0) {
return head.data;
} else if (index == size - 1) {
return tail.data;
} else {
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
return p.data;
}
}
@Override
public E set(int index, E element) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get index out of range");
}
E ret = null;
if (index == 0) {
ret = head.data;
head.data = element;
} else if (index == size - 1) {
ret = tail.data;
tail.data = element;
} else {
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
ret = p.data;
p.data = element;
}
return ret;
}
@Override
public int size() {
return size;
}
@Override
public int indexOf(E element) {
Node p = head;
int index = 0;
while (!p.data.equals(element)) {
p = p.next;
index++;
if (p == head) { //change code
return -1;
}
}
return index;
}
@Override
public boolean contains(E element) {
return indexOf(element) != -1;
}
@Override
public boolean isEmpty() {
return size == 0 && head == null && tail == null;
}
@Override
public void clear() {
head = null;
tail = null;
size = 0;
}
@Override
public void sort(Comparator<E> c) {
if (c == null) {
throw new IllegalArgumentException("comparator can not be null");
}
if (size == 0 || size == 1) {
return;
}
Node nodeA = head;
Node nodeB = nodeA.next;
while (true) {
while (true) {
if (c.compare(nodeA.data, nodeB.data) > 0) {
swap(nodeA, nodeB);
}
if (nodeB == tail) {
break;
}
nodeB = nodeB.next;
}
if (nodeA.next == tail) {
break;
}
nodeA = nodeA.next;
nodeB = nodeA.next;
}
}
private void swap(Node nodeA, Node nodeB) {
E temp = nodeA.data;
nodeA.data = nodeB.data;
nodeB.data = temp;
}
@Override
public List<E> subList(int fromIndex, int toIndex) {
if (fromIndex < 0 || toIndex >= size || fromIndex > toIndex) {
throw new IllegalArgumentException("must 0 <= fromIndex <= toIndex <= size - 1");
}
LinkedSinglyList<E> list = new LinkedSinglyList<>();
Node nodeA = head;
for (int i = 0; i < fromIndex; i++) {
nodeA = nodeA.next;
}
Node nodeB = head;
for (int i = 0; i < toIndex; i++) {
nodeB = nodeB.next;
}
Node p = nodeA;
while (true) {
list.add(p.data);
if (p == nodeB) {
break;
}
p = p.next;
}
return list;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[');
if (isEmpty()) {
sb.append(']');
} else {
Node p = head;
while (true) {
sb.append(p.data);
if (p == tail) {
sb.append(']');
break;
}
sb.append(',');
sb.append(' ');
p = p.next;
}
}
return sb.toString();
}
@Override
public Iterator<E> iterator() {
return new LinkedSinglyCircularListIterator();
}
class LinkedSinglyCircularListIterator implements Iterator<E> {
private Node cur = head;
private boolean flag = true; //是否在第一圈
@Override
public boolean hasNext() {
if (isEmpty()) {
return false;
}
return flag;
}
@Override
public E next() {
E ret = cur.data;
cur = cur.next;
if (cur == head) {
flag = false;
}
return ret;
}
}
}
二、单链表(循环单链表)的应用
（一）、约瑟夫环问题（循环单链表）
据说著名犹太历史学家Josephus有过一下的故事:在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲在一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3个人该人必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。
然而Josephus和他的朋友并不想遵从，Josephus要 他的朋友先假装遵从,他将朋友与自己安排在了第16个与第31个位置，于是逃过了这场死亡游戏。
//提供两种解决方法
//法一：在循环链表类里面添加一个实现该功能的方法
//约瑟夫环问题
public void josephusLoop() {
if (size <= 2) {
return;
}
Node p = head;
while (size != 2) {
p = p.next;
Node del = p.next;
if (del == head) {
head = del.next;
} else if (del == tail) {
tail = p;
}
p.next = del.next;
del.next = null;
p = p.next;
size--;
}
}
//法二：在实现类时解决
int index = 0;
while (list.size() != 2) {
index = (index + 2) % list.size();
list.remove(index);
}
System.out.println(list);
（二）、单链表的反转(重点)
重新创建一个含虚拟头结点的新链表，然后遍历需要反转的链表，每遍历一个就插入到新链表的头（头插法）
//直接在循环单链表里添加一个反转方法，
//直接提供完整代码(循环单链表的实现、约瑟夫环问题、链表的反转)
package p3.链式结构;
import p1.接口.List;
import java.util.Comparator;
import java.util.Iterator;
//单向循环链表
public class LinkedSinglyCircularList<E> implements List<E> {
//定义结点对象
private class Node {
E data; //数据域
Node next; //指针域
public Node(){
this(null,null);
}
public Node(E data) {
this(data,null);
}
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
@Override
public String toString() {
return data.toString();
}
}
private Node head; //头指针
private Node tail; //尾指针
private int size; //元素的个数
public LinkedSinglyCircularList() {
head = null;
tail = null;
size = 0;
}
public LinkedSinglyCircularList(E[] arr) {
if (arr == null || arr.length == 0) {
throw new IllegalArgumentException("arr is null");
}
for (int i = 0; i < arr.length; i++) {
add(arr[i]);
}
}
@Override
public void add(E element) {
add(size, element);
}
@Override
public void add(int index, E element) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("add index out of range");
}
Node n = new Node(element);
if (size == 0) {
head = n;
tail = n;
tail.next = head; //new code
} else if (index == 0) {
n.next = head;
head = n;
tail.next = head; //new code
} else if (index == size) {
n.next = tail.next; //new code
tail.next = n;
tail = n;
} else {
Node p = head;
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
n.next = p.next;
p.next = n;
}
size++;
}
@Override
public void remove(E element) {
int index = indexOf(element);
if (index != -1) {
remove(index);
}
}
@Override
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove index out of range");
}
E ret = null;
if (size == 1) {
ret = head.data;
head = null;
tail = null;
} else if (index == 0) {
Node n = head;
ret = n.data;
head = n.next;
n.next = null;
tail.next = head; //new code
} else if (index == size - 1) {
Node p = head;
while (p.next != tail) {
p = p.next;
}
ret = tail.data;
p.next = tail.next; //change code
tail = p;
} else {
Node p = head;
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
Node n = p.next;
ret = n.data;
p.next = n.next;
n.next = null;
}
size--;
return ret;
}
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get index out of range");
}
if (index == 0) {
return head.data;
} else if (index == size - 1) {
return tail.data;
} else {
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
return p.data;
}
}
@Override
public E set(int index, E element) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get index out of range");
}
E ret = null;
if (index == 0) {
ret = head.data;
head.data = element;
} else if (index == size - 1) {
ret = tail.data;
tail.data = element;
} else {
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
ret = p.data;
p.data = element;
}
return ret;
}
@Override
public int size() {
return size;
}
@Override
public int indexOf(E element) {
Node p = head;
int index = 0;
while (!p.data.equals(element)) {
p = p.next;
index++;
if (p == head) { //change code
return -1;
}
}
return index;
}
@Override
public boolean contains(E element) {
return indexOf(element) != -1;
}
@Override
public boolean isEmpty() {
return size == 0 && head == null && tail == null;
}
@Override
public void clear() {
head = null;
tail = null;
size = 0;
}
@Override
public void sort(Comparator<E> c) {
if (c == null) {
throw new IllegalArgumentException("comparator can not be null");
}
if (size == 0 || size == 1) {
return;
}
Node nodeA = head;
Node nodeB = nodeA.next;
while (true) {
while (true) {
if (c.compare(nodeA.data, nodeB.data) > 0) {
swap(nodeA, nodeB);
}
if (nodeB == tail) {
break;
}
nodeB = nodeB.next;
}
if (nodeA.next == tail) {
break;
}
nodeA = nodeA.next;
nodeB = nodeA.next;
}
}
private void swap(Node nodeA, Node nodeB) {
E temp = nodeA.data;
nodeA.data = nodeB.data;
nodeB.data = temp;
}
@Override
public List<E> subList(int fromIndex, int toIndex) {
if (fromIndex < 0 || toIndex >= size || fromIndex > toIndex) {
throw new IllegalArgumentException("must 0 <= fromIndex <= toIndex <= size - 1");
}
LinkedSinglyList<E> list = new LinkedSinglyList<>();
Node nodeA = head;
for (int i = 0; i < fromIndex; i++) {
nodeA = nodeA.next;
}
Node nodeB = head;
for (int i = 0; i < toIndex; i++) {
nodeB = nodeB.next;
}
Node p = nodeA;
while (true) {
list.add(p.data);
if (p == nodeB) {
break;
}
p = p.next;
}
return list;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[');
if (isEmpty()) {
sb.append(']');
} else {
Node p = head;
while (true) {
sb.append(p.data);
if (p == tail) {
sb.append(']');
break;
}
sb.append(',');
sb.append(' ');
p = p.next;
}
}
return sb.toString();
}
@Override
public Iterator<E> iterator() {
return new LinkedSinglyCircularListIterator();
}
class LinkedSinglyCircularListIterator implements Iterator<E> {
private Node cur = head;
private boolean flag = true; //是否在第一圈
@Override
public boolean hasNext() {
if (isEmpty()) {
return false;
}
return flag;
}
@Override
public E next() {
E ret = cur.data;
cur = cur.next;
if (cur == head) {
flag = false;
}
return ret;
}
}
//约瑟夫环问题
public void josephusLoop() {
if (size <= 2) {
return;
}
Node p = head;
while (size != 2) {
p = p.next;
Node del = p.next;
if (del == head) {
head = del.next;
} else if (del == tail) {
tail = p;
}
p.next = del.next;
del.next = null;
p = p.next;
size--;
}
}
//链表反转的问题
public void reverse() {
if (size == 0 || size == 1) {
return;
}
Node dummpyHead = new Node(); //虚拟头结点
Node p = head;
for (int i = 0; i < size; i++) {
Node n = new Node(p.data);
if (dummpyHead.next == null) {
tail = n;
}
n.next = dummpyHead.next;
dummpyHead.next = n;
p = p.next;
}
head = dummpyHead.next;
}
}
测试代码
package p0.测试;
import p3.链式结构.LinkedSinglyCircularList;
import java.util.Comparator;
public class TestLinkedSinglyList {
public static void main(String[] args) {
LinkedSinglyCircularList<Integer> list = new LinkedSinglyCircularList<>();
for (int i = 1; i <= 10; i++) {
list.add((int) (Math.random() * 100));
}
System.out.println(list);
list.reverse();
System.out.println(list);
list.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
System.out.println(list);
list.clear();
for (int i = 1; i <= 41; i++) {
list.add(i);
}
//从单向循环链表的内部来处理 处理结点与结点之间的关系
//list.josephusLoop();
//从单向循环链表的外部来处理 处理就是角标之间的关系
/*
1 2 5
0 1 2
i
*/
int index = 0;
while (list.size() != 2) {
index = (index + 2) % list.size();
list.remove(index);
}
System.out.println(list);
//拉丁方阵的问题 ???
}
}
测试输出
[69, 74, 0, 57, 73, 7, 13, 13, 76, 63] [63, 76, 13, 13, 7, 73, 57, 0, 74, 69] [0, 7, 13, 13, 57, 63, 69, 73, 74, 76] [16, 31]
（三）、逢七过（循环单链表）
1.好友围坐在酒桌前，从任意一人开始轮流报数，数字从1开始。
2.凡是遇到任何7的倍数，如14、21或含7的数字如17、27均喊“过”。
3.遇到反应慢了没有敲zhi打桌面的人则失败。失败的惩罚就是罚酒或者表演节目。
4.接下来，被惩罚过的人重新开始报数， 可以从10以下任意- -个数字开始
打印每个人应该报的数字
package p3.链式结构;
import java.util.ArrayList;
import java.util.Scanner;
//逢七过游戏
/*
输入玩家的个数
输入从哪个玩家开始
输入该玩家从哪个数字开始
输入一共玩几个数字
打印出每个玩家将要报出的所有数字
*/
public class SevenGame {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print(">>>请输入玩家的个数：");
int playerCount = input.nextInt();
System.out.print(">>>请输入从哪个玩家开始：");
int beginPlayer = input.nextInt();
System.out.print(">>>请输入从哪个数字开始：");
int beginNumber = input.nextInt();
System.out.print(">>>请输入数字的最大值：");
int maxNumber = input.nextInt();
//创建玩家的集合
LinkedSinglyCircularList<ArrayList<String>> list = new LinkedSinglyCircularList<>();
//分别创建玩家的对象
for (int i = 0; i < playerCount; i++) {
list.add(new ArrayList<>());
}
//开始的玩家的角标
int index = beginPlayer - 1;
//将数字 依次分给每一个玩家
for (int num = beginNumber; num <= maxNumber; num++) {
list.get(index++ % playerCount).add(getAnswer(num));
}
for (int i = 0; i < list.size(); i++) {
System.out.println("第" + (i + 1) + "位玩家：" + list.get(i));
}
}
private static String getAnswer(int num) {
if (num % 7 == 0 || (num + "").contains("7")) {
return "过";
}
return num + "";
}
}
测试输出
>>>请输入玩家的个数：4 >>>请输入从哪个玩家开始：3 >>>请输入从哪个数字开始：1 >>>请输入数字的最大值：20 第1位玩家：[3, 过, 11, 15, 19] 第2位玩家：[4, 8, 12, 16, 20] 第3位玩家：[1, 5, 9, 13, 过] 第4位玩家：[2, 6, 10, 过, 18]
（四）、思考？
拉丁方阵问题：
比如链表内容： 1 2 3 4
第一次输出 1 2 3 4
第二次输出 2 3 4 1
第三次输出 3 4 1 2
…
这篇关于第三章(2) 线性结构+链式存储= ? 循环单链表的实现以及链表的应用的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-05-31全网首发第二弹！软考2024年5月《软件设计师》真题+解析+答案！（11-20题）
- 2024-05-31全网首发！软考2024年5月《软件设计师》真题+解析+答案！（21-30题）
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司，哪像华为一样，用得上IPD（集成产品开发）？
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm，再安排pandas等模块，说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型？
- 2024-05-29鸿蒙原生应用再新丁！新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式（Iterator）
