当前页面: 开发资料首页 → J2SE 专题 → Josephu 问题 删除链表老是删不了,请帮忙分析下哪里错了? thx
Josephu 问题 删除链表老是删不了,请帮忙分析下哪里错了? thx
摘要: Josephu 问题 删除链表老是删不了,请帮忙分析下哪里错了? thx
Josephu 问题:
import java.io.*;
class Josephu {
public static void main(String args[]){
int nn = 4;
int mm = 2;
int kk = 3;
//建第一个人
People head_p = new People(1);
//建一个随操作不断变化的节点
People now_p = head_p;
//new People 建nn-1个人
for (int i = 2; i<=nn; i++){
People new_p = new People(i);
now_p.pNext=new_p;
new_p.pre=now_p;
now_p = new_p;
}
//建环行链表9
now_p.pNext=head_p;
head_p.pre = now_p;
People temp_head = head_p;
//找到第K个人
while(true){
if(now_p.getNum()==kk){
break;
}
now_p = now_p.pNext;
}
//删除从第k个人开始的第m个人
while(nn!=0){
for(int i=1;i
now_p = now_p.pNext;//使now_p指向那个人
}
int s=now_p.getNum();
now_p.pre = now_p.pNext;//删除第m个
System.out.println (now_p.getNum()+"--------");
nn--;
System.out.println ("被抛出的是: "+ s);
}
}
}
class People{
public int num;
public People pNext=null;
public People pre = null;
public People(int num){
this.num = num;
}
public int getNum(){
return num;
}
public void printPeople(){
System.out.println ("People "+ num);
}
}
晚了,明天来看~~~~~~~~~~up
楼主在删除结点时候前驱后继关系没搞清楚
建议不要用双向链表,单项可能方便些
我用单链表实现的
class Josephus
{
int players = 0;
int beginner = 0;
int everCount = 0;
People head = new People(1);
People cur_p = null;
People pre_p = null;
public Josephus(int players, int beginner, int everCount)
{
this.players = players;
this.beginner = beginner;
this.everCount = everCount;
}
public void createGame()
{
cur_p = head;
for(int i = 2; i <= players; i++)
{
pre_p = new People(i);
cur_p.pNext = pre_p;
cur_p = pre_p;
}
cur_p.pNext = head;
cur_p = head;
}
public void gameBegin()
{
moveTo(beginner);
while(players > 0)
{
moveTo(everCount);
printCurPlayer();
deleteCurPlayer();
players--;
}
}
private void moveTo(int num)
{
for(int i = 1; i < num; i++)
{
pre_p = pre_p.pNext;
cur_p = cur_p.pNext;
}
}
private void printCurPlayer()
{
System.out.println(cur_p);
}
private void deleteCurPlayer()
{
pre_p.pNext = cur_p.pNext;
cur_p = cur_p.pNext;
}
}
class People
{
public int ID = 0;
public People pNext=null;
public People(int ID)
{
this.ID = ID;
}
public String toString()
{
return ("People: " + this.ID);
}
}
class Test
{
public static void main(String[] args)
{
Josephus jsp = new Josephus(6, 3, 2);
jsp.createGame();
jsp.gameBegin();
}
}
为什么结果和我用手计算的结果不同呢?
顺序好象和你的不大一样.