约瑟夫斯问题求解与停车场停车问题.doc

实验一：约瑟夫斯问题求解 一、问题描述 1、实验题目 约瑟夫斯（Josephus）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。 2、基本要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 3、测试数据 n=7，7个人的密码依次为：3，1，7，2，4，8，4。m初值为6（正确的出列顺序应为6，1，4，7，2，3，5）。 二、需求分析 1、本程序利用循环链表结构模拟出约瑟夫斯问题中在任意人数每人任意编号情况下，各编号的出列顺序 2、程序运行后显示提示信息， 3、建立一个输出函数，程序自动输出正确的序列。 三、概要设计 为实现上述功能，用单向循环链表存储结构模拟此过程，因此需要有单向循环链表这一数据结构。 定义一个结点类型来储存每个人编号及密码： typedef int ElemType; typedef struct node { ElemType mima; int bianhao; struct node *next; }SLNODE; 2、单向循环链表抽象数据类型定义：SLNODE类型 数据关系：主程序流程及其模块调用关系 2）模块调用关系主程序模块 实现的抽象数据类型typedef int ElemType; typedef struct node { ElemType mima; int bianhao; struct node *next; }SLNODE; 2、实现每个操作的伪码 //创建空链表 SLNODE *initlist() { SLNODE *head; head =(SLNODE *) malloc( sizeof(SLNODE) ); head-next = NULL; return head; } //尾插法输入循环链表； void createfromRear( SLNODE *head,int n)//注意控制n0; { SLNODE *r, *s; ElemType x; int i=1;//利用i来控制输入次数 r = head; cout输入第i 个密码; cinx; while (x0i=n) { s =(SLNODE*) malloc( sizeof(SLNODE) ); s-mima =x; s-bianhao=i; r-next =s; r=s; /*r永远指向链表的最后一个结点*/ r-next =NULL; i++; if(i=n)//控制输入提示语句出现个数 { cout输入第i 个密码; cinx; } } } //循环链表 void xunhuan(SLNODE *head) { 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学号：0