约瑟夫环问题

菜★鸟

用数据结构链式结构实现下列问题：

n个人（编号为1，2，3，……，n (n>0) ）按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出两个值：一个为首先报数的人的编号i (0<i<=n)，另一个为起始报数上限值m。接着从编号为i的人开始按顺时针方向自1起顺序报数，报到m时停止报数，且报到m的人出列，并将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数，……，如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，给出出列人的编号序列。

这是我写的代码，不知道什么地方出错，运行的时候总是会出现随机数，而且结点貌似也不对，跪求大虾指教：

#include<iostream.h>
#include<stdlib.h>

typedef struct
{
  int code,password;
} ElemType;
struct  LNode  {              // 定义单链表节点类型
    ElemType  data;    // 存放结点中的数据信息
    LNode  *next;          // 指示下一个结点地址的指针
  };
#include"Y_Link.h"
void main()
{
int i,n,l,m,j;
ElemType h;
LNode *L=NULL,*p1=NULL,*p2=NULL;
InitList(L);
i=1;
cout<<"总人数:"<<endl;
cin>>n;
while(i<=n)
{
h.code=i;
cout<<"输入第"<<i<<"个人的密码:"<<endl;
cin>>h.password;
InsertList(L,h,-1);
i++;
}
cout<<"首次报数的编号l,上限值m"<<endl;
cin>>l>>m;
p1=p2=L;
while(p1->next!=NULL)
p1=p1->next;
p1->next=p2;

for(j=1;j<=l;j++)
L=L->next;

for(i=1;i<=n;i++)
{
for(j=0;j<m;j++)
{
p2=L;
L=L->next;
}
cout<<"第"<<i<<"个退出的是："<<L->data.code<<endl;
  m=L->data.password;
p2->next=L->next;
      L=p2->next;
}
}

void InitList (LNode *&H)      //初始化单链表
{
   H=(LNode *)malloc(sizeof(LNode));   // 产生头结点H
           if (H==NULL) exit(0);    // 存储分配失败，退出系统
           H->next=NULL;// 指针域为空
}

bool InsertList ( LNode *&H, ElemType item, int pos)//向单链表插入一个元素
{
if(pos<-1){
  cout<<"pos值无效!"<<endl;
  return false;
}
    LNode* newptr;
newptr=new LNode;
newptr->data=item;
LNode* cp=H->next;
LNode* ap=H;
if(pos==0){
  while(cp!=NULL){
   if(item.code< cp->data.code)
    break;
   else{
    ap=cp;
    cp=cp->next;
   }
  }
}
else if(pos==-1)
  while(cp!=NULL){ap=cp;cp=cp->next;}
else{
  int i=0;
  while(cp!=NULL){
   i++;
   if(i==pos)
    break;
   else{
                  ap=cp;cp=cp->next;
   }
  }
  if(cp==NULL&&i+1<pos){
   cout<<"pos值超出单链表长度加1!"<<endl;
   return false;
  }
}
if(ap==NULL){
  newptr->next=H;
  H=newptr;
}
else
{
        newptr->next=cp;
  ap->next=newptr;
}
return true;
}
      

guojisheng1987

编程问题还是期待高人解决。

ecjiuhe01

不是很了解....

菜★鸟

貌似结点有问题。。。

NETcui0912

好吧，我很迷茫的浏览了以下文字部分，然后直接越过了数字部分。。。偶是纯粹的菜鸟啊，不解释