约瑟夫环-数据结构

时间：2024.4.21

数据结构期末

试验报告

学院：

专业：

学号：

班级：

姓名：

2010.12.12

Joseph约瑟夫环上机实验报告

实验名称：joseph约瑟夫环

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

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

2~）建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。

3~）建立一个输出函数，将正确的输出序列

4~）测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？

实验过程：

1.基本算法以及分析：

本程序主要是以建立单循环链表的形式，建立起一个约瑟夫环，然后根据之前创立的结点，输入结点里的一些数据，如下

typedef struct Node

{

int Index; 在当前环中所处的位置，即编号

int Password; 在当前环中的所带的密码

struct Node *next;

}JosephuNode;

程序有主函数开始，首先，提示输入创建约瑟夫环环数以及每个环上所带的密码。然后，开始调用JosephuNode *Creat_Node函数，利用单循环链表建立起约瑟夫环，tail->next = head;就是将最后一个结点的后继指向头结点，函数结尾 return head; 将约瑟夫环的头指针返回，并将它赋值head，然后主函数继续调用Josephu函数，通过讲head和Password引入函数，以建立两个嵌套循环输出并实现如下功能：

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

2.程序源代码：

约瑟夫环

#include <stdio.h>

#include <malloc.h>

typedef struct Node

{

int Index;

int Password;

struct Node *next;

}JosephuNode;

/////////////////////////////////////////////// 使用单循环链表创建约瑟夫环

JosephuNode *Creat_Node(int numbers)

{

int i,pass;

JosephuNode *head, *tail;

head = tail = (JosephuNode *)malloc(sizeof(JosephuNode)); //申请头结点

for (i = 1; i <numbers; ++i)

{

tail->Index = i;

printf("\t\t请输入第%d号所带密码: ",i); //输入当前结点所带密码

scanf("%d",&pass);

tail->Password=pass;

tail->next = (JosephuNode *)malloc(sizeof(JosephuNode)); //申请一个新结点

tail = tail->next; //指针指向下一个结点

}

tail->Index = i;

printf("\t\t请输入第%d号所带密码: ",i);

scanf("%d",&pass);

tail->Password=pass;

tail->next = head; //将尾结点指针指向表头

return head;

}//Creat_Node

///////////////////////////////////////////////// 约瑟夫环

void Josephu(JosephuNode *head,int Password)

{

int i,j;

JosephuNode *tail;

for (i = 1; tail != head; ++i)

{

for (j = 1; j <Password; ++j)

{

tail = head;

head = head->next;

}

tail->next = head->next;

printf("\n\t\t第%d个出局的人的编号是：%d\t密码是：%d",i,head->Index,head->Password);

Password=head->Password;

free(head);

head = tail->next;

}

i =head->Password;

j=head->Index;

printf("\n\t\t第7个出局的人的编号是：%d\t密码是：%d\n",j,i);

free(head);

} //Josephu

/////////////////////////////////////

void main()

{

int numbers, Password;

char stop;

JosephuNode *head;

printf("\t\t----------------- 约瑟夫环问题 -----------------\n");

printf("\t\t例如：输入约瑟夫问题的人数和起始密码：7,20\n");

printf("\t\t---------------------------------------------------\n");

{

printf("\t\t开始...\n\t\t输入约瑟夫环问题的人数和起始密码：");

scanf("%d,%d", &numbers, &Password);

head=Creat_Node(numbers);

printf("\t\t---------------\n");

printf("\t\t输出结果如下\n");

Josephu(head,Password);

printf("\t\t-----------------------------------------------\n");

printf("\t\t是否继续进行？是Y(y),否N(n)\t");

getchar();

scanf("%c",&stop);

getchar();

printf("\t\t-----------------------------------------------\n");

}while(stop=='y'||stop=='Y');

}

3.运行结果

程序开始的欢迎界面：

输入约瑟夫环的人数7 初始密码20

输入密码：3 1 7 2 4 7 4

输入y程序继续运行，n 则退出

4.心得体会

此程序目前的缺点在于，结点密码数据类型定义的存储类型是int型，不能超过-2147483648～2147483648，一旦超过则程序输出结果有误，另一个缺点就是程序运行当中，一旦中途输入出现错误，则无法返回，必须将当前操作结束等到下个主函数的循环开始，或者直接退出重新运行此程序。优点则在于程序运行速度较快，不会出现输出结果有误的问题

经过这次集中上机的实验，从开始选题到自己上手还是编写程序的过程中，我学会了很多的东西，以前对C语言的知识和算法总是模棱两可的，经过这次练习，在某些方面上还是经过了加强的训练。此次，实验，从开始构建循环链表然后实现约瑟夫环功能的过程中，中途也遇见一些问题，但都逐一克服，相信在这次的实验中提升了较大的自身动手实践能力。学好数据结构！

第二篇：约瑟夫环

沈阳航空航天大学

课程设计报告

课程设计名称：数据结构课程设计课程设计题目：约瑟夫环

院（系）：理学院

专业：信息与计算科学

班级： 84140101

学号： 2008041401025

姓名：王文龙

指导教师：张翼飞

沈阳航空航天大学课程设计报告

沈阳航空航天大学

课程设计任务书

约瑟夫环

沈阳航空航天大学课程设计报告

1 问题分析 ................................................................................................... 3

1.1 问题重述 ............................................................................................ 3

1.2 问题分析 ............................................................................................ 3

2 程序设计 ................................................................................................. 4

2.1 总体设计 ............................................................................................ 4

2.1.1 数据结构设计 ............................................................................... 4

2.1.2 函数设计 ..................................................................................... 4

2.2 函数调用关系 .................................................................................... 5

2.3 主要函数流程图 ................................................................................ 6

3 调试分析 ................................................................................................. 8

4 测试及运行结果 ..................................................................................... 9

参考文献 ..................................................................................................... 10

附录 ....................................................................................................... 11

沈阳航空航天大学课程设计报告错误！未指定书签。

1 问题分析

1.1 问题重述

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

1.2 问题分析

本程序主要是以建立单循环链表的形式，建立起一个约瑟夫环，然后根据之前创立的结点，输入结点里的一些数据，如下

typedef struct Node

{

int Index; 在当前环中所处的位置，即编号 int Password; 在当前环中的所带的密码 struct Node *next;

}JosephuNode;

程序有主函数开始，首先，提示输入创建约瑟夫环环数以及每个环上所带的密码。然后，开始调用JosephuNode *Creat_Node函数，利用单循环链表建立起约瑟夫环，tail->next = head;就是将最后一个结点的后继指向头结点，函数结尾 return head; 将约瑟夫环的头指针返回，并将它赋值head，然后主函数继续调用Josephu函数，通过讲head和Password引入函数，以建立两个嵌套循环输出并实现题目所要求的功能。

沈阳航空航天大学课程设计报告错误！未指定书签。

2 程序设计

2.1 总体设计

2.1.1 数据结构设计

使用单循环链表创建约瑟夫环：

#include <stdio.h>

#include <malloc.h>

typedef struct Node

{

int Index;

int Password;

struct Node *next;

}JosephuNode;

2.1.2 函数设计

表2.1 函数列表

约瑟夫环

沈阳航空航天大学课程设计报告错误！未指定书签。

2.2 函数调用关系

图2.2 函数调用关系图

约瑟夫环

沈阳航空航天大学课程设计报告错误！未指定书签。

2.3 主要函数流程图

（1）Creat_Node函数流程图如图2.3所示

约瑟夫环

图2.3 JosephuNode *Creat_Node流程图

沈阳航空航天大学课程设计报告错误！未指定书签。

（2）Josephu函数流程图

约瑟夫环

图2.4 Josephu函数流程图

沈阳航空航天大学课程设计报告错误！未指定书签。

3 调试分析

1、问题：若输入相同的数字，可能导致程序无法正确的建立单循环链表解决：建立一个函数，使如果输入了相同的数字，则会ruturn error，使程序终止。

2、问题：输入的数据为空时无法继续程序的运行。

解决：经查阅书籍，更正错误，修正程序。

沈阳航空航天大学课程设计报告错误！未指定书

签。

4 测试及运行结果

约瑟夫环

图2.5约瑟夫环的运行结果

沈阳航空航天大学课程设计报告错误！未指定书

签。

参考文献

[1] 严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社，2007

[2] 谭浩强，C语言程序设计教程. 北京：清华大学出版社，2005

[3] 徐孝凯，数据结构课程实验. 北京：清华大学出版社，2006

[4] 秦锋，袁志祥数据结构（C语言版）例题详解与课程设计指导. 北京：中国

科学技术大学出版社，2007

[5] 秦锋，数据结构（C语言版）. 北京：中国科学技术大学出版社，2005

沈阳航空航天大学课程设计报告

附录

源程序清单：

#include <stdio.h>

#include <malloc.h>

typedef struct Node

{

int Index;

int Password;

struct Node *next;

}JosephuNode;

/////////////////////////////////////////////// 使用单循环链表创建约瑟夫环

JosephuNode *Creat_Node(int numbers)

{

int i,pass;

JosephuNode *head, *tail;

head = tail = (JosephuNode *)malloc(sizeof(JosephuNode)); //申请头结点

for (i = 1; i <numbers; ++i)

{

tail->Index = i;

printf("\t\t请输入第%d号所带密码: ",i); //输入当前结点所带密码

scanf("%d",&pass);

tail->Password=pass;

tail->next = (JosephuNode *)malloc(sizeof(JosephuNode)); //申请一个新结点

tail = tail->next; //指针指向下一个结点 }

tail->Index = i;

printf("\t\t请输入第%d号所带密码: ",i);

scanf("%d",&pass);

tail->Password=pass;

tail->next = head; //将尾结点指针指向表头

return head;

}//Creat_Node

///////////////////////////////////////////////// 约瑟夫环

沈阳航空航天大学课程设计报告

void Josephu(JosephuNode *head,int Password)

{

int i,j;

JosephuNode *tail;

for (i = 1; tail != head; ++i)

{

for (j = 1; j <Password; ++j)

{

tail = head;

head = head->next;

}

tail->next = head->next;

printf("\n\t\t第%d个出局的人的编号是：%d\t密码是：%d",i,head->Index,head->Password);

Password=head->Password;

free(head);

head = tail->next;

}

i =head->Password;

j=head->Index;

printf("\n\t\t第7个出局的人的编号是：%d\t密码是：%d\n",j,i); free(head);

} //Josephu

/////////////////////////////////////

void main()

{

int numbers, Password;

char stop;

JosephuNode *head;

printf("\t\t----------------- 约瑟夫环问题 -----------------\n");

printf("\t\t例如：输入约瑟夫问题的人数和起始密码：7,20\n"); printf("\t\t---------------------------------------------------\n");

{

printf("\t\t开始...\n\t\t输入约瑟夫环问题的人数和起始密码："); scanf("%d,%d", &numbers, &Password);

head=Creat_Node(numbers);

printf("\t\t---------------\n");

printf("\t\t输出结果如下\n");

Josephu(head,Password);

沈阳航空航天大学课程设计报告

printf("\t\t-----------------------------------------------\n"); printf("\t\t是否继续进行？是Y(y),否N(n)\t"); getchar(); scanf("%c",&stop); getchar(); printf("\t\t-----------------------------------------------\n"); }while(stop=='y'||stop=='Y');

}

沈阳航空航天大学课程设计报告

约瑟夫环

更多相关推荐：

数据结构约瑟夫环课程设计实验报告: 徐州工程学院信电工程学院数据结构课程设计学院课程设计报告课程名称数据结构课程设计报告专业班级学生姓名学号设计题目约瑟夫环指导教师设计起止时间年月日至年月日徐州工程学院信电工程学院数据结构课程设计徐州工程学院信电...
约瑟夫环数据结构实验报告: 数据结构上机实验报告1需求分析1用一个循环链表实现n个人按顺时针排成一圈每个人看作一个节点每个节点都是一个结构体类型包含三个域序号域data密码域key指向下一个人的指针域next2程序开始时由用户任意输入人数...
数据结构实验报告1约瑟夫环: 一上机实验的问题和要求约瑟夫环问题描述编号是12nngt0的n个人按照顺时针方向围坐一圈每人持有一正整数密码开始时任选一个正整数作为报数上限值m从某个人开始按顺时针方向自1开始顺序报数报到m时停止报数报m的人出...
数据结构约瑟夫环实验报告: 数据结构实验报告实验课程线性表的应用专业年级班级姓名学号实验报告
数据结构实验报告约瑟夫环20xx053003: 工程实践1项目报告20xx年12月成都信息工程学院计算机学院一问题描述约瑟夫环问题描述设有n个人围坐在圆桌周围现从某个位置i上的人开始报数数到m的人就站出来下一个人即原来的第m1个位置上的人又从1开始报数再是数...
数据结构实验报告一-约瑟夫环问题: 实验1约瑟夫环问题1．需求分析（1）输入的形式和输入值的范围：每一次输入的值为两个正整数，中间用逗号隔开。若分别设为n,m，则输入格式为：n,m。不对非法输入做处理，即假设输入都是合法的。（2）输出的形式：输出…
数据结构与算法实验报告-约瑟夫环: 题目约瑟夫环问题班级姓名学号完成日期20xx1228一需求分析1问题描述设有n个人围坐在一个圆桌周围现从第s个人开始报数数到第m的人出列然后从出列的下一个人重新开始报数数到第m的人又出列如此反复直到所有的人全部...

数据结构约瑟夫环问题: 数据结构实验报告题目约瑟夫环问题一设计内容问题描述约瑟夫环问题的一种描述是编号为123n的n个人按顺时针方向围坐一圈每人手持一个密码正整数一开始任选一个整数作为报数上限值从第一人开始顺时针自1开始顺序报数报到m...
数据结构约瑟夫环课程设计报告: 课程设计报告一需求分析1本演示程序中利用单向循环链表存储结构模拟约瑟夫问题的进行程序运行后首先要求用户指定初始报数上限值然后读取个人的密码可设n30此题所用的循环链表中不需要头结点因此在程序设计中应注意空表和非...
约瑟夫环-数据结构: 课程学号实验日期实验序号实验题目实验成绩实验评语北京电子科技学院BESTI实验报告数据结构班级20xx姓名20xx420指导老师实验一约瑟夫环约瑟夫Joeph问题的一种描述是编号为12n的n个人按顺时针方向围坐...
数据结构课程设计约瑟夫环报告: 目录目录1任务书2正文4一数据结构定义41抽象数据类型42存储结构定义43基本操作5二解题过程71问题分解72模块结构73解题思路8三实现9四实验结果131实验数据132实验结果13五实验小结161数据结构使用...
数据结构约瑟夫环的课程设计报告: 武汉工业学院数学与计算机学院数据结构课程设计设计题目约瑟夫环专业班级计算机6班学号100702129姓名王元指导教师李禹生20xx年9月3日1一选题背景题目约瑟夫环问题描述编号为12n的n个人按顺时针方向围坐圈...

数据结构约瑟夫环实验报告（35篇）

热门关注