C 数据结构之约瑟夫环

#include <iostream.h>#include <stdlib.h>struct Member//定义结构体{int number;int password;Member *next;};class Joseph{public:Member *frist;//头指针int size;Joseph(void);~Joseph(void);int Size(void) const;//返回长度Member *Index(int i);//定位void Create(int i);//构造循环单链表int Delete(int i);//删除结点并返回number的值};Joseph::Joseph(){//frist=new Member;Member *p=new Member;frist=p;size=0;}Member *Joseph::Index(int i){if(i==0)return frist;Member *p=frist->next;int j=1;while(j<i){p=p->next;j++;}return p;}int Joseph::Size(void)const{return size;}void Joseph::Create(int i){for(int j=1;j<=i;j++){Member *p=Index(j-1);Member *q=new Member;q->number=j;p->next=q;size++;};//Member *p=Index(i);//p->next=frist;}Joseph::~Joseph(void){Member *p,*q;p=frist;while(size!=0){q=p;p=p->next;delete q;size--;}size=0;frist=NULL;}int Joseph::Delete(int i){Member *s,*p=Index(i-1);s=p->next;p->next=p->next->next;int x=s->number;cout<<x<<" ";int y=s->password;delete s;size--;return y;}void main(void){Joseph jos;int i;cout<<"Please input number of people :"<<endl;cin>>i;jos.Create(i);int frist;//设初始值cout<<"Please input the frist number :"<<endl;cin>>frist;for(int k=1;k<=i;k++)//用循环输入每个人的密码{cout<<"please input No."<<k<<"`s password:"<<endl;Member *b=jos.Index(k);cin>>b->password;}cout<<"The final is :"<<endl;int l=frist%i;if (l==0) l=i;for(int b=i-1;b>0;b--){frist=jos.Delete(l);l=(frist+l-1)%b;int e=jos.Size();if(l==0)l=e;}jos.Delete(l);cout<<endl;}。

#include"stdio.h" //预处理命令打开输入输出头文件#include"stdlib.h" //预处理命令打开标准库头文件#define MAXPASSWORDVALUE 20 //最大的密码的上线值#define MAXPERSONNUMBER 30 //最大人数#define MAXFIRSTCOUNTVALUE 20 //第一个M最大的上线值//#define MAXPASSWORD 10 //最大的密码上线typedef struct Node //定义人这个结构体{int data;//人的名字，即位置1.2.3...int password;//人的密码struct Node *next;//移动的指针}Node, *LinkList;//结构体指针变量，用于使用结构体中的属性//函数的声明void CreatLinkList(LinkList *);//声明建立单链表的函数void InitLinkList(LinkList *,int );//声明初始化单链表的函数int GetPassword();//获得每人的密码的函数int GetPersonNumber();//获得最大人数的函数//int GetPersonNumber();//int GetFirstCountValue();//获得初始的M值void GetOutputOrder(LinkList* , int, int, int* );//遍历单链表的函数void printResult(int * ,int );//输出遍历结果的函数//对以上各函数的定义//函数1构建链表void CreatLinkList(LinkList *L)//函数->>构建单链表{(*L) = (LinkList)malloc(sizeof(Node));if ((*L) == NULL){printf("memory allocation failed, goodbye");exit(1);}}//函数2初始化链表void InitLinkList(LinkList *L, int personNumber)//初始化单链表Node *p, *q;int i ;p = (*L);p->data = 1;p->password = GetPassword();for (i = 2; i <= personNumber; i++){q = (LinkList)malloc(sizeof(Node));if (q == NULL){printf("memory allocation failed, goodbye");exit(1);}q->password = GetPassword();q->data = i;p->next = q;p = q;}p->next = (*L);}//函数3为每个人输入一个密码int GetPassword()//给每个人赋密码{//定义变量int password;static int count = 1;//------------------------------------printf("\n请输入第%d的密码:",count);//可自加的提示文字scanf("%d",&password);//输入第1-n个人的密码while (password > MAXPASSWORDVALUE || password < 0)//当输入的密码大于最大密码的上限或是小于零的时候{printf("您输入的数字无效，请输入在0到%d的整数:",MAXPASSWORDVALUE);//提示请输入0-n的整数scanf("%d",&password);//重新输入密码}printf("第%d个人的密码为%d",count,password);//每输入后显示这个人的密count++;//计步器return password;//每循环一次返回一个密码值}//函数4获取玩游戏的人数int GetPersonNumber()//确定需要处理的人数{//定义变量int personNumber;//------------------------------------------------printf("请输入需要输入人的数目:");//提示语言scanf("%d",&personNumber);//输入参加游戏的人数while (personNumber > MAXPERSONNUMBER || personNumber < 0)//当人数大于最大人数或是小于0的时候{printf("\n你输入的数字无效,请输入在0到%d的整数",MAXPERSONNUMBER);//提示你要输入从0到最大人数个人数scanf("%d",&personNumber);//重新输入参加游戏的人数}printf("最终确定的人数为%d\n",personNumber);//输入完显示最终完游戏的人数return personNumber;//将人数返回到主函数}//函数5确定玩游戏开始时的M值int GetFirstCountValue()//确定开始的上限值{//定义变量int firstCountValue;//-----------------------------------------------printf("请输入初始的上限值");//提示语scanf("%d",&firstCountValue);//让你输入M最初始的值while (firstCountValue > MAXFIRSTCOUNTVALUE || firstCountValue < 2)//当输入的值大于M初始值上限或是小于2{printf("\n你输入的数字无效,请输入在2到%d的整数",MAXFIRSTCOUNTVALUE);//提示你输入2-M上限大小的数scanf("%d",&firstCountValue);//重新输入M的初始值printf("最终的上限值为%d",firstCountValue);//显示你输入的M的初始值return firstCountValue;//吧M的初始值返回到值函数}//函数6实现游戏过程void GetOutputOrder(LinkList *L, int personNumber, int reportValue, int array[MAXPERSONNUMBER])//遍历链表函数的定义{//变量的定义Node *p, *q;int count = 1, i = 0;p = (*L);//---------------------------------while (personNumber)//当人数值返回的为真时（没有用的，一定为真）{while (count != reportValue)//当M得初始值不为1时{//一个一个输出（游戏过程）q = p;p = p->next;count++;}array[i++] = p ->data;reportValue = p->password;q->next = p->next;free(p);p = q->next;count = 1;personNumber--;}}//函数7遍历单链表void printResult(int array[],int personNumer)//输出结果{//定义变量int i;//--------------------------------------printf("\n出队的顺序为:");//提示语for(i = 0; i < personNumer; i++)//循环输出链表内的值{printf("%-3d",array[i]);}printf("\n");}//函数8...主函数!!!!!!!int main(void)//主函数定义{//变量的定义LinkList L;int personNumber, reportValue;int array[MAXPERSONNUMBER];//------------------------------------------------personNumber = GetPersonNumber();//将函数4获取参加游戏的人数的函数的返回值赋到变量内reportValue = GetFirstCountValue();//将函数5获取M的初始值函数的返回值赋到变量内CreatLinkList(&L);//调用函数1建立一个单链表InitLinkList(&L, personNumber);//调用函数2初始化单链表GetOutputOrder(&L, personNumber, reportValue, array);//调用函数6实现游戏过程printResult(array, personNumber);//调用函数7遍历单链表system("pause");//结束return 0;}。

2009级数据结构实验报告实验名称：实验线性表实现约瑟夫问题求解学生姓名：桂柯易班级：2009211120班内序号：07学号：09210580日期：2010年10月31日1.实验要求【实验目的】1．熟悉C++语言的基本编程方法,掌握集成编译环境的调试方法；2．学习指针、模板类、异常处理的使用；3．掌握线性表的操作实现方法；4．培养使用线性表解决实际问题的能力。

【实验内容】利用循环链表实现约瑟夫问题的求解。

约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。

从序号为1的人开始报数，顺时针数到m的那个人出列。

他的下一个人又从1开始报数，数到m 的那个人又出列。

依此规则重复下去，直到所有人全部出列。

请问最后一个出列的人的编号。

2.程序分析2.1 存储结构存储结构：循环链表2.2 关键算法分析【设计思想】首先，设计实现约瑟夫环问题的存储结构。

由于约瑟夫环本身具有循环性质，考虑采用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。

循环链表的结点定义为如下结构类型：struct Node{int number;Node *next;};其次，建立一个不带头结点的循环链表并由头指针first指示。

最后，设计约瑟夫环问题的算法。

【伪代码】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->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);}4、输入报数的起始人号数k;5、Node *q = new Node;计数器初始化i=1;6、循环n次删除结点并报出位置（其中第一个人后移k个）当i<n时移动指针m-2次p=p->next;删除p结点的后一结点qq=p->next;p->next=q->next;*L = p->next;报出位置后Delete q;计数器i++;【复杂度】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;}时间复杂度：O（n）if(i==1) i+=LengthList(*L);Node *p;p=*L;int j=0;while(j<i-2) {p=p->next;j++;}q = p->next;p->next=p->next->next;*L = p->next;return(q);时间复杂度：O（n2）算法的空间复杂度：O（n2）2.3 其他程序源代码：#include<iostream>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()//主函数{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<<"尾指针异常!"<<endl;//尾指针异常处理}void Joseph(Node *L,int n,int m)//输出每次出列的人{int k;cout<<"请输入第一个报数人：";cin>>k;if(k<1||k>n){cout<<"请输入1-"<<n<<"之间的数"<<endl;} else{cout<<"\n出列顺序:\n";for(int i=1;i<n;i++){Node *q = new Node;if(i==1) q=DeleteList(&L,k+m-1,q);//第一个出列人的号数else q=DeleteList(&L,m,q);cout<<"号数："<<q->number<<endl;delete q;//释放出列人的存储空间}cout<<"最后一个出列号数是："<<L->number<<endl;;//输出最后出列人的号数}}Node *DeleteList(Node **L,int i,Node *q) //寻找每次出列的人{if(i==1) i+=LengthList(*L);//顺序依次出列情况的处理方式Node *p;p=*L;int j=0;while(j<i-2) {p=p->next;j++;}q = p->next;p->next=p->next->next;*L = p->next;return(q);}int LengthList(Node *L)//计算环上的人数{if(L){cout<<"尾指针错误!"<<endl;}//异常处理else{int i=1;Node *p=L->next;while(p!=L){i++;p=p->next;}return(i);}}3.程序运行结果1.测试主函数流程：2.测试条件：如上图所示，人数为20人，所报数为6，第一个报数的人是1号。

第二章习题与解答一判断题1．线性表的逻辑顺序与存储顺序总是一致的。

2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二单选题 (请从下列A，B，C，D选项中选择一项)1．线性表是( ) 。

(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（）个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的；(B) 部分地址必须是连续的；(C) 一定是不连续的；(D) 连续与否均可以。

4．用链表表示线性表的优点是（）。

(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

(A)单链表(B)双链表(C)单循环链表(D)带头结点的双循环链表6．循环链表的主要优点是( )。

(A)不在需要头指针了(B)已知某个结点的位置后，能够容易找到他的直接前趋(C)在进行插入、删除运算时，能更好的保证链表不断开(D)从表中的任意结点出发都能扫描到整个链表7．下面关于线性表的叙述错误的是( )。

约瑟夫环实验报告总结【篇一：约瑟夫环实验报告】实验报告课程名称：数据结构实验名称：顺序表和链表的应用实验编号：实验一指导教师：一、实验目的（1）掌握线性表的基本操作（插入、删除、查找）以及线性表合并等运算在顺序存储结构、链式存储结构上的实现。

重点掌握链式存储结构实现的各种操作。

（2）掌握线性表的链式存储结构的应用。

二、实验内容与实验步骤（1）实验内容：实现约瑟夫环，约瑟夫环（joseph）问题的一种描述是：编号为1、2、3……n的n个人按照顺时针方向围坐一圈，每人持有一个密码（正整数）。

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

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

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

（2）抽象数据类型和设计的函数描述，说明解决设想。

首先定义一个链表，用其中的data项存储每个人的编号，用password项存储每个人所持有的密码，并且声明一个指针。

之后使用creatlist_cl函数来创建一个循环链表，在其中的data和password中存入编号和密码，最后使最后一个节点的next指向l，使其能够形成循环队列。

定义了函数display来显示链表当中的内容，以确定存储的数据没有错误。

定义了函数delete_l来实现约瑟夫环中依次删除的功能，依次比较，如果某个人所持的密码和m值相等，则删除这个结点，并且输出此时该结点的编号和密码，实现出列的功能。

（3）简短明确地写出实验所采用的存储结构，并加以说明。

该实验我主要采用的是线性表的链式存储结构，首先定义了链表的结构，其中包括data项和password项，分别存储每个人的编号和所持密码，还声明了指向下一个结点的指针，该指针可以连接各个结点，并且将最后一个结点的指针指向第一个结点使之成为一个循环链表。

三、实验环境操作系统：windows 7调试软件名称：vc++版本号：6.0上机地点：综合楼311四、实验过程与分析（1）主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明设计的巧班级：学号：姓名：组号：实验成绩：批阅教师签字：实验日期：实验时间：妙之处。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

C语言的循环链表和约瑟夫环C语言的循环链表和约瑟夫环约瑟夫问题）是一个数学的应用问题，对于学习C语言四非常挺有帮助的，下面是店铺为大家搜集整理出来的有关于C语言的循环链表和约瑟夫环，一起了解下吧!循环链表的实现单链表只有向后结点，当单链表的尾链表不指向NULL，而是指向头结点时候，形成了一个环，成为单循环链表，简称循环链表。

当它是空表，向后结点就只想了自己，这也是它与单链表的主要差异，判断node->next是否等于head。

代码实现分为四部分：1. 初始化2. 插入3. 删除4. 定位寻找代码实现：1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1void ListInit(Node *pNode){int item;Node *temp,*target;cout<<"输入0完成初始化"<<endl; cin="">>item;if(!item)return ;if(!(pNode)){ //当空表的时候，head==NULLpNode = new Node ;if(!(pNode))exit(0);//未成功申请pNode->data = item;pNode->next = pNode;}else{//for(target = pNode;target->next!=pNode;target = target->next);4 15 16 17 18 19 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 3 0 3 1 3 2 3 3 3 4 3 5 3temp = new Node;if(!(temp))exit(0);temp->data = item;temp->next = pNode;target->next = temp;}}}void ListInsert(Node *pNode,int i){ //参数是首节点和插入位置Node *temp;Node *target;int item;cout<<"输入您要插入的值:"<<endl; cin="">>item;if(i==1){temp = new Node;if(!temp)exit(0);temp->data = item;for(target=pNode;target->next != pNode;target = target->next);temp->next = pNode;target->next = temp;pNode = temp;}else{target = pNode;for (int j=1;j<i-1;++j) target="target-">next;temp = new Node;if(!temp)exit(0);temp->data = item;temp->next = target->next;target->next = temp;}}void ListDelete(Node *pNode,int i){Node *target,*temp;if(i==1){for(target=pNode;target->next!=pNode;target=target ->next);temp = pNode;//保存一下要删除的首节点 ,一会便于释放6 37 38 39 4 0 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 5 0 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5pNode = pNode->next;target->next = pNode;temp;}else{target = pNode;for(int j=1;j<i-1;++j) target="target-">next;temp = target->next;//要释放的nodetarget->next = target->next->next;temp;}}int ListSearch(Node *pNode,int elem){ //查询并返回结点所在的位置Node *target;int i=1;for(target = pNode;target->data!=elem && target->next!= pNode;++i)target = target->next;if(target->next == pNode && target->data!=elem)return 0;else return i;}</i-1;++j)></i-1;++j)></endl;></endl;>5 96 0 6 1 6 2 6 3 6 4 6 5 6 6 67 68 69 7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 8约瑟夫问题约瑟夫环(约瑟夫问题)是一个数学的'应用问题：已知n个人(以编号1，2，3…n分别表示)围坐在一张圆桌周围。

约瑟夫问题详解（CC++）Josephus 约瑟夫问题假设n个竞赛者排成一个环形，依次顺序编号1，2，…，n。

从某个指定的第1号开始，沿环计数，每数到第m个人就让其出列，且从下一个人开始重新计数，继续进行下去。

这个过程一直进行到所有的人都出列为止。

最后出列者为优胜者。

无论是用链表实现还是用数组实现来解约瑟夫问题都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较麻烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。

注意到原问题仅仅是要求出最后的胜利者的序号，而不是要模拟整个过程。

因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意：问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。

求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）: k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。

现在我们把他们的编号做一下转换：k --> 0k+1 --> 1k+2 --> 2......k-2 --> n-2变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x 是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？变回去的公式很简单：x'=(x+k)%n如何知道(n-1)个人报数的问题的解？显然，只要知道(n-2)个人的解就行了。

(n-2)个人的解呢？当然是先求(n-3)的情况---- 这显然就是一个倒推问题！递推公式：令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]递推公式f[1]=0;f[i]=(f[i-1]+m)%i; (i>1)有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。