约瑟夫环实验报告

实验一  线性的基本操作及其应用 一、 实验目的 1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。 二、 实验内容和要求 [问题描述] 约瑟夫（Joseph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 [基本要求] 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 [测试数据] 由学生任意指定。 如：m的初值为20；n的值为7；密码：3，1，7，2，4，8，4； （正确的输出结果应为6，1，4，7，2，3，5）。 (上要求写出多批数据测试结果) [实现提示] 程序运行后首先要求用户输入初始报数上限值m，人数n,(设n≤30)。然后输入各人的密码。 [选作内容] 向上述程序中添加在顺序结构上实现的部分。 三、 算法设计 1、主要思想： 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质，考虑采用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。循环链表的结点定义为如下结构类型： typedef struct LNode { int num,pwd; //num存储人的序号，pwd存储人的密码 struct LNode *next; }; 其次，建立一个不带头结点的循环链表并由头指针Head指示。  最后，设计约瑟夫环问题的算法。 2、本程序包含四个模块 1）主函数 void main() { int m,n;//分别为报数上限和人数 printf("\n参数m,n传递报数上限和人数.\n\n请输入m和n：\n"); scanf("%d %d",&m,&n); creatLinkList(n);//带哦用创建链表函数 enterPwd(n);//调用输入密码函数 printf("\n出列的人依次是：\n"); outList(m,n); } 2） 创建链表函数creatLinkList()——根据用户输入的人数创建人数相等数量结点的循环链表。 3） 输入密码函数enterPwd()——根据用户输入的密码，存入相应结点的数据域pwd； 4） 输出出列人的序号函数outList(m,n) 3、 核心算法 根据用户输入的报数上限以及人数，在一个循环里面循环和人数相等的次数。这个循环里面还有一个小的循环用于找到每次出列的结点，小循环找到了出列结点的上一个结点。然后记下这个结点，接着去除要出列结点的数据域里的pwd，然后free（）这个结点。开始找下一个出列的结点。 for(i=1;i<=n;i++) //搜索循环链表 { for(a=1;anext; } p=pt->next; m=p->pwd; printf("%d",p->num); //输出人的序号 pt->next=p->next; free(p); //释放动态

申请

关于撤销行政处分的申请关于工程延期监理费的申请报告关于减免管理费的申请关于减租申请书的范文关于解除警告处分的申请

的结点空间 四、 调试分析 1、 在编译时发现没有导入#include 2、 在调试的时候发现不需要头结点的。 五、 实验结果 1.输入报数上限为20和人数为8，密码分别为3,6,5,7,8，2，1,4.然后输出结果如图1所示。 2. 输入报数上限为7和人数为6，密码分别为3,4,5,1,2，6.然后输出结果如图2所示。 图1 实验结果 图2 实验结果 六、

总结

初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf

1． 在编程解决约瑟夫环的问题的时候用到了单向循环链表，自己在开始的时候使用了头结点，然后对它循环查找出列的结点的时候不知道怎么忽略它，最后省略了头结点。 2． 在建立单向循环链表的时候不够熟练，导致链表在报数的时候找不到头指针，并且指针的操作上还有待改进，不能完全灵活使用。 3． 在查找出列结点的时候容易出错，我在写代码的时候只剩下两个数的时候出错了。后来我在要删除的结点前面加了个指针p，才使程序运行成功。 4． 通过这个这个实验，我对链表的各种操作更加熟悉。 七、 源程序（带注释） #include #include //元素类型。节点类型，指针类型， typedef struct LNode { int num,pwd; //num存储人的序号，pwd存储人的密码 struct LNode *next; }; struct LNode *head,*p,*pt; //创建循环链表函数 int creatLinkList(int n)//参数为传递人数 { int i; head=(struct LNode*)malloc(sizeof(struct LNode));//创建一个带头结点的链表 if(!head) { return 0;//创建失败，返回0； } p=head; for(i=1;i<=n;i++) { pt=(struct LNode*)malloc(sizeof(struct LNode)); if(!pt) return 0; p->next=pt; p=pt; } p->next=head;//构成循环链表 pt=head; return 0; } 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; //ped 存储人的密码 pt=pt->next; } pt=p; //return j; return 0; } int outList(int m,int n)//参数为报数上限值和人数 { int i,a; for(i=1;i<=n;i++) //搜索循环链表 { for(a=1;anext; } p=pt->next; m=p->pwd; printf("%d    ",p->num); //输出人的序号 pt->next=p->next; free(p); //释放动态申请的结点空间 } return 0; } //主函数 void main() { int m,n;//分别为报数上限和人数 printf("\n参数m,n传递报数上限和人数.\n\n请输入m和n：\n"); scanf("%d %d",&m,&n); creatLinkList(n);//带哦用创建链表函数 enterPwd(n);//调用输入密码函数 printf("\n出列的人依次是：\n"); outList(m,n); }