✓实验题目：约瑟夫环问题

一、实验目的

  加深理解链表的定义

  掌握链表的表示与实现

二、实验内容

设有n个人围成一圈，每个人持有一个密码m，现从第1个人开始报数，报m的出圈，再从他的下一个人重新报数，报m的出圈，如此下去直到圈中只剩一人。求该人的编号及出圈次序。

三、设计与编码

1、基本思想

当m不等于1的时候，根据输入的密码m，找前驱，然后摘链删去报m的人，循环删除，直到最后一个；当m 等于1的时候，另外处理。

2、编码

#include

struct Node

{

  int data;

  Node *next;

};

class CLinkList

{

  public:

    CLinkList(int a[ ], int n);  //建立有n个元素的单循环链表

    ~CLinkList();             //析构函数

    int Length();            //求单循环链表的长度

    void ysf(int n,int m);   //实现n个人密码为m的约瑟夫环问题

    void PrintList( );      //遍历单循环链表，按序号依次输出各元素

 private:

   Node *first;     //单循环链表的头指针

};

CLinkList::CLinkList(int a[ ], int n)

 {

    first=new Node;

first->data=a[0];

    Node *r,*s;

    r=first;          //尾指针初始化

for (int i=1; i    {

      s=new Node;

s->data=a[i]; //为每个数组元素建立一个结点

r->next=s; //插入到终端结点之后

      r=s;

    }

r->next=first; //单循环链表建立完毕，将终端结点的指针域置为头指针

 }

CLinkList::~CLinkList()

{

    Node *p,*t;;

    p=first;

    int i=0,len=Length();

while(i    {

        t=p;

p=p->next;

        delete t;

        i++;

    }

}

int CLinkList::Length( )

{

  if(first==NULL)

    return 0;

  Node  *p = first;

  int i = 1;

while(p->next!=first)

  {

p = p->next;

    i++;

  }

  return i;

}

void CLinkList::ysf(int n,int m)

{

    Node *p;

    /*p=first;*/

    int x;

    int i;

     if(m==1)

     {

while(p->next!=p)

       {

x=p->next->data;

p->next=p->next->next;

cout<        

       }

cout<<"最后圈内留下的人的编号是"<data<     }

    else{

     p=first;

while(p->next!=p)

    {

for(i=0;i      {

p=p->next;

      }

x=p->next->data;

p->next=p->next->next;

p=p->next;

cout<    }

cout<<"最后圈内留下的人的编号是"<data<}

void CLinkList::PrintList( )

{

    Node *p;

cout<data;

p=first->next;

    while (p!=first)

    {

cout<<" "<data;

p=p->next;

    }

cout<}

void main()

{

    int a[20],n,m,i;

cout<<"请输入圈内总人数：";

cin>>n;

for(i=0;i        a[i]=i+1;

cout<<"请输入密码值：";

cin>>m;

    CLinkList L(a,n);

//    L.PrintList();

    L.ysf(n,m);

}

四、调试与运行

1、调试时遇到的主要问题及解决

刚开始没有考虑到m=1的问题；m不等于1的时候找前驱条件容易出错

2、运行结果（输入及输出，可以截取运行窗体的界面）

五、实验心得下载本文