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

实验3（第3周实验指导）约瑟夫序列一、实验题目求解《约瑟夫序列》的问题二、实验课时2课时。

三、实验目的１. 掌握“管理信息系统”书本第3章的相关内容２. 学习“单向链表”的数据结构及其有关操作3. 学习编写程序四、实验内容１．学习约瑟夫序列２．学习《约瑟夫序列》程序的例子（本例从一号开始报数）a) 3.作业: 编写程序求解以下问题, 现有运动会门票要赠与你们班（两个班各有67人, 学号从1到67）的10个幸运儿, 要求采用约瑟夫序列来抽签, 全班以学号顺序排号围坐在一张圆桌周围。

从编号为18的人开始顺序报数, 数到18的那个人出列；他的下一个人又从1开始报数, 数到18的那个人又出列；依此规律重复下去, 直到圆桌周围的剩下10个人就是幸运儿。

程序有如下要求:b)读取你们班名单文本文件的内容, 存入一个单向链表, 并以学号排序, 节点要求保存学号, 姓名和性别等信息。

c)针对这个链表进行以上的问题求解。

程序输出10个幸运儿的学号, 姓名, 性别五、实验报告要求1.独立完成, 作业交电子版2.给出程序源代码。

3.写出10个幸运儿的名字4.写实验心得或小结。

六、实验结果:程序源代码如下:#include <stdio.h>#include <stdlib.h>typedef struct node{int number;char info[100]; //将学生的学号, 姓名, 性别等信息都利用info[]来存储struct node *next;}dlnode,*dlink;struct node *head,*p,*temp1,*temp2;FILE *fp;struct node* Creatlist(int num) //创建班级列表{int i;head=(dlnode*)malloc(sizeof(dlnode));head->number=1;head->next=head;p=head;if((fp=fopen("calss2.txt","r"))==NULL) //打开存储学生信息的文本class2.txt{printf("\nCannot open file strike any key exit!");exit(1);}fgets(head->info,100,fp); //头结点可用于存储标题信息for(i=1;i<=num;i++){temp1=(dlnode*)malloc(sizeof(dlnode));temp1->number=i;fgets(temp1->info,100,fp); //将每个学生的信息导入入相应的info字符数组中,//每个学生对应一条info[]信息temp1->next=p->next;p->next=temp1;p=temp1;}p=head;printf("班级名单如下:\n");printf("序号学号姓名性别\n\n"); //printf(" %s\n",head->info);while(p->next!=head){printf(" %s\n",p->next->info);p=p->next;}return head;}void drowlots(dlnode *head,int num,int m) //主处理函数{int i,j;p=head;i=1;j=num;while(j!=10){if(i==m&&p->next!=head){temp2=p->next;//printf(" %d \n",temp2->number); //可输出被淘汰的学生的序号p->next=temp2->next;free(temp2);i=1;j=j-1;}else{if(p->next==head) i--;p=p->next;i++;}}p=head->next;printf("\n10名幸运儿如下:\n\n");printf("序号学号姓名性别\n\n");//printf(" %s\n",head->info);while(p!=head){printf(" %s\n",p->info);p=p->next;}}void main() //主函数{int n,m;n=67;head=Creatlist(n);printf("输入报数的编号: ");scanf("%d",&m);drowlots(head,n,m);syatem(“pause”);}运行结果:七、实验心得:本次实验所涉及的数据结构知识的难度并不高, 所涉及的程序主要用c语言编写, 在主处理函数drowlots()设计的时候, 思路比较清晰。

数据结构实验报告题目：约瑟夫环姓名：学号：专业班级：指导教师：课题工作时间：一．需求分析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()是最主要的函数，分别执行两种算法，并在执行的同时按照出列顺序输出元素信息（编号，密码），并在结尾输出两种算法执行所用的时间长短。

约瑟夫环数据结构实验报告《约瑟夫环数据结构实验报告》摘要：本实验旨在通过使用约瑟夫环数据结构来模拟约瑟夫问题，并通过实验结果分析该数据结构的性能和适用场景。

实验结果表明，约瑟夫环数据结构在解决约瑟夫问题方面具有良好的性能和效率，并且可以应用于一定范围的实际问题中。

1. 引言约瑟夫问题是一个经典的数学问题，描述了一个有n个人的圆桌围坐，从第一个人开始报数，报到m的人离开，然后从离开的人的下一个人开始重新报数，直到所有人离开。

在本实验中，我们将使用约瑟夫环数据结构来模拟这一问题，并分析其性能和适用场景。

2. 实验方法我们首先定义了一个约瑟夫环的数据结构，并实现了相应的插入、删除等操作。

然后，我们使用不同规模的数据集进行了实验，记录了每次操作的时间开销，并进行了性能分析。

3. 实验结果实验结果表明，约瑟夫环数据结构在解决约瑟夫问题方面具有良好的性能和效率。

在不同规模的数据集下，其操作时间基本保持在可接受的范围内，并且随着数据规模的增加，性能表现基本保持稳定。

4. 结论约瑟夫环数据结构在解决约瑟夫问题方面具有良好的性能和效率，并且可以应用于一定范围的实际问题中。

然而，在处理大规模数据时，仍需进一步优化算法和数据结构，以提高性能和效率。

5. 展望未来，我们将进一步研究约瑟夫环数据结构在实际问题中的应用，并探索其在其他领域的潜在价值。

同时，我们也将继续优化算法和数据结构，以提高其性能和适用范围。

综上所述，约瑟夫环数据结构在解决约瑟夫问题方面具有良好的性能和效率，并且具有一定的实际应用价值。

通过本实验，我们对该数据结构有了更深入的了解，并为其在实际问题中的应用提供了一定的参考和借鉴。

约瑟夫环数据结构实验报告约瑟夫环数据结构实验报告引言约瑟夫环是一种经典的数学问题，它涉及到一个有趣的数据结构。

本次实验旨在通过实现约瑟夫环数据结构，深入理解该问题，并探索其在实际应用中的潜力。

本报告将介绍实验的设计和实现过程，并分析实验结果。

实验设计在本次实验中，我们选择使用链表来实现约瑟夫环数据结构。

链表是一种非常灵活的数据结构，适合用于解决约瑟夫环问题。

我们设计了一个Josephus类，其中包含了创建环、添加元素、删除元素等操作。

实验实现1. 创建环在Josephus类中，我们首先需要创建一个循环链表。

我们使用一个头节点来表示环的起始位置。

在创建环的过程中，我们可以选择指定环的长度和起始位置。

2. 添加元素在创建环之后，我们可以通过添加元素来向约瑟夫环中插入数据。

我们可以选择在环的任意位置插入元素，并且可以动态地调整环的长度。

3. 删除元素根据约瑟夫环的规则，每次删除一个元素后，下一个元素将成为新的起始位置。

我们可以通过删除元素的操作来模拟约瑟夫环的运行过程。

在删除元素时，我们需要考虑环的长度和当前位置。

实验结果通过实验，我们得出了以下结论：1. 约瑟夫环数据结构可以有效地模拟约瑟夫环问题。

通过创建环、添加元素和删除元素的操作，我们可以模拟出约瑟夫环的运行过程，并得到最后剩下的元素。

2. 约瑟夫环数据结构具有一定的应用潜力。

除了解决约瑟夫环问题，该数据结构还可以用于其他类似的问题，如任务调度、进程管理等。

3. 约瑟夫环数据结构的时间复杂度较低。

由于约瑟夫环的特殊性质，我们可以通过简单的链表操作来实现该数据结构，使得其时间复杂度较低。

结论本次实验通过实现约瑟夫环数据结构，深入理解了该问题，并探索了其在实际应用中的潜力。

通过创建环、添加元素和删除元素的操作，我们可以模拟出约瑟夫环的运行过程，并得到最后剩下的元素。

约瑟夫环数据结构具有一定的应用潜力，并且具有较低的时间复杂度。

通过本次实验，我们对数据结构的设计和实现有了更深入的理解，并为将来的研究和应用奠定了基础。

数据结构约瑟夫环实习报告一、实习题目约瑟夫环（Josephus Problem）是一种经典的问题，编号为1,2,……,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数上限值M，从第一个人开始按顺时针方向自1开始顺序报数，报到M时停止报数。

报M的人出列，将他的密码作为新的M值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

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

二、实习目的1. 熟悉单向循环链表的存储结构及其应用。

2. 加深对线性链表这种数据结构的基本概念理解。

3. 锻炼较强的思维和动手能力，更加了解编程思想和编程技巧。

三、实习内容1. 采用单向循环链表实现约瑟夫环。

2. 从键盘输入整数m，通过create函数生成一个具有m个结点的单向循环链表。

3. 从键盘输入整数s（1<s<m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，如此循环，直到输出了这个环表的全部结点为止。

四、程序设计1. 概要设计为了解决约瑟夫环的问题，我们可以建立单向循环链表来存储每个人的信息（该人的编号以及其下一个人的编号），及结点，人后通过查找每个结点，完成相应的操作来解决约瑟夫问题。

抽象数据类型定义：数据对象：D数据关系：R1基本操作：操作结果：构造2. 详细设计（1）初始化循环单链表```cvoid initList(LNode *head) {head->next = head;head->number = 0;}```（2）尾插法建立循环单链表```cvoid createFromTail(LNode *head, int m, int pass, int length) { LNode *p = head;int i;for (i = 1; i <= m; i++) {LNode *s = (LNode *)malloc(sizeof(LNode));s->number = i;s->pass = pass;s->next = NULL;p->next = s;p = s;}p->next = head; // 使链表形成一个环}```（3）从链表中删除结点```cvoid deleteFromList(LNode *head, LNode *p) {if (p->next == head) { // 删除的是头结点head = p->next;}p->next = p->next->next;free(p);}```（4）约瑟夫计数```cvoid yuesefu(LNode *head, int m, int n, int *sequence) { int count = 0;LNode *p = head;while (p->next != p) { // 当链表中还有多个结点时循环 count = 0;LNode *q = p->next;while (count < n) {q = q->next;count++;}sequence[count] = q->number; // 记录下出列的人的编号deleteFromList(head, q); // 删除该结点p = q->next; // 从下一个结点又开始计算n = m; // 新的M值}}```五、实验结果与分析通过以上程序设计，我们可以得到约瑟夫环的出列顺序。

一、实验目的1. 理解并掌握约瑟夫问题的基本原理和解决方法。

2. 学习使用循环链表解决线性问题。

3. 提高编程能力和算法设计能力。

二、实验原理约瑟夫问题（Josephus Problem）是一个著名的数学问题，也称为约瑟夫环问题。

问题描述为：N个人围成一圈，从第一个人开始按顺时针方向报数，每数到M的人出列，然后从下一个人开始继续报数，直到所有人都出列。

我们需要找到一种方法，计算出每个人出列的顺序。

三、实验内容1. 创建一个循环链表，模拟N个人围成一圈。

2. 编写一个函数，实现报数和出列操作。

3. 输出每个人出列的顺序。

四、实验步骤1. 定义一个循环链表节点结构体，包含编号和指向下一个节点的指针。

2. 创建一个循环链表，包含N个节点，节点的编号依次为1到N。

3. 编写一个函数`kill(int m, int n)`，实现报数和出列操作：- 初始化一个指针指向第一个节点。

- 从第一个节点开始，按照报数上限M进行报数，每数到M的人出列。

- 更新指针，指向下一个节点，继续报数。

- 重复上述步骤，直到所有节点都被删除。

4. 输出每个人出列的顺序。

五、实验代码```c#include <stdio.h>#include <stdlib.h>// 定义循环链表节点结构体typedef struct Node {int number; // 节点编号struct Node next; // 指向下一个节点的指针} Node;// 创建循环链表Node create(int n) {Node head = NULL, tail = NULL, temp = NULL; for (int i = 1; i <= n; i++) {temp = (Node)malloc(sizeof(Node));temp->number = i;temp->next = NULL;if (head == NULL) {head = temp;tail = temp;} else {tail->next = temp;tail = temp;}}tail->next = head; // 形成循环链表return head;}// 输出循环链表void printList(Node head) {Node temp = head;do {printf("%d ", temp->number);temp = temp->next;} while (temp != head);printf("\n");}// 解决约瑟夫问题void josephus(int m, int n) {Node head = create(n);Node temp = head, pre = NULL;for (int i = 1; i <= n; i++) {for (int j = 1; j < m; j++) {pre = temp;temp = temp->next;}printf("%d ", temp->number);pre->next = temp->next; // 删除节点 free(temp);temp = pre->next;}printf("\n");}int main() {int m, n;printf("请输入报数上限M: ");scanf("%d", &m);printf("请输入人数N: ");scanf("%d", &n);printf("初始站队为: ");josephus(m, n);return 0;}```六、实验结果与分析通过运行实验代码，可以得到每个人出列的顺序。

数据结构实验报告—约瑟夫问题求解《计算机软件技术基础》实验报告 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）。

三、概要设计为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码信息，因此需要循环链表结构体这个抽象数据类型。

1．循环链表结构体抽象数据类型定义：ADT Node{数据对象：D={ai,bi,ci|ai∈ int,bi ∈ int,ci∈(Node*),i=1,2...,n,n ≥0}:数据关系： R=?基本操作：CreatList(int n)// Order(int m,node *l)}ADT node；构建循环单链表；// 输出函数，输出出列顺序并删除链表中的结点；2.ADT 的 C 语言形式说明：typedef struct Node{int num;//结点的数据域，存放编号；int word; //结点的数据域，存放密码；struct Node *next; //结点的指针域，存放指向下一结点的指针；}Node；Node *CreatList( )// 建立循环单项链表；void Order(Node *h) //输出出列顺序并删除结点；3.主程序流程及其模块调用关系:1） . 主程序流程：先提示用户输入相关数据：总人数，运行循环链表结构体模块，输入每个人持有的密码值，创建出新链表，运行输出函数模块，再输入初始密码m值，输出出列序列。

实验报告实验一线性表的基本操作及其应用一、实验目的1、复习C语言程序设计中的知识。

2、熟悉线性表的逻辑结构。

3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。

二、实验内容本次实验提供2个题目，如果实现第一个题目有困难，可做第二个题目题目一：约瑟夫环[问题描述]约瑟夫（Joseph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人可有代表本人的序号。

一开始任选一个正整数m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

试设计一个程序求出出列顺序。

[基本要求]利用单向链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

[测试数据]由学生任意指定。

如：m的初值为5；n的值为7；序号：3，1，7，2，4，8，4；(报告上要求写出多批数据测试结果)[实现提示]程序运行后首先要求用户输入初始报数m，人数n,(设n≤30)。

然后输入各人的序号。

[选作内容]向上述程序中添加在顺序结构上实现的部分实验题目一：约瑟夫环一．需求分析1．利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

2．演示程序以用户和计算机的对话方式执行，即在计算机上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中的非法字符）和运算结构显示在其后。

3.程序执行的命令包括：1）输入报数上限值；2）输入人数以及所持密码；3）输出出列顺序；4）结束2）测试数据4.由学生任意指定。

如：m的初值为5；n的值为7；序号：3，1，7，2，4，8，4；二．概要设计为实现上述程序功能，需建立单向循环链表以存储此结构。

为此，需要一个抽象数据结构类型。

1.链表结点的抽象数据类型定义为：ADT2.本程序包含三个模块：3）主程序模块；4）循环链表的创建模块——实现创建循环链表；5）出列操作的模块——实现最终的出列操作；各模块之间的调用关系如下：出列操作的模块<——主程序模块——>循环链表的创建模块三.详细设计1.元素类型，结点类型和指针类型struct Lnode{int password;struct Lnode *next;};typedef struct Lnode *LinkList;2. 子函数1，创建循环链表int Creatlist_L(LinkList &head,int n)程序的实现：int Creatlist_L(LinkList &head,int n){//利用引用调用得到头指针head;int i;LinkList p,q;printf("请依次输入各位密码：");for(i=1;i<=n;i++){if(i==1){//申请一个空间，将头指针head和指针p均指向第一个结点；head=p=(LinkList)malloc(sizeof(struct Lnode));if(p==0) return 0; //分配存储空间失败}else{q=(LinkList)malloc(sizeof(struct Lnode));if(q==0) return 0;p->next=q;//通过next将下一个结点和前一个结点连起来;p=q;}scanf("%d",&(p->password));//一次输入对应的密码；}p->next=head;//构成循环链表，并返回链表的头指针return 0;}void DeleteNode(LinkList head,int m,int n){LinkList p,q;int j,i;p=head;for(j=1;j<n;j++){//先出列前n-1个人，并依次释放其结点的空间；for(i=1;i<m;i++,p=p->next);//寻找第m个人；printf("%d ",p->password);p->password=p->next->password;//将后一个结点的数据全部赋值于当前p所指的结点q=p->next;p->next=p->next->next;//p指向其下一个的下个一结点，重新开始寻找；free(q);}printf("%d",p->password);//最后一个人出列，并释放其结点所占空间；free(p);} }scanf("%d",&(p->password));//一次输入对应的密码；}p->next=head;//构成循环链表，并返回链表的头指针return 0;}3.主函数的实现，对两个子函数的调用void main(){int n,m;LinkList List;printf("输入人数:");scanf("%d",&n);printf("输入值m:");scanf("%d",&m);Creatlist_L(List,n);DeleteNode(List,m,n);printf("\n");}4.函数的调用关系图反映了演示程序的层次结构：main——>Creatlist;main——>DeleteNode;四调试分析1.由于对引用调用理解的不透侧，导致刚开始修改了很长时间。

数据结构实验报告约瑟夫环约瑟夫环是一个古老而有趣的问题，也是数据结构中一个经典的应用。

它的故事发生在公元前1世纪，当时犹太人正面临罗马的入侵。

为了避免被俘虏，一群犹太士兵决定以一种特殊的方式自杀，而不是被罗马人俘虏。

他们围成一个圈，按照某个规则进行自杀，直到只剩下一个人为止。

这就是著名的约瑟夫环问题。

在这个问题中，我们有n个人，编号从1到n，围成一个圈。

按照一定的规则，从第一个人开始报数，每次报到m的人将被淘汰。

然后，从下一个人开始重新报数，如此循环，直到只剩下一个人为止。

这个问题的解决方法有很多，其中最常见的是使用链表数据结构。

我们可以将每个人表示为一个节点，节点之间通过指针连接，形成一个环形链表。

每次淘汰一个人后，只需要将指针跳过被淘汰的节点，重新连接链表。

为了更好地理解这个问题，我们可以通过一个简单的例子来演示。

假设有10个人，编号从1到10，每次报数到3的人将被淘汰。

首先，我们将这10个人表示为一个环形链表：1->2->3->4->5->6->7->8->9->10->1。

按照规则，第一次报数到3的人是3号，所以我们将3号节点从链表中删除：1->2->4->5->6->7->8->9->10->1。

接下来，从4号节点开始重新报数。

第二次报数到3的人是6号，所以我们再次将6号节点从链表中删除：1->2->4->5->7->8->9->10->1。

以此类推，直到只剩下一个人为止。

通过这个例子，我们可以看到约瑟夫环问题的解决方法非常简单直观。

使用链表数据结构，每次淘汰一个人后，只需要将指针跳过被淘汰的节点，重新连接链表。

这种方法的时间复杂度为O(n*m)，其中n为人数，m为报数的次数。

除了链表，还有其他数据结构可以用来解决约瑟夫环问题。