《约瑟夫斯问题求解与停车场停车问题》由会员分享，可在线阅读，更多相关《约瑟夫斯问题求解与停车场停车问题（28页珍藏版）》请在金锄头文库上搜索。
1、计算机软件技术基础2013实验报告I数据结构_031120206_李希文实验一：约瑟夫斯问题求解一、问题描述1、实验题目 约瑟夫斯（Josephus）问题的一种描述是：编号为1，2，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。2、基本要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。3、测试数据n=7，7个人的
2、密码依次为：3，1，7，2，4，8，4。m初值为6（正确的出列顺序应为6，1，4，7，2，3，5）。二、需求分析1、本程序利用循环链表结构模拟出约瑟夫斯问题中在任意人数每人任意编号情况下，各编号的出列顺序2、程序运行后显示提示信息，建立输入处理，输入n输入以及每个人的密码；m的初值。控制输入的n、m及个人密码必为正整数。3、建立一个输出函数，程序自动输出正确的序列。三、概要设计为实现上述功能，用单向循环链表存储结构模拟此过程，因此需要有单向循环链表这一数据结构。1、 定义一个结点类型来储存每个人编号及密码： typedef int ElemType; typedef struct node E
3、lemType mima; int bianhao; struct node *next; SLNODE; 2、单向循环链表抽象数据类型定义： ADT 数据对象：SLNODE类型 数据关系：线性关系 基本操作： SLNODE *initlist();/创建空链表 void createfromRear( SLNODE *head,int n);/尾插法输入循环链表；利用n来控制输入次数 void DelLinkList(SLNODE *p); /* 删除p指针指向结点的后一个结点 */ void xunhuan(SLNODE *head);/循环链表 3、主程序流程及其模块调用关系 1）主函数
4、流程输入起始m调用输出函数，输出出列顺序编号输入n个编号密码输入编号总数n 2）模块调用关系 主程序模块 单向循环链表单元模块：实现单向循环链表的抽象数据类型 单向循环链表单元模块主函数模块 四、详细设计1、单向循环链表结点类型typedef int ElemType;typedef struct nodeElemType mima;int bianhao;struct node *next; SLNODE; 2、实现每个基本操作的伪码 /创建空链表SLNODE *initlist()SLNODE *head;head =(SLNODE *) malloc( sizeof(SLNODE) );
5、head-next = NULL; return head;/尾插法输入循环链表；void createfromRear( SLNODE *head,int n)/注意控制n0; SLNODE *r, *s; ElemType x;int i=1;/利用i来控制输入次数r = head;cout输入第ix; while (x0&imima =x;s-bianhao=i; r-next =s;r=s; /*r永远指向链表的最后一个结点*/ r-next =NULL; i+;if(i=n)/控制输入提示语句出现个数cout输入第ix; /循环链表void xunhuan(SLNODE *head)
6、SLNODE *r;r=head;while(r-next!=NULL)r=r-next;r-next=head;/删除函数；void DelLinkList(SLNODE *p) /* 删除p指针指向结点的后一个结点 */ SLNODE *q; if(p-next !=NULL) q=p-next ; /* q指向p的后继结点 */ p-next=q-next; /* 修改p结点的指针域 */ free(q); /* 删除并释放结点 */ 3、主函数伪码int main()cout实验名称：实验一.约瑟夫斯求解问题endl;cout学号：031120206endl;cout姓名：李希文end
7、l;cout0;coutn;while(n=0);cout输入编号密码0; coutm;while(m=0);cout输出出列顺序编号;shuchu(head,m);coutendl;cout0 & head-next!=head)/控制不再空链表时操作 i=1;/重新计数while(inext=head)/循环时略过头结点 r=r-next;r=r-next;i+;if(r-next=head)/循环时略过头结点r=r-next;j=r-next-mima;coutnext-bianhaonext=NULL;这一步，致使存储空间无法使用。故无法运行。再添加了该步骤后，以解决。 2）结果显示正
8、确，但其后出现了一大串奇怪字符 经检查：在输出函数中忘记控制空链表结束循环，致使该程序无止境循环。加入控制空链表后问题解决。六、使用说明程序运行后用户根据提示输入编号总数n、n个编号密码以及起始m，如输入数字不合要求，程序会要求用户重复输出。程序将自动调用输出函数，输出出列顺序编号。七、调试结果n=7，7个人的密码依次为：3，1，7，2，4，8，4。m初值为6（正确的出列顺序应为6，1，4，7，2，3，5）。八、实验的收获 在该试验中不仅强化了链表知识，还进一步学习并尝试要运用了循环链表。书本知识的学习与实际操作是截然不同的，有可能较熟的知识在编写程序时只因为一个符号而不能运行。编写代码十分考验耐心与细心。九、附录源程序清单#include #include /* puts, printf */#include /* time_t, struct tm, time, localtime */using namespace std;/链表的存储结构；typedef int ElemType;typedef struct nodeElemType mima;int bianhao;struct node *next;
