数据结构实训报告_约瑟夫环JOSEPH环(含代码)

约瑟夫环

------------数据结构上机实验报告

班级：

姓名：

学号：

一．需求分析

1.问题描述

编号是1,2,……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选编号是1,2，……，n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（为正整数）,一开始任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始顺序报数，报到数m时停止报数。报m 的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重1开始报数，如此下去，直到所有人全部出列为止。

2.任务要求

利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。

(1). 输入的形式和输入值的范围

本程序中，输入报数上限值m和人数上限n，密码cipher，均限定为正整数，输入的形式为一个，以“回车符”为结束标志的正整数。

(2). 输出的形式

从屏幕显示出列顺序。

(3). 程序功能

提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。

二．概要设计

本程序分为SCLinList.h和Joseph.c两个文件

1.SCLinList.h

单循环链表头文件。实现的功能为：

(1)初始化： SCLLInitiate()

(2)求当前元素个数： ListLength()

(3)插入一个结点： SCLLInsert()

(4)删除一个结点： SCLLDelete()

(5)取一个结点值： SCLLGet()

(6)判断链表是否为空： SCLLNotEmpty()

2.Joseph.c

Joseph文件。实现的功能为：

(1)删除链表：SCLLDeleteAfter()

(2)约瑟夫环函数：JesephRing()

(3)子函数：fac()

(4)主函数：main()

三．详细设计

1.SCLinList.h

(1)定义结构体typedef struct Node

{

DataType data;

struct Node *next;

}SCLNode;

(2)初始化： SCLLInitiate(SCLNode **head)

(3)求当前元素个数： ListLength(SCLNode *head)

(4)插入一个结点： SCLLInsert(SCLNode *head,int i,DataType x)

(5)删除一个结点： SCLLDelete(SCLNode *head,int i,DataType *x)

(6)取一个结点值： SCLLGet(SCLNode *head,int i,DataType *x)

(7)判断链表是否为空： SCLLNotEmpty(SCLNode *head)

2.Joseph.c

(1)定义结构体：typedef struct

{

int number;

int cipher;

}DataType

(2)删除链表：SCLLDeleteAfter(SCLNode *p)

(3)约瑟夫环函数：JesephRing(SCLNode *head,int m)

(4)子函数：fac(int)

(5)主函数：main(void)

四．源代码

详见代码

五．测试

1.输入n=7,m=20,编码依次为1,2,3,4,5,6,7，密码依次为3,1,7,2,4,7,4时

2.输入n=5,m=10,编码依次为1,2,3,4,5密码依次为1,2,3,4,5时

3.输入n=3,m=3,编码依次为1,2,3密码依次为4,5,6时

六．总结

1．通过此次作业,对链表存储结构有了更深的理解和把握,以及应用链表的知识解决和分析问题的能力有了新的提高，提高了理论和实际相结合的能力。2.经过多次调试以及修改，将原本不能输入数据的程序修改到可以手动输入所需数据的程序，完善了程序的功能，加深了对程序的了解。

3.对代码进行了注释，更深刻的理解了代码中各个语句的含义。

4.通过此次作业，复习了C语言中的函数调用，结构体输入的方法，以及带参数的数组如何实现的方法等。

5.在本次试验中，出现了几个问题，如：定义数组时出现了错误，以及结构体的输入时出现了错误。经过多次调试，终于得到解决。我也对此程序有了更深刻的了解。

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

基础成绩：82分《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现 专业：网络工程 班级：网络102 姓名：张晨曦 学号： 102534 完成日期：2012/6/20 一、试验内容

- 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 struct list {

- int num,code; struct list *next; }; void main() { printf("Joseph问题求解算法的设计与实现\n \n"); int i,j,m=1; int key; // 密码. int n; //人数. list *p,*s,*head; head=(list *)malloc(sizeof(list)); //为头结点分配空间. p=head; //使指针指向头节点 printf("输入人的总个数:"); scanf("%d",&n); for(i=1;i<=n;i++) { printf("第%d个人的密码:\n",i); scanf("%d",&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; printf("\n\n输入初始值:\n"); scanf("%d",&key); printf("\n出列顺序为:\n"); do { j=1; p=head; while(jnext;//使P指向下一结点 j++; } //报数过程. i=p->num; key=p->code; printf("%d\n",i); s->next=p->next;

protel软件实习报告

沈阳航空航天大学 电子设计应用软件训练总结报告 学生姓名：鹿智 学院专业：电子信息工程 班级学号：94020104 指导教师：赵晨光 训练时间：2011年7月8日至2011年7月22日

电子设计应用软件训练任务 【训练任务】 （一）PROTEL部分 1、熟练掌握PROTEL软件的使用； 2、按要求绘制电路原理图； 3、能够按要求建立元件库和封装库； 4、按要求根据电路原理图绘制PCB版图（能够用自动布线和手动布线相结合）。（二）软件设计部分 按照给定的软件设计任务完成相应的软件设计 【基本要求及说明】 （一）PROTEL部分 1、电路原理图图纸尺寸设置为A4； 2、电路原理图见附图； 3、按指定电路图在PROTEL 99中绘制原理图； 4、根据原理图绘制印制板图； 5、根据要求创建原理图器件和该器件的相应的封装。 （二）软件设计部分 按软件设计要求实现相应的功能 【按照要求撰写总结报告】 指导教师年月日 负责教师年月日 学生签字年月日 成绩评定表 评语、建议或需要说明的问题： 成绩 指导教师签字：日期：

PROTEL 训练任务

软件设计任务 约瑟夫（Joseph）问题 [问题描述］约瑟夫（Joseph）问题的一种描述是：编号为1，2，，...,n 的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从l报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 ［基本要求］利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 ［实现提示］程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。

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

信息学院 数据结构实验报告 学号：姓名：班级 课程名称：数据结构实验名称：约瑟夫环 实验性质：①综合性实验√②设计性实验③验证性实验实验时间：2017.10 试验地点： 本实验所用设备：PC及VS2010 【数据结构】： typedef struct _RingNode { int pos; // 位置 struct _RingNode *next; }RingNode, *RingNodePtr; 【算法思想】： 以单链表实现约瑟夫环 用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。（约瑟夫环问题Josephus）。以环状链表实现 【算法描述】： void CreateRing(RingNodePtr pHead, int count) { RingNodePtr pCurr = NULL, pPrev = NULL; int i = 1; pPrev = pHead; while(--count > 0) { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 }

void PrintRing(RingNodePtr pHead) { RingNodePtr pCurr; printf("%d", pHead->pos); pCurr = pHead->next; while(pCurr != NULL) { if(pCurr->pos == 1) break; printf("\n%d", pCurr->pos); pCurr = pCurr->next; } } void KickFromRing(RingNodePtr pHead, int m) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == m) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; pCurr = pCurr->next; if (pPrev == pCurr) { // 最后一个 printf("\n%d", pCurr->pos); // 显示出圈循序 free(pCurr); break; } i++; } } int main()

约瑟夫问题算法及数据结构课程设计报告

线性表的操作及其应用 一、问题描述 线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。 二、基本要求 1、选择合适的存储结构，建立线性表； 2、利用顺序存储结构求解约瑟夫环问题； 3、利用单链表和循环链表分别求解约瑟夫环问题； 4、利用队列求解约瑟夫环问题。 三、测试数据 约瑟夫环的测试数据为7，报数为1至3。 四、算法思想 由于用到四种不同的存储结构，它们的算法思想依次是： 1、首先建立一个顺序表模拟整个约瑟夫环，手动输入顺序表长（即参加约瑟夫循环的人数）和循环的次数和表元素。用已经输出总人数和顺序表长作比较，作为外层循环条件。并对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查顺序表此次是不是我们设立的标记，如果不是则循环次数加1，当达到要求的循环次数时就将循环次数设置为0，输出该元素到屏幕并将总输出元素加1。每次外循环我们都会移到表的下一个位置，作为新的判断条件，每次报到表尾的时候，我们都将重新设置到表尾，作为下次循环的表元素。 2、首先采用链式循环链表建立整个约瑟夫环，手动输入第一次的循环次数和每个人所持下一个循环次数。设立判断指针指向表头，并将该指针是否为空作为外层循环条件。做一个内层循环，将判断指针移动到循环要输出的数，并设立一个前指针指向该指针的前一个位置，输出该元素后，将循环次数重新赋值成该元素。接着判断前指针和判断指针比较，如果相等说明整个表已经输出完毕，否则将删除该位置的元素。 3、用链式队列建立循环约瑟夫环，手动输入人数，第一次的循环次数和每个人所持下一个循环次数。并将每一个元素依次入队列，根据第一次循环次数，建立一个for循环，每一次循环都出队列，如果达到要求的循环次数就输出，否则进队列，这样这个数字就出现在队尾。第一个数输出后，以队列的非空作为循环条件，判断方式如上。 4、用循环队列建立约瑟夫环，将1-7个元素依次进入循环队列，以队列的长度作为与已输出的元素作为判断条件，对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查该该位置的元素是不是我们设立的标记-1，如果不是则循环次数加1，将队首指针移

约瑟夫环实验报告

一．需求分析 1.约瑟夫环（Joseph）问题的一种描述是：编号为1，2……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。 3.程序执行的命令包括： 1）输入初始密码和人数2）输入所有人的密码3）显示输入的所有人的编号及相应的密码4）输出出列密码及编号5）结束 4.测试数据 (1)m=20, n=7, 7个人的密码依次为3，1，7，2，4，8，4 (2)m=20,n=1 (3)m=20,n=0 前面一组为常规数据，后面两组为边缘数据 二、概要设计 为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需要有一个抽象数据类型。该抽象数据类型的定义为： ADT LinkList { 数据对象：D={ ai | ai ∈termset,i=1,2,……n,n>=0}， termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系：R1={ | ai-1, ai ∈D , i=2,……n} 基本操作： LinkList EvaluList(int n);//对单向循环链表进行尾插入赋值 int size(LinkList L);//求链表的节点个数 Status ScanList(LinkList L);//遍历单向循环链表 Status Joseph(LinkList &L,int m);//约瑟夫环的实现 } 此抽象数据类型中的一些常量如下：#define TRUE 1 #define FALSE 0 #define OK 1

约瑟夫环实习报告(参考)

题目：编制一个程序模拟约瑟夫问题 一﹑需求分析 1. 本程序将模拟约瑟夫问题，求出出列的编号，并在每次出列后显示此时的顺序，本程序采用循环链表作为存储结构，无带头结点。 2. 输入可以是文件输入或标准输入，链表长度size>0，各个结点所带的密码值secret>0,第一次的报数m>0，若m<1，将提示更正。 3. 本程序在输入完毕后将先输出刚输入的内容,再提供报数后，开始进行运算,每出列一次将显示出列者和出列后链表顺序。 4. 测试数据：长度7，密码：3,1,7,2,4,8,4，报数初值6；长度-1，密码：3,2,5,6,4；长度5，密码：3,2,5,0,4; 长度5，密码：3,2,5,6,4，报数初值-1,4。 二﹑概要设计 采用循环链表表示约瑟夫环 1. 循环链表的抽象定义： ADT CycList{ 数据对象:D={i a ,i b |i a ,i b ∈ I ,i=1,2,…3,n>0} 数据关系:R={|i a ,i b ∈D,I=1,2…3} 基本操作: CreatList(&L,&in) 初始条件：输入流有效，输入的值合法，申请空间成功 操作结果：构造一个非空的循环链表 PrintList(const L) 初始条件：循环链表L 已存在 操作结果：输出L Fun(&L,Secret) 初始条件：循环链表L 已存在 操作结果：得到出列顺序 } 2. 本程序包含两个模块： 1) 主程序模块 2) 循环链表模块

三﹑详细设计 #include using namespace std; //每个人的号码和密码。 struct people { int NO; int pass; }node; template class Link { private: static Link* freelist;//静态数据成员的头接点。public: struct people element; Link* next;

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

《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现专业：计算机科学与技术 班级： 姓名： 学号： 完成日期：

一、试验内容 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 输入总人数n 创建并初始化 n个结点 输入第一个报 的数key n==0 报数过程 输出出列者 的编号及密 码 结束 n--

四、源程序代码 //Joseph问题求解算法的设计与实现 #include #include struct list { int num,code; struct list *next; }; void main() { printf("Joseph问题求解算法的设计与实现\n \n"); int i,j,m=1; int key; // 密码. int n; //人数 . 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

约瑟夫环课程设计实验报告

《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目：joseph环 姓名： 院系：计算机学院 专业： 年级： 学号： 指导教师： 2011年12月18日

目录 1 课程设计的目的 (2) 2 需求分析 (2) 3 课程设计报告内容 (3) 1、概要设计 (3) 2、详细设计 (3) 3、调试分析 (x) 4、用户手册 (x) 5、测试结果 (6) 6、程序清单 (7) 4 小结 (10) 1、课程设计的目的 （1）熟练使用C++编写程序，解决实际问题； （2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2、需求分析 1、问题描述： 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 2、要求： 利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 3、测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ 输出形式：建立一个输出函数，将正确的输出序列

3、课程设计报告内容 概要设计： 在理解了题目后，我先想到的是我们所学的单链表，利用单链表先建立循环链表进行存贮，建立完循环链表后，我将所要编写的函数分为了两块，一块是经过学过的单链表改编的循环链表的基本操作函数，还有一块是运行约瑟夫环的函数。 详细设计： 我先建立一个结构体，与单链表一样，只是多了一个存密码的code域 struct LinkNode { int data; /删除的是尾结点时（不知道为什么我写程序里总是编译出现错误）{ q->next=head; //重新链接 delete a; len--; return out; } else { q->next=a->next; delete a; len--; return out; } } } } 5、测试结果：

数据结构实验约瑟夫环..

数据结构课程设计题目 1.目的 数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。 2.内容 本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。 约瑟夫环问题的描述是：设编号为1，2，…，n的n个人按顺时针方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出圈，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都出圈为止。令n最大值为100。要求设计一个程序模拟此过程，求出出圈的编号序列。 3.设计： 1）对设计内容进行分析

2）逻辑设计 1、循环链表抽象数据类型定义 typedef struct LNode//定义单循环链表中节点的结构 { int num;//编号 int pwd;//password struct LNode *next;//指向下一结点的指针 }LNode; 2、本程序包含一下几个模块 （1）构造结点模块 LNode *createNode(int m_num,int m_pwd) { 图2 约瑟夫环原理演示图

数据结构课程设计——约瑟夫环报告(含代码)

#include #include typedef struct LNode { //数据域 int cipher; //密码 int number; //编号 struct LNode *next; //指针域 }LNode,*LinkList; void InitList(LinkList &L) //创建一个只有头结点链表{ L = (LinkList)malloc(sizeof(LNode)); if(!L) { exit(1); printf("/n/nError!/n/n"); } L->next = L; } void CreateList(int n,LinkList &L) //初始化循环单链表 { LinkList p,q; q = L; printf("分别输入每个人的密码："); for(int i = 1;i <= n;i++) { int k; scanf("%d",&k); if(k <= 0) { printf("\n\n密码有误!\n\n"); exit(1); } p = (LinkList)malloc(sizeof(LNode)); if(!p) { exit(1); printf("/n/nError!/n/n"); } p->cipher = k; p->number = i;

L->next = p; L = p; } L->next = q->next; free(q); } void PrintList(int x,int n,LinkList L) //输出出列顺序 { LinkList p,q; p = L; for(int i = 1;i <= n;i++) { for(int j = 1;j < x;j++) p = p->next; q = p->next; x = q->cipher; printf("%d ",q->number); p->next = q->next; free(q); } } int main() { printf("=============约瑟夫环==============\n\n\n"); int n,x; LinkList L; L = NULL; InitList(L); //构造空链表 printf("输入初始密码："); scanf("%d",&x); //初始密码为x printf("\n"); printf("输入参与总人数："); scanf("%d",&n); //总共的人数n printf("\n"); CreateList(n,L); //建立好一个约瑟夫环printf("\n\n\n===================================\n\n"); printf("出列编号为："); PrintList(x,n,L); //输出出列顺序 printf("\n\n"); return 0; }

约瑟夫环实习报告

综合实验约瑟夫环实习报告 一、实习题 约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 1．需求分析和说明 分析约瑟夫问题：n个人围成圈，每人各持一个密码，任选一个正整数作为报数上限值m，从第一个人开始，数到第m个人，删除并以出列者密码作为新的m值，从下一个人开始进行第二轮操作，直到所有人都出列。例如n=6, m=3, 处理过程下图。 2．设计 n个人围圈，形成线性关系；处理为逐个删除，故用链式结构合适；又人员围成圆圈，所以此链式结构采用循环方式较好；排号按照一个方向进行，故数据结构采用带头结点的单向循环链表。假设人员以首次的编号命名，对每个人员采用编号和密码加以描述。利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 存储结构： typedef struct Node { ElemType date; //编号 int mima; //密码 struct Node *next; }Node,*LinkList; 单向循环链表： LinkList H; //表头指针 Node *Q,*Pre;//*Q指新建结点，*pre指向当前工作结点 Q=(Node*)malloc(sizeof(Node)); 构造函数： void InitList(LinkList *H); //初始化循环链表 void InPut(LinkList H,int *A);//插入结点 void DelList(LinkList H,int *x, int*a); //删除结点 算法思想： 声明一个Node类型的单向循环链表。从键盘顺序输入n个人的密码, 建立约瑟夫环。，定报数上限，计数并逐个读取并删除第m个结点，更新m的数值，重复上述步骤，直到链表为空。 调用关系： 程序任务简单，故设计在一个main()函数内，有主函数调研相关函数操作。 算法实现框架： 声明数据类型的单向循环链表->输入人数N->依次输入N个人的密码用尾插法建立循环链表->输入M的初值->按规则计数并调用删除函数并显示结点的序号释放该结点—>结点的

约瑟夫环实习报告

约瑟夫环 实习报告 题目：编制一个程序求出约瑟夫环问题的出列顺序。 班级：06计算机A班姓名：林树地学号：0615111044 完成日期：2008-05-01 顺序表实现 一、需求分析 1. 本程序需要由用户在键盘上输入程序中的相关数据。 2. 先输入初始密码m (m>0)和环中人的个数n（n<50），再依次输入每个人的密码。输 入形式是以“回车”为结束标志的整型数。 3. 依次输出约瑟夫环中的出列者的编号。 4. 测试数据： 初值m=20，n=7，7个人的密码依次为：3，1，7，2，4，8，4。 出列顺序应为6，1，4，7，2，3，5。 二、概要设计 以顺序表表示环中的人： 1.顺序表数据类型定义为： ADT sqlist{ 数据对象：D={ a i|a i∈Elemtype,i=1,2,……n；n≥0} 数据关系：R1={| a i-1,a i∈D,i=2,……,n} 基本操作： initlist_sq(&l) 操作结果：构造一个空的顺序表 }ADT sqlist 2．本程序包含两个模块 ①主程序模块 void main(){ 接受命令； 处理命令； } ②顺序表单元模块——实现顺序表抽象数据类型； 各模式块之间的调用关系如下； 主程序模块→顺序表单元模块 三、详细设计 1．顺序表类型 typedef struct{ int elem[50];//存密码

int length; }sqlist; 2．主函数和其他函数的伪码算法 void main() { int m,n;//m为密码，n为小孩个数 cout<<"请输入初始密码m和人数n(n不大于50):"; while(n<1||n>50) { cin>>m>>n; if(n<1||n>50) cout<<"人数不合法，请重输"<>Jos.elem[Jos.length];//存密码 cout<<"出列顺序为："; int i=-1;//i为数组下标（下一值为0） for(int k=0;k

数据结构课程设计报告约瑟夫环完整版

******************* 实践教学 ******************* 兰州理工大学 软件职业技术学院 2011年春季学期 算法与数据结构课程设计 题目：约瑟夫环 专业班级： 姓名： 学号： 指导教师： 成绩：

摘要 约瑟夫环问题是典型的线性表的应用实例，其开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好的库。而对于后者则要求应用程序功能完备，易使用等特点。 经过分析，我们使用MICROSOFT公司的Microsoft Visual C++6.0开发工具，利用其提供的各种面向对象的开发工具，尤其是数据窗口这一能方便而简洁操纵数据库的智能化对象，首先在短时间内建立系统应用原型，然后，对初始原型系统进行需求迭代，不断修正和改进，直到形成用户满意的可行系统。 关键词：单循环链表；c语言；约瑟夫环；

序言 数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。 本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。 通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。

数据结构实验报告—约瑟夫问题求解

《计算机软件技术基础》实验报告 I —数据结构 实验一、约瑟夫斯问题求解 一、问题描述 1.实验题目：编号 1,2,....,n的n个人顺时针围坐一圈，每人持有一个密码（正整数）。 开始选择一个正整数作为报数上限m，从第一个人开始顺时针自 1 报数，报到m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从 1 报数，直至所有人全部出列。 2. 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。 3. 测试数据： n=7,7 个人的密码依次为：3,1,7,2,4,8, 4.m初值为6（正确的出列顺序 应为 6,1,4,77,2,3）。 二、需求分析 1. 本程序所能达到的基本可能： 该程序基于循环链表来解决约瑟夫问题。用循环链表来模拟n 个人围坐一圈，用链表 中的每一个结点代表一个人和他所代表的密码。在输入初始密码后m，对该链表进行遍历，直到第 m个结点，令该结点的密码值作为新的密码值，后删除该结点。重复上述过程，直至所有的结点被释放空间出列。 2. 输入输出形式及输入值范围： 程序运行后提示用户输入总人数。输入人数 n 后，程序显示提示信息，提示用户输入第 i个人的密码，在输入达到预定次数后自动跳出该循环。程序显示提示信息，提示用户输入 初始密码，密码须为正整数且不大于总人数。 3．输出形式 提示用户输入初始密码，程序执行结束后会输出相应的出列结点的顺序，亦即其编号。 用户输入完毕后，程序自动运行输出运行结果。 4.测试数据要求： 测试数据 n=7，7 个人的密码依次为：3， 1， 7， 2， 4， 8， 4。 m初值为 6（正确的出列 顺序应为6， 1， 4，7， 2， 3， 5）。 三、概要设计 为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码

约瑟夫环代码C++版

实习报告 题目：约瑟夫环 班级：031014 姓名：刘嵩学号：03101409 完成日期：2011.11.16 一、需求分析 1.本演示程序中，要求用户输入人数n和初始报数上限的值m。并依次输入n个人 的密码（password）。程序输出n个人的出列顺序。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之 后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和越算结 果显示在其后。 3.程序执行的命令包括 1）构造链表2）依照题意对链表进行操作，每次删除一个链表的节点并将删 除节点的编号输出3）结束 4. 测试数据 Sample input 7 20 3 1 7 2 4 8 4 Sample output 6 1 4 7 2 3 5 二、概要设计（算法描述） 为实现上述程序功能，应以循环列表表示n个人围坐一圈。循环列表每个节点所要包含的信息包括：1.每个人的编号 2.每个人的密码 3.指向下一个节点的指针。建好链表后，从链表的首个节点开始，顺着链表向后移m次，得到一个节点Node。输出Node的编号，并将Node从链表中删除，然后讲Node的密码值作为新的m。重复以上步骤，直到所有节点均被从链表中删除为止。算法复杂度为O(m*n)。 三、详细设计 代码如下: #include using namespace std; struct node { int id; int password; node* next; }; int main() { i nt m,n; c out<<"Enter the number of people:"; c in>>n; c out<<"Enter the value of 'm':";

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

数据结构实验报告 题目：约瑟夫环 姓名： 学号： 专业班级： 指导教师： 课题工作时间：

一．需求分析 1.约瑟夫环（Joseph）问题的一种描述是：设有编号1,2,3。。。n(n>0)的N个人围成一个圈，每个人持有一个密码（正整数）。开始时从第k（1<=k<=n）个人按顺时针方向自1开始顺序报数，报到m（m为第K个人的密码）的人出圈，再以这个人顺时针方向上的下一个人的密码为m，并开始重新从1报数。如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。 3.测试数据 (1)m=20, n=7, 结果依次为为3，1，7，2，4，8，4 (2)m=20,n=1 (3)m=20,n=0 前面一组为常规数据，后面两组为边缘数据 二、概要设计 本程序是多文件程序，构成的函数有 int main() 主函数，输出出队序列 int initsuiji() 随机数产生初始化 int suiji(int x,int y) 随机数产生函数 int InitList(SqList &L) 初始化顺序表 int ListInsert(SqList &L,int i,ElemType e) 在顺序表中插入元素 int ListDelete(SqList &L,int i,ElemType &e) 删除顺序表中的元素 int shunxu(int number) 顺序存储算法 JosephuNode *Creat_Node(int numbers) 创建单循环链表 void Josephu(JosephuNode *head,int Password) 添加元素信息 int lianbiao(int number) 链表算法 其中，void main()是最主要的函数，分别执行两种算法，并在执行的同时按照出列顺序输出元素信息（编号，密码），并在结尾输出两种算法执行所用的时间长短。 三、详细设计 头文件 #include #include #include

数据结构约瑟夫环的课程设计报告

武汉工业学院数学与计算机学院 数据结构课程设计 设计题目：约瑟夫环 专业大类计算机 班级计算机6班 学号 100702129 姓名王元 指导教师李禹生 2011年9月3 日

一．选题背景： 题目：约瑟夫环 问题描述： 编号为1,2，…..，n的n个人按顺时针方向围坐圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新重新从1报数，如此下去，直至所有人全部出列为止。 基本要求： ⑴建立模型，确定存储结构； ⑵对任意 n个人，密码为 m，实现约瑟夫环问题； ⑶出圈的顺序可以依次输出，也可以用一个数组存储。 设计指导思想： 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。其次，建立一个不带头结点的循环链表并由头指针 first 指示。最后，设计约瑟夫环问题的算法。下面给出伪代码描述，操作示意图如图 2-1 所示。

二．方案论证： 本方案通过建立单循环链表模拟了约瑟夫问题；首先，建立一个结构体node，然后给他开辟一个储存空间；利用头指针head标记链表，利用尾指针向后移将建立的结点连接成我们需要的单循环链表， 过程如下： 约瑟夫问题中的人数个数即为链表的长度，链表中node->num 编号n，node->data为每个人的密码。建立单循环链表后，通过初始报数上限找到出列的结点，输出该结点的node->num值，将该结点中的data中数作为新密码开始下一个步的开始，将该结点从链表中删除，并释放该结点的空间。重复此过程，直到剩下最后一个结点，就直接将该结点中的num值输出，删除该结点，并释放该结点的空间。输出的num值即为约瑟夫中人的编号。 三．过程论述： typedef struct node { int data; int num; struct node *next; }listnode; 定义一个结构体用来储存学生的编号和所携带的密码 for(i=1;i<=n;i++) { printf("输入第%d号同学的密码:",i); scanf("%d",&j);//输入学生所带密码 p1->next=(listnode*)malloc(sizeof(listnode));//建立一个新的空间，并将它的地址赋给p1->next p1=p1->next; p1->data=j; p1->num=i;//对结点的num和data成员赋值 p1->next=head->next;//构成单循环链表 } 定义指针p1，然后建立一个新结点并将p1->next指向它的地址，然后将这个地址赋给p1，最后将head->next赋给p1->next,构成一个单循环链表，并不断在尾部插入新的结点，直至所有人都进入循环链表中，而且在循环的过程中给结点的num和data成员赋值

数据结构约瑟夫环课程设计报告书

《数据结构》课程设计报告书 设计题目：约瑟夫环 专业： 班级： 姓名： 指导教师： 完成日期：

目录 一、问题描述 (1) 二、基本要求 (1) 三、测试数据 (1) 四、算法思想 (2) 五、模块划分 (3) 六、数据结构 (4) 七、源程序 (4) 八、界面设计 (6) 九、运行与测试 (6) 十、总结 (8) 十一、思考与感悟 (9)

课程设计设计报告书 一、问题描述 约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫问题的描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈, 每人有一个密码（整数），留作其出圈后应报到后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景，后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。p->link=head解决问题的核心步骤：先建立一个具有n个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。 二、基本要求 (1)输入的形式和输入值的范围：输入的形式是以数字的形式输入，输入范围为-2147483648～2147483648 (2)输出的形式：字符串形式输出 (3)程序所能达到的功能：达到符合约瑟夫环要求的响应功能。 三、测试数据 进入程序，显示“1.开始游戏0.退出游戏”输入非0数进入游戏，输入0退出游戏。 进入游戏后显示“输入总人数”，输入大于0的整数；若输入错误，则光标处清空，重新输入。 后提示“输入开始人的序号”；范围是大于零，小于总人数的整数，若输入错误，则光标处清空，重新输入。 后提示“输入间隔数字”，范围是任意正整数；若输入错误，则光标处清空，重新输入。 按回车键，显示结果，并重新询问“1.开始游戏0.退出游戏”。

数据结构实验一约瑟夫问题

HUNAN UNIVERSITY 课程实习报告 题目：约瑟夫问题 学生姓名刘海龙 学生学号201326010115 专业班级软件1 3 0 1 指导老师李晓鸿 完成日期 2 0 1 4 年11 月18 日

一、需求分析 1.输入的形式和输入值的范围 本程序中，输入的人数n和报数值m均为整数，n、m均大于0，输入的形式为：n，m （n、m输入时用逗号隔开） 2.程序功能 提供用户从键盘输入约瑟夫环的关键数据，人数n和报数值m，并显示出列顺序。 3.输出的形式 在DOS界面上输出这n个数的输出序列。 4.测试数据 ①输入（n，m均为正整数，且n>m） 10，3 输出 3 6 9 2 7 1 8 5 10 4 ②输入（n，m均为正整数，且n

二、概要设计 抽象数据类型 n（n为正整数）个人的编号为1~n，1相当于唯一的“第一元素”，n相当于唯一的“最后元素”，除最后元素n外，剩下的n-1个编号均有唯一的后继，除第一元素1外，剩下的n-1个编号均有唯一的前驱，符合线性结构，故应以线性表实现该结构。 ADT alist { 数据对象： D={a i| a i∈int，i=1，2，…，n，n≥0}. 数据关系： Rl={ | a i-1，a i∈D，i=2，…，n} 基本操作： InitList（&L，size）//构造一个空线性表L。 Append(&L，e) //新元素e入表 Remove(&L，i) //删除表中第i个元素，即将i之后的元素往前移一位。 DesList（&L）//销毁线性表，释放内存空间 } 无论选择哪种数据结构都应有一个结构初始化操作及相应的结构销毁操作，本程序的结构初始化操作为：InitList（&L，size），结构销毁操作为DesList（&L）。 在将n个人的编号存进线性表时，需要一个添加操作，故设计Append(&L， e)，其用于向线性表表尾添加新元素e。 “出列”相当于删除线性表中某个指定的元素，这就需要一个删除操作，故设计Remove(&L，i)，其根据下标索引需要删除的元素，“删除”即相当于将该元素 之后的所有元素向前移动一位。 算法的基本思想 n个人的编号为1,2,3,…,n(n>0)，并且这n个人根据编号大小依序排列，即将这n 个编号依序存入线性表中，报数值m为正整数。 ①．编号为1的人从1开始依序报数，即从线性表的第一个元素起开始访问，并依 序逐个访问它的下一个元素。 ②．当轮到剩余人群中编号最大的人报数时，剩余人中编号最小的作为他的下一位， 继续报数，即当线性表的表尾元素访问完后，将表头元素作为下一个访问对象。 ③．数到m时报数停止，并且数到m的人出列，他的下一位从1开始重新报数。 即访问进行到第m次时停止，将第m次访问到的元素从表中删除，并在DOS界 面上输出对应的编号，然后从它的下一个元素开始新一轮的访问（每轮m次）。 ④．重复步骤2、3，直到出列n个人为止，即当表内元素均被删除为止，此时， 整个出列序列已经输出在DOS界面上。