约瑟夫环数据结构实验报告.docx

数据结构上机实验报告
1、需求分析
1:用一个循环链表实现n个人按顺时针排成一圈,每个人看作一个节点,每个节点都是一个结构体类型,包含三个域: 序号域(data), 密码域(key),指向下一个人的指针域(next).
2:程序开始时由用户任意输入人数n及一个正整数作为报数上限值m,一个正整数作为密码最大值,判断所输密码是否在范围内。然后为依次每一个人指定一个密码
3:初始密码为用户外部输入的密码m, 从第一个人开始按顺市针方向自1开始报数.,报道m的时停止,报m的人出列,将他的密码作为新的密码值(m), 从他在顺针方向的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止.
4:本程序最终结果为n 的人的出列顺序
5:测试数据: m的初值为1; n =5(即有5个人)57个人的密码依次为:1,2,3,4,,正确的出列顺序应为1,2,4,3,5。
2概要分析
抽象数据类型的定义:
为实现上述程序的功能,可以用整数存储用户的输入。并将用户输入的值存储于线性表中。
算法的基本思想:约瑟夫环问题中的数据是人所在的位置,而这种数据是存在“第一元素、最后元素”,并且存在“唯一的前驱和后继的”,符合线性表的特点。由于需要模拟约瑟夫环的出列问题,可以采用顺序表来实现线性表,完成出列顺序的输出。
核心算法主要分为两步:
1、确定需要删除的位置,2、设置并删除该位置。
已知报数间隔m,我们可以把当前位置加上m获得需要删除的位置,如果获得的位置超过顺序表中实际元素的总长度,则可以通过减去数组的实际长度来修正(即模拟环状计数)。然后把顺序表中的当前指向位置设置为该位置,继而删掉该位置。
反复进行上述确定位置和删除位置的操作,直到顺序表为空。
主程序的流程:
程序由三个模块组成:
(1)输入模块:无提示语句,直接输入总人数n和报数次数m,中间用逗号隔开。
(2)构造链表并输入每个人信息模块:
(3)主要处理出列的函数:分别在DOS下和文件中,按移除元素的顺序依次显示其位置。
3、详细设计
 
     1) 主程序模块
 int main()
 {
     int m,n,i=0;
  LinkList s;
  printf("请输入报数上限m和人数n:\n"); 
  do{
   if(i>0)
    printf("输入有误,请重新输入:\n");
  scanf("%d",&m);
 
  getchar();
  scanf("%d",&n);
  getchar();
  i++;
  }while(m <= 0 || n <= 0);
  s=CreatList_L(n);
  ListDelete_L(s,m,n);
  return 0;
 }
      2) 构造链表并输入每个人信息模块;
LinkList L,r,q;
 int i,key;
 printf("请输入%d个数字作为每个人的密码:\n",n);
 for(i=1;i<=n;i++)
 {
  scanf("%d",&key);  //输入每个人的密码
  r=(LinkList)malloc(sizeof(LNode));