数据结构.约瑟夫环问题
- 格式：docx
- 大小：17.58 KB
- 文档页数：4
约瑟夫环问题(采用的是工程C++)
约瑟夫问题的一种描述为：编号1,2,…,n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。
一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。
试设计一个程序，求出出列顺序。
利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。
例如m的初值为20；n=7，7个人的密码依次是：3,1,7,2,4,8,4,出列顺序为6,1,4,7,2,3,5。
以下是解答:
下面采用的是供称文件的形式(采用三种不同个是.h .cpp .cpp):
//头文件的声明:
#include <iostream>
typedef int ElemType;
typedef struct Node
{
ElemType num;
ElemType data;
struct Node *next;
} Node ,*LinkList;
void InitList(LinkList H);
int Creat_list(LinkList H);
void Printansewer(LinkList H,int n);
//主要执行文件:
#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct Node
{
ElemType num;
ElemType data;
struct Node *next;
} Node ,*LinkList;
//初始化单链表
void InitList(LinkList H){
H=(Node*)malloc(sizeof(Node));
H->next=NULL;
cout<<"ok"<<endl;
}
//建立单链表
int Creat_list(LinkList H){
LinkList p, p1;
int n;
cout<<"请输入选择人数n的值："; //你数入选择的人数cin>>n;
cout<<"请分别输入相应人的密码："<<endl;
p1 = H;//使p1具有了空间
for(int i=1;i<=n;i++)
{
p=(Node*)malloc(sizeof(Node)); //产生新的结点
p->next = NULL;
cin>>p->data;
p->num=i;
H->next = p;
H=p;//L指向了最后节点的数据域
}
H->next=p1->next;//构成循环单链表
return n;
}
//输出其出列的人的序号
void Printansewer(LinkList H,int n){
int m;
LinkList q,p=H;
cout<<"请输入报数上限值m的值：";
cin>>m;
cout<<"请睁大你的眼睛奇迹就是这样产生：";
cout<<"\n";
cout<<endl;
cout<<"下面分别是人出列的序号："<<endl;
for(int i1=1;i1<=n;i1++)
{
for(int k=1;k<m;k++) //查找结点
p=p->next;
q=p->next;
m=q->data;//进行交换其值，作为新的m
cout<<q->num<<" ";
p->next=q->next;//删除结点
free(q);//释放结点
}
}
//main函数:
#include <iostream>
#include "ds.h"
using namespace std;
void main(){
Node a;
LinkList p;//p是指针
p = &a;
int n,k,m,num; //num为其人数的接受值
do
{
cout<<"\n";
cout<<"\n 0. 初始化链表" ;
cout<<"\n";
cout<<"\n 1. 建立循环单链表" ;
cout<<"\n 2. 运行程序";
cout<<"\n 3. 结束程序运行";
cout<<"\n======================================";
cout<<"\n 请输入您的选择命令（0，1，2，3）";
cin>>k;
switch(k)
{
case 0: {
InitList(p);} break; //调用其相应的函数
case 1: {
num=Creat_list(p);//调用其相应的函数
cout<<"\n ok"<<endl;}break;
case 2: {
Printansewer(p,num);//调用其相应的函数
cout<<endl;
cout<<"\n ok"<<endl;}break;
}
}while(k!=3);/*switch{}*/
cout<<"\n 再见！";
cout<<"\n 打回车键，返回。
"; }/*main{}*/。
