顺序表实现约瑟夫环的问题,C语言

计算机科学与工程学院

《算法与数据结构》试验报告[一]

专业班级10级计算机工程02 试验地点计算机大楼计工教研室学生学号1005080222 指导教师蔡琼

学生姓名肖宇博试验时间2012-2-29

试验项目算法与数据结构

试验类别基础性（）设计性（）综合性（√）其它（）

试验目的及要求（1）掌握用VC++上机调试线性表的基本方法；（2）掌握顺序表的存储结构以及基本运算的实现。

成

绩评定表

类别评分标准分值得分合计

上机表现

积极出勤、遵守纪律

主动完成设计任务

30分

程序与报告

程序代码规范、功能正确

报告详实完整、体现收获

70分

备注：

评阅教师：

日期：年月日

试验内容

一、实验目的和要求

1、实验目的：

（1）掌握用VC++上机调试线性表的基本方法；

（2）掌握顺序表的存储结构以及基本运算的实现。

2、实验内容

约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，m为任意一个正整数。从第一个人开始顺时针

方向自1起顺序报数，报到m时停止并且报m的人出列，再从他的

下一个人开始重新从1报数，报到m时停止并且报m的人出列。如

此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，

对任意给定的m和n，求出出列编号序列。

3、实验要求：用顺序表实现。

二、设计分析

根据实验要求，采用顺序表来完成本次实验。

实验中定义了两个顺序表，一个用来存储n个人的序号，另一个用来存储n个人的出队顺序及序号。

程序中充分考虑了如果出队的元素大于队列的元素个数时应该有的情况，如果出现这样的错误就提示！否则继续出队！

三、源程序代码

#include

#include

#define MAXSIZE 10 // 宏替换最大值

typedef struct

{

int data[MAXSIZE];

int length;

}Sqlist;

void CreatList(Sqlist *&L,int a[],int n) //创建顺序表

{

L=(Sqlist *)malloc(sizeof(Sqlist));

for(int i=0;i

{

L->data[i]=a[i];

}

L->length=n;

}

void InitList(Sqlist *&L) //初始化顺序表

{

L=(Sqlist *)malloc(sizeof(Sqlist));

L->length=0;

}

void DestoryList(Sqlist *&L) //释放顺序表空间{

free(L);

}

void josephus(Sqlist *&L) //约瑟夫环的核心代码{

int t=0;

int m=0;

printf("请输入数到几个人出来");

printf("\n");

scanf("%d",&m);

if(m>L->length)

{

printf("没有这么多人呀！╮(╯_╰)╭");

}

else

{

printf("出列顺序为：");

for(int q=L->length;q>=1;q--)

{

t=(t+m-1)%q;

printf("\n");

printf("\t%d\t",L->data[t]);

for(int j=t+1;j<=q-1;j++)

L->data[j-1]=L->data[j];

}

printf("\n");

}

}

void main()

{

Sqlist *s;

InitList(s);

int a[MAXSIZE];

int n=0;

printf("请键入要输入几个数");

printf("\n");

scanf("%d",&n);

for(int i=0;i

{

a[i]=i+1;

}

CreatList(s,a,n);

josephus(s);

DestoryList(s);

printf("\n");

}四、测试用例（尽量覆盖所有分支）

1.当输入1，2，3，4。。。。。。n的这些数字范围以内的话，可以得到正确的结果如图：

2.当输入的n比较大的时候的情况如图：

3.当输入序列少，出对数大时:

4.当输入要出列的元素大于队列里的元素，这将会提示错误如图：

c语言实现约瑟夫环问题

(一)基本问题 1?问题描述 设有编号为1,2,…小的n (n> 0)个人围成一个圈，每个人持有一个密码m。从第一个 人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m 时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。建立模型，确定存储结构。对任意n个人，密码为m, 实现约瑟夫环问题。 2.数据结构设计 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点 定义为如下结构类型： struct Node { int data; Node *n ext; }； 其次，建立一个不带头结点的循环链表并由头指针first指示 3.算法设计 1、工作指针first, r, s, p, q初始化 2、输入人数（n）和报数（m） 3、循环n次，用尾插法创建链表 Node *q; for（i nt i=1;i<=n ;i++） { Node *p; p=new Node; p-> data =i;

p->next=NULL; if(i==1) L=q=p; else { q->next=p; q=q->next; } } q->next=L; if(L!=NULL){return(L);} 4、输入报数的起始人号数k; 5、Node *q = new Node; 计数器初始化i=1; 6、循环n 次删除结点并报出位置(其中第一个人后移当 k 个) inext; 删除p 结点的后一结点q q=p->next; p->next=q->next; *L = p->next; 报出位置后Delete q; 计数器i++; 运行流程图

约瑟夫环实验报告

一．需求分析 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.能熟练地利用顺序存储结构实现线性表的基本操作。 3.能熟练地掌握顺序存储结构中算法的实现。 二、实验内容 1.建立含有若干个元素的顺序表，并将结果在屏幕上输出。 2.对刚建立的顺序表实现插入、删除、修改、查找，并将结果在屏幕上输出。 3.解决约瑟夫问题：假设有n个人按1、2、3、…、n的顺序围成一圈，现在，从第s 个人开始按1、2、3、…、m的顺序报数，数到m的人出圈，接着从出圈的下一个人开始重复此过程，直到所有人出圈为止。试用顺序表解决这个问题。 三、算法描述 1.第1题、第2题的算法提示 对第1题，先定义顺序表的数据类型，然后以1～n的序号建立顺序表，将输出结果单独定义成一个函数，以便后面反复使用它。对第2题，为操作方便，将插入、删除、修改、查找等操作都定义成单独的子函数形式。为查看这些操作的效果，可以在调用前后分别输出表的结果。 2.第3题的算法提示 对于第3题，可以将n个人的编号存入一个一维数组中，表的长度就是人数n，因此，就可以用一维数组来代替顺序表。算法的思想是：先求出出圈人的编号，用一个临时单元保存它，然后从出圈人的后一个开始，直到最后一个，都按顺序向前移动一个位置，再将临时单元中的出圈人编号存入最后。当这个重复步骤完成后，数组中存放的是出圈人的逆序列。本题中，围圈的人数n、出圈的报数号m、开始报数的位置s在程序中预先给定为10、3、2。当然，也可以从键盘临时输入。 四、源程序 第1、2题的源程序及程序清单 #include using namespace std; const int MaxSize=100; class List{ public: List(){length=0;} // 建立一个空表 List(int a[], int n); //建立一个长度为n的顺序表 ~List(){} int Length(){return length;} //求线性表的长度

约瑟夫问题

一问题描述 1 题目内容：约瑟夫(Joseph)问题的一种描述是:编号为1,2,..., n的n 个人按顺时针方向围坐一圈, 每人持有一个密码(正整数)。一开始选任一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将它的密码作为新的m值。试设计一个程序求出出列顺序。 2 基本要求：利用单项循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 3 测试数据：m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4（正确的出列顺序应为6，1，4，7，2，3，5）。 二需求分析 程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列 三概要设计 利用单项循环链表存储结构模拟此过程 1 循环链表的抽象数据类型 循环链表是单链表的一种变化形式，把单链表的最后一个节点的next指针指向第一个节点，整个链表就形成了一个环。

2 循环链表的基本操作（仅列出用在本程序的） creat(n) 操作结果：构造一个长度为n的无头节点的循环链表,并返回指向最后一个节点的指针 find(m,s) 初始条件：循环链表存在 操作结果：找到当前元素（即s）后面第m个元素 print(&m,&n,&s) 初始条件：循环链表存在 操作结果：从s中删除约舍夫问题中下一个被删除的元素，并将此元素显示在屏幕上 3 本程序包括4个模块： 主程序模块； 创建循环链表模块； 找节点模块； 删节点模块； 各模块调用关系如下图所示：

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

《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目：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、测试结果：

顺序表实现约瑟夫环的问题c语言

计算机科学与工程学院 《算法与数据结构》试验报告[一] 专业班级10级计算机工程02 试验地点计算机大楼计工教研室学生学号1005080222 指导教师蔡琼 学生姓名肖宇博试验时间2012-2-29 试验项目算法与数据结构 试验类别基础性（）设计性（）综合性（√）其它（） 试验目的及要求（1）掌握用VC++上机调试线性表的基本方法；（2）掌握顺序表的存储结构以及基本运算的实现。 成绩评定表 类别评分标准分值得分合计 上机表现积极出勤、遵守纪律 主动完成设计任务 30分 程序与报告程序代码规范、功能正确 报告详实完整、体现收获 70分

备注： 评阅教师： 日期：年月日 试验内容 一、实验目的和要求 1、实验目的： （1）掌握用VC++上机调试线性表的基本方法； （2）掌握顺序表的存储结构以及基本运算的实现。 2、实验内容 约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，m为任意一个正整数。从第一个人开始顺时针 方向自1起顺序报数，报到m时停止并且报m的人出列，再从他的 下一个人开始重新从1报数，报到m时停止并且报m的人出列。如 此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程， 对任意给定的m和n，求出出列编号序列。 3、实验要求：用顺序表实现。 二、设计分析 根据实验要求，采用顺序表来完成本次实验。 实验中定义了两个顺序表，一个用来存储n个人的序号，另一个用来存储n个人的出队顺序及序号。 程序中充分考虑了如果出队的元素大于队列的元素个数时应该有的情况，如果出现这样的错误就提示！否则继续出队！ 三、源程序代码 #include #include #define MAXSIZE 10 // 宏替换最大值 typedef struct { int data[MAXSIZE]; int length; }Sqlist; void CreatList(Sqlist *&L,int a[],int n) //创建顺序表 { L=(Sqlist *)malloc(sizeof(Sqlist));

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

《数据结构》课程实验 实验报告 题目：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

约瑟夫环问题讲解

2009年02月24日星期二下午 05:03 问题描述:约瑟夫环问题；有N个人围成一个环，从第一个人开始报数，报到M 的人退出环，并且由他的M值来代替原有的M值，要求输出离开环的顺序。#include #include using namespace std; //结点中数据域的类型定义 typedef struct { int number;//标号 int chipher;//手中的值 }DataType; //带头结点的单循环链表 typedef struct node { DataType data; struct node *next; }Scnode; //初始化 void MyInit(Scnode **head)//指向指针的指针。 { if((*head=(Scnode *)malloc(sizeof(Scnode)))==NULL) exit(1);//动态分配 (*head)->next=*head; } //插入 int MyInsert(Scnode *head,int i,DataType x) { Scnode *p,*q; int j; p=head->next;j=1; while(p->next!=head&&jnext; j++; }

if(j!=i-1&&i!=1) {cout<<"erro!!!!!!!!!"; return 0;} if((q=(Scnode *)malloc(sizeof(Scnode)))==NULL) exit(1); q->data=x; q->next=p->next; p->next=q; return 1; } //删除 int MyDelete(Scnode *head,int i,DataType *x) { Scnode *p,*q; int j; p=head;j=1; while(p->next!=head&&jnext; j++; } if(j!=i-1) {cout<<"erro!!!!!!!!!"; return 0;} q=p->next; *x=q->data; p->next=p->next->next; free(q); return 1; } //取数据元素 int MyGet(Scnode *head,int i,DataType *x) { Scnode *p; int j; p=head;j=0;

数据结构经典题目及c语言代码

《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include #include // 链表节点 typedef struct _RingNode { int pos; struct _RingNode *next; }RingNode, *RingNodePtr; // 创建约瑟夫环，pHead:链表头指针，count:链表元素个数 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 KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr;

C语言课程设计报告约瑟夫环胡存夫

C语言课程设计报告约瑟夫环胡存夫

沈阳航空航天大学 课程设计报告 课程设计名称：C语言课程设计课程设计题目：约瑟夫环 院（系）：计算机学院 专业：计算机科学与技术班级：3410301 学号： 姓名：胡存夫 指导教师：丁一军

目录 1 课程设计介绍 ......................................................... 错误!未定义书签。 1.1课程设计内容及要求 ........................................... 错误!未定义书签。 1.2系统需求............................................................... 错误!未定义书签。 2 课程设计原理 ......................................................... 错误!未定义书签。 2.1课设题目粗略分析 ............................................... 错误!未定义书签。 2.2.1 功能模块图..................................................... 错误!未定义书签。 2.2.2 流程图分析..................................................... 错误!未定义书签。 3 调试与分析............................................................. 错误!未定义书签。 3.1调试过程............................................................... 错误!未定义书签。参考文献 .................................................................... 错误!未定义书签。附录（关键部分程序清单） ................................... 错误!未定义书签。

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

《计算机软件技术基础》实验报告 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.约瑟夫环（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

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

数据结构课程设计题目 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 约瑟夫环原理演示图

c语言实现约瑟夫环问题

（一）基本问题 1.问题描述 设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m 时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。建立模型，确定存储结构。对任意n个人，密码为m，实现约瑟夫环问题。 2.数据结构设计 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型： struct Node { int data; Node *next; }; 其次，建立一个不带头结点的循环链表并由头指针first指示 3.算法设计 1、工作指针first，r，s，p，q初始化 2、输入人数（n）和报数（m） 3、循环n次，用尾插法创建链表 Node *q; for(int i=1;i<=n;i++) { Node *p; p=new Node; p-> data =i;

p->next=NULL; if(i==1) L=q=p; else { q->next=p; q=q->next; } } q->next=L; if(L!=NULL){return(L);} 4、输入报数的起始人号数k; 5、Node *q = new Node;计数器初始化i=1; 6、循环n次删除结点并报出位置（其中第一个人后移k个） 当inext; 删除p结点的后一结点q q=p->next; p->next=q->next; *L = p->next; 报出位置后Delete q; 计数器i++; 运行流程图

C语言实现约瑟夫环

《约瑟夫环》实验报告 专业：网络工程班级 学号姓名 一、问题描述： 约瑟夫问题的一种描述是：编号为1，2，……，n点的n个人按顺时针方向围坐一个圈，每人持有一个密码。一开始选一个正整数作为报数上限值m，从第一个人开始从顺时针方向自1开始报数，报到m时停止。报到m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始从新从1报数，如此下去，直达所有人出列。 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。 测试数据：m的初始值为20；n=7，7个人的密码依次是3，1，7，2，4，8，4，首先m的值为6（正确的出列顺序为6，1，4，7，2，3，5） 二、程序设计的基本思想，原理和算法描述： 采用结构体定义单链表，格式为：struct Lnode {int number; int password; struct Lnode*next; }Lnode,*p,*q,*head; 其中number是人的排列序号，password是各人所持有的密码值，next是节点指针。Lnode是节点变量，p、q是节点，head是头指针。 程序的代码：定义变量n，i,m,j 输入人的数量n If n<=0或n>30 重新输入n值 当0password 尾指针指向头指针，形成循环链表 输入初始报数上限值m 当1<=j<=n时 循环找出报m的节点p 输出报m节点的编号p->number 将p->password赋给m值 删除此节点 结束 三、源程序及注释： #include #include struct Lnode/*定义链表*/ {int number;

约瑟夫环问题源代码(C语言)

约瑟夫环问题如下：已知n 个人(n>=1)围桌一园桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m 的那个人出列。他的下一个人又从1开始报数，数到m 的那个人又出列。依此规则重复下去，直到所有人全部出列。求解最后一个出列的人的编号。 本次实验是以顺序表求解约瑟夫环问题，程序流程图及程序运行结果如下： 程序代码如下： #include #include #include using namespace std; struct Node //循环节点的定义 { int number; //编号 Node *next; }; Node *CreateList(Node *L,int &n,int &m); //建立约瑟夫环函数 void Joseph(Node *L,int n,int m); //输出每次出列号数函数 Node *DeleteList(Node **L,int i,Node *q); //寻找每次出列人的号数 int LengthList(Node *L); //计算环上所有人数函数 void main() //主函数 { system("color 75"); //设置颜色以美观 Node *L; L=NULL; //初始化尾指针 int n, m; cout<<"请输入人数N ："; cin>>n; //环的长度

if(n<1){cout<<"请输入正整数!";} //人数异常处理 else { cout<<"请输入所报数M："; cin>>m; if(m<1){cout<<"请输入正整数!";} //号数异常处理 else { L=CreateList(L,n,m); //重新给尾指针赋值 Joseph(L,n,m); } } system("pause"); } Node *CreateList(Node *L,int &n,int &m) //建立一个约瑟夫环（尾插法） { Node *q; for(int i=1;i<=n;i++) { Node *p; p=new Node; p->number=i; p->next=NULL; if(i==1) L=q=p; //工作指针的初始化 else { q->next=p; q=q->next; } } q->next=L; if(L!=NULL){return(L);} //返回尾指针 else cout<<"尾指针异常!"<>k; if(k<1||k>n){cout<<"请输入1-"<

约瑟夫问题的C语言算法(循环链表)

算法：n个人围成一圈，每个人都有一个互不相同的密码，该密码是一个整数值，选择一个人作为起点，然后顺时针从1到k（k为起始点手中的密码值）数数。数到k的人退出圈子，然后从下一个人开始继续从1到j（j为刚退出圈子人的密码数）数数，数到j的人退出圈子。重复上述操作，直到最后一人 代码如下： # include # include //free(),malloc()所在库文件 # define n 9 //数字个数 # define overflow 0 //判断溢出情况 int keyw[n]={4,7,5,9,3,2,6,1,8}; //欲处理数的数组 typedef struct lnode //声明结构体，包括两个成员，一个是数值，另一个是指向下个结点的指针 { int keyword; struct lnode *next; }lnode,* linklist; void joseph(linklist p,int m,int x) //定义约瑟夫环函数：p为循环列表头结点，m 为初始值，x为数组长度 { linklist q; //声明变量 int i; if(x==0)return; q=p; m%=x; if(m==0)m=x; for(i=1;i<=m;i++) //找到下一个结点 { p=q; q=p->next; } p->next=q->next; i=q->keyword; printf("%5d",q->keyword); free(q); joseph(p,i,x-1); //递归调用 } int main() { int i,m; linklist lhead,p,q;

约瑟夫环问题 实验报告完整版

实验报告 实验课名称：数据结构实验一 实验名称：约瑟夫环问题 时间 班级000 学号000 姓名神刀公 子 1.问题描述 约瑟夫环问题 （1）问题描述 设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 （2）基本要求 建立模型，确定存储结构。 对任意n个人，密码为m，实现约瑟夫环问题。 出圈的顺序可以依次输出，也可以用一个数组存储。 （3）思考： 采用顺序存储结构如何实现约瑟夫环问题？ 如果每个人持有的密码不同，应如何实现约瑟夫环问题？ 2.数据结构设计 由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：struct Node { int data; //数据域 Node *next; //next指针指向下一个结点 }; 3.算法设计 问题要求建立模型，确定存储结构，之后对任意n个人，密码为m，实现约瑟夫环问题，出圈的顺序可以依次输出，也可以用一个数组存储。

设计流程图如图1.1所示。 开始 输出提示语 输入所需参数 创建链表，计算，得出结果 输出结果 结束 图1.1 设计流程图 （1）创建循环链表 由于内容的要求以及问题的方便，用循环链表作为本次实验的抽象数据类型。申请一个结点作为第一个结点，之后调用creat_list函数将后续结点一次插入链接，构造为循环链表。 NODE *link(int number) { NODE *head=NULL,*p=NULL,*q=NULL; int i=1; head=(struct node*)malloc(sizeof(struct node)); head->value=i; p=head; for(i=2; i<=number; i++)

约瑟夫环实验报告(3种方法实现)

约瑟夫环的三种实现方法的实验报告 公选题：约瑟夫环（使用一维数组、一维结构体数组、循环链表三种方法完成）一，实验目的 1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。 2、掌握利用一维数组，结构体，还有循环链表的各种操作来进行具体的实际应用。 3、加强程序设计的能力。 二，实验内容 什么是约瑟夫环？ 约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。 举例如下； n = 9, k = 1, m = 5 【解答】 出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。 三，怎么用程序来实现这个实际场景？ 要实现这个场景有多种语言（C，C++，JA V A语言，C#），每一种语言在实现的过程中各有不同，在实现上复杂程度也不同。针对自己目前的水平以及查阅相关资料，做了如下的一些解决方案。 四，三种解决方法（） 1，使用一维数组： #include #define N 10//总人数 #define M 5//间隔数 void main() { int a[N]; int count=0; int i=0; while(i<10)

{ int x; printf("请输入第%d个元素的值：\n",i+1); scanf("%d",&x); a[i]=x; i++; } printf("所有元素信息如下：\n"); for(int j=0;jN-1) i=0; } printf("%d ",i?a[i-1]:a[N-1]); a[(i?(i-1):(N-1))]=0;//哪一个出列了哪一个值就标记为0 } printf("\n"); } 2，使用一维结构体数组： #include #define N 100

顺序表实现约瑟夫环的问题C语言

顺序表实现约瑟夫环的问题C语言 计算机科学与工程学院 《算法与数据结构》试验报告[一] 10级计算机工程02计算机大楼计工教研专业班级试验地点室学生学号1005080222 指导教师蔡琼学生姓名肖宇博试验时间 2012-2-29 试验项目算法与数据结构 试验类别基础性() 设计性() 综合性(?) 其它( ) (1)掌握用VC++上机调试线性表的基本方法; 试(2)掌握顺序表的存储结构以及基本运算的实现。验 目的求及 要 成绩评定表 类别评分标准分值得分合计 积极出勤、遵守纪律 上机表现 30分 主动完成设计任务 程序代码规范、功能正确 程序与报告 70分 报告详实完整、体现收获 计算机科学与工程学院 备注: 评阅教师:

日期: 年月日 试验内容 一、实验目的和要求 1、实验目的: (1)掌握用VC++上机调试线性表的基本方法; (2)掌握顺序表的存储结构以及基本运算的实现。 2、实验内容 约瑟夫环问题:设编号为1，2，3，……，n的n(n>0)个人按顺 时针方向围坐一圈，m为任意一个正整数。从第一个人开始顺时针 方向自1起顺序报数，报到m时停止并且报m的人出列，再从他的下 一个人开始重新从1报数，报到m时停止并且报m的人出列。如此下 去，直到所有人全部出列为止。要求设计一个程序模拟此过程，对 任意给定的m和n，求出出列编号序列。 3、实验要求:用顺序表实现。 二、设计分析 根据实验要求，采用顺序表来完成本次实验。 实验中定义了两个顺序表，一个用来存储n个人的序号，另一个用来存储n个人的出队顺序及序号。 程序中充分考虑了如果出队的元素大于队列的元素个数时应该有的情况，如果出现这样的错误就提示～否则继续出队～ 三、源程序代码 #include #include #define MAXSIZE 10 // 宏替换最大值

题目：约瑟夫环问题

数据结构上机实验报告 02090401 12 雒文杰题目：约瑟夫环问题 一．问题描述 设有n个人围做一圈，现从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人又出列，如此下去，直到所有人都出列为止。试设计确定他们的出列次序序列的程序。 二．基本要求 运用循环单链表解决约瑟夫环问题。 三．算法说明 本程序采用循环单链表的算法来解决约瑟夫环问题：建立一个循环单链表，按顺序查找指定结点，找到后删除，最后打印删除的编号序列。 四．源程序清单 #include #include #define n 7 #define NULL 0 struct clist {int data,order; /* 人的序号, 密码*/ struct clist *next; /* 指向下一个节点的指针*/ }; typedef struct clist cnode; typedef cnode *clink; clink createclist(int *array,int len) /* 建立循环链表*/ {clink head; clink before; clink new_node; int i; head=(clink)malloc(sizeof(cnode)); if(!head) return NULL; head->data=array[0]; head->order=1; head->next=NULL; before=head; for(i=1;i

{new_node=(clink)malloc(sizeof(cnode)); if(!new_node) return NULL; new_node->data=array[i]; new_node->order=i+1; new_node->next=NULL; before->next=new_node; before=new_node; } new_node->next=head; return head; } void main() {clink head,ptr; int find,j,i,a,list[n]; printf("Please input 'm'\n"); for(i=0;inext; ptr=head->next; head->next=ptr->next; find=ptr->data; printf("order is %d\n",ptr->order); free(ptr); for(j=1;jnext; ptr=head->next; head->next=ptr->next; find=ptr->data; printf("order is %d\n",ptr->order); free(ptr); /* 让最后一个人也出列*/ } }