数据结构约瑟夫环问题

题目：约瑟夫环问题

一．设计内容

[问题描述] 

约瑟夫环问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈，每人手持一个密码（正整数）。一开始任选一个整数作为报数上限值，从第一人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将它的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去直到所有人全部出列为止。试设计程序实现之。

[基本要求]  

利用循环链表存储结构模拟此过程，按照出列的顺序打印各人的编号。

[实验提示]

程序运行后首先要求用户指定初始报数上限值。然后读取各人的密码。设n<=30。

程序执行后，要求用户在计算机终端上显示“提示信息”后，用键盘输入“提示信息”中规定的命令，以“回车符”为结束标志。相应的输入数据和运算结果显示在其后。

二、设计目的

1. 达到熟练掌握C++语言的基本知识和技能；

2. 能够利用所学的基本知识和技能，解决简单的面向对象程序设计问题。

3.把课本上的知识应用到实际生活中，达到学以致用的目的。

三、系统分析与设计（确定程序功能模块）

1、为实现上述程序的功能，应以有序链表表示集合。

基本操作：

InitList(&L)

    操作结果：构造一个空的有序表L。

DestroyList(&L)

  初始条件：有序表L已存在。

  操作结果：销毁有序表L。

ListEmpty(L)

初始条件：有序表L已存在。

操作结果：若L为空表，则返回TRUE，否则返回FALSE。

ListLength(L)

初始条件：有序表L已存在。

操作结果：返回L中数据元素个数。

GetElem(L,i)

初始条件：有序表L已存在，并且1≤i≤ListLength(L)。

操作结果：返回L中第i个数据元素。

LocatePos(L,e)

初始条件：有序表L已存在，e和有序表中元素同类型的值。

操作结果：若L中存在和e相同的元素，则返回位置；否则返回0。

InsertElem(&L,e)

初始条件：有序表L已存在

操作结果：在L中，按有序关系插入值和e相同的数据元素。

DeleteElem(&L,i)

初始条件：有序表L已存在。

操作结果：删除L中第i个数据元素。

ListTraverse(L,visit())

初始条件：有序表L已存在。

操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。

} ADT OrderedList

2、本程序包含两个模块：

       （1）主程序模块：

         void main(){

              初始化；

              调用函数（接受命令，处理命令）}

       （2）有序表单元模块——实现有序表的抽象数据类型。

        （3）输出函数模块——有序表的输出。

四、源程序代码

#include"stdio.h"

#include"malloc.h"

//1.元素类型，结点类型和指针类型

 typedef struct LNode         //定义结构体，

{

 int num,pwd;                 //num用来存储人的序号，pwd用来存储人的密码

 struct LNode *next;

};

struct LNode *head,*p,*pt;    //定义结点

//2、    创建循环链表函数

int creatLinkList(int n)      //参数n传递人数，

{

   int i;

   head=(struct LNode*)malloc(sizeof(struct LNode));

                            //创建一个带头结点的链表

   if(!head)  {return 0;}    //创建不成功，返回0

   p=head;

for(i=1;i  {

     pt=(struct LNode*)malloc(sizeof(struct LNode));

     if(!pt)  {return 0;}

p->next=pt;

     p=pt;

  }

p->next=head;        //构成循环链表

    pt=head;

    return 0;

} 

//3.创建输入密码函数

 int enterPwd(int n)        //参数n传递人数

{

   int i,j;

   printf("\\n请输入密码: \\n");

for( i=1;i<=n;i++)

    {

       scanf("%d",&j);

pt->num=i; //num存储人的序号

pt->pwd=j; //pwd存储人的密码

pt=pt->next;

    }

    pt=p;

    return j;

} 

 //4、创建输出函数

 int outList(int m,int n)    //参数m、n传递报数上限值和人数

{

   int i,a;

for(i=1;i<=n;i++) //用一个for循环搜索循环链表

   {

for(a=1;a      {

pt=pt->next;

      }

p=pt->next;

m=p->pwd;

printf("%d ",p->num); //输出人的序号

pt->next=p->next;

      free(p);          //释放动态申请的结点空间

   }

   return 0;

}

 //主函数

void main()

{   int m,n;   //m为报数上限值，n为人数

    printf("\\n参数m、n传递报数上限值和人数;\\n");

    printf("\\n请输入 m 和 n: \\n");

    scanf("%d %d",&m,&n);

    creatLinkList( n);  //调用创建链表函数

    enterPwd( n);       //调用输入密码函数

    printf("\\n出队的人依次是:\\n");

    outList( m,n);      //调用输出链表函数

}

五、测试结果及功能说明

输入报数上限值为m为6 ，人数n为7；

7个人数密码依次是1，2，3，4，5，6，7；

出队的人号码依次是：6，5，4，3，2，1，7

六、设计体会

数据结构是一门比较抽象的课程，但是也是一门最基础的课程学的过程。在现实生活的应用也非常广泛通过设计该实验让我更加深刻的掌握了掌握了，有关链表的知识，同时也认识到了自己在平时学习当中的盲点，通过这次实验发现了自己在数据结构这门功课上存在严重的不足。链表中的指针理解不够，运用不够熟练，常常出现一些莫名其妙的问题，调试费时太多。今后一定会多编程，多思索。在以后的学习过程中还需要不断的完善学习，希望能把数据结构这门课学习的更加深入，更加透彻。最后，非常感谢老师在实验的过程所提供的帮助和指导。