数据结构——简单应用单链表

约瑟夫问题

Josephu 问题为: 设编号为1, 2, .. n的n个人围坐一圈,约定编号为k (1<=k<=n)的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。

**提示**: 用一个不带头结点的循环链表来处理Josephu问题: 先构成一个有 n个结点的单循环链表,然后由k结
点起从1开始计数,计到m时,对应结点从链表中删除,然后再从被删除结点的下一个结点又从1开始计数,直
到最后一个结点从链表中删除算法结束。


单向环形链表

image-20230116230614412

约瑟夫问题分析图

image-20230116230924680

代码实现分析

  • 先创建一个单项环形链表

    1. 先创建第一个节点,让first指向该节点,并形成环形

    2. 后边当我们每创建一个新的节点,就把该节点,加到已有的环形链表中即可

  • 遍历环形链表

    1. 先让一个辅助指针(temp),指向first

    2. 然后通过一个while循环遍历该链表即可 ( temp.next=first)遍历结束

      这里有张图片:
      image-20230117170218531

  • 生成小孩出圈的顺序

    1. 先创建一个辅助指针(helper),让它指向环形链表的最后一个

    2. 报数前,先让first和helper移动到startNo

    3. 当小孩报数时,让first与helper同时移动m-1次

    4. 这时first指向的小孩出圈

      first=first.next helper.next=first
    5. 此时原来first指向的节点就会被回收

      这里有张图片:
      image-20230117170339763

创建节点的代码

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
//先创建一个Child类表示一个节点
class Child {
private int no;
private Child next; //指向下一个节点,默认null

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

public int getNo ( ) {
return no;
}

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

public Child getNext ( ) {
return next;
}

public void setNext ( Child next ) {
this.next = 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
//创建一个环形的单向链表
class CireSingleLinkedList {
//创建一个first节点,没有编号
private Child first = new Child ( -1 );

//添加小孩节点,构建一个环形链表
public void CreatChildList ( int nums ) {
//对nums 进行数据校验
if ( nums < 1 ) {
System.out.println ( "nums的值不正确" );
return;
}
//创建环形链表
Child temp = null; //辅助指针,帮助构建环形指针
for ( int i = 1 ; i <= nums ; i++ ) {
//根据编号创建小孩节点
Child boy = new Child ( i );
//如果是第一个小孩
if ( i == 1 ) {
first = boy;
first.setNext ( first );
temp = first;
}
else {
temp.setNext ( boy );//把之前最的后辅助节点的next指向新加的
boy.setNext ( first );//此时处在最后的节点的next指向first
temp = boy; //辅助节点往后移
}
}
}

//遍历环形链表
public void list ( ) {
//判断链表是否为空
if ( first == null ) {
System.out.println ( "链表为空,没有任何小孩\n" );
return;
}
//因为first不能动,所以我们仍然使用一个辅助指针完成遍历
Child temp = first;
while (true) { //满足条件说明已经是最后一个,遍历完毕
System.out.printf ( "小孩的编号为%d\n", temp.getNo ( ) );
if ( temp.getNext ( ) == first ) {
return;
}
temp = temp.getNext ( );//后移
}
}
}

小孩出圈顺序代码

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
//小孩出圈
//根据用户的输入,计算出小孩出圈的顺序

/**
* @param startNo 开始节点 ,表示从第几个小孩开始
* @param countNum 每次数几下(m)
* @param nums 表示最初有几个人
*/
public void countBoy ( int startNo, int countNum, int nums ) {
//先对数据进行校验
if ( first == null || startNo < 1 || startNo > nums ) {
System.out.println ( "参数输入有误,请从新输入" );
return;
}
//先创建一个辅助指针(helper),让它指向环形链表的最后一个
Child helper = first;
while (true) {
if ( helper.getNext ( ) == first ) { //说明helper指向最后一个节点
break;
}
helper = helper.getNext ( );
}
//先将first移动到startNo节点
for ( int j = 0 ; j < startNo - 1 ; j++ ) {
first=first.getNext ( );
helper = helper.getNext ( );
}
//当小孩报数时,让first与helper同时移动m-1次,然后出圈
//这里是一个循环操作,直到圈中只有一个节点
while (helper!=first) { //helper==first(helper.getnext()==helper)说明圈中只有一个节点
//让first与helper同时移动countNum-1次
for ( int j = 0 ; j < countNum - 1 ; j++ ) {
first=first.getNext ( );
helper = helper.getNext ( );
}
//此时first指向的节点是要出圈的小孩
System.out.printf ( "小孩%d出圈\n", first.getNo ( ) );
//将此时first指向的小孩弄出圈
first = first.getNext ( );
helper.setNext ( first );
}
System.out.printf ( "最后留在圈中的小孩编号%d\n",first.getNo () );
}