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

《数据结构》课程实验实验报告题目：Joseph问题求解算法的设计与实现专业：计算机科学与技术 班级：姓名： 学号： 完成日期：一、试验内容约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。二、试验目的掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。流程图输入总人数n创建并初始化n个结点输入第一个报的数key输入总人数n创建并初始化n个结点输入第一个报的数keyn==0报数过程报数过程输出出列者的编号及密码输出出列者的编号及密码结束n--结束n--四、源程序代码//Joseph问题求解算法的设计与实现#include<stdio.h>#include<stdlib.h>structlist{ intnum,code; structlist*next;};voidmain(){ printf("Joseph问题求解算法的设计与实现\n\n"); inti,j,m=1; intkey;//密码. intn;//人数.list*p,*s,*head; head=(list*)malloc(sizeof(list));//为头结点分配空间. p=head; printf("输入人的总个数:"); scanf("%d",&n); for(i=1;i<=n;i++) {key=rand()%100; printf("第%d个人的密码:%d\n",i,key); s=p; p=(list*)malloc(sizeof(list));//创建新的结点. s->next=p; p->num=i; p->code=key; } p->next=head->next; p=head; head=head->next; free(p);//释放头结点. p=head; do{ printf("\n第%d号成员的密码为:%d",p->num,p->code);//输出链表. p=p->next; }while(p!=head); printf("\n\n输入第一个报的数:\n"); scanf("%d",&key); printf("\n出列顺序为:\n"); do {j=1; p=head; while(j<key){ s=p; p=p->next; j++; }//报数过程. i=p->num; key=p->code; printf("%d:第%d号成员出列\n",m,i); m++; s->next=p->next; head=p->next;//重新定义head,下次循环的开始结点. free(p);//释放已出列的结点. n--;//人数减一. }while(n>0);}五、调试过程调试过程中,曾出现过缺少分号、括号之类的错误,还出现过运算顺序颠倒，致使运算出现了错误，在经过仔细的检查并且向人请教,终于得出了正确结果.六、结果分析Joseph问题求解算法的设计与实现输入人的总个数:5第1个人的密码:41第2个人的密码:67第3个人的密码:34第4个人的密码:0第5个人的密码:69第1号成员的密码为:41第2号成员的密码为:67第3号成员的密码为:34第4号成员的密码为:0第5