约瑟夫问题对应算法的实现(思路分析) [Java][数据结构]
约瑟夫问题对应算法的实现(思路分析)
我们前面已经创建好了单向环形链表类了,这个时候我们要通过这个单向环形链表类来解决约瑟夫问题:
约瑟夫问题算法的具体实现的思路分析:
-
需求创建一个辅助指针(变量)helper,事先应该指向环形链表的最后这个节点
-
加上我们在单向链表中封装的first指针,我们就可以完成节点出链表的操作,首先我们要确定从第几个节点开始报数,假设是从第k个开始报数,那么我们就让first和helper指针同时移动k - 1次
上面的first就是指向第一个报数的小孩节点,而上面的helper指向的就是报数的小孩的前一个位置,这个时候如果first指针指向的小孩节点要进行一个出链表,这个时候就是先让first后移,然后让helper指向后移之后first指向的结点位置,
-
当小孩开始报数时,让first和helper指针同时移动m - 1次(m就是报数到多少就出队列的数字) , 这里应该为从自己开始报数 ,所以报2的时候就是移动第一次,那么报m时也就是移动m - 1次, 然后移动完成之后我们的first就指向了待出链表的小孩
-
那么让first指向的小孩节点出圈: (执行下面操作即可)
first = first.next; //让first指针指向下一个位置,那么此时的first指向的结点就会被跳过 helper.next = first; //让helper.next目前还是指向原来的first,所以我们要使用helper.next指向现在 //的first //此时原来first指针指向的结点就没有任何的引用指向它,就会等待被垃圾回收
补充:
为什么我们可以使用helper指针指向first结点的前一个节点?
- 因为我们的first指针是指向我们的待删除结点,但是这时候我们是一个单向链表,在单向链表中我们不能完成自我删除(在双向链表中可以完成自我删除) , 我们在单向链表中要通过带删除结点的前一个结点来删除带删除结点
当我们的first指针指向我们的待删除结点之后,让我们的first结点移动m - 1次,一直重复执行,每次移动m - 1次之后first就指向了待删除结点,那么我们删除了该待删除结点之后first自然就会后移,就会指向我们删除位置的下一个节点,也就是开始报数的小孩,那么我们只需要再遍历m - 1次就可以又找到下一次的待删除位置了然后一直重复执行,直到执行到我们的单向环形链表中只有一个节点为止
- 当环形链表中只有一个节点的时候我们就要退出了,因为当链表中只有一个节点的时候 这个时候first和helper指向了同一个节点,这个时候都指向了自己,通过上面的通用操作就删除不了这个最后一个节点了
- 当只剩最后一个节点的时候我们就退出循环,单独执行这个最后一个节点的删除,直接让frist指向null就可以了(我们可以让helper也指向null , 那么最后这个结点也就等待被回收了)
补充二:
当我们使用private修饰next属性之后,这时候我们不能使用 first.getNext() = helper,不能这样执行,因为first.getNext()其实就是获取到了一个值,他并不是一个变量,我们获取的值只能是赋给某个变量(这个是一个语法错误, 我们的工具会报错的, 我们只能是helper = first.getNext(), 而不是first.getNext() = helper) , 我们如果想要修改first的next属性就要通过first.setNext(helper)来完成
- 总之就是值只能是赋给变量,不能将值赋给值 , 值赋给值就相当于 1 = 2, 这个肯定是错误的