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

数据结构上机实验报告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，5.首先没的值为1,正确的出列顺序应为1，2，4，3，5。2概要分析抽象数据类型的定义：为实现上述程序的功能，可以用整数存储用户的输入。并将用户输入的值存储于线性表中。算法的基本思想：约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点。由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出。核心算法主要分为两步：1、确定需要删除的位置，2、设置并删除该位置。已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。反复进行上述确定位置和删除位置的操作，直到顺序表为空。主程序的流程：程序由三个模块组成：（1）输入模块：无提示语句，直接输入总人数n和报数次数m，中间用逗号隔开。（2）构造链表并输入每个人信息模块：（3）主要处理出列的函数：分别在DOS下和文件中，按移除元素的顺序依次显示其位置。3、详细设计

1.本程序包含三个模块

1)主程序模块

intmain()

{

intm,n,i=0;

LinkLists;

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);

return0;

}

2)构造链表并输入每个人信息模块；LinkListL,r,q;

inti,key;

printf("请输入%d个数字作为每个人的密码:\n",n);

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

{

scanf("%d",&key);

//输入每个人的密码

r=(LinkList)malloc(sizeof(LNode));

if(i==1)

{

L=q=r;

}

else{

q->next=r;

q=r;

}

r->num=i;

r->pwd=key;

}

r->next=L;//使最后节点指向首节点，形成循环链表

returnL;//向主函数返回创建完成的循环链表首节点的地址}3）主要处理出列的函数：voidListDelete_L(LinkList&L,intm,intn){

LinkListp,s;

intj;

while(n>0){//只要人数大于0就继续，直到全部出列

p=L;

for(j=1;j<m;j++){

//顺序找到第m个节点（人）并使指针指向该节点

s=p;

p=p->next;

}

printf("出列人原来的序号是:%d\n",p->num);//输出出列人序号

m=p->pwd;//将出列人的密码作为新的报数值m

s->next=p->next;//将出列的节点（人）从循环链表中删除

L=p->next;

free(p);

n--;

}}4、调试分析（1）编写程序时，指针运用不熟练，导致调试时错误过多，花费了太多时间，后通过对指针相关知识的进一步了解，改正了程序中的错误，正确运行了程序。（2）数据结构是一门比较抽象的课程，但是也是一门最基础的课程学的过程。在现实生活的也非常广泛通过设计该实验让我更加深刻的掌握了有关链表的知识，同时也认识到了自己在平时学习当中的盲点。通过这次实验发现了自己在数据结构这门功课上存在严重的不足。链表中的指针理解不够，运用不够熟练，常常出现一些莫名其妙的问题，调试费时太多。今后一定会多编程，多思索。在以后的学习过程中还需要不断的完善学习，希望能把数据结构这门课学习的更加深入，更加透彻。5、测试结果6、附录#include<stdio.h>#include<malloc.h>typedefstructLNode{

intpwd,num;

structLNode*next;}LNode,*LinkList;LinkListCreatList_L(intn){

//建立循环链表

LinkListL,r,q;

inti,key;

printf("请输入%d个数字作为每个人的密码:\n",n);

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

{

scanf("%d",&key);

//输入每个人的密码

r=(LinkList)malloc(sizeof(LNode));

if(i==1)

{

L=q=r;

}

else{

q->next=r;

q=r;

}

r->num=i;

r->pwd=key;

}

r->next=L;//使最后节点指向首节点，形成循环链表

returnL;//向主函数返回创建完成的循环链表首节点的地址}voidListDelete_L(LinkList&L,intm,intn){

LinkListp,s;

intj;

while(n>0){//只要人数大于0就继续，直到全部出列

p=L;

for(j=1;j<m;j++){

//顺序找到第m个节点（人）并使指针指向该节点

s=p;

p=p->next;

}

printf("出列人原来的序号是:%d\n",p->num);//输出出列人序号

m=p->pwd;//将出列人的密码作为新的报数值m

s->next=p->next;//将出列的节点（人）从循环链表中删除

L=p->next;

free(p);

n--;

}}

intmain()

{

intm,n,i=0;

LinkLists;

printf("请输入报数上限m和人数n:\n");

do{

if(i>0)

printf("输入有误，