约瑟夫问题描述： 编号为1，2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始
编号为1，2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数。（n,m,每个人密码均由键盘输入）
方法1．报m的人出列（将其删除），从他在顺时针方向上的下一个人开始重新从一报数，……，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和此人密码。
方法2. 报m的人出列（将其删除），将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从一报数，……，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和此人密码。 展开
#include<stdio.h>
#include<malloc.h>
//1.元素类型，结点类型和指针类型
typedef struct LNode //定义结构体，
{
int number,password; //num用来存储人的序号，pwd用来存储人的密码
struct LNode *next;
}SLX;
struct LNode *head,*p,*pt; //定义结点
//2 、创建循环链表函数
int CreatLinkListFunction(int n) //参数n传递人数，
{
int i;
head=(struct LNode*)malloc(sizeof(SLX)); //创建一个带头结点的链表
p=head;
for(i=1;i<n;i++)
{
pt=(struct LNode*)malloc(sizeof(SLX));
p->next=pt;
p=pt;
}
p->next=head; //构成循环链表
pt=head;
return 0;
}
//3.创建输入密码函数
int EnterPassword(int n) //参数n传递人数
{
int i,k;
printf("\n请输入密码: \n");
for( i=1;i<=n;i++)
{
scanf("%d",&k);
pt->number=i; //num存储人的序号
pt->password=k; //pwd存储人的密码
pt=pt->next;
}
pt=p;//创建循环链表 此时P是头结点head 这个函数存入密码 之后再一次返回密码
return 0;
}
//4、创建输出函数
int OutListFunction(int m,int n) //参数m、n传递报数上限值和人数
{
int i,a;
for(i=1;i<=n;i++) //用一个for循环搜索循环链表
{
for(a=1;a<m;a++) //删除结点
{
pt=pt->next;
}
p=pt->next;
m=p->password;
printf("%d ",p->number); //输出人的序号
pt->next=p->next;
free(p); //释放动态申请的结点空间
}
return 0;
}
//主函数
void main()
{ int m,n; //m为报数上限值，n为人数
printf("\n参数m、n传递报数上限值和人数;\n");
printf("\n请输入 m 和n: \n");
scanf("%d %d",&m,&n);
CreatLinkListFunction( n); //调用创建链表函数
EnterPassword( n); //调用输入密码函数
printf("\n出队的人依次是:\n");
OutListFunction( m,n); //调用输出链表函数
}
#include<malloc.h>
typedef int Datetype;
//----------声明结点-------------
typedef struct node{
int state;
struct node* next;
}ListNode;
//--------主程序------------
int main()
{
int i,n,Num[10];
ListNode *h;
printf("输入人数");
scanf("%d",&n);
h=CreatList(n);
for(i=1,i<=n,i++)
{
h->state =n;//把编号从链表头结点开始传给链表
h=h->next;
printf("输入第%d个人的密码",i);
scanf("%d",&Num[i]);
p->Num[i]=m;
}
PrintList(h,Num,n);
return 0;
}
//---------创建链表-----------
ListNode *CreatList(int n){
ListNode *p,*pre;
ListNode *head;
head=(ListNode*)malloc(sizeof(ListNode));
head->next =Null;
pre=head;
for(int i=0;i<n,i++){
p=(ListNode*)malloc(sizeof(ListNode));
pre->next =p;/*将p指向的新结点插入链表*/
pre=p;
}
p->next =head;//循环链表
return head;
}
//----------主要操作 输出链表------------
ListNode *PrintList(ListNode *h,int Num,int n){
ListNode *p,*q;
p=h;
while(p->next !=Null&&Num>0)
{
for(int i=0,i<n,i++){
int j=0;
while(j<Num[j+1]-1)//在前一个位子停下经行去结点操作
{
p=p->next ;
j++
}
q=p->next;
p->next=q->next
printf("%d",&q->state );//输出编号第21行定义
free(q);
p=p->next ;//p指向下一个结点
}
}
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
typedef int Status;
typedef double ElemType;
//-----------------------------------
//定义单向循环链表
typedef struct LNode
{
int number;
int data;
struct LNode *next;
}LNode, *LinkList;
//-----------------------------------
LinkList EvaluList(int n);//对单向循环链表进行尾插入赋值
int size(LinkList L);//求链表的节点个数
Status ScanList(LinkList L);//遍历单向循环链表
Status Joseph(LinkList &L,int m);//约瑟夫环的实现
